A Unifying Framework for the Capacitated Vehicle Routing Problem Under Risk and Ambiguity

Shubhechyya Ghosal (), Chin Pang Ho () and Wolfram Wiesemann ()
Additional contact information
Shubhechyya Ghosal: Imperial College Business School, Imperial College London, London SW7 2AZ, United Kingdom
Chin Pang Ho: School of Data Science, City University of Hong Kong, Hong Kong
Wolfram Wiesemann: Imperial College Business School, Imperial College London, London SW7 2AZ, United Kingdom

Operations Research, 2024, vol. 72, issue 2, 425-443

Abstract: We propose a generic model for the capacitated vehicle routing problem (CVRP) under demand uncertainty. By combining risk measures, satisficing measures, or disutility functions with complete or partial characterizations of the probability distribution governing the demands, our formulation bridges the popular but often independently studied paradigms of stochastic programming and distributionally robust optimization. We characterize when an uncertainty-affected CVRP is (not) amenable to a solution via a popular branch-and-cut scheme, and we elucidate how this solvability relates to the interplay between the employed decision criterion and the available description of the uncertainty. Our framework offers a unified treatment of several CVRP variants from the recent literature, such as formulations that optimize the requirements violation or the essential riskiness indices, and it, at the same time, allows us to study new problem variants, such as formulations that optimize the worst case expected disutility over Wasserstein or ϕ -divergence ambiguity sets. All of our formulations can be solved by the same branch-and-cut algorithm with only minimal adaptations, which makes them attractive for practical implementations.

Keywords: Transportation; capacitated vehicle routing problem; stochastic programming; distributionally robust optimization; branch-and-cut (search for similar items in EconPapers)
Date: 2024
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2021.0669 (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:72:y:2024:i:2:p:425-443

Access Statistics for this article

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