IDEAS home Printed from https://ideas.repec.org/a/spr/flsman/v36y2024i4d10.1007_s10696-023-09529-3.html
   My bibliography  Save this article

Bundle generation for the vehicle routing problem with occasional drivers and time windows

Author

Listed:
  • Simona Mancini

    (University of Palermo
    University of Klagenfurt)

  • Margaretha Gansterer

    (University of Klagenfurt)

Abstract

In this paper, we address the vehicle routing problem (VRP) with occasional drivers (ODs) and time windows (TWs). The problem (VRP-OD-TW) is an extension of the VRP-OD, where ODs serve customers within given TWs. Differently from the basic version of VRP-OD-TW, we assume that ODs not only accept single requests, but they can also serve bundles of requests. To deal with the bundle-to-driver assignment problem, an auction-based system has been designed; a company offers a set of bundles to the ODs, who bid for all the bundles they consider attractive. There is no limit on the number of bids a driver can place, but at most one bid per OD can be assigned to avoid infeasible workloads. This system could yield a large cost reduction for the company, but its success is strongly related to the bundles offered. Hence, determining bundles which are attractive for ODs and profitable for the company, becomes a crucial issue. We propose two different bundling strategies, which make use of a spatial-temporal representation of customers in a three-dimensional (3D) space. The former is based on the generation of 3D corridors, while the latter relies on 3D clustering techniques. Through extensive computational results, we show that the former technique outperforms the latter in terms of both solution quality and computational times and that both the approaches strongly outperform bundle generation techniques that neglect the temporal dimension and rely only on spatial information.

Suggested Citation

  • Simona Mancini & Margaretha Gansterer, 2024. "Bundle generation for the vehicle routing problem with occasional drivers and time windows," Flexible Services and Manufacturing Journal, Springer, vol. 36(4), pages 1189-1221, December.
    • Handle: RePEc:spr:flsman:v:36:y:2024:i:4:d:10.1007_s10696-023-09529-3
    DOI: 10.1007/s10696-023-09529-3
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10696-023-09529-3
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10696-023-09529-3?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. Tho V. Le & Satish V. Ukkusuri, 2019. "Influencing factors that determine the usage of the crowd-shipping services," Papers 1902.08681, arXiv.org.
    2. Michele D. Simoni & Edoardo Marcucci & Valerio Gatta & Christian G. Claudel, 2020. "Potential last-mile impacts of crowdshipping services: a simulation-based evaluation," Transportation, Springer, vol. 47(4), pages 1933-1954, August.
    3. Englmaier, Florian & Guillén, Pablo & Llorente, Loreto & Onderstal, Sander & Sausgruber, Rupert, 2009. "The chopstick auction: A study of the exposure problem in multi-unit auctions," International Journal of Industrial Organization, Elsevier, vol. 27(2), pages 286-291, March.
    4. Gansterer, Margaretha & Hartl, Richard F., 2018. "Collaborative vehicle routing: A survey," European Journal of Operational Research, Elsevier, vol. 268(1), pages 1-12.
    5. Triki, Chefi & Oprea, Simona & Beraldi, Patriza & Crainic, Teodor Gabriel, 2014. "The stochastic bid generation problem in combinatorial transportation auctions," European Journal of Operational Research, Elsevier, vol. 236(3), pages 991-999.
    6. 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.
    7. Margaretha Gansterer & Richard F. Hartl, 2018. "Centralized bundle generation in auction-based collaborative transportation," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 40(3), pages 613-635, July.
    8. Tobias Buer & Rasmus Haass, 2018. "Cooperative liner shipping network design by means of a combinatorial auction," Flexible Services and Manufacturing Journal, Springer, vol. 30(4), pages 686-711, December.
    9. Mancini, Simona & Gansterer, Margaretha, 2022. "Bundle generation for last-mile delivery with occasional drivers," Omega, Elsevier, vol. 108(C).
    10. Xiao Lin & Yoshinari Nishiki & Lóránt A. Tavasszy, 2020. "Performance and Intrusiveness of Crowdshipping Systems: An Experiment with Commuting Cyclists in The Netherlands," Sustainability, MDPI, vol. 12(17), pages 1-14, September.
    11. 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.
    12. Valerio Gatta & Edoardo Marcucci & Marialisa Nigro & Sergio Maria Patella & Simone Serafini, 2018. "Public Transport-Based Crowdshipping for Sustainable City Logistics: Assessing Economic and Environmental Impacts," Sustainability, MDPI, vol. 11(1), pages 1-14, December.
    13. Margaretha Gansterer & Richard F. Hartl, 2016. "Request evaluation strategies for carriers in auction-based collaborations," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 38(1), pages 3-23, January.
    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. Berger, Susanne & Bierwirth, Christian, 2010. "Solutions to the request reassignment problem in collaborative carrier networks," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 46(5), pages 627-638, September.
    16. 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)

    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. Mancini, Simona & Gansterer, Margaretha, 2022. "Bundle generation for last-mile delivery with occasional drivers," Omega, Elsevier, vol. 108(C).
    2. Gansterer, Margaretha & Hartl, Richard F. & Sörensen, Kenneth, 2020. "Pushing frontiers in auction-based transport collaborations," Omega, Elsevier, vol. 94(C).
    3. Margaretha Gansterer & Richard F. Hartl & Sarah Wieser, 2021. "Assignment constraints in shared transportation services," Annals of Operations Research, Springer, vol. 305(1), pages 513-539, October.
    4. 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.
    5. Lafkihi, Mariam & Pan, Shenle & Ballot, Eric, 2019. "Freight transportation service procurement: A literature review and future research opportunities in omnichannel E-commerce," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 125(C), pages 348-365.
    6. Tapia, Rodrigo J. & Kourounioti, Ioanna & Thoen, Sebastian & de Bok, Michiel & Tavasszy, Lori, 2023. "A disaggregate model of passenger-freight matching in crowdshipping services," Transportation Research Part A: Policy and Practice, Elsevier, vol. 169(C).
    7. Scherr, Yannick Oskar & Gansterer, Margaretha & Hartl, Richard F., 2024. "Request acceptance with overbooking in dynamic and collaborative vehicle routing," European Journal of Operational Research, Elsevier, vol. 314(2), pages 612-629.
    8. 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).
    9. Gansterer, Margaretha & Hartl, Richard F. & Savelsbergh, Martin, 2020. "The value of information in auction-based carrier collaborations," International Journal of Production Economics, Elsevier, vol. 221(C).
    10. Zhang, Zhuoye & Zhang, Fangni, 2024. "Optimal operation strategies of an urban crowdshipping platform in asset-light, asset-medium, or asset-heavy business format," Transportation Research Part B: Methodological, Elsevier, vol. 189(C).
    11. Hammami, Farouk & Rekik, Monia & Coelho, Leandro C., 2019. "Exact and heuristic solution approaches for the bid construction problem in transportation procurement auctions with a heterogeneous fleet," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 127(C), pages 150-177.
    12. 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).
    13. Rossolov, Oleksandr & Susilo, Yusak O., 2024. "Are consumers ready to pay extra for crowd-shipping e-groceries and why? A hybrid choice analysis for developing economies," Transportation Research Part A: Policy and Practice, Elsevier, vol. 187(C).
    14. 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).
    15. Mancini, Simona & Gansterer, Margaretha & Hartl, Richard F., 2021. "The collaborative consistent vehicle routing problem with workload balance," European Journal of Operational Research, Elsevier, vol. 293(3), pages 955-965.
    16. Stokkink, Patrick & Cordeau, Jean-François & Geroliminis, Nikolas, 2024. "A column and row generation approach to the crowd-shipping problem with transfers," Omega, Elsevier, vol. 128(C).
    17. 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.
    18. Martin Savelsbergh & Marlin W. Ulmer, 2024. "Challenges and opportunities in crowdsourced delivery planning and operations—an update," Annals of Operations Research, Springer, vol. 343(2), pages 639-661, December.
    19. 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.
    20. Mario Binetti & Leonardo Caggiani & Rosalia Camporeale & Michele Ottomanelli, 2019. "A Sustainable Crowdsourced Delivery System to Foster Free-Floating Bike-Sharing," Sustainability, MDPI, vol. 11(10), pages 1-24, May.

    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:spr:flsman:v:36:y:2024:i:4:d:10.1007_s10696-023-09529-3. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.