VRPU: An Efficient Robust Optimization Approach for the Vehicle Routing Problem with Uncertain Travel Times and Demands

In the Vehicle Routing Problem with Time Windows (VRPTW), dealing with demand and travel time uncertainties poses significant challenges in terms of model efficacy, service expenditures, and customer satisfaction, notably in extensive operational scenarios. In this paper, we introduce VRPU as a solution to the robust VRPTW encompassing uncertain demands and travel time. VRPU adopts a robust optimization approach and, drawing on budget uncertainty theory, formulates uncertainty variables and reconceptualizes the arrival times at customers as a complex recursive function. The model is addressed through a two-stage Adaptive Large Neighborhood Search heuristic (ALNS), with the primary stage focused on minimizing the total number of utilized vehicles and the subsequent stage dedicated to minimizing total travel costs.Compared to the current state-of-the-art methods, the results of our two-stage Adaptive Large Neighborhood Search (ALNS) algorithm, tested on the Solomon and Gehring & Homberger benchmark datasets, demonstrate that, while incurring a certain computational overhead, it achieves more robust solutions. Additionally, when applied to the deterministic Vehicle Routing Problem with Time Windows (VRPTW), our algorithm successfully identifies the known optimal solutions within the current benchmark datasets.