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

, , , , and

BibTeX reference

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

This cahier was revised in July 1992

Research Axis

Research application