An exact solution approach for the time-dependent traveling-salesman problem

Russ J.Vander Wiel, Nikolaos V. Sahinidis

Research output: Contribution to journalArticlepeer-review


We present an algorithm for solving the time-dependent traveling-salesman problem (TDTSP), a generalization of the classical traveling salesman problem in which the cost of travel between two cities depends on the distance between the cities and the position of the transition in the tour. The algorithm is derived by applying Benders decomposition to a mixed-integer linear programming formulation for the problem. We identify trivial TDTSPs for which a standard implementation of the algorithm requires an exponential number of iterations to converge. This motivates the development of an efficient, network-flow-based method for finding Pareto-optimal dual solutions of a highly degenerate subproblem. Preliminary computational experience demonstrates that the use of these Pareto-optimal solutions has a dramatic impact on the performance of the algorithm.

Original languageEnglish (US)
Pages (from-to)797-820
Number of pages24
JournalNaval Research Logistics
Issue number6
StatePublished - Sep 1996

ASJC Scopus subject areas

  • Modeling and Simulation
  • Ocean Engineering
  • Management Science and Operations Research


Dive into the research topics of 'An exact solution approach for the time-dependent traveling-salesman problem'. Together they form a unique fingerprint.

Cite this