IDEAS home Printed from https://ideas.repec.org/a/eee/transb/v187y2024ics0191261524001516.html
   My bibliography  Save this article

Approximate dynamic programming for pickup and delivery problem with crowd-shipping

Author

Listed:
  • Mousavi, Kianoush
  • Bodur, Merve
  • Cevik, Mucahit
  • Roorda, Matthew J.

Abstract

We study a variant of dynamic pickup and delivery crowd-shipping operation for delivering online orders within a few hours from a brick-and-mortar store. This crowd-shipping operation is subject to a high degree of uncertainty due to the stochastic arrival of online orders and crowd-shippers that impose several challenges for efficient matching of orders to crowd-shippers. We formulate the problem as a Markov decision process and develop an Approximate Dynamic Programming (ADP) policy using value function approximation for obtaining a highly scalable and real-time matching strategy while considering temporal and spatial uncertainty in arrivals of online orders and crowd-shippers. We incorporate several algorithmic enhancements to the ADP algorithm, which significantly improve the convergence. We compare the ADP policy with an optimization-based myopic policy using various performance measures. Our numerical analysis with varying parameter settings shows that ADP policies can lead to up to 25.2% cost savings and a 9.8% increase in the number of served orders. Overall, we find that our proposed framework can guide crowd-shipping platforms for efficient real-time matching decisions and enhance the platform delivery capacity.

