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

A probabilistic approach to pickup and delivery problems with time window uncertainty

Author

Listed:
  • Györgyi, Péter
  • Kis, Tamás

Abstract

In this paper, we study a dynamic and stochastic pickup and delivery problem proposed recently by Srour, Agatz and Oppen. We demonstrate that the cost structure of the problem permits an effective solution method without generating multiple scenarios. Instead, our method is based on a careful analysis of the transfer probability from one customer to the other. Our computational results confirm the effectiveness of our approach on the dataset of Srour et al., as well as on new, large problem instances.

Suggested Citation

  • Györgyi, Péter & Kis, Tamás, 2019. "A probabilistic approach to pickup and delivery problems with time window uncertainty," European Journal of Operational Research, Elsevier, vol. 274(3), pages 909-923.
    • Handle: RePEc:eee:ejores:v:274:y:2019:i:3:p:909-923
    DOI: 10.1016/j.ejor.2018.10.031
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221718308841
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2018.10.031?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. 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.
    2. 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.
    3. Berbeglia, Gerardo & Cordeau, Jean-François & Laporte, Gilbert, 2010. "Dynamic pickup and delivery problems," European Journal of Operational Research, Elsevier, vol. 202(1), pages 8-15, April.
    4. 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.
    5. Ferrucci, Francesco & Bock, Stefan & Gendreau, Michel, 2013. "A pro-active real-time control approach for dynamic vehicle routing problems dealing with the delivery of urgent goods," European Journal of Operational Research, Elsevier, vol. 225(1), pages 130-141.
    6. Oktay Günlük & Tracy Kimbrel & Laszlo Ladanyi & Baruch Schieber & Gregory B. Sorkin, 2006. "Vehicle Routing and Staffing for Sedan Service," Transportation Science, INFORMS, vol. 40(3), pages 313-326, August.
    7. 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.
    8. Gregorio Tirado & Lars Magnus Hvattum, 2017. "Improved solutions to dynamic and stochastic maritime pick-up and delivery problems using local search," Annals of Operations Research, Springer, vol. 253(2), pages 825-843, June.
    9. 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.
    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. Tao, Liangyan & Liu, Sifeng & Xie, Naiming & Javed, Saad Ahmed, 2021. "Optimal position of supply chain delivery window with risk-averse suppliers: A CVaR optimization approach," International Journal of Production Economics, Elsevier, vol. 232(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. 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. Ritzinger, Ulrike & Puchinger, Jakob & Rudloff, Christian & Hartl, Richard F., 2022. "Comparison of anticipatory algorithms for a dial-a-ride problem," European Journal of Operational Research, Elsevier, vol. 301(2), pages 591-608.
    3. 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.
    4. 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.
    5. Ferrucci, Francesco & Bock, Stefan, 2015. "A general approach for controlling vehicle en-route diversions in dynamic vehicle routing problems," Transportation Research Part B: Methodological, Elsevier, vol. 77(C), pages 76-87.
    6. Marlin W. Ulmer & Alan Erera & Martin Savelsbergh, 2022. "Dynamic service area sizing in urban delivery," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 44(3), pages 763-793, September.
    7. Zolfagharinia, Hossein & Haughton, Michael, 2018. "The importance of considering non-linear layover and delay costs for local truckers," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 109(C), pages 331-355.
    8. Stefan Vonolfen & Michael Affenzeller, 2016. "Distribution of waiting time for dynamic pickup and delivery problems," Annals of Operations Research, Springer, vol. 236(2), pages 359-382, January.
    9. Stefan Vonolfen & Michael Affenzeller, 2016. "Distribution of waiting time for dynamic pickup and delivery problems," Annals of Operations Research, Springer, vol. 236(2), pages 359-382, January.
    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. 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.
    12. 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.
    13. 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.
    14. Marlin W. Ulmer, 2020. "Horizontal combinations of online and offline approximate dynamic programming for stochastic dynamic vehicle routing," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 28(1), pages 279-308, March.
    15. Dimitris Bertsimas & Patrick Jaillet, & Sébastien Martin, 2019. "Online Vehicle Routing: The Edge of Optimization in Large-Scale Applications," Operations Research, INFORMS, vol. 67(1), pages 143-162, January.
    16. Srour, F.J. & Agatz, N.A.H. & Oppen, J., 2014. "Strategies for Handling Temporal Uncertainty in Pickup and Delivery Problems with Time Windows," ERIM Report Series Research in Management ERS-2014-015-LIS, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.
    17. Barrett W. Thomas, 2007. "Waiting Strategies for Anticipating Service Requests from Known Customer Locations," Transportation Science, INFORMS, vol. 41(3), pages 319-331, August.
    18. Srour, F.J. & Agatz, N.A.H. & Oppen, J., 2014. "The Value of Inaccurate Advance Time Window Information in a Pick-up and Delivery Problem," ERIM Report Series Research in Management ERS-2014-002-LIS, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.
    19. Fleckenstein, David & Klein, Robert & Steinhardt, Claudius, 2023. "Recent advances in integrating demand management and vehicle routing: A methodological review," European Journal of Operational Research, Elsevier, vol. 306(2), pages 499-518.
    20. Zolfagharinia, Hossein & Haughton, Michael, 2016. "Effective truckload dispatch decision methods with incomplete advance load information," European Journal of Operational Research, Elsevier, vol. 252(1), pages 103-121.

    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:274:y:2019:i:3:p:909-923. 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.