Order Picking in an Automatic Warehouse: Solving Online Asymmetric TSPs
Please always quote using this URN: urn:nbn:de:0297-zib-3519
- 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 \emph{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.
Author: | Atef Abdel-Aziz Abdel-Hamid, Norbert Ascheuer, Martin Grötschel |
---|---|
Document Type: | ZIB-Report |
Tag: | Automatic Storage System; Online-Algorithm; Traveling Salesman Problem |
MSC-Classification: | 90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Bxx Operations research and management science / 90B06 Transportation, logistics |
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Bxx Operations research and management science / 90B90 Case-oriented studies | |
Date of first Publication: | 1998/02/25 |
Series (Serial Number): | ZIB-Report (SC-98-08) |
ZIB-Reportnumber: | SC-98-08 |
Published in: | Appeared in: Mathematical Methods of Operations Research, 49, 1999, 501-515 |