Heuristic Bounds and Test Problem Generation for the Time-Dependent Traveling Salesman Problem

Russ J. Vander Wiel and Nikolaos V. Sahinidis
Additional contact information
Russ J. Vander Wiel: Department of Mechanical and Industrial Engineering, University of Illinois, Urbana, Illinois 61801
Nikolaos V. Sahinidis: Department of Mechanical and Industrial Engineering, University of Illinois, Urbana, Illinois 61801

Transportation Science, 1995, vol. 29, issue 2, 167-183

Abstract: The Time-Dependent Traveling Salesman Problem (TDTSP) is a generalization of the Traveling Salesman Problem (TSP) 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. There exists a number of applications of the TDTSP in the fields of distribution and scheduling. We present a new mixed-integer linear programming (MILP) formulation for the TDTSP. A directed multi-partite graph representation of this model facilitates the development of a local search heuristic which extends the well known Lin-Kernighan tour improvement heuristic to the TDTSP. A second upper bound is derived by applying a Benders-decomposition-based heuristic to the MILP formulation. The Benders master problem is further approximately solved to provide a lower bound. We also develop a method for generating TDTSP instances with known optimal solutions. Finally, computational experience with the heuristics and problem generator is presented for problems with up to 100 cities. The results demonstrate that the heuristics can achieve optimal or very good near-optimal solutions on a variety of problem classes with minimal computational effort.

Date: 1995
References: Add references at CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.29.2.167 (application/pdf)

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:inm:ortrsc:v:29:y:1995:i:2:p:167-183

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().