A two‐commodity flow formulation for the traveling salesman and the makespan problems with time windows

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 partcularly well suited to handling 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 ( n 2 ) variables. Implementation issues are discussed and numerical experimentations have been realized for problems of up to 60 nodes.