A branch‐and‐bound 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 consists of finding a Hamiltonian tour of least total duration. In this paper we exploit some properties of the problem and develop a branch‐and‐bound algorithm which outperforms the state‐of‐the‐art branch‐and‐cut procedure by Cordeau et al. [5].Keywords
This publication has 24 references indexed in Scilit:
- Investigating the use of metaheuristics for solving single vehicle routing problems with time-varying traversal costsJournal of the Operational Research Society, 2013
- An integer programming approach for the time-dependent TSPElectronic Notes in Discrete Mathematics, 2010
- The time-dependent traveling salesman problem and single machine scheduling problems with sequence dependent setup timesDiscrete Optimization, 2008
- An asymmetric TSP with time windows and with time-dependent travel times and costs: An exact solution through a graph transformationEuropean Journal of Operational Research, 2008
- A branch-and-cut algorithm for a production scheduling problem with sequence-dependent and time-dependent setup timesComputers & Operations Research, 2008
- The moving-target traveling salesman problemJournal of Algorithms, 2003
- Vehicle dispatching with time-dependent travel timesEuropean Journal of Operational Research, 2003
- The time-dependent traveling salesman problemPhysica A: Statistical Mechanics and its Applications, 2002
- A restricted dynamic programming heuristic algorithm for the time dependent traveling salesman problemEuropean Journal of Operational Research, 1996
- A classification of formulations for the (time-dependent) traveling salesman problemEuropean Journal of Operational Research, 1995