Name
Title | ||
|---|---|---|
Analysis and Branch-and-Cut Algorithm for the Time-Dependent Travelling Salesman Problem |
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. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1287/trsc.1120.0449 | Transportation Science |
Keywords | Field | DocType |
travelling salesman problem,linear programming,integer programming,branch and cut,traveling salesman problem | Nearest neighbour algorithm,Bottleneck traveling salesman problem,Mathematical optimization,Combinatorics,Branch and cut,Algorithm,Integer programming,Travelling salesman problem,Linear programming,2-opt,Mathematics,Lin–Kernighan heuristic | Journal |
Volume | Issue | ISSN |
48 | 1 | 0041-1655 |
Citations | PageRank | References |
18 | 0.90 | 22 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jean-Francois Cordeau | 1 | 337 | 24.97 |
| Gianpaolo Ghiani | 2 | 548 | 40.62 |
| E. Guerriero | 3 | 104 | 11.21 |