The Robust Vehicle Routing Problem with Time Windows: Compact Formulation and Branch-Price-and-Cut Method

Pedro Munari (), Alfredo Moreno (), Jonathan De La Vega (), Douglas Alem (), Jacek Gondzio () and Reinaldo Morabito ()
Additional contact information
Pedro Munari: Department of Production Engineering, Federal University of São Carlos, 13565-905 São Carlos-SP, Brazil
Alfredo Moreno: Department of Production Engineering, Federal University of São Carlos, 13565-905 São Carlos-SP, Brazil
Jonathan De La Vega: Department of Production Engineering, Federal University of São Carlos, 13565-905 São Carlos-SP, Brazil
Douglas Alem: University of Edinburgh Business School, University of Edinburgh, Edinburgh EH8 9JS, Scotland, United Kingdom
Jacek Gondzio: School of Mathematics, University of Edinburgh, Edinburgh EH9 3FD, Scotland, United Kingdom; NASK Research Institute, 01-045 Warsaw, Poland
Reinaldo Morabito: Department of Production Engineering, Federal University of São Carlos, 13565-905 São Carlos-SP, Brazil

Transportation Science, 2019, vol. 53, issue 4, 1043–1066

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 with 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 Solomon’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.

Keywords: vehicle routing; time windows; robust optimization; polyhedral-interval uncertainty; compact model; branch-price-and-cut (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (19)

Downloads: (external link)
https://doi.org/10.1287/trsc.2018.0886 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:53:y:2019:i:4:p:1043-1066

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().