IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v72y2024i2p425-443.html
   My bibliography  Save this article

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

Author

Listed:
  • 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)

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.

Suggested Citation

  • Shubhechyya Ghosal & Chin Pang Ho & Wolfram Wiesemann, 2024. "A Unifying Framework for the Capacitated Vehicle Routing Problem Under Risk and Ambiguity," Operations Research, INFORMS, vol. 72(2), pages 425-443, March.
    • Handle: RePEc:inm:oropre:v:72:y:2024:i:2:p:425-443
    DOI: 10.1287/opre.2021.0669
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.2021.0669
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.2021.0669?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:oropre:v:72:y:2024:i:2:p:425-443. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.