A branch‐and‐bound algorithm for the time‐dependent travelling salesman problem. Issue 3 (19th June 2018)

• Record Type: Journal Article
• Authors: Arigliano, Anna; Calogiuri, Tobia; Ghiani, Gianpaolo; Guerriero, Emanuela
• Is Part Of: Networks. Volume 72:Issue 3(2018)
• Page Start: 382
• Page End: 392
• Publication Date: 2018-06-19
• Subjects: branch‐and‐bound -- lower bound -- time‐dependent -- transportation -- travelling salesman problem -- vehicle routing; Network analysis (Planning) -- Periodicals; 658.4032
• DOI: 10.1002/net.21830
• Languages: English
• ISSNs: 0028-3045

Abstract

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].