Solving the Asymmetric Travelling Salesman Problem with time windows by branch-and-cut |
| |
| Authors: | Norbert Ascheuer Matteo Fischetti Martin Grötschel |
| |
| Institution: | (1) Intranetz GmbH, Bergstr. 22, 10115 Berlin, Germany, http://www.intranetz.de, DE;(2) Dipartimento di Elettronica ed Informatica, University of Padova, Italy (work supported by C.N.R., Italy), IT;(3) Konrad–Zuse–Zentrum für Informationstechnik Berlin (ZIB), Takustr. 7, 14195 Berlin–Dahlem, Germany, http://www.zib.de, DE |
| |
| Abstract: | 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.
Received: August 1999 / Accepted: September 2000?Published online April 12, 2001 |
| |
| Keywords: | : Asymmetric Travelling Salesman Problem – time windows – integer programs – branch& cut-algorithm – heuristics – control of stacker cranes |
| 本文献已被 SpringerLink 等数据库收录！ |
|
