An enhanced lower bound for the Time-Dependent Traveling Salesman Problem
2 : Università del Salento - Dipartimento di Ingegneria dell'Innovazione
Given a graph whose arc traversal times vary over time, the Time-Dependent Travelling Salesman Problem
amounts to find a Hamiltonian tour of least total duration. In this research work we define a new lower bounding
scheme whose parameters are determined by fitting the traffic data. Computational results show that, when
embedded into a branch-and-bound procedure, this lower bounding mechanism allows to solve to optimality a
larger number of instances than state-of-the-art algorithms.
| Subject : | : | Abstracts |
| Topics | : | Special Session: Time-Dependent Vehicle Routing Problem (organized by Emanuela Guerriero) |
| Keywords | : | travelling salesman problem ; time dependence ; lower and upper bounds |
| PDF version | : |  PDF version |
