IDEAS home Printed from https://ideas.repec.org/a/inm/ortrsc/v40y2006i4p421-438.html
   My bibliography  Save this article

Solving a Dynamic and Stochastic Vehicle Routing Problem with a Sample Scenario Hedging Heuristic

Author

Listed:
  • Lars M. Hvattum

    (Molde University College, 6411 Molde, Norway)

  • Arne Løkketangen

    (Molde University College, 6411 Molde, Norway)

  • Gilbert Laporte

    (HEC Montréal, Canada)

Abstract

The statement of the standard vehicle routing problem cannot always capture all aspects of real-world applications. As a result, extensions or modifications to the model are warranted. Here we consider the case when customers can call in orders during the daily operations; i.e., both customer locations and demands may be unknown in advance. This is modeled as a combined dynamic and stochastic programming problem, and a heuristic solution method is developed where sample scenarios are generated, solved heuristically, and combined iteratively to form a solution to the overall problem.

Suggested Citation

  • Lars M. Hvattum & Arne Løkketangen & Gilbert Laporte, 2006. "Solving a Dynamic and Stochastic Vehicle Routing Problem with a Sample Scenario Hedging Heuristic," Transportation Science, INFORMS, vol. 40(4), pages 421-438, November.
    • Handle: RePEc:inm:ortrsc:v:40:y:2006:i:4:p:421-438
    DOI: 10.1287/trsc.1060.0166
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/trsc.1060.0166
    Download Restriction: no
    File URL: https://libkey.io/10.1287/trsc.1060.0166?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. Gendreau, Michel & Laporte, Gilbert & Seguin, Rene, 1996. "Stochastic vehicle routing," European Journal of Operational Research, Elsevier, vol. 88(1), pages 3-12, January.
    2. R. Montemanni & L. M. Gambardella & A. E. Rizzoli & A. V. Donati, 2005. "Ant Colony System for a Dynamic Vehicle Routing Problem," Journal of Combinatorial Optimization, Springer, vol. 10(4), pages 327-343, December.
    3. Willem Klein Haneveld & Maarten van der Vlerk, 1999. "Stochastic integer programming:General models and algorithms," Annals of Operations Research, Springer, vol. 85(0), pages 39-57, January.
    4. Mitrovic-Minic, Snezana & Krishnamurti, Ramesh & Laporte, Gilbert, 2004. "Double-horizon based heuristics for the dynamic pickup and delivery problem with time windows," Transportation Research Part B: Methodological, Elsevier, vol. 38(8), pages 669-685, September.
    5. Mitrovic-Minic, Snezana & Laporte, Gilbert, 2004. "Waiting strategies for the dynamic pickup and delivery problem with time windows," Transportation Research Part B: Methodological, Elsevier, vol. 38(7), pages 635-655, August.
    6. Dimitris J. Bertsimas & Garrett van Ryzin, 1991. "A Stochastic and Dynamic Vehicle Routing Problem in the Euclidean Plane," Operations Research, INFORMS, vol. 39(4), pages 601-615, August.
    7. Bertsimas, Dimitris & Van Ryzin, Garrett., 1991. "A stochastic and dynamic vehicle routing problem in the Euclidean plane," Working papers 3286-91., Massachusetts Institute of Technology (MIT), Sloan School of Management.
    8. Russell W. Bent & Pascal Van Hentenryck, 2004. "Scenario-Based Planning for Partially Dynamic Vehicle Routing with Stochastic Customers," Operations Research, INFORMS, vol. 52(6), pages 977-987, December.
    9. R. T. Rockafellar & Roger J.-B. Wets, 1991. "Scenarios and Policy Aggregation in Optimization Under Uncertainty," Mathematics of Operations Research, INFORMS, vol. 16(1), pages 119-147, February.
    10. Jürgen Branke & Martin Middendorf & Guntram Noeth & Maged Dessouky, 2005. "Waiting Strategies for Dynamic Vehicle Routing," Transportation Science, INFORMS, vol. 39(3), pages 298-312, August.
    11. 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.
    12. Michel Gendreau & Gilbert Laporte & René Séguin, 1996. "A Tabu Search Heuristic for the Vehicle Routing Problem with Stochastic Demands and Customers," Operations Research, INFORMS, vol. 44(3), pages 469-477, June.
    13. 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.
    14. Soumia Ichoua & Michel Gendreau & Jean-Yves Potvin, 2006. "Exploiting Knowledge About Future Demands for Real-Time Vehicle Dispatching," Transportation Science, INFORMS, vol. 40(2), pages 211-225, May.
    15. Dimitris J. Bertsimas & Garrett van Ryzin, 1993. "Stochastic and Dynamic Vehicle Routing in the Euclidean Plane with Multiple Capacitated Vehicles," Operations Research, INFORMS, vol. 41(1), pages 60-76, February.
    16. 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.
    17. Stein W. Wallace, 2000. "Decision Making Under Uncertainty: Is Sensitivity Analysis of Any Use?," Operations Research, INFORMS, vol. 48(1), pages 20-25, February.
    18. Astrid S. Kenyon & David P. Morton, 2003. "Stochastic Vehicle Routing with Random Travel Times," Transportation Science, INFORMS, vol. 37(1), pages 69-82, February.
    19. Barrett W. Thomas & Chelsea C. White, 2004. "Anticipatory Route Selection," Transportation Science, INFORMS, vol. 38(4), pages 473-487, November.
    20. R. Jagannathan, 1985. "Use of Sample Information in Stochastic Recourse and Chance-Constrained Programming Models," Management Science, INFORMS, vol. 31(1), pages 96-108, January.
    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. Pillac, Victor & Gendreau, Michel & Guéret, Christelle & Medaglia, Andrés L., 2013. "A review of dynamic vehicle routing problems," European Journal of Operational Research, Elsevier, vol. 225(1), pages 1-11.
    2. Liu, Chuanju & Lin, Shaochong & Shen, Zuo-Jun Max & Zhang, Junlong, 2023. "Stochastic service network design: The value of fixed routes," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 174(C).
    3. Soeffker, Ninja & Ulmer, Marlin W. & Mattfeld, Dirk C., 2022. "Stochastic dynamic vehicle routing in the light of prescriptive analytics: A review," European Journal of Operational Research, Elsevier, vol. 298(3), pages 801-820.
    4. Wang, Zhongxiang & Haghani, Ali, 2020. "Column generation-based stochastic school bell time and bus scheduling optimization," European Journal of Operational Research, Elsevier, vol. 286(3), pages 1087-1102.
    5. Yan, Shangyao & Lin, Jenn-Rong & Lai, Chun-Wei, 2013. "The planning and real-time adjustment of courier routing and scheduling under stochastic travel times and demands," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 53(C), pages 34-48.
    6. Zhang, Jian & Woensel, Tom Van, 2023. "Dynamic vehicle routing with random requests: A literature review," International Journal of Production Economics, Elsevier, vol. 256(C).
    7. Alves de Queiroz, Thiago & Iori, Manuel & Kramer, Arthur & Kuo, Yong-Hong, 2023. "Dynamic scheduling of patients in emergency departments," European Journal of Operational Research, Elsevier, vol. 310(1), pages 100-116.
    8. Ulmer, Marlin W. & Soeffker, Ninja & Mattfeld, Dirk C., 2018. "Value function approximation for dynamic multi-period vehicle routing," European Journal of Operational Research, Elsevier, vol. 269(3), pages 883-899.
    9. Wang, Xuping & Ruan, Junhu & Shi, Yan, 2012. "A recovery model for combinational disruptions in logistics delivery: Considering the real-world participators," International Journal of Production Economics, Elsevier, vol. 140(1), pages 508-520.
    10. Zhang, Jian & Luo, Kelin & Florio, Alexandre M. & Van Woensel, Tom, 2023. "Solving large-scale dynamic vehicle routing problems with stochastic requests," European Journal of Operational Research, Elsevier, vol. 306(2), pages 596-614.
    11. Côté, Jean-François & Alves de Queiroz, Thiago & Gallesi, Francesco & Iori, Manuel, 2023. "A branch-and-regret algorithm for the same-day delivery problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 177(C).

    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. Pillac, Victor & Gendreau, Michel & Guéret, Christelle & Medaglia, Andrés L., 2013. "A review of dynamic vehicle routing problems," European Journal of Operational Research, Elsevier, vol. 225(1), pages 1-11.
    2. Zhang, Jian & Woensel, Tom Van, 2023. "Dynamic vehicle routing with random requests: A literature review," International Journal of Production Economics, Elsevier, vol. 256(C).
    3. Soumia Ichoua & Michel Gendreau & Jean-Yves Potvin, 2006. "Exploiting Knowledge About Future Demands for Real-Time Vehicle Dispatching," Transportation Science, INFORMS, vol. 40(2), pages 211-225, May.
    4. Barrett W. Thomas, 2007. "Waiting Strategies for Anticipating Service Requests from Known Customer Locations," Transportation Science, INFORMS, vol. 41(3), pages 319-331, August.
    5. Nikola Mardešić & Tomislav Erdelić & Tonči Carić & Marko Đurasević, 2023. "Review of Stochastic Dynamic Vehicle Routing in the Evolving Urban Logistics Environment," Mathematics, MDPI, vol. 12(1), pages 1-44, December.
    6. Soeffker, Ninja & Ulmer, Marlin W. & Mattfeld, Dirk C., 2022. "Stochastic dynamic vehicle routing in the light of prescriptive analytics: A review," European Journal of Operational Research, Elsevier, vol. 298(3), pages 801-820.
    7. Marlin W. Ulmer & Dirk C. Mattfeld & Felix Köster, 2018. "Budgeting Time for Dynamic Vehicle Routing with Stochastic Customer Requests," Transportation Science, INFORMS, vol. 52(1), pages 20-37, January.
    8. Miguel Andres Figliozzi & Hani S. Mahmassani & Patrick Jaillet, 2007. "Pricing in Dynamic Vehicle Routing Problems," Transportation Science, INFORMS, vol. 41(3), pages 302-318, August.
    9. Marlin W. Ulmer & Justin C. Goodson & Dirk C. Mattfeld & Marco Hennig, 2019. "Offline–Online Approximate Dynamic Programming for Dynamic Vehicle Routing with Stochastic Requests," Service Science, INFORMS, vol. 53(1), pages 185-202, February.
    10. Diego Muñoz-Carpintero & Doris Sáez & Cristián E. Cortés & Alfredo Núñez, 2015. "A Methodology Based on Evolutionary Algorithms to Solve a Dynamic Pickup and Delivery Problem Under a Hybrid Predictive Control Approach," Transportation Science, INFORMS, vol. 49(2), pages 239-253, May.
    11. Cristián E. Cortés & Doris Sáez & Alfredo Núñez & Diego Muñoz-Carpintero, 2009. "Hybrid Adaptive Predictive Control for a Dynamic Pickup and Delivery Problem," Transportation Science, INFORMS, vol. 43(1), pages 27-42, February.
    12. Russell W. Bent & Pascal Van Hentenryck, 2004. "Scenario-Based Planning for Partially Dynamic Vehicle Routing with Stochastic Customers," Operations Research, INFORMS, vol. 52(6), pages 977-987, December.
    13. Chrysanthos E. Gounaris & Wolfram Wiesemann & Christodoulos A. Floudas, 2013. "The Robust Capacitated Vehicle Routing Problem Under Demand Uncertainty," Operations Research, INFORMS, vol. 61(3), pages 677-693, June.
    14. Zhang, Jian & Luo, Kelin & Florio, Alexandre M. & Van Woensel, Tom, 2023. "Solving large-scale dynamic vehicle routing problems with stochastic requests," European Journal of Operational Research, Elsevier, vol. 306(2), pages 596-614.
    15. Cheung, Bernard K.-S. & Choy, K.L. & Li, Chung-Lun & Shi, Wenzhong & Tang, Jian, 2008. "Dynamic routing model and solution methods for fleet management with mobile technologies," International Journal of Production Economics, Elsevier, vol. 113(2), pages 694-705, June.
    16. Jürgen Branke & Martin Middendorf & Guntram Noeth & Maged Dessouky, 2005. "Waiting Strategies for Dynamic Vehicle Routing," Transportation Science, INFORMS, vol. 39(3), pages 298-312, August.
    17. 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.
    18. 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.
    19. 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.
    20. Alejandro Toriello & William B. Haskell & Michael Poremba, 2014. "A Dynamic Traveling Salesman Problem with Stochastic Arc Costs," Operations Research, INFORMS, vol. 62(5), pages 1107-1125, October.

    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:ortrsc:v:40:y:2006:i:4:p:421-438. 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.