A polyhedral study of the asymmetric traveling salesman problem with time windows
A polyhedral study of the asymmetric traveling salesman problem with time windows
复制标题
DOI：
10.1002/1097-0037(200009)36:2
复制
发表时间：
2000-09
期刊：
影响因子：
2.1
通讯作者：
Norbert Ascheuer;M. Fischetti;M. Grötschel
中科院分区：
文献类型：
--
作者：
Norbert Ascheuer;M. Fischetti;M. Grötschel
带时间窗的非对称旅行商问题（ATSP-TW）是调度和路由应用的基本模型。在本文中，我们提出了一个制定的问题，只涉及0/1-变量与潜在的有向图的弧。这样做的好处是避免了额外的变量以及相关的（通常是非常无效的）链接约束。在制定中，时间窗口的限制建模的“不可行路径消除”的约束。我们提出了这些约束的基本形式沿着与一些可能的加强。其他几类有效的不等式来自相关的非对称旅行商问题也被描述，沿着提升定理。我们还研究了模型整数解的凸船体的ATSP-TW多面体P_{TW}$。我们证明了即使只有一个时间窗，确定P_{TW}$的维数也是强NP-完全问题.在后一种情况下，我们提供了一个极小方程组$P_{TW}$。计算实验的新配方报告在一个配套文件[1997年]，我们表明，它优于替代配方的某些类别的问题实例。
The asymmetric travelling salesman problem with time windows (ATSP-TW) is a basic model for scheduling and routing applications. In this paper we present a formulation of the problem involving only 0/1-variables associated with the arcs of the underlying digraph. This has the advantage of avoiding additional variables as well as the associated (typically very ineffective) linking constraints. In the formulation, time window restrictions are modelled by means of ``infeasible path elimination'' constraints. We present the basic form of these constraints along with some possible strengthenings. Several other classes of valid inequalities derived from related asymmetric travelling salesman problems are also described, along with a lifting theorem. We also study the ATSP-TW polytope, $P_{TW}$, defined as the convex hull of the integer solutions of our model. We show that determining the dimension of $P_{TW}$ is strongly {\em NP}--complete problem, even if only one time window is present. In this latter case, we provide a minimal equation system for $P_{TW}$. Computational experiments on the new formulation are reported in a companion paper [1997] where we show that it outperforms alternative formulations on some classes of problem instances.