Branch-Price-and-Cut Algorithms for the Vehicle Routing Problem with Stochastic and Correlated Travel Times

Borzou Rostami (), Guy Desaulniers (), Fausto Errico () and Andrea Lodi ()
Additional contact information
Borzou Rostami: Lazaridis School of Business and Economics, Wilfrid Laurier University, Waterloo, Ontario N2L 3C5, Canada; Canada Excellence Research Chair (CERC) in Data Science for Real ‐Time Decision Making, Polytechnique Montréal, Montréal, Quebec H3C 3A7, Canada;
Guy Desaulniers: Department of Mathematics and Industrial Engineering, Polytechnique Montréal, Montréal, Quebec H3C 3A7, Canada; Group for Research in Decision Analysis (GERAD), Montréal, Quebec H3T 1J4, Canada;
Fausto Errico: Group for Research in Decision Analysis (GERAD), Montréal, Quebec H3T 1J4, Canada; Department of Civil Engineering, École de Technologie Supérieure de Montréal, Montréal, Quebec H3C 1K3, Canada; Interuniversity Research Centre on Enterprise Networks, Logistics and Transportation (CIRRELT), Montréal (QC) H3T 1J4, Canada
Andrea Lodi: Canada Excellence Research Chair (CERC) in Data Science for Real ‐Time Decision Making, Polytechnique Montréal, Montréal, Quebec H3C 3A7, Canada Group for Research in Decision Analysis (GERAD), Montréal, Quebec H3T 1J4, Canada

Operations Research, 2021, vol. 69, issue 2, 436-455

Abstract: In this paper, we consider a version of the capacitated vehicle routing problem (CVRP) where travel times are assumed to be uncertain and statistically correlated (CVRP-SCT). In particular, we suppose that travel times follow a multivariate probability distribution whose first and second moments are known. The main purpose of the CVRP-CST is to plan vehicle routes whose travel times are reliable, in the sense that observed travel times are not excessively dispersed with respect to their expected value. To this scope we adopt a mean-variance approach, where routes with high travel time variability are penalized. This leads to a parametric binary quadratic program for which we propose two alternative set partitioning reformulations and show how to exploit the structure of the correlation matrix when there is correlation only between adjacent links. For each model, we develop an exact branch-price-and-cut algorithm, where the quadratic component is dealt with either in the column generation master problem or in its subproblem. We tested our algorithms on a rich collection of instances derived from well-known data sets. Computational results show that our algorithms can efficiently solve problem instances with up to 75 customers. Furthermore, the obtained solutions significantly reduce the time variability when compared with standard CVRP solutions.

Keywords: vehicle routing; uncertain travel times; correlation; convex quadratic programming; branch-price-and-cut (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
https://doi.org/10.1287/opre.2020.2037 (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:oropre:v:69:y:2021:i:2:p:436-455

Access Statistics for this article

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