Optimization Online


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

Shubhechyya Ghosal(s.ghosal16***at***imperial.ac.uk)
Chin Pang Ho(clint.ho***at***cityu.edu.hk)
Wolfram Wiesemann(ww***at***imperial.ac.uk)

Abstract: We propose a generic model for the capacitated vehicle routing problem (CVRP) under demand uncertainty. By combining risk 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, while 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 $\phi$-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: Capacitated Vehicle Routing Problem, Stochastic Programming, (Distributionally) Robust Optimization

Category 1: Applications -- OR and Management Sciences

Category 2: Robust Optimization

Category 3: Stochastic Programming


Download: [PDF]

Entry Submitted: 10/14/2021
Entry Accepted: 10/14/2021
Entry Last Modified: 10/14/2021

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society