> > 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


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

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