A Time Bucket Formulation for the Traveling Salesman Problem with Time Windows
A Time Bucket Formulation for the Traveling Salesman Problem with Time Windows
复制标题
DOI：
10.1287/ijoc.1100.0432
复制
发表时间：
2012-12-01
影响因子：
2.1
通讯作者：
Tramontani, Andrea
中科院分区：
文献类型：
--
作者：
Dash, Sanjeeb;Guenluek, Oktay;Tramontani, Andrea
带时间窗的旅行商问题 (TSPTW) 是找到访问一组城市一次的最小成本路径的问题，其中每个城市必须在给定的时间窗内访问过。我们提出了一个基于将时间窗口划分为我们称为“桶”的子窗口的问题的扩展公式。我们为这个公式提出了切割平面，这些平面在计算上比文献中已知的切割平面更有效，因为它们利用了时间窗口的划分。为了获得时间窗口的良好划分，我们提出了一种基于迭代线性规划（LP）的过程，该过程可以产生不同大小的桶。该公式的 LP 松弛产生了 TPTW 的强下界，并为我们的分支剪切算法提供了一个良好的起点。我们还针对文献中的硬测试问题提供了令人鼓舞的计算结果，即实际调度应用程序产生的不对称实例，以及随机生成的对称实例。特别是，我们解决了许多以前未解决的基准实例。
The traveling salesman problem with time windows (TSPTW) is the problem of finding a minimum-cost path visiting a set of cities exactly once, where each city must be visited within a given time window. We present an extended formulation for the problem based on partitioning the time windows into subwindows that we call buckets. We present cutting planes for this formulation that are computationally more effective than the ones known in the literature because they exploit the division of the time windows into buckets. To obtain a good partition of the time windows, we propose an iterative linear programming (LP)-based procedure that may produce buckets of different sizes. The LP relaxation of this formulation yields strong lower bounds for the TSPTW and provides a good starting point for our branch-and-cut algorithm. We also present encouraging computational results on hard test problems from the literature, namely, asymmetric instances arising from a practical scheduling application, as well as randomly generated symmetric instances. In particular, we solve a number of previously unsolved benchmark instances.