Analysis and branch-and-cut algorithm for the time-dependent travelling salesman problem

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.

https://doi.org/10.1287/trsc.1120.0449

Cite as:

@article{Cordeau_2014,
	doi = {10.1287/trsc.1120.0449},
	url = {https://doi.org/10.1287%2Ftrsc.1120.0449},
	year = 2014,
	month = {feb},
	publisher = {Institute for Operations Research and the Management Sciences ({INFORMS})},
	volume = {48},
	number = {1},
	pages = {46--58},
	author = {Jean-Fran{c{c}}ois Cordeau and Gianpaolo Ghiani and Emanuela Guerriero},
	title = {Analysis and Branch-and-Cut Algorithm for the Time-Dependent Travelling Salesman Problem},
	journal = {Transportation Science}
}