Analysis and Branch-and-Cut Algorithm for the Time-Dependent Travelling Salesman Problem

Jean-François Cordeau (), Gianpaolo Ghiani () and Emanuela Guerriero ()
Additional contact information
Jean-François Cordeau: CIRRELT, HEC Montréal, Montréal H3T 2A7, Canada
Gianpaolo Ghiani: Dipartimento di Ingegneria dell'Innovazione, Università del Salento, 73100 Lecce, Italy
Emanuela Guerriero: Dipartimento di Ingegneria dell'Innovazione, Università del Salento, 73100 Lecce, Italy

Transportation Science, 2014, vol. 48, issue 1, 46-58

Abstract: Given a graph whose arc traversal times vary over time, the time-dependent travelling salesman problem (TDTSP) consists in finding a Hamiltonian tour of least total duration covering the vertices of the graph. The contribution of this paper is twofold. First, we describe a lower and upper bounding procedure that requires the solution of a simpler (yet NP-hard) asymmetric travelling salesman problem (ATSP). In addition, we prove that this ATSP solution is optimal for the TDTSP if all the arcs share a common congestion pattern. Second, we formulate the TDTSP as an integer linear programming model for which valid inequalities are devised. These inequalities are then embedded into a branch-and-cut algorithm that is able to solve instances with up to 40 vertices.

Keywords: travelling salesman problem; time dependence; lower and upper bounds; branch and cut (search for similar items in EconPapers)
Date: 2014
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (17)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.1120.0449 (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:48:y:2014:i:1:p:46-58

Access Statistics for this article

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