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

Scenario-Based Planning for Partially Dynamic Vehicle Routing with Stochastic Customers

Author

Listed:
  • Russell W. Bent

    (Department of Computer Science, Brown University, Box 1910, Providence, Rhode Island 02912)

  • Pascal Van Hentenryck

    (Department of Computer Science, Brown University, Box 1910, Providence, Rhode Island 02912)

Abstract

The multiple vehicle routing problem with time windows (VRPTW) is a hard and extensively studied combinatorial optimization problem. This paper considers a dynamic VRPTW with stochastic customers, where the goal is to maximize the number of serviced customers. It presents a multiple scenario approach (MSA) that continuously generates routing plans for scenarios including known and future requests. Decisions during execution use a distinguished plan chosen, at each decision, by a consensus function. The approach was evaluated on vehicle routing problems adapted from the Solomon benchmarks with a degree of dynamism varying between 30% and 80%. They indicate that MSA exhibits dramatic improvements over approaches not exploiting stochastic information, that the use of consensus function improves the quality of the solutions significantly, and that the benefits of MSA increase with the (effective) degree of dynamism.

Suggested Citation

  • 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.
    • Handle: RePEc:inm:oropre:v:52:y:2004:i:6:p:977-987
    DOI: 10.1287/opre.1040.0124
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.1040.0124
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.1040.0124?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. Gilbert Laporte & François Louveaux & Hélène Mercure, 1992. "The Vehicle Routing Problem with Stochastic Travel Times," Transportation Science, INFORMS, vol. 26(3), pages 161-170, August.
    3. Michel Gendreau & François Guertin & Jean-Yves Potvin & Éric Taillard, 1999. "Parallel Tabu Search for Real-Time Vehicle Routing and Dispatching," Transportation Science, INFORMS, vol. 33(4), pages 381-390, November.
    4. 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.
    5. 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.
    6. Dimitris J. Bertsimas, 1992. "A Vehicle Routing Problem with Stochastic Demand," Operations Research, INFORMS, vol. 40(3), pages 574-585, June.
    7. Swihart, Michael R. & Papastavrou, Jason D., 1999. "A stochastic and dynamic model for the single-vehicle pick-up and delivery problem," European Journal of Operational Research, Elsevier, vol. 114(3), pages 447-464, May.
    8. Nicola Secomandi, 2001. "A Rollout Policy for the Vehicle Routing Problem with Stochastic Demands," Operations Research, INFORMS, vol. 49(5), pages 796-802, October.
    9. Russell Bent & Pascal Van Hentenryck, 2004. "A Two-Stage Hybrid Local Search for the Vehicle Routing Problem with Time Windows," Transportation Science, INFORMS, vol. 38(4), pages 515-530, November.
    10. 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.
    11. Warren Powell & Joel Shapiro & Hugo Simao, 2001. "A Representational Paradigm for Dynamic Resource Transformation Problems," Annals of Operations Research, Springer, vol. 104(1), pages 231-279, April.
    12. 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.
    13. A Larsen & O Madsen & M Solomon, 2002. "Partially dynamic vehicle routing—models and algorithms," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 53(6), pages 637-646, June.
    14. Warren B. Powell, 1996. "A Stochastic Formulation of the Dynamic Assignment Problem, with an Application to Truckload Motor Carriers," Transportation Science, INFORMS, vol. 30(3), pages 195-219, August.
    15. Soumia Ichoua & Michel Gendreau & Jean-Yves Potvin, 2000. "Diversion Issues in Real-Time Vehicle Dispatching," Transportation Science, INFORMS, vol. 34(4), pages 426-438, November.
    16. Martin Savelsbergh & Marc Sol, 1998. "Drive: Dynamic Routing of Independent Vehicles," Operations Research, INFORMS, vol. 46(4), pages 474-490, August.
    17. 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.
    18. 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.
    19. Marius M. Solomon, 1987. "Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints," Operations Research, INFORMS, vol. 35(2), pages 254-265, April.
    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. 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.
    2. Barrett W. Thomas & Chelsea C. White, 2004. "Anticipatory Route Selection," Transportation Science, INFORMS, vol. 38(4), pages 473-487, November.
    3. Zhang, Jian & Woensel, Tom Van, 2023. "Dynamic vehicle routing with random requests: A literature review," International Journal of Production Economics, Elsevier, vol. 256(C).
    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. 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.
    6. Jian Yang & Patrick Jaillet & Hani Mahmassani, 2004. "Real-Time Multivehicle Truckload Pickup and Delivery Problems," Transportation Science, INFORMS, vol. 38(2), pages 135-148, May.
    7. 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.
    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. 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.
    10. 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.
    11. 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.
    12. Ghiani, Gianpaolo & Guerriero, Francesca & Laporte, Gilbert & Musmanno, Roberto, 2003. "Real-time vehicle routing: Solution concepts, algorithms and parallel computing strategies," European Journal of Operational Research, Elsevier, vol. 151(1), pages 1-11, November.
    13. 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.
    14. Allan Larsen & Oli B. G. Madsen & Marius M. Solomon, 2004. "The A Priori Dynamic Traveling Salesman Problem with Time Windows," Transportation Science, INFORMS, vol. 38(4), pages 459-472, November.
    15. 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.
    16. 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.
    17. 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.
    18. 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.
    19. Sheng Liu & Long He & Zuo-Jun Max Shen, 2021. "On-Time Last-Mile Delivery: Order Assignment with Travel-Time Predictors," Management Science, INFORMS, vol. 67(7), pages 4095-4119, July.
    20. 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.

    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:52:y:2004:i:6:p:977-987. 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.