Solving the asymmetric travelling salesman problem with time windows by branch-and-cut

Solving the asymmetric travelling salesman problem with time windows by branch-and-cut

0.00 Avg rating0 Votes
Article ID: iaor2002968
Country: Germany
Volume: 90
Issue: 3
Start Page Number: 475
End Page Number: 506
Publication Date: Jan 2001
Journal: Mathematical Programming
Authors: , ,
Keywords: programming: branch and bound, programming: integer
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.

Reviews

Required fields are marked *. Your email address will not be published.