A Branch-and-Price Algorithm for the Vehicle Routing Problem with Stochastic Demands and Probabilistic Duration Constraints

Alexandre M. Florio (), Richard F. Hartl (), Stefan Minner and Juan-José Salazar-González ()
Additional contact information
Alexandre M. Florio: Department of Business Decisions and Analytics, University of Vienna, 1090 Vienna, Austria
Richard F. Hartl: Department of Business Decisions and Analytics, University of Vienna, 1090 Vienna, Austria
Juan-José Salazar-González: Departamento de Matemáticas, Estadística e Investigación Operativa, Universidad de La Laguna, 38271 La Laguna, Tenerife, Spain

Transportation Science, 2021, vol. 55, issue 1, 122-138

Abstract: In many routing applications, it is necessary to place limits on the duration of the individual routes. When demands are stochastic and restocking during route execution is allowed, the durations of the resulting routes are also stochastic. In this paper, we consider the vehicle routing problem with stochastic demands and probabilistic duration constraints (VRPSD-PDC). We assume optimal restocking, which means that, during the route execution, replenishment trips to the depot are performed in an optimal way. The resulting optimization problem calls for a set of routes with minimal total expected cost for visiting all customers, such that the duration of each route, with a given probability, does not exceed a prescribed limit. We solve the VRPSD-PDC with a novel branch-and-price algorithm. An orienteering-based completion bound is proposed to control the growth of labels in the pricing algorithm. Feasibility of a priori routes is verified by applying Chebyshev’s bounds, by Monte Carlo simulation and statistical inference, or by analytically deriving the distribution of the route duration. Consistency checks are incorporated into the branch-and-price framework to detect statistical errors. Computational experiments are performed with demands following binomial, Poisson, or negative binomial probability distributions and with duration constraints enforced at the levels of 90%, 95%, and 98%. Optimal solutions to the VRPSD-PDC may contain routes that serve an expected demand that is larger than the capacity of the vehicle. These solutions actively employ optimal restocking to reduce traveling costs and the number of required vehicles. Sensitivity analyses indicate that high demand variability negatively impacts the solution, both in terms of total expected cost and the number of routes employed.

Keywords: stochastic vehicle routing; optimal restocking; chance constraint; branch-and-price; Monte Carlo method (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
https://doi.org/10.1287/trsc.2020.1002 (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:55:y:2021:i:1:p:122-138

Access Statistics for this article

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