A branch‐and‐bound algorithm for the time‐dependent travelling salesman problem | Zendy

Arigliano Anna | Zendy; Calogiuri Tobia | Zendy; Ghiani Gianpaolo | Zendy; Guerriero Emanuela | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

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

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research