A branch & cut algorithm for the asymmetric traveling salesman problem with precedence constraints
A branch & cut algorithm for the asymmetric traveling salesman problem with precedence constraints
复制标题
DOI：
10.1023/a:1008779125567
复制
发表时间：
2000-10-01
影响因子：
2.2
通讯作者：
Reinelt, G
中科院分区：
文献类型：
--
作者：
Ascheuer, N;J端nger, M;Reinelt, G
在这篇文章中，我们考虑了经典的非对称旅行商问题（ATSP）的一个变种，即ATSP中的优先约束要求某些节点必须先于其他节点在任何可行的有向巡回赛。该问题作为调度和路由中的基本模型出现，并且具有广泛的应用范围，从直升机路由（Timlin，Master's Thesis，Department of Combinatorics and Optimization，University of Waterloo，1989），柔性制造中的排序（Ascheuer等人，Programming and Combinatorial Optimization，University of Waterloo，Waterloo，1990，pp. 19-28;同上，SIAM Journal on Optimization，vol. 3，pp. 25-42，1993），到自动存储系统中的堆垛机起重机路线（Ascheuer，Ph. D.技术，Tech。柏林大学，1995年）。我们给出了一个整数规划模型，并总结了已知的有效不等式类。我们详细描述了一个分支和切割算法的实现，并给出了计算结果的现实世界的实例和基准问题从TSPLIB。我们实现的结果表明，我们的实现优于文献中发现的其他实现。具有200多个节点的真实的世界实例可以在几分钟的CPU时间内解决到最优。作为副产品，我们得到了一个分支和切割算法的ATSP。TSPLIB中的所有实例都可以在合理的计算时间内求解到最优。
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.