|
|
Pedro Munari |
|
Robust Vehicle Routing Problems |
||||||||||||||||
|
(1) The robust vehicle routing problem with time windows: compact formulation and branch-price-and-cut method
-
Munari, P.; Moreno, A.; De La Vega, J.; Alem, D.; Gondzio, J.; Morabito, R.
Abstract:
We address the robust vehicle routing problem with time windows (RVRPTW) under customer demand and travel time uncertainties. As presented thus far in the literature, robust counterparts of standard formulations have challenged general-purpose optimization solvers and specialized branch-and-cut methods. Hence, optimal solutions have been reported for small-scale instances only. Additionally, although the most successful methods for solving many variants of vehicle routing problems are based on the column generation technique, the RVRPTW has never been addressed by this type of method. In this paper, we introduce a novel robust counterpart model based on the well-known budgeted uncertainty set, which has advantageous features in comparison to other formulations and presents better overall performance when solved by commercial solvers. This model results from incorporating dynamic programming recursive equations into a standard deterministic formulation and does not require the classical dualization scheme typically used in robust optimization. In addition, we propose a branch-price-and-cut method based on a set partitioning formulation of the problem, which relies on a robust resource constrained elementary shortest path problem to generate routes that are robust regarding both vehicle capacity and customer time windows. Computational experiments using Solomons's instances show that the proposed approach is effective and able to obtain robust solutions within a reasonable running time. The results of an extensive Monte Carlo simulation indicate the relevance of obtaining robust routes for a more reliable decision-making process in real-life settings.
Download:
[Full paper]
[Supplementary Material]
(2) Compact formulations for the robust vehicle routing problem with time windows under demand and travel time uncertainty
-
Campos, R.; Munari, P.; Coelho, L.
Abstract:
We provide new compact formulations for the robust vehicle routing problem with time windows (RVRPTW) under cardinality- and knapsack-constrained demand and travel time uncertainty. Particularly, we propose the first compact model that addresses the RVRPTW under travel time uncertainty considering the knapsack uncertainty set. Our models use different types of constraints to control time propagation based on the well-known Miller-Tucker-Zemlin and single commodity flow constraints. The latter has not been explored even for the deterministic variant of the problem, so we first state them explicitly. We also design tailored branch-and-cut algorithms based on the proposed formulations, which rely on a dynamic programming algorithm to verify if a solution is robust feasible in respect to demand and time, and use specific as well as standard separation methods found in the literature.
We present detailed computational results on RVRPTW instances, compare the performance of our models and algorithms and evaluate the impact and advantages of implementing each studied uncertainty set.
Download:
[Full paper]
[Supplementary Material] |
||||||||||||||||