Groupe d’études et de recherche en analyse des décisions


A Two-Commodity Flow Formulation for the Traveling Salesman and the Makespan Problems with Time Windows

, , , et

We present 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 problem, the linear relaxation of the formulation involves only O(n) constraints and O(n2) variables. Implementation issues are discussed and numerical experimentations have been realized for problems of up to 60 nodes.

, 21 pages

Ce cahier a été révisé en juillet 1992