2428. The robust time-dependent vehicle routing problem with time windows and budget uncertainty
Invited abstract in session MB-27: Vehicle Routing under Uncertainty , stream Stochastic and Robust optimization.
Monday, 10:30-12:00Room: Maurice Keyworth G.02
Authors (first author is the speaker)
| 1. | Igor Malheiros
|
| CNRS, LIRMM | |
| 2. | Michael Poss
|
| CNRS, LIRMM | |
| 3. | Vitor Nesello
|
| Atoptima | |
| 4. | Anand Subramanian
|
| Universidade Federal da Paraíba |
Abstract
The Vehicle Routing Problem with Time Windows (VRPTW) is a classic problem with many applications. To develop more precise routing plans, academics and practitioners may consider travel time variations throughout the day, e.g., longer durations during rush hours. In the Time-Dependent VRPTW (TDVRPTW), travel time becomes a function of time. This work introduces a new variation of the TDVRPTW: the Robust TDVRPTW (RTDVRPTW) under uncertain travel times. Specifically, we assume all travel times belong to a known budget uncertainty set. The RTDVRPTW aims to provide precise planned routes designed in advance while remaining resistant to uncertainties, such as accidents or roadwork. First, we study the computability of the time-dependent travel time function in robust optimization under different assumptions. Second, we propose two approaches to solve our model: (i) an exact approach based on a compact formulation and (ii) a metaheuristic approach designed for large-scale instances. Finally, we conduct experiments using different configurations of uncertainty sets and simulate them with real traffic data. The results show that our proposed model produces solutions with a better trade-off between robustness and cost than other models in the literature.
Keywords
- Robust Optimization
- Vehicle Routing
Status: accepted
Back to the list of papers