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. To improve schedule accuracy, the models may consider time dependency in travel time. The real traffic data used as input to the optimizers are often obtained by location providers that predict the travel times for specified timeframes. The predictors estimate travel time based on historical data, where uncertainties from accidents, weather conditions, and working roads, may add unpredictable delays. These providers enhance their forecasts by monitoring live traffic and updating travel times throughout the day.

Since routes are typically designed in advance, updates are hard to integrate once execution starts. In this context, this work introduces the robust time-dependent VRPTW (RTDVRPTW), which uses robust optimization to handle uncertainty in travel times.

In this talk, we discuss the computational properties of RTDVRPTW under various assumptions, present exact and heuristic solution methods, and share results from real-data experiments to offer practical insights.