Premium
An exact solution approach for the time‐dependent traveling‐salesman problem
Author(s) -
Vander Wiel Russ J.,
Sahinidis Nikolaos V.
Publication year - 1996
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/(sici)1520-6750(199609)43:6<797::aid-nav2>3.0.co;2-#
Subject(s) - travelling salesman problem , mathematical optimization , exact solutions in general relativity , bottleneck traveling salesman problem , computer science , mathematics , mathematical analysis
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. © 1996 John Wiley & Sons, Inc.