SC 98-08 Atef Abdel-Aziz Abdel-Hamid, Norbert Ascheuer, Martin Grötschel: Order Picking in an Automatic Warehouse: Solving Online
Asymmetric TSPs (Appeared in: Mathematical Methods of Operations Research,
49, 1999, 501-515)
Abstract: We report on a joint project with industry that had the aim
to sequence
transportation requests within an automatic storage system in such a
way that the overall travel time is minimized. The manufacturing
environment is such that scheduling decisions have to be made before
all jobs are known. We have modeled this task as an online
Asymmetric Traveling Salesman Problem (ATSP). Several heuristics for
the online ATSP are compared computationally within a simulation
environment to judge which should be used in practice. Compared to the
priority rule used so far, the optimization package reduced the
unloaded travel time by about 40 %. Because of these significant
savings our procedure was implemented as part of the control software
for the stacker cranes of the storage systems.
Keywords: Traveling Salesman Problem,
Online-Algorithm,
Automatic Storage System
MSC: 90B06, 90B90