IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v285y2020i1p172-182.html
   My bibliography  Save this article

Optimal a priori tour and restocking policy for the single-vehicle routing problem with stochastic demands

Author

Listed:
  • Florio, Alexandre M.
  • Hartl, Richard F.
  • Minner, Stefan

Abstract

We present a model for the single-vehicle routing problem with stochastic demands (SVRPSD) with optimal restocking. The model is derived from a characterization of the SVRPSD as a Markov decision process (MDP) controlled by a certain class of policies, and is valid for general discrete demand probability distributions. We transform this MDP into an equivalent mixed-integer linear model, which is then used to solve small instances to optimality. By doing so, we are able to quantify the drawbacks associated with the detour-to-depot restocking policy, an assumption of many exact approaches for the (multivehicle) VRPSD. We also examine the tradeoff between the deterministic a priori cost and the stochastic restocking cost for varying route load scenarios. Finally, a wait-and-see model for the SVRPSD is proposed, and is used within a parallel heuristic to solve larger literature instances with up to 150 nodes and Poisson distributed demands. Computational experiments demonstrate the effectiveness of the heuristic approach, and also indicate under which circumstances near-optimal solutions can be obtained by the myopic strategy of a priori route cost minimization.

Suggested Citation

  • Florio, Alexandre M. & Hartl, Richard F. & Minner, Stefan, 2020. "Optimal a priori tour and restocking policy for the single-vehicle routing problem with stochastic demands," European Journal of Operational Research, Elsevier, vol. 285(1), pages 172-182.
  • Handle: RePEc:eee:ejores:v:285:y:2020:i:1:p:172-182
    DOI: 10.1016/j.ejor.2018.10.045
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221718309135
    Download Restriction: Full text for ScienceDirect subscribers only

    File URL: https://libkey.io/10.1016/j.ejor.2018.10.045?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Gendreau, Michel & Laporte, Gilbert & Seguin, Rene, 1996. "Stochastic vehicle routing," European Journal of Operational Research, Elsevier, vol. 88(1), pages 3-12, January.
    2. 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.
    3. G. Clarke & J. W. Wright, 1964. "Scheduling of Vehicles from a Central Depot to a Number of Delivery Points," Operations Research, INFORMS, vol. 12(4), pages 568-581, August.
    4. Dimitris J. Bertsimas, 1992. "A Vehicle Routing Problem with Stochastic Demand," Operations Research, INFORMS, vol. 40(3), pages 574-585, June.
    5. Nicola Secomandi, 2001. "A Rollout Policy for the Vehicle Routing Problem with Stochastic Demands," Operations Research, INFORMS, vol. 49(5), pages 796-802, October.
    6. 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.
    7. 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.
    8. 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.
    9. 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.
    10. Dror, Moshe & Trudeau, Pierre, 1986. "Stochastic vehicle routing with modified savings algorithm," European Journal of Operational Research, Elsevier, vol. 23(2), pages 228-235, February.
    11. 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.
    12. Cyrus Derman, 1962. "On Sequential Decisions and Markov Chains," Management Science, INFORMS, vol. 9(1), pages 16-24, October.
    13. Noorizadegan, Mahdi & Chen, Bo, 2018. "Vehicle routing with probabilistic capacity constraints," European Journal of Operational Research, Elsevier, vol. 270(2), pages 544-555.
    14. 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.
    15. Bastian, Cock & Rinnooy Kan, Alexander H. G., 1992. "The stochastic vehicle routing problem revisited," European Journal of Operational Research, Elsevier, vol. 56(3), pages 407-412, February.
    16. Krishna Chepuri & Tito Homem-de-Mello, 2005. "Solving the Vehicle Routing Problem with Stochastic Demands using the Cross-Entropy Method," Annals of Operations Research, Springer, vol. 134(1), pages 153-181, February.
    17. Pandelis, D.G. & Kyriakidis, E.G. & Dimitrakos, T.D., 2012. "Single vehicle routing problems with a predefined customer sequence, compartmentalized load and stochastic demands," European Journal of Operational Research, Elsevier, vol. 217(2), pages 324-332.
    18. James R. Yee & Bruce L. Golden, 1980. "A note on determining operating strategies for probabilistic vehicle routing," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 27(1), pages 159-163, March.
    19. Cyrus Derman & Morton Klein, 1965. "Some Remarks on Finite Horizon Markovian Decision Models," Operations Research, INFORMS, vol. 13(2), pages 272-278, April.
    20. Tsirimpas, P. & Tatarakis, A. & Minis, I. & Kyriakidis, E.G., 2008. "Single vehicle routing with a predefined customer sequence and multiple depot returns," European Journal of Operational Research, Elsevier, vol. 187(2), pages 483-495, June.
    21. 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.
    22. Michel Gendreau & Ola Jabali & Walter Rei, 2016. "50th Anniversary Invited Article—Future Research Directions in Stochastic Vehicle Routing," Transportation Science, INFORMS, vol. 50(4), pages 1163-1173, November.
    23. Justin C. Goodson & Jeffrey W. Ohlmann & Barrett W. Thomas, 2013. "Rollout Policies for Dynamic Solutions to the Multivehicle Routing Problem with Stochastic Demand and Duration Limits," Operations Research, INFORMS, vol. 61(1), pages 138-154, February.
    24. Dimitris Bertsimas & Philippe Chervi & Michael Peterson, 1995. "Computational Approaches to Stochastic Vehicle Routing Problems," Transportation Science, INFORMS, vol. 29(4), pages 342-352, November.
    25. 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.
    26. Tatarakis, A. & Minis, I., 2009. "Stochastic single vehicle routing with a predefined customer sequence and multiple depot returns," European Journal of Operational Research, Elsevier, vol. 197(2), pages 557-571, September.
    27. Chris Groër & Bruce Golden & Edward Wasil, 2009. "The Consistent Vehicle Routing Problem," Manufacturing & Service Operations Management, INFORMS, vol. 11(4), pages 630-643, February.
    28. Justin C. Goodson & Barrett W. Thomas & Jeffrey W. Ohlmann, 2016. "Restocking-Based Rollout Policies for the Vehicle Routing Problem with Stochastic Demand and Duration Limits," Transportation Science, INFORMS, vol. 50(2), pages 591-607, May.
    29. Stewart, William R. & Golden, Bruce L., 1983. "Stochastic vehicle routing: A comprehensive approach," European Journal of Operational Research, Elsevier, vol. 14(4), pages 371-385, December.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Zhang, Jian & Woensel, Tom Van, 2023. "Dynamic vehicle routing with random requests: A literature review," International Journal of Production Economics, Elsevier, vol. 256(C).
    2. Florio, Alexandre M. & Gendreau, Michel & Hartl, Richard F. & Minner, Stefan & Vidal, Thibaut, 2023. "Recent advances in vehicle routing with stochastic demands: Bayesian learning for correlated demands and elementary branch-price-and-cut," European Journal of Operational Research, Elsevier, vol. 306(3), pages 1081-1093.
    3. Maheshwari, Pratik & Kamble, Sachin & Belhadi, Amine & Venkatesh, Mani & Abedin, Mohammad Zoynul, 2023. "Digital twin-driven real-time planning, monitoring, and controlling in food supply chains," Technological Forecasting and Social Change, Elsevier, vol. 195(C).
    4. 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.
    5. Maskooki, Alaleh & Kallio, Markku, 2023. "A bi-criteria moving-target travelling salesman problem under uncertainty," European Journal of Operational Research, Elsevier, vol. 309(1), pages 271-285.
    6. Karels, Vincent C.G. & Rei, Walter & Veelenturf, Lucas P. & Van Woensel, Tom, 2024. "A vehicle routing problem with multiple service agreements," European Journal of Operational Research, Elsevier, vol. 313(1), pages 129-145.

    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. 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.
    2. 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.
    3. Luo, Zhixing & Qin, Hu & Zhang, Dezhi & Lim, Andrew, 2016. "Adaptive large neighborhood search heuristics for the vehicle routing problem with stochastic demands and weight-related cost," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 85(C), pages 69-89.
    4. 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.
    5. 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.
    6. 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.
    7. 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.
    8. 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.
    9. Zhang, Junlong & Lam, William H.K. & Chen, Bi Yu, 2016. "On-time delivery probabilistic models for the vehicle routing problem with stochastic demands and time windows," European Journal of Operational Research, Elsevier, vol. 249(1), pages 144-154.
    10. 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.
    11. Ann M. Campbell & Barrett W. Thomas, 2008. "Probabilistic Traveling Salesman Problem with Deadlines," Transportation Science, INFORMS, vol. 42(1), pages 1-21, February.
    12. Justin C. Goodson & Barrett W. Thomas & Jeffrey W. Ohlmann, 2016. "Restocking-Based Rollout Policies for the Vehicle Routing Problem with Stochastic Demand and Duration Limits," Transportation Science, INFORMS, vol. 50(2), pages 591-607, May.
    13. 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.
    14. 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.
    15. 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.
    16. Wadi Khalid Anuar & Lai Soon Lee & Hsin-Vonn Seow & Stefan Pickl, 2022. "A Multi-Depot Dynamic Vehicle Routing Problem with Stochastic Road Capacity: An MDP Model and Dynamic Policy for Post-Decision State Rollout Algorithm in Reinforcement Learning," Mathematics, MDPI, vol. 10(15), pages 1-70, July.
    17. Krishna Chepuri & Tito Homem-de-Mello, 2005. "Solving the Vehicle Routing Problem with Stochastic Demands using the Cross-Entropy Method," Annals of Operations Research, Springer, vol. 134(1), pages 153-181, February.
    18. Tatarakis, A. & Minis, I., 2009. "Stochastic single vehicle routing with a predefined customer sequence and multiple depot returns," European Journal of Operational Research, Elsevier, vol. 197(2), pages 557-571, September.
    19. 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.
    20. 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.

    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:eee:ejores:v:285:y:2020:i:1:p:172-182. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.