Suggested Citation

  • Mousavi, Kianoush & Bodur, Merve & Cevik, Mucahit & Roorda, Matthew J., 2024. "Approximate dynamic programming for pickup and delivery problem with crowd-shipping," Transportation Research Part B: Methodological, Elsevier, vol. 187(C).
    • Handle: RePEc:eee:transb:v:187:y:2024:i:c:s0191261524001516
    DOI: 10.1016/j.trb.2024.103027
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0191261524001516
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.trb.2024.103027?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. Hugo P. Simão & Jeff Day & Abraham P. George & Ted Gifford & John Nienow & Warren B. Powell, 2009. "An Approximate Dynamic Programming Algorithm for Large-Scale Fleet Management: A Case Application," Transportation Science, INFORMS, vol. 43(2), pages 178-197, May.
    2. Stacy A. Voccia & Ann Melissa Campbell & Barrett W. Thomas, 2019. "The Same-Day Delivery Problem for Online Purchases," Service Science, INFORMS, vol. 53(1), pages 167-184, February.
    3. Baris Yildiz & Martin Savelsbergh, 2019. "Provably High-Quality Solutions for the Meal Delivery Routing Problem," Transportation Science, INFORMS, vol. 53(5), pages 1372-1388, September.
    4. Alnaggar, Aliaa & Gzara, Fatma & Bookbinder, James H., 2021. "Crowdsourced delivery: A review of platforms and academic literature," Omega, Elsevier, vol. 98(C).
    5. Cleophas, Catherine & Cottrill, Caitlin & Ehmke, Jan Fabian & Tierney, Kevin, 2019. "Collaborative urban transportation: Recent advances in theory and practice," European Journal of Operational Research, Elsevier, vol. 273(3), pages 801-816.
    6. Al-Kanj, Lina & Nascimento, Juliana & Powell, Warren B., 2020. "Approximate dynamic programming for planning a ride-hailing system using autonomous fleets of electric vehicles," European Journal of Operational Research, Elsevier, vol. 284(3), pages 1088-1106.
    7. Iman Dayarian & Martin Savelsbergh & John-Paul Clarke, 2020. "Same-Day Delivery with Drone Resupply," Transportation Science, INFORMS, vol. 54(1), pages 229-249, January.
    8. Boysen, Nils & Emde, Simon & Schwerdfeger, Stefan, 2022. "Crowdshipping by employees of distribution centers: Optimization approaches for matching supply and demand," European Journal of Operational Research, Elsevier, vol. 296(2), pages 539-556.
    9. Allahviranloo, Mahdieh & Baghestani, Amirhossein, 2019. "A dynamic crowdshipping model and daily travel behavior," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 128(C), pages 175-190.
    10. Michael Z. Spivey & Warren B. Powell, 2004. "The Dynamic Assignment Problem," Transportation Science, INFORMS, vol. 38(4), pages 399-419, November.
    11. Marlin Ulmer & Martin Savelsbergh, 2020. "Workforce Scheduling in the Era of Crowdsourced Delivery," Transportation Science, INFORMS, vol. 54(4), pages 1113-1133, July.
    12. Marlin W. Ulmer & Barrett W. Thomas & Ann Melissa Campbell & Nicholas Woyak, 2021. "The Restaurant Meal Delivery Problem: Dynamic Pickup and Delivery with Deadlines and Random Ready Times," Transportation Science, INFORMS, vol. 55(1), pages 75-100, 1-2.
    13. Nabila Azi & Michel Gendreau & Jean-Yves Potvin, 2012. "A dynamic vehicle routing problem with multiple delivery routes," Annals of Operations Research, Springer, vol. 199(1), pages 103-112, October.
    14. Archetti, Claudia & Savelsbergh, Martin & Speranza, M. Grazia, 2016. "The Vehicle Routing Problem with Occasional Drivers," European Journal of Operational Research, Elsevier, vol. 254(2), pages 472-480.
    15. 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.
    16. Daniel R. Jiang & Warren B. Powell, 2015. "An Approximate Dynamic Programming Algorithm for Monotone Value Functions," Operations Research, INFORMS, vol. 63(6), pages 1489-1511, December.
    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. 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. 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.
    3. 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.
    4. 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.
    5. Bosse, Alexander & Ulmer, Marlin W. & Manni, Emanuele & Mattfeld, Dirk C., 2023. "Dynamic priority rules for combining on-demand passenger transportation and transportation of goods," European Journal of Operational Research, Elsevier, vol. 309(1), pages 399-408.
    6. Alnaggar, Aliaa & Gzara, Fatma & Bookbinder, James H., 2024. "Compensation guarantees in crowdsourced delivery: Impact on platform and driver welfare," Omega, Elsevier, vol. 122(C).
    7. Mancini, Simona & Gansterer, Margaretha, 2022. "Bundle generation for last-mile delivery with occasional drivers," Omega, Elsevier, vol. 108(C).
    8. Martin W.P Savelsbergh & Marlin W. Ulmer, 2022. "Challenges and opportunities in crowdsourced delivery planning and operations," 4OR, Springer, vol. 20(1), pages 1-21, March.
    9. Chen, Xinwei & Wang, Tong & Thomas, Barrett W. & Ulmer, Marlin W., 2023. "Same-day delivery with fair customer service," European Journal of Operational Research, Elsevier, vol. 308(2), pages 738-751.
    10. Ausseil, Rosemonde & Ulmer, Marlin W. & Pazour, Jennifer A., 2024. "Online acceptance probability approximation in peer-to-peer transportation," Omega, Elsevier, vol. 123(C).
    11. Yang, Dingtong & Hyland, Michael F. & Jayakrishnan, R., 2024. "Tackling the crowdsourced shared-trip delivery problem at scale with a novel decomposition heuristic," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 188(C).
    12. Nils Boysen & Stefan Fedtke & Stefan Schwerdfeger, 2021. "Last-mile delivery concepts: a survey from an operational research perspective," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 43(1), pages 1-58, March.
    13. 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).
    14. Zehtabian, Shohre & Larsen, Christian & Wøhlk, Sanne, 2022. "Estimation of the arrival time of deliveries by occasional drivers in a crowd-shipping setting," European Journal of Operational Research, Elsevier, vol. 303(2), pages 616-632.
    15. Mohri, Seyed Sina & Nassir, Neema & Thompson, Russell G. & Lavieri, Patricia Sauri, 2024. "Public transportation-based crowd-shipping initiatives: Are users willing to participate? Why not?," Transportation Research Part A: Policy and Practice, Elsevier, vol. 182(C).
    16. Boysen, Nils & Emde, Simon & Schwerdfeger, Stefan, 2022. "Crowdshipping by employees of distribution centers: Optimization approaches for matching supply and demand," European Journal of Operational Research, Elsevier, vol. 296(2), pages 539-556.
    17. Banerjee, Dipayan & Erera, Alan L. & Stroh, Alexander M. & Toriello, Alejandro, 2023. "Who has access to e-commerce and when? Time-varying service regions in same-day delivery," Transportation Research Part B: Methodological, Elsevier, vol. 170(C), pages 148-168.
    18. Baris Yildiz & Martin Savelsbergh, 2019. "Provably High-Quality Solutions for the Meal Delivery Routing Problem," Transportation Science, INFORMS, vol. 53(5), pages 1372-1388, September.
    19. Bathke, Henrik & Hartmann, Evi, 2021. "Accepting a crowdsourced delivery - A choice-based conjoint analysis," Chapters from the Proceedings of the Hamburg International Conference of Logistics (HICL), in: Jahn, Carlos & Kersten, Wolfgang & Ringle, Christian M. (ed.), Adapting to the Future: Maritime and City Logistics in the Context of Digitalization and Sustainability. Proceedings of the Hamburg International Conf, volume 32, pages 65-95, Hamburg University of Technology (TUHH), Institute of Business Logistics and General Management.
    20. Wang, Jianxin & Lim, Ming K. & Liu, Weihua, 2024. "Promoting intelligent IoT-driven logistics through integrating dynamic demand and sustainable logistics operations," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 185(C).

    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:transb:v:187:y:2024:i:c:s0191261524001516. 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/wps/find/journaldescription.cws_home/548/description#description .

    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.