首页 | 本学科首页   官方微博 | 高级检索  
     检索      


A Branch & Cut Algorithm for the Asymmetric Traveling Salesman Problem with Precedence Constraints
Authors:Norbert Ascheuer  Michael Jünger  Gerhard Reinelt
Institution:(1) Konrad-Zuse-Zentrum für Informationstechnik Berlin, Takustr. 7, D-14195 Berlin-Dahlem, Germany;(2) Institut für Informatik der Universität zu Köln, Pohligstr. 1, D-50969 Köln, Germany;(3) Institut für Angewandte Mathematik, Universität Heidelberg, Im Neuenheimer Feld 293, D-69120, Heidelberg, Germany
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.
Keywords:asymmetric traveling salesman problem  precedence constraints  branch&  cut
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号