Title | ||
---|---|---|
Solving the Asymmetric Travelling Salesman Problem with time windows by branch-and-cut |
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. |
Year | DOI | Venue |
---|---|---|
2001 | 10.1007/PL00011432 | Math. Program. |
Keywords | Field | DocType |
Key words: Asymmetric Travelling Salesman Problem – time windows – integer programs – branch&cut-algorithm – heuristics – control of stacker cranes,Mathematics Subject Classification (2000): 90C10,90C27,90C35 | Cutting-plane method,Mathematical optimization,Branch and cut,Algorithm,Travelling salesman problem,Integer programming,Heuristics,Stacker,Optimization problem,Mathematics,Lin–Kernighan heuristic | Journal |
Volume | Issue | ISSN |
90 | 3 | 0025-5610 |
Citations | PageRank | References |
68 | 3.45 | 20 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Norbert Ascheuer | 1 | 237 | 19.04 |
Matteo Fischetti | 2 | 2505 | 260.53 |
Martin Grötschel | 3 | 1570 | 724.54 |