  Given a graph whose arc traversal times vary over time, the Time-Dependent
Travelling Salesman Problem consists in finding a Hamiltonian tour of least
total duration covering the vertices of the graph. The main goal of this work
is to define tight upper bounds for this problem by reusing the information
gained when solving instances with similar features. This is customary in
distribution management, where vehicle routes have to be generated over and
over again with similar input data. To this aim, we devise an upper bounding
technique based on the solution of a classical (and simpler) time-independent
Asymmetric Travelling Salesman Problem, where the constant arc costs are
suitably defined by the combined use of a Linear Program and a mix of
unsupervised and supervised Machine Learning techniques. The effectiveness of
this approach has been assessed through a computational campaign on the real
travel time functions of two European cities: Paris and London. The overall
average gap between our heuristic and the best-known solutions is about
0.001\%. For 31 instances, new best solutions have been obtained.
