Efficient Local Search for Vehicle Routing Problems with Uncertain Demands

This work addresses efficient local search for vehicle routing problems under demand uncertainty. We propose novel data structures for efficiently computing the worst-case total demand of a route during move evaluation. Using these data structures, we theoretically derive new asymptotic upper bounds for the time complexity of evaluating a move, improving upon existing results in the literature. Extensive computational experiments demonstrate that our method significantly reduces computational time in practice compared to current approaches.