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 paper we exploit a new degree of freedom in the Cordeau et al. (2014) speed decomposition. This approach results in a parameterized family of lower bounds. The parameters are chosen by fitting the traffic data. The first model is nonlinear and difficult to solve. Hence, we devise a linearization which gives rise to a compact Mixed Integer Linear Programming model. Then, we develop an optimality condition which allows to further reduce the size of the model. 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.
An enhanced lower bound for the Time-Dependent Travelling Salesman Problem
Adamo, Tommaso;Ghiani, G.;Guerriero, E.
2020-01-01
Abstract
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 paper we exploit a new degree of freedom in the Cordeau et al. (2014) speed decomposition. This approach results in a parameterized family of lower bounds. The parameters are chosen by fitting the traffic data. The first model is nonlinear and difficult to solve. Hence, we devise a linearization which gives rise to a compact Mixed Integer Linear Programming model. Then, we develop an optimality condition which allows to further reduce the size of the model. 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.File | Dimensione | Formato | |
---|---|---|---|
1-s2.0-S0305054819302370-main.pdf
solo utenti autorizzati
Descrizione: Articolo
Tipologia:
Versione editoriale
Licenza:
NON PUBBLICO - Accesso privato/ristretto
Dimensione
1.16 MB
Formato
Adobe PDF
|
1.16 MB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.