New Exact Algorithm for the Vehicle Routing Problem with Stochastic Demands

Alexandre M. Florio (), Richard F. Hartl () and Stefan Minner
Additional contact information
Alexandre M. Florio: Department of Business Decisions and Analytics, University of Vienna, 1010 Vienna, Austria;
Richard F. Hartl: Department of Business Decisions and Analytics, University of Vienna, 1010 Vienna, Austria;

Transportation Science, 2020, vol. 54, issue 4, 1073-1090

Abstract: This paper considers the vehicle routing problem with stochastic demands under optimal restocking. We develop an exact algorithm that is effective for solving instances with many vehicles and few customers per route. In our experiments, we show that in these instances, solving the stochastic problem is most relevant (i.e., the potential gains over the deterministic equivalent solution are highest). The proposed branch-price-and-cut algorithm relies on an efficient labeling procedure, exact and heuristic dominance rules, and completion bounds to price profitable columns. Instances with up to 76 nodes could be solved in less than five hours, and instances with up to 148 nodes could be solved in long runs of the algorithm. The experiments also allowed new findings on the problem. The solution to the stochastic problem is up to 10% less costly than the deterministic equivalent solution. Opening new routes reduces restocking costs and in many cases results in solutions with less transportation costs. When the number of routes is not fixed, the optimal solutions under detour-to-depot and optimal restocking are nearly equivalent. However, when the number of routes is limited and the expected demand along a route is allowed to exceed the vehicle capacity, optimal restocking may be significantly more cost-effective than the detour-to-depot policy.

Keywords: stochastic vehicle routing; optimal restocking; branch price and cut; stochastic dynamic programming (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
https://doi.org/10.1287/trsc.2020.0976 (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:54:y:2020:i:4:p:1073-1090

Access Statistics for this article

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