Solving the Asymmetric Travelling Salesman Problem with Time Windows by Branch-and-Cut
Please always quote using this URN: urn:nbn:de:0297-zib-4191
- Many optimization problems have several equivalent mathematical models. It is often not apparent which of these models is most suitable for practical computation, in particular, when a certain application with a specific range of instance sizes is in focus. Our paper addresses the Asymmetric Travelling Salesman Problem with time windows (ATSP-TW) from such a point of view. The real--world application we aim at is the control of a stacker crane in a warehouse. We have implemented codes based on three alternative integer programming formulations of the ATSP-TW and more than ten heuristics. Computational results for real-world instances with up to 233 nodes are reported, showing that a new model presented in a companion paper outperforms the other two models we considered --- at least for our special application --- and that the heuristics provide acceptable solutions.
Author: | Norbert Ascheuer, Matteo Fischetti, Martin Grötschel |
---|---|
Document Type: | ZIB-Report |
Tag: | Asymmetric Travelling Salesman Problem; Branch&Cut-Algorithm; Control of Stacker Cranes; Heuristics; Integer Programs; Time Windows |
MSC-Classification: | 90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C10 Integer programming |
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C27 Combinatorial optimization | |
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C35 Programming involving graphs or networks [See also 90C27] | |
Date of first Publication: | 1999/08/20 |
Series (Serial Number): | ZIB-Report (SC-99-31) |
ZIB-Reportnumber: | SC-99-31 |
Published in: | Appeared in: Math. Program., Ser. A, Vol 90, No 3: 475-506 (2000) |