G-90-44
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.
Published October 1990 , 21 pages
This cahier was revised in July 1992