Technical Note--An Exact Algorithm for the Time-Constrained Traveling Salesman Problem

• Published in: Operations research 1983-10, Vol.31 (5), p.938-945
• Main Author: Baker, Edward K
• Format: Article
• Language: English
• Subjects: 491 exact solution time-constrained traveling salesman problem; 837 time-constrained route selection
• ISSN: 0030-364X; 1526-5463
• DOI: 10.1287/opre.31.5.938

The time-constrained traveling salesman problem is a variation of the familiar traveling salesman problem that includes time window constraints on the time a particular city, or cities, may be visited. This note presents a concise formulation of the time-constrained traveling salesman problem. The model assumes that the distances of the problem are symmetrical and that the triangle inequality holds. Additionally, the model allows the salesman to wait at a city, if necessary, for a time window to open. The dual of the formulation is shown to be a disjunctive graph model, which is well known from scheduling theory. A longest path algorithm is used to obtain bounding information for subproblems in a branch and bound solution procedure. Computational results are presented for several small to moderate size problems.