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.