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

作者：Cordeau Jean Francois^*; Ghiani Gianpaolo; Guerriero Emanuela

来源：Transportation Science, 2014, 48(1): 46-58.

DOI：10.1287/trsc.1120.0449

• travelling salesman problem
• time dependence
• lower and upper bounds
• branch and cut

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.

• 出版日期2014-2