A Time-Dependent No-Overlap Constraint: Application to Delivery Problems

International audienceThe Time-Dependent Traveling Salesman Problem (TDTSP)is the extended version of the TSP where arc costs depend on the timewhen the arc is traveled. When we consider urban deliveries, travel timesvary considerably during the day and optimizing a delivery tour comesdown to solving an instance of the TDTSP. In this paper we presenta global constraint, extended from the no-overlap constraint, that integratestime-dependent transition costs and we compare the performanceof CP models for the TDTSP with and without the new constraint