EURO-Online login
- New to EURO? Create an account
- I forgot my username and/or my password.
- Help with cookies
(important for IE8 users)
3935. Polynomial-time algorithms to compute violation in the robust vehicle routing problem with time windows and budget uncertainty
Invited abstract in session TD-35: Location and transportation problems under uncertainty, stream Stochastic, Robust and Distributionally Robust Optimization.
Tuesday, 14:30-16:00Room: 44 (building: 303A)
Authors (first author is the speaker)
| 1. | Igor Malheiros
|
| CNRS, LIRMM | |
| 2. | Michael Poss
|
| CNRS, LIRMM | |
| 3. | Artur Pessoa
|
| Universidade Federal Fluminense | |
| 4. | Anand Subramanian
|
| Universidade Federal da Paraíba |
Abstract
This research focuses on the robust vehicle routing problem with time windows (VRPTW) under uncertain travel times. More specifically, we assume all travel times belong to a known budget uncertainty set. To solve large-scale instances, one often resorts to local search algorithms. These algorithms involve checking whether a route is feasible regarding the time window; if it is not, evaluate its infeasibility. Our goal is to study the computation of the infeasibility of the robust VRPTW with budget uncertainty for two classical cases of functions. We prove that the computation of both cases is polynomially solvable by providing dynamic programming algorithms to solve them.
Keywords
- Robust Optimization
- Vehicle Routing
- Programming, Dynamic
Status: accepted
Back to the list of papers