Efficient Move Evaluations for Time-Dependent Vehicle Routing Problems with Route Duration Constraints

We consider the Vehicle Routing Problem with Time Windows, time-dependent travel times and in which route duration is constrained or minimized. This problem arises in many real world transportation applications, for instance when modelling road traffic congestion and driver shifts with maximum allowed working time. In the rapidly growing field of e-commerce logistics, higher quality solutions are desired while the available computation time must decrease to lower customer lead-times. To obtain high quality solutions for instances of 1000+ requests, (meta-) heuristics are needed, which typically rely on some form of Neighborhood Search. In such algorithms, it is crucial to quickly check feasibility and exact objective change of local improvement moves. Although constant time checks based on pre-processing are known for both the time-dependent VRPTW, and the VRPTW with duration constraints, the combination of the two is significantly harder, leading to quadratic time complexity in the number of requests. We show how pre-processing can be used to decrease the move evaluation complexity from quadratic to linear time. Furthermore, we introduce a new data structure that reduces computation times further by maintaining linear time move evaluation complexity even when the neighborhood is searched in non-lexicographic order. We support our complexity results by presenting numerical results of various benchmark instances.

Registration to Remy Spliet, spliet@ese.eur.nl is required for availability of lunch.