IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v86y1999i0p569-58410.1023-a1018995927636.html
   My bibliography  Save this article

New optimality cuts for a single‐vehicle stochastic routing problem

Author

Listed:
  • C. Hjorring
  • J. Holt

Abstract

In the Vehicle Routing literature, investigations have concentrated on problems in whichthe customer demands are known precisely. We consider an application in which the demandsare unknown prior to the creation of vehicle routes, but follow some known probabilitydistribution. Because of the variability in customer demands, it is possible that the actualtotal customer demand may exceed the capacity of the vehicle assigned to service thosecustomers. In this case, we have a route failure , and there is an additional cost related to thecustomer at which the vehicle stocks out. We aim to find routes that minimise the sum of thedistance travelled plus any additional expected costs due to route failure. Because of thedifficulty of this problem, this investigation only considers a single‐vehicle problem. Tofind optimal routes, the integer L‐shaped method is used. We solve a relaxed IP in which thedistance travelled is modelled exactly, but the expected costs due to route failure are approximated.Constraints are dynamically added to prevent subtours and to further improve therelaxation. Additional constraints (optimality cuts) are added which progressively form atighter approximation of the costs due to route failure. Gendreau et al. [6] apply a similarmethodology to a closely related problem. They add optimality cuts, each of which imposesa useful bound on the route failure cost for only one solution. In addition to that cut, wegenerate “general” optimality cuts, each of which imposes a useful bound on the route failurecost for many solutions. Computational results attesting to the success of this approach arepresented. Copyright Kluwer Academic Publishers 1999

Suggested Citation

  • 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.
  • Handle: RePEc:spr:annopr:v:86:y:1999:i:0:p:569-584:10.1023/a:1018995927636
    DOI: 10.1023/A:1018995927636
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1023/A:1018995927636
    Download Restriction: Access to full text is restricted to subscribers.

    File URL: https://libkey.io/10.1023/A:1018995927636?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.

    Citations

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


    Cited by:

    1. 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.
    2. François V. Louveaux & Juan-José Salazar-González, 2018. "Exact Approach for the Vehicle Routing Problem with Stochastic Demands and Preventive Returns," Service Science, INFORMS, vol. 52(6), pages 1463-1478, December.
    3. 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.
    4. 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.
    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. Moreno, Alfredo & Munari, Pedro & Alem, Douglas, 2019. "A branch-and-Benders-cut algorithm for the Crew Scheduling and Routing Problem in road restoration," European Journal of Operational Research, Elsevier, vol. 275(1), pages 16-34.
    7. Jean-François Côté & Michel Gendreau & Jean-Yves Potvin, 2020. "The Vehicle Routing Problem with Stochastic Two-Dimensional Items," Transportation Science, INFORMS, vol. 54(2), pages 453-469, March.
    8. 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.
    9. Zahra Azadi & Harsha Gangammanavar & Sandra Eksioglu, 2020. "Developing childhood vaccine administration and inventory replenishment policies that minimize open vial wastage," Annals of Operations Research, Springer, vol. 292(1), pages 215-247, September.
    10. 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.
    11. 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.
    12. 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.
    13. Jorge Oyola & Halvard Arntzen & David L. Woodruff, 2018. "The stochastic vehicle routing problem, a literature review, part I: models," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 7(3), pages 193-221, September.
    14. Zhan, Yang & Wang, Zizhuo & Wan, Guohua, 2021. "Home service routing and appointment scheduling with stochastic service times," European Journal of Operational Research, Elsevier, vol. 288(1), pages 98-110.
    15. 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.
    16. 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.
    17. 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.
    18. 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.
    19. Nicola Secomandi, 2001. "A Rollout Policy for the Vehicle Routing Problem with Stochastic Demands," Operations Research, INFORMS, vol. 49(5), pages 796-802, October.
    20. 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.
    21. 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.
    22. 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.
    23. Santos, A.M.P. & Fagerholt, Kjetil & Laporte, Gilbert & Guedes Soares, C., 2022. "A stochastic optimization approach for the supply vessel planning problem under uncertain demand," Transportation Research Part B: Methodological, Elsevier, vol. 162(C), pages 209-228.
    24. 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.

    More about this item

    Statistics

    Access and download statistics

    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:spr:annopr:v:86:y:1999:i:0:p:569-584:10.1023/a:1018995927636. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.