Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)

A Branch & Cut Algorithm for the Asymmetric Traveling Salesman Problem with Precedence Constraints

Please always quote using this URN: urn:nbn:de:0297-zib-3391
  • In this paper we consider a variant of the classical ATSP, namely the asymmetric Hamiltonian path problem (or equivalently ATSP) with precedence constraints. In this problem precedences among the nodes are present, stating that a certain node has to precede others in any feasible sequence. This problem occurs as a basic model in scheduling and routing and has a wide range of applications varying from helicopter routing[Timlin89], sequencing in flexible manufacturing [AscheuerEscuderoGroetschelStoer90,AscheuerEscuderoGroetschelStoer93], to stacker crane routing in an automatic storage system[Ascheuer95]. 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 up to 174 nodes could be solved to optimality within a few minutes of CPU-time. As a side product we obtained a branch&cut-algorithm for the ATSP. All instances in TSPLIB could be solved to optimality in a reasonable amount of computing time.

Download full text files

  • Revised Version JAN99

  • Original Version: A Branch & Cut Algorithm for the Asymmetric Hamiltonian Path Problem with Precedence Constraints

  • Revised Version JAN99

Export metadata

Additional Services

Share in Twitter Search Google Scholar Statistics - number of accesses to the document
Metadaten
Author:Norbert Ascheuer, Michael Jünger, Gerhard Reinelt
Document Type:ZIB-Report
Date of first Publication:1997/12/19
Series (Serial Number):ZIB-Report (SC-97-70)
ZIB-Reportnumber:SC-97-70
Published in:Appeared in: Computational Optimization and Applications, 17(1):61-84 (2000)
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.