IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v35y2023i2p423-439.html
   My bibliography  Save this article

An Improved Integer L -Shaped Method for the Vehicle Routing Problem with Stochastic Demands

Author

Listed:
  • Y. N. Hoogendoorn

    (Erasmus School of Economics, Erasmus University Rotterdam, 3062 Rotterdam, Netherlands)

  • R. Spliet

    (Erasmus School of Economics, Erasmus University Rotterdam, 3062 Rotterdam, Netherlands)

Abstract

We present an improved integer L -shaped method for the vehicle routing problem with stochastic demands. It exhibits speedups up to a factor of 325 compared with the current state-of-the-art, which allows us to solve 153 previously unsolved benchmark instances to optimality. The algorithm builds on the state-of-the-art in a few ways. First, we rectify a few technical issues found in the current literature. Second, we improve valid inequalities known as partial route inequalities. Finally, we introduce three new types of valid inequalities.

Suggested Citation

  • Y. N. Hoogendoorn & R. Spliet, 2023. "An Improved Integer L -Shaped Method for the Vehicle Routing Problem with Stochastic Demands," INFORMS Journal on Computing, INFORMS, vol. 35(2), pages 423-439, March.
    • Handle: RePEc:inm:orijoc:v:35:y:2023:i:2:p:423-439
    DOI: 10.1287/ijoc.2023.1271
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/ijoc.2023.1271
    Download Restriction: no
    File URL: https://libkey.io/10.1287/ijoc.2023.1271?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
    ---><---

    References listed on IDEAS

    as
    1. C. Hjorring & J. Holt, 1999. "New optimality cuts for a single‐vehicle stochastic routing problem," Annals of Operations Research, Springer, vol. 86(0), pages 569-584, January.
    2. Dror, Moshe, 1993. "Modeling vehicle routing with uncertain demands as a stochastic program: Properties of the corresponding solution," European Journal of Operational Research, Elsevier, vol. 64(3), pages 432-441, February.
    3. Michel Gendreau & Gilbert Laporte & René Séguin, 1995. "An Exact Algorithm for the Vehicle Routing Problem with Stochastic Demands and Customers," Transportation Science, INFORMS, vol. 29(2), pages 143-155, May.
    4. Alexandre M. Florio & Richard F. Hartl & Stefan Minner, 2020. "New Exact Algorithm for the Vehicle Routing Problem with Stochastic Demands," Transportation Science, INFORMS, vol. 54(4), pages 1073-1090, July.
    5. Wen-Huei Yang & Kamlesh Mathur & Ronald H. Ballou, 2000. "Stochastic Vehicle Routing Problem with Restocking," Transportation Science, INFORMS, vol. 34(1), pages 99-112, February.
    6. Moshe Dror & Gilbert Laporte & Pierre Trudeau, 1989. "Vehicle Routing with Stochastic Demands: Properties and Solution Frameworks," Transportation Science, INFORMS, vol. 23(3), pages 166-176, August.
    7. Gilbert Laporte & FranÇois V. Louveaux & Luc van Hamme, 2002. "An Integer L -Shaped Algorithm for the Capacitated Vehicle Routing Problem with Stochastic Demands," Operations Research, INFORMS, vol. 50(3), pages 415-423, June.
    8. A N Letchford & J Lysgaard & R W Eglese, 2007. "A branch-and-cut algorithm for the capacitated open vehicle routing problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 58(12), pages 1642-1651, December.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Majid Salavati-Khoshghalb & Michel Gendreau & Ola Jabali & Walter Rei, 2019. "A Rule-Based Recourse for the Vehicle Routing Problem with Stochastic Demands," Transportation Science, INFORMS, vol. 53(5), pages 1334-1353, September.
    2. Nicola Secomandi & François Margot, 2009. "Reoptimization Approaches for the Vehicle-Routing Problem with Stochastic Demands," Operations Research, INFORMS, vol. 57(1), pages 214-230, February.
    3. De La Vega, Jonathan & Gendreau, Michel & Morabito, Reinaldo & Munari, Pedro & Ordóñez, Fernando, 2023. "An integer L-shaped algorithm for the vehicle routing problem with time windows and stochastic demands," European Journal of Operational Research, Elsevier, vol. 308(2), pages 676-695.
    4. Novoa, Clara & Storer, Robert, 2009. "An approximate dynamic programming approach for the vehicle routing problem with stochastic demands," European Journal of Operational Research, Elsevier, vol. 196(2), pages 509-515, July.
    5. Prasanna Balaprakash & Mauro Birattari & Thomas Stützle & Marco Dorigo, 2015. "Estimation-based metaheuristics for the single vehicle routing problem with stochastic demands and customers," Computational Optimization and Applications, Springer, vol. 61(2), pages 463-487, June.
    6. Majid Salavati-Khoshghalb & Michel Gendreau & Ola Jabali & Walter Rei, 2019. "A hybrid recourse policy for the vehicle routing problem with stochastic demands," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 8(3), pages 269-298, September.
    7. Chen, Lijian & Chiang, Wen-Chyuan & Russell, Robert & Chen, Jun & Sun, Dengfeng, 2018. "The probabilistic vehicle routing problem with service guarantees," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 111(C), pages 149-164.
    8. Salavati-Khoshghalb, Majid & Gendreau, Michel & Jabali, Ola & Rei, Walter, 2019. "An exact algorithm to solve the vehicle routing problem with stochastic demands under an optimal restocking policy," European Journal of Operational Research, Elsevier, vol. 273(1), pages 175-189.
    9. Florent Hernandez & Michel Gendreau & Ola Jabali & Walter Rei, 2019. "A local branching matheuristic for the multi-vehicle routing problem with stochastic demands," Journal of Heuristics, Springer, vol. 25(2), pages 215-245, April.
    10. Benjamin Biesinger & Bin Hu & Günther R. Raidl, 2018. "A Genetic Algorithm in Combination with a Solution Archive for Solving the Generalized Vehicle Routing Problem with Stochastic Demands," Transportation Science, INFORMS, vol. 52(3), pages 673-690, June.
    11. Gilbert Laporte & FranÇois V. Louveaux & Luc van Hamme, 2002. "An Integer L -Shaped Algorithm for the Capacitated Vehicle Routing Problem with Stochastic Demands," Operations Research, INFORMS, vol. 50(3), pages 415-423, June.
    12. Bertazzi, Luca & Secomandi, Nicola, 2018. "Faster rollout search for the vehicle routing problem with stochastic demands and restocking," European Journal of Operational Research, Elsevier, vol. 270(2), pages 487-497.
    13. Walter Rei & Michel Gendreau & Patrick Soriano, 2010. "A Hybrid Monte Carlo Local Branching Algorithm for the Single Vehicle Routing Problem with Stochastic Demands," Transportation Science, INFORMS, vol. 44(1), pages 136-146, February.
    14. Nicola Secomandi, 2001. "A Rollout Policy for the Vehicle Routing Problem with Stochastic Demands," Operations Research, INFORMS, vol. 49(5), pages 796-802, October.
    15. Goodson, Justin C. & Ohlmann, Jeffrey W. & Thomas, Barrett W., 2012. "Cyclic-order neighborhoods with application to the vehicle routing problem with stochastic demand," European Journal of Operational Research, Elsevier, vol. 217(2), pages 312-323.
    16. Jinil Han & Chungmok Lee & Sungsoo Park, 2014. "A Robust Scenario Approach for the Vehicle Routing Problem with Uncertain Travel Times," Transportation Science, INFORMS, vol. 48(3), pages 373-390, August.
    17. Ann M. Campbell & Barrett W. Thomas, 2008. "Probabilistic Traveling Salesman Problem with Deadlines," Transportation Science, INFORMS, vol. 42(1), pages 1-21, February.
    18. Jorge Oyola & Halvard Arntzen & David L. Woodruff, 2017. "The stochastic vehicle routing problem, a literature review, Part II: solution methods," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 6(4), pages 349-388, December.
    19. Alan L. Erera & Juan C. Morales & Martin Savelsbergh, 2010. "The Vehicle Routing Problem with Stochastic Demand and Duration Constraints," Transportation Science, INFORMS, vol. 44(4), pages 474-492, November.
    20. F. Hooshmand Khaligh & S.A. MirHassani, 2016. "A mathematical model for vehicle routing problem under endogenous uncertainty," International Journal of Production Research, Taylor & Francis Journals, vol. 54(2), pages 579-590, January.

    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:orijoc:v:35:y:2023:i:2:p:423-439. 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.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with 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.