Properties and Bounds for the Single-vehicle Capacitated Routing Problem with Time-dependent Travel Times and Multiple Trips

This paper deals with a problem where the same vehicle performs several routes to serve a set of customers and arc traversal times vary along the planning horizon. The relationship with its time-invariant counterpart is investigated and a procedure to compute lower and upper bounds on the optimal solution value is developed. Computational results on instances, based on the Paris (France) road graph, show the effectiveness of this approach.