> > Time-Dependent Traveling Salesman Problem

This is the free portion of the full article. The full article is available to licensed users only.
How do I get access?

Time-Dependent Traveling Salesman Problem

Article Outline

Keywords

Formulations of TDTSP
Envelopes and Tight Formulations
Network Interpretation of TDTSP
Decomposition Algorithm for TDTSP
Heuristics for TDTSP
Conclusion
See also
References

Keywords TDTSP - Benders decomposition - Convexification - Multistage optimization

Given a list of cities, the classical traveling salesman problem is aimed at finding the least cost tour through the cities. The time-dependent traveling salesman problem is a generalization of the traveling salesman problem where the cost of travel between cities is also dependent on the order in which they are traversed. We now provide a more formal description of the two problems. Consider a set of cities 𝒩 = {1, …, n} and a mapping, D: 𝒩 × 𝒩 → R, that associates with each ordered city-pair a cost incurred when a travel/transition is undertaken starting from the first city and ending at the second city. The data may be pictorially visualized