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

Russ J. Vander Wiel and Nikolaos V. Sahinidis

Naval Research Logistics (NRL), 1996, vol. 43, issue 6, 797-820

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

Date: 1996
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
https://doi.org/10.1002/(SICI)1520-6750(199609)43:63.0.CO;2-#

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:wly:navres:v:43:y:1996:i:6:p:797-820

Access Statistics for this article

More articles in Naval Research Logistics (NRL) from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().