caa a22 4500 475750470 CHVBK 20180406123522.0 cr unu---uuuuu 170329e20001001xx s 000 0 eng 10.1023/A:1008779125567 doi (NATIONALLICENCE)springer-10.1023/A:1008779125567 A Branch & Cut Algorithm for the Asymmetric Traveling Salesman Problem with Precedence Constraints [Elektronische Daten] [Norbert Ascheuer, Michael Jünger, Gerhard Reinelt] In this article we consider a variant of the classical asymmetric traveling salesman problem (ATSP), namely the ATSP in which precedence constraints require that certain nodes must precede certain other nodes in any feasible directed tour. This problem occurs as a basic model in scheduling and routing and has a wide range of applications varying from helicopter routing (Timlin, Master's Thesis, Department of Combinatorics and Optimization, University of Waterloo, 1989), sequencing in flexible manufacturing (Ascheuer et al., Integer Programming and Combinatorial Optimization, University of Waterloo, Waterloo, 1990, pp. 19-28; Idem., SIAM Journal on Optimization, vol. 3, pp. 25-42, 1993), to stacker crane routing in an automatic storage system (Ascheuer, Ph.D. Thesis, Tech. Univ. Berlin, 1995). We give an integer programming model and summarize known classes of valid inequalities. We describe in detail the implementation of a branch&cut-algorithm and give computational results on real-world instances and benchmark problems from TSPLIB. The results we achieve indicate that our implementation outperforms other implementations found in the literature. Real world instances with more than 200 nodes can be solved to optimality within a few minutes of CPU-time. As a side product we obtain a branch&cut-algorithm for the ATSP. All instances in TSPLIB can be solved to optimality in a reasonable amount of computation time. Kluwer Academic Publishers, 2000 asymmetric traveling salesman problem nationallicence precedence constraints nationallicence branch&cut nationallicence Ascheuer Norbert Konrad-Zuse-Zentrum für Informationstechnik Berlin, Takustr. 7, D-14195, Berlin-Dahlem, Germany aut Jünger Michael Institut für Informatik der Universität zu Köln, Pohligstr. 1, D-50969, Köln, Germany aut Reinelt Gerhard Institut für Angewandte Mathematik, Universität Heidelberg, Im Neuenheimer Feld 293, D-69120, Heidelberg, Germany aut Computational Optimization and Applications Kluwer Academic Publishers 17/1(2000-10-01), 61-84 0926-6003 17:1<61 2000 17 10589 https://doi.org/10.1023/A:1008779125567 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1023/A:1008779125567 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Ascheuer Norbert Konrad-Zuse-Zentrum für Informationstechnik Berlin, Takustr. 7, D-14195, Berlin-Dahlem, Germany aut NATIONALLICENCE 700 1- Jünger Michael Institut für Informatik der Universität zu Köln, Pohligstr. 1, D-50969, Köln, Germany aut NATIONALLICENCE 700 1- Reinelt Gerhard Institut für Angewandte Mathematik, Universität Heidelberg, Im Neuenheimer Feld 293, D-69120, Heidelberg, Germany aut NATIONALLICENCE 773 0- Computational Optimization and Applications Kluwer Academic Publishers 17/1(2000-10-01), 61-84 0926-6003 17:1<61 2000 17 10589 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer