The Robust Time-Dependent Vehicle Routing Problem with Time Windows and Budget Uncertainty

The vehicle routing problem with time windows (VRPTW) is a classical problem with many applications. In practice, travel times are time dependent because of traffic and uncertain events, such as accidents, weather, and road work. If these features are ignored, routes planned in advance may become infeasible. Although routing models incorporating time-dependent travel times typically rely on historical traffic data from location service providers, they do not capture uncertainty, and integrating real-time updates during execution remains difficult. This work introduces the robust time-dependent VRPTW, which uses robust optimization to handle uncertainty in time-dependent travel times. We study its computational properties and develop innovative exact approaches, including compact formulations, decomposition strategies, and a branch-and-cut algorithm with lazy cut generation. We also propose a primal heuristic based on iterated local search for larger instances. Experiments on adapted benchmark and real-world instances evaluate the algorithms and the model’s robustness. The best exact method solves about 78% of the instances to optimality within one hour. Simulations on real-world data show that the proposed model reduces infeasibilities compared with existing approaches while maintaining reasonable costs and computational times. These results provide planners and operators with more reliable schedules under uncertain traffic conditions, demonstrating the practical value of robustness in time-dependent vehicle routing.

Funding: This work was supported by the Conselho Nacional de Desenvolvimento Científico e Tecnológico [Grants 309580/2021-8, 406245/2021-5, and 409595/2025-0] and the Association Nationale de la Recherche et de la Technologie [Grant CIFRE: 2021/1269].

Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2025.0387.