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.
https://doi.org/10.1016/j.cor.2019.104795Cite as:
@article{Adamo_2020,
doi = {10.1016/j.cor.2019.104795},
url = {https://doi.org/10.1016%2Fj.cor.2019.104795},
year = 2020,
month = {jan},
publisher = {Elsevier {BV}},
volume = {113},
pages = {104795},
author = {Tommaso Adamo and Gianpaolo Ghiani and Emanuela Guerriero},
title = {An enhanced lower bound for the Time-Dependent Travelling Salesman Problem},
journal = {Computers {&}amp$mathsemicolon$ Operations Research}
}