New integer linear programming formulation for the traveling salesman problem with time windows: minimizing tour duration with waiting times
New integer linear programming formulation for the traveling salesman problem with time windows: minimizing tour duration with waiting times
复制标题
带时间窗的旅行商问题的新整数线性规划公式：通过等待时间最小化旅行持续时间
DOI：
10.1080/02331934.2013.824445
复制
发表时间：
2013
期刊：
影响因子：
2.2
通讯作者：
B. Dengiz
中科院分区：
文献类型：
--
作者：
Imdat Kara;Özge Koç;Fulya Altiparmak;B. Dengiz
旅行商问题是最有吸引力和研究最多的组合优化问题之一，有许多变体，其中之一被称为“时间窗旅行商问题（TSPTW）”。在这个问题中，每个城市（节点，客户）必须在最早和最晚时间定义的时间窗口内访问。在TSPTW中，如果旅行者提前到达，他/她必须在城市等待;因此等待时间直接影响旅游的持续时间。这将是有用的，以开发一个新的模型可解决任何优化器直接。在本文中，我们提出了一个新的整数线性规划公式具有O（n2）的二元变量和O（n2）的约束，其中（n）等于底层图的节点数。目标函数是最小化总行程时间加上总等待时间。对一组具有20个和40个节点的测试问题进行了计算比较。建议和现有的配方的性能进行了分析相对于线性规划松弛和CPU时间。新的提法在两个性能标准方面都大大优于现有的提法。适应我们的制定多旅客的情况下，一些特殊情况下的额外限制说明。
The travelling salesman problem, being one of the most attractive and well-studied combinatorial optimization problems, has many variants, one of which is called ‘travelling salesman problem with Time Windows (TSPTW)’. In this problem, each city (nodes, customers) must be visited within a time window defined by the earliest and the latest time. In TSPTW, the traveller has to wait at a city if he/she arrives early; thus waiting times directly affect the duration of a tour. It would be useful to develop a new model solvable by any optimizer directly. In this paper, we propose a new integer linear programming formulation having O(n2) binary variables and O(n2) constraints, where (n) equals the number of nodes of the underlying graph. The objective function is stated to minimize the total travel time plus the total waiting time. A computational comparison is made on a suite of test problems with 20 and 40 nodes. The performances of the proposed and existing formulations are analysed with respect to linear programming relaxations and the CPU times. The new formulation considerably outperforms the existing one with respect to both the performance criteria. Adaptation of our formulation to the multi-traveller case and some additional restrictions for special situations are illustrated.