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

Joint optimization of parcel allocation and crowd routing for crowdsourced last-mile delivery

Author

Listed:
  • Wang, Li
  • Xu, Min
  • Qin, Hu

Abstract

Urban last-mile delivery providers are facing more and more challenges with the explosive development of e-commerce. The advancement of smart mobile and communication technology in recent years has stimulated the development of a new business model of city logistics, referred to as crowdsourced delivery or crowd-shipping. In this paper, we investigate a form of crowdsourced last-mile delivery that utilizes the journeys of commuters/travelers (crowd-couriers) to deliver parcels from intermediate stations to customers. We consider a logistics service provider that jointly optimizes parcel allocation to intermediate stations and the delivery routing of the crowd-couriers. The joint optimization model gives rise to a new variant of the last-mile delivery problem. We propose a data-driven column generation algorithm to solve the problem based on a set-partitioning formulation. Additionally, a rolling-horizon approach is proposed to address large-scale instances. Extensive numerical experiments are conducted to verify the efficiency of our model and solution approach, as well as the significance of the joint optimization of parcel allocation and the delivery route of the crowdsourced last-mile delivery. The results show that our data-driven column generation algorithm can obtain (near-)optimal solutions for up to 200 parcels in significantly less time than the exact algorithm. For larger instances, the combination of the data-driven column generation algorithm and the rolling-horizon approach can obtain good-quality solutions for up to 1000 parcels in 15 min. Moreover, compared with crowd-courier route optimization only, the joint optimization of parcel allocation and crowd-routing reduces the total cost by 32%.

Suggested Citation

  • Wang, Li & Xu, Min & Qin, Hu, 2023. "Joint optimization of parcel allocation and crowd routing for crowdsourced last-mile delivery," Transportation Research Part B: Methodological, Elsevier, vol. 171(C), pages 111-135.
    • Handle: RePEc:eee:transb:v:171:y:2023:i:c:p:111-135
    DOI: 10.1016/j.trb.2023.03.007
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0191261523000504
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.trb.2023.03.007?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. Yu, Vincent F. & Jodiawan, Panca & Redi, A.A.N. Perwira, 2022. "Crowd-shipping problem with time windows, transshipment nodes, and delivery options," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 157(C).
    2. Perboli, Guido & Brotcorne, Luce & Bruni, Maria Elena & Rosano, Mariangela, 2021. "A new model for Last-Mile Delivery and Satellite Depots management: The impact of the on-demand economy," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 145(C).
    3. repec:inm:orijoo:v:4:y:2022:i:3:p:278-303 is not listed on IDEAS
    4. 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.
    5. Carlos F. Daganzo, 2005. "Logistics Systems Analysis," Springer Books, Springer, edition 0, number 978-3-540-27516-9, December.
    6. Ahamed, Tanvir & Zou, Bo & Farazi, Nahid Parvez & Tulabandhula, Theja, 2021. "Deep Reinforcement Learning for Crowdsourced Urban Delivery," Transportation Research Part B: Methodological, Elsevier, vol. 152(C), pages 227-257.
    7. Wang, Yuan & Zhang, Dongxiang & Liu, Qing & Shen, Fumin & Lee, Loo Hay, 2016. "Towards enhancing the last-mile delivery: An effective crowd-tasking model with scalable solutions," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 93(C), pages 279-293.
    8. Behrend, Moritz & Meisel, Frank, 2018. "The integration of item-sharing and crowdshipping: Can collaborative consumption be pushed by delivering through the crowd?," Transportation Research Part B: Methodological, Elsevier, vol. 111(C), pages 227-243.
    9. Nieto-Isaza, Santiago & Fontaine, Pirmin & Minner, Stefan, 2022. "The value of stochastic crowd resources and strategic location of mini-depots for last-mile delivery: A Benders decomposition approach," Transportation Research Part B: Methodological, Elsevier, vol. 157(C), pages 62-79.
    10. Alnaggar, Aliaa & Gzara, Fatma & Bookbinder, James H., 2021. "Crowdsourced delivery: A review of platforms and academic literature," Omega, Elsevier, vol. 98(C).
    11. Wenyi Chen & Martijn Mes & Marco Schutten, 2018. "Multi-hop driver-parcel matching problem with time windows," Flexible Services and Manufacturing Journal, Springer, vol. 30(3), pages 517-553, September.
    12. Çavdar, Bahar & Sokol, Joel, 2015. "A distribution-free TSP tour length estimation model for random graphs," European Journal of Operational Research, Elsevier, vol. 243(2), pages 588-598.
    13. Mancini, Simona & Gansterer, Margaretha, 2022. "Bundle generation for last-mile delivery with occasional drivers," Omega, Elsevier, vol. 108(C).
    14. Max Shen, Zuo-Jun & Qi, Lian, 2007. "Incorporating inventory and routing costs in strategic location models," European Journal of Operational Research, Elsevier, vol. 179(2), pages 372-389, June.
    15. 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.
    16. Iman Dayarian & Martin Savelsbergh, 2020. "Crowdshipping and Same‐day Delivery: Employing In‐store Customers to Deliver Online Orders," Production and Operations Management, Production and Operations Management Society, vol. 29(9), pages 2153-2174, September.
    17. Kafle, Nabin & Zou, Bo & Lin, Jane, 2017. "Design and modeling of a crowdsource-enabled system for urban parcel relay and delivery," Transportation Research Part B: Methodological, Elsevier, vol. 99(C), pages 62-82.
    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. Xiao, Haohan & Xu, Min & Wang, Shuaian, 2023. "A game-theoretic model for crowd-shipping operations with profit improvement strategies," International Journal of Production Economics, Elsevier, vol. 262(C).
    2. Eskandarzadeh, Saman & Fahimnia, Behnam, 2024. "Containerised parcel delivery: Modelling and performance evaluation," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 186(C).
    3. Xiao, Haohan & Xu, Min & Wang, Shuaian, 2023. "Crowd-shipping as a Service: Game-based operating strategy design and analysis," Transportation Research Part B: Methodological, Elsevier, vol. 176(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. Ausseil, Rosemonde & Ulmer, Marlin W. & Pazour, Jennifer A., 2024. "Online acceptance probability approximation in peer-to-peer transportation," Omega, Elsevier, vol. 123(C).
    2. 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.
    3. 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.
    4. Behrend, Moritz & Meisel, Frank & Fagerholt, Kjetil & Andersson, Henrik, 2021. "A multi-period analysis of the integrated item-sharing and crowdshipping problem," European Journal of Operational Research, Elsevier, vol. 292(2), pages 483-499.
    5. 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.
    6. Mancini, Simona & Gansterer, Margaretha, 2022. "Bundle generation for last-mile delivery with occasional drivers," Omega, Elsevier, vol. 108(C).
    7. Behrend, Moritz & Meisel, Frank & Fagerholt, Kjetil & Andersson, Henrik, 2019. "An exact solution method for the capacitated item-sharing and crowdshipping problem," European Journal of Operational Research, Elsevier, vol. 279(2), pages 589-604.
    8. 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.
    9. 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.
    10. Marlin Ulmer & Martin Savelsbergh, 2020. "Workforce Scheduling in the Era of Crowdsourced Delivery," Transportation Science, INFORMS, vol. 54(4), pages 1113-1133, July.
    11. Alnaggar, Aliaa & Gzara, Fatma & Bookbinder, James H., 2024. "Compensation guarantees in crowdsourced delivery: Impact on platform and driver welfare," Omega, Elsevier, vol. 122(C).
    12. Wang, Haibo & Alidaee, Bahram, 2023. "White-glove service delivery: A quantitative analysis," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 175(C).
    13. Ghaderi, Hadi & Zhang, Lele & Tsai, Pei-Wei & Woo, Jihoon, 2022. "Crowdsourced last-mile delivery with parcel lockers," International Journal of Production Economics, Elsevier, vol. 251(C).
    14. Di Puglia Pugliese, Luigi & Ferone, Daniele & Macrina, Giusy & Festa, Paola & Guerriero, Francesca, 2023. "The crowd-shipping with penalty cost function and uncertain travel times," Omega, Elsevier, vol. 115(C).
    15. Alireza Ermagun & Ali Shamshiripour & Amanda Stathopoulos, 2020. "Performance analysis of crowd-shipping in urban and suburban areas," Transportation, Springer, vol. 47(4), pages 1955-1985, August.
    16. Ermagun, Alireza & Stathopoulos, Amanda, 2018. "To bid or not to bid: An empirical study of the supply determinants of crowd-shipping," Transportation Research Part A: Policy and Practice, Elsevier, vol. 116(C), pages 468-483.
    17. Zhang, Jian & Woensel, Tom Van, 2023. "Dynamic vehicle routing with random requests: A literature review," International Journal of Production Economics, Elsevier, vol. 256(C).
    18. Pourrahmani, Elham & Jaller, Miguel, 2021. "Crowdshipping in last mile deliveries: Operational challenges and research opportunities," Socio-Economic Planning Sciences, Elsevier, vol. 78(C).
    19. Azcuy, Irecis & Agatz, Niels & Giesen, Ricardo, 2021. "Designing integrated urban delivery systems using public transport," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 156(C).
    20. Shen, Hui & Lin, Jane, 2020. "Investigation of crowdshipping delivery trip production with real-world data," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 143(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:171:y:2023:i:c:p:111-135. 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.