Exact and Anytime Search for the Time-Dependent TSP with Time-Windows

In a first part, we shall introduce an algorithm for solving the Time-Dependent TSP with Time-Windows that combines an anytime DP-based search with constraint propagation and local search. This algorithm may also be used to solve the TSP with Time-Windows, and we shall experimentally compare it with many other solvers on a classical benchmark, and also on a new benchmark based on a stochastic model that allows us to control the hardness of Time-Window constraints.