A Branch-and-Cut Algorithm for the Asymmetric Hamiltonian Path Problem with Precedence Constraints

Ascheuer, Norbert and Jünger, Michael and Reinelt, Gerhard (2000) A Branch-and-Cut Algorithm for the Asymmetric Hamiltonian Path Problem with Precedence Constraints.
Published in: Computational optimization and applications : an international journal. Vol. 17 (1). pp. 61-84.


In this article we consider a variant of the classical asymmetric traveling salesman problem, namely the asymmetric Hamiltonian path problem in which precedence constraints require that certain nodes must precede certain other nodes in any feasible directed Hamiltonian path. This problem occurs as a basic model in scheduling and routing and has a wide range of applications varying from helicopter routing (Timlin 1989), sequencing in flexible manufacturing (Ascheuer, Escudero, Grötschel, Stoer, 1990; Ascheuer, Escudero, Grötschel, Stoer, 1993), to stacker crane routing in an automatic storage system (Ascheuer, 1995). We give an integer programming model and summarize known classes of valid inequalities. We describe in detail the implementation of a branch-and-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-and-cut algorithm for the ATSP. All instances in TSPLIB can be solved to optimality in a reasonable amount of computation time.

Download: [img] Postscript - Preprinted Version
Download (576kB) | Preview
Editorial actions: View Item View Item (Login required)
Content information:
Deposit Information:
ZAIK Number: zpr98-323
Depositing User: Prof. Dr. Michael Jünger
Date Deposited: 03 Apr 2003 00:00
Last Modified: 19 Dec 2011 09:45
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/323