Abstract
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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
N. Ascheuer, “Ein Schnittebenenverfahren für ein Reihenfolgeproblem in der flexiblen Fertigung,” Master's Thesis, Universität Augsburg, Germany, 1989.
N. Ascheuer, “Hamiltonian path problems in the on-line optimization of flexible manufacturing systems,” PhD Thesis, Tech. Univ. Berlin, 1995. Avail. at URL http://www.zib.de/ZIBbib/Publications/.
N. Ascheuer, L. Escudero, M. Grötschel, and M. Stoer, “On identifying in polynomial time violated subtour elimination and precedence forcing constraints for the sequential ordering problem,” in Integer Programming and Combinatorial Optimization, R. Kannan and W.R. Pulleyblank (Eds.), University ofWaterloo: Waterloo, 1990, pp. 19-28.
N. Ascheuer, L. Escudero, M. Grötschel, and M. Stoer, “A cutting plane approach to the sequential ordering problem (with applications to job scheduling in manufacturing),” SIAM Journal on Optimization, vol. 3, pp. 25-42, 1993.
N. Ascheuer, M. Jünger, and G. Reinelt, “Heuristic algorithms for the ATSP with precedence constraints-A computational comparison,” In preparation.
E. Balas and M. Fischetti, “A lifting procedure for the asymmetric traveling salesman polytope and a large new class of facets,” Mathematical Programming, vol. 58, pp. 325-352, 1993.
E. Balas, M. Fischetti, and W. Pulleyblank, “The precedence constrained asymmetric traveling salesman polytope,” Math. Prog., vol. 68, pp. 241-265, 1995.
S. Chen and S. Smith, “Commonality and genetic algorithms,” Technical Report CMU-RI-TR-96-27, Carnegie Mellon University, Pittsburgh, 1996.
L.F. Escudero, “An inexact algorithm for the sequential ordering problem,” European Journal of Operational Research, vol. 37, pp. 236-253, 1988.
L.F. Escudero, “On the implementation of an algorithm for improving a solution to the sequential ordering problem,” Trabajos de Investigacion-Operativa, vol. 3, pp. 117-140, 1988.
L.F. Escudero, M. Guignard, and K. Malik, “A Lagrangean relax-and-cut approach for the sequential ordering problem with precedence constraints,” Annals of Operations Research, vol. 50, pp. 219-237, 1994.
M. Fischetti, “Facets of the asymmetric traveling salesman polytope,” Mathematics of Operations Research, vol. 16, pp. 42-56, 1991.
M. Fischetti and P. Toth, “Apolyhedral approach to the asymmetric traveling salesman problem,” Management Science, vol. 43, no. 11, pp. 1520-1536, 1997.
L.M. Gambardella and M. Dorigo, “HAS-SOP: Hybrid ant system for the sequential ordering problem,” Technical Report IDSIA-11-97, IDSIA, Lugano, Switzerland, 1997.
M. Grötschel, “Polyedrische Charakterisierungen kombinatorischer Optimierungsprobleme,” Hain: Meisenheim am Glan, 1977.
M. Grötschel and M. Padberg, “Polyhedral theory,” in The Traveling Salesman Problem, E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, and D.B. Shmoys (Eds.), John Wiley & Sons, New York, 1985.
M. Jünger, G. Reinelt, and G. Rinaldi, “The traveling salesman problem,” in Handbooks in Operations Research and Management Science, vol. 7: Network Models, M.O. Ball, T.L. Magnanti, C.L. Monma, and G.L. Nemhauser (Eds.), Elsevier Sci. B.V., Amsterdam, 1995, Ch. 4, pp. 225-330.
M. Jünger, G. Reinelt, and S. Thienel, “Provably good solutions for the traveling salesman problem,” Zeitschrift für Operations Research, vol. 22, pp. 83-95, 1998.
M. Jünger and S. Thienel. “Introduction toABACUS-Abranch and cut system,” Operations Research Letters, vol. 40, no. 2, pp. 183-217, 1994.
M. Jünger and S. Thienel, “Introduction to ABACUS-A branch and cut system,” Technical Report No. 97.263, Institut für Informatik, Universität zu Köln, 1997. See on-line documentation under URL http://www.informatik.uni-koeln.de/ls juenger/projects/abacus.html.
M. Padberg and G. Rinaldi, “An efficient algorithm for the minimum capacity cut problem,” Mathematical Programming, vol. 47, pp. 19-36, 1990.
M. Padberg and G. Rinaldi, “Facet identification for the symmetric traveling salesman polytope,” Mathematical Programming, vol. 47, pp. 219-257, 1990.
M. Padberg and M.R. Rao, “Odd minimum cut-sets and b-matchings,” Math. of OR, vol. 7, pp. 67-80, 1982.
G. Reinelt, “TSPLIB-A traveling salesman problem library,” ORSA Journal on Computing, vol. 3, pp. 376-384, 1991. See http://www.iwr.uni-heidelberg.de/iwr/comopt/soft/TSPLIB95/TSPLIB.html.
M. Timlin, “Precedence constrained routing,” Master's Thesis, Department of Combinatorics and Optimization, University of Waterloo, 1989.
M.T. FialaTimlin and W.R. Pulleyblank, “Precedence constrained routing and helicopter scheduling: Heuristic design,” Interfaces, vol. 22, no. 3, pp. 100-111, 1992.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Ascheuer, N., Jünger, M. & Reinelt, G. A Branch & Cut Algorithm for the Asymmetric Traveling Salesman Problem with Precedence Constraints. Computational Optimization and Applications 17, 61–84 (2000). https://doi.org/10.1023/A:1008779125567
Issue Date:
DOI: https://doi.org/10.1023/A:1008779125567