Solving the Asymmetric Travelling Salesman Problem with time windows by branch-and-cut

Citation
N. Ascheuer et al., Solving the Asymmetric Travelling Salesman Problem with time windows by branch-and-cut, MATH PROGR, 90(3), 2001, pp. 475-506
Citations number
43
Language
INGLESE
art.tipo
Article
Categorie Soggetti
Mathematics
Journal title
MATHEMATICAL PROGRAMMING
ISSN journal
0025-5610 → ACNP
Volume
90
Issue
3
Year of publication
2001
Pages
475 - 506
Database
ISI
SICI code
0025-5610(200105)90:3<475:STATSP>2.0.ZU;2-#
Abstract
Many optimization problems have several equivalent mathematical models. It is often not apparents which of these models is most suitable for practical computation, in particular, when a certain application with a specific ran ge of instance sizes is in focus. Our paper addresses the Asymmetric Travel ling Salesman Problem with time windows (ATSP-TW) from such a point of view . The real-world application we aim at is die control of a stacker crane in a warehouse. We have implemented codes based on three alternative integer programming fo rmulations of the ATSP-TW and more than ten heuristies. Computational resul ts 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 model s we considered - at least for our special application - and that the heuri stics provide acceptable solutions.