Premium
A branch‐and‐bound algorithm for the time‐dependent travelling salesman problem
Author(s) -
Arigliano Anna,
Calogiuri Tobia,
Ghiani Gianpaolo,
Guerriero Emanuela
Publication year - 2018
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21830
Subject(s) - travelling salesman problem , tree traversal , graph traversal , branch and bound , exploit , bottleneck traveling salesman problem , 2 opt , algorithm , graph , mathematics , running time , computer science , mathematical optimization , combinatorics , computer security
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].