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

Edward K. Baker
Additional contact information
Edward K. Baker: University of Miami, Coral Gables, Florida

Operations Research, 1983, vol. 31, issue 5, 938-945

Abstract: 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.

Keywords: 491 exact solution time-constrained traveling salesman problem; 837 time-constrained route selection (search for similar items in EconPapers)
Date: 1983
References: Add references at CitEc
Citations: View citations in EconPapers (11)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.31.5.938 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:31:y:1983:i:5:p:938-945

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().