A two-commodity flow formulation for the traveling salesman and the makespan problems with time windows
A two-commodity flow formulation for the traveling salesman and the makespan problems with time windows
复制标题
旅行推销员的两种商品流动公式和时间窗的完工时间问题
作者：
A. Langevin;M. Desrochers;J. Desrosiers;Sylvie Gélinas;F. Soumis
本文针对旅行商问题提出了一种新的两种商品流公式。每个商品对应一个资源，该资源可以在所有节点的旅程中分发或拾取。该公式特别适合处理时间窗口约束；使用的资源就是时间。这个公式可以扩展到完工时间问题。对于 n 节点问题，公式的线性松弛仅涉及 O(n) 约束和 O(n2) 变量。讨论了实现问题，并针对多达 40 个节点的问题实现了数值实验。 （一个）
This paper presents a new two-commodity flow formulation for the traveling salesman problem. Each commodity corresponds to a resource that is either distributed or picked-up along the tour of all nodes. This formulation is particularly well-suited to handle time window constraints; the resource used is then the time. This formulation can be extended to the makespan problem. For a n-node proble, the linear relaxation of the formulation involves only O(n) constraints and O(n2) variables. Implementation issuesare discussed and numerical experimentations have been realized for problems of up to 40 nodes. (A)