Scientific Program > Talks by Speaker > Visser Thomas

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 modeling road traffic congestion and driver shifts with maximum allowed working time. 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 preprocessing 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 preprocessing 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.