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

A Generalized Bin Packing Problem for parcel delivery in last-mile logistics

Author

Listed:
  • Baldi, Mauro Maria
  • Manerba, Daniele
  • Perboli, Guido
  • Tadei, Roberto

Abstract

In this paper, we present a new problem arising at a tactical level of setting a last-mile parcel delivery service in a city by considering different Transportation Companies (TC), which differ in cost and service quality. The courier must decide which TCs to select for the service in order to minimize the total cost and maximize the total service quality. We show that the problem can be modeled as a new packing problem, the Generalized Bin Packing Problem with bin-dependent item profits (GBPPI), where the items are the parcels to deliver and the bins are the TCs. The aim of the GBPPI is to select the appropriate fleet from TCs and determine the optimal assignment of parcels to vehicles such that the overall net cost is minimized. This cost takes into account both transportation costs and service quality. We provide a Mixed Integer Programming formulation of the problem, which is the starting point for the development of efficient heuristics that can address the GBPPI for instances involving up to 1000 items. Extensive computational tests show the accuracy of the proposed methods. Finally, we present a last-mile logistics case study of an international courier which addresses this problem.

Suggested Citation

  • Baldi, Mauro Maria & Manerba, Daniele & Perboli, Guido & Tadei, Roberto, 2019. "A Generalized Bin Packing Problem for parcel delivery in last-mile logistics," European Journal of Operational Research, Elsevier, vol. 274(3), pages 990-999.
    • Handle: RePEc:eee:ejores:v:274:y:2019:i:3:p:990-999
    DOI: 10.1016/j.ejor.2018.10.056
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S037722171830924X
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2018.10.056?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. Manerba, Daniele & Mansini, Renata & Riera-Ledesma, Jorge, 2017. "The Traveling Purchaser Problem and its variants," European Journal of Operational Research, Elsevier, vol. 259(1), pages 1-18.
    2. Perboli, Guido & Tadei, Roberto & Gobbato, Luca, 2014. "The Multi-Handler Knapsack Problem under Uncertainty," European Journal of Operational Research, Elsevier, vol. 236(3), pages 1000-1007.
    3. Crainic, Teodor Gabriel & Perboli, Guido & Pezzuto, Miriam & Tadei, Roberto, 2007. "Computing the asymptotic worst-case of bin packing lower bounds," European Journal of Operational Research, Elsevier, vol. 183(3), pages 1295-1303, December.
    4. Crainic, Teodor Gabriel & Gobbato, Luca & Perboli, Guido & Rei, Walter, 2016. "Logistics capacity planning: A stochastic bin packing formulation and a progressive hedging meta-heuristic," European Journal of Operational Research, Elsevier, vol. 253(2), pages 404-417.
    5. Holzapfel, Andreas & Kuhn, Heinrich & Sternbeck, Michael G., 2018. "Product allocation to different types of distribution center in retail logistics networks," European Journal of Operational Research, Elsevier, vol. 264(3), pages 948-966.
    6. Mohamed Maiza & Abdenour Labed & Mohammed Radjef, 2013. "Efficient algorithms for the offline variable sized bin-packing problem," Journal of Global Optimization, Springer, vol. 57(3), pages 1025-1038, November.
    7. Boysen, Nils & Schwerdfeger, Stefan & Weidinger, Felix, 2018. "Scheduling last-mile deliveries with truck-based autonomous robots," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 126189, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    8. Ülkü, M. Ali & Bookbinder, James H., 2012. "Optimal quoting of delivery time by a third party logistics provider: The impact of shipment consolidation and temporal pricing schemes," European Journal of Operational Research, Elsevier, vol. 221(1), pages 110-117.
    9. Mauro Baldi & Teodor Crainic & Guido Perboli & Roberto Tadei, 2014. "Branch-and-price and beam search algorithms for the Variable Cost and Size Bin Packing Problem with optional items," Annals of Operations Research, Springer, vol. 222(1), pages 125-141, November.
    10. Luigi Ranieri & Salvatore Digiesi & Bartolomeo Silvestri & Michele Roccotelli, 2018. "A Review of Last Mile Logistics Innovations in an Externalities Cost Reduction Vision," Sustainability, MDPI, vol. 10(3), pages 1-18, March.
    11. Boysen, Nils & Schwerdfeger, Stefan & Weidinger, Felix, 2018. "Scheduling last-mile deliveries with truck-based autonomous robots," European Journal of Operational Research, Elsevier, vol. 271(3), pages 1085-1099.
    12. Zhou, Lin & Baldacci, Roberto & Vigo, Daniele & Wang, Xu, 2018. "A Multi-Depot Two-Echelon Vehicle Routing Problem with Delivery Options Arising in the Last Mile Distribution," European Journal of Operational Research, Elsevier, vol. 265(2), pages 765-778.
    13. Baldi, Mauro Maria & Crainic, Teodor Gabriel & Perboli, Guido & Tadei, Roberto, 2012. "The generalized bin packing problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 48(6), pages 1205-1220.
    14. Teodor Gabriel Crainic & Guido Perboli & Roberto Tadei, 2008. "Extreme Point-Based Heuristics for Three-Dimensional Bin Packing," INFORMS Journal on Computing, INFORMS, vol. 20(3), pages 368-384, August.
    15. Vakulenko, Yulia & Hellström, Daniel & Hjort, Klas, 2018. "What's in the parcel locker? Exploring customer value in e-commerce last mile delivery," Journal of Business Research, Elsevier, vol. 88(C), pages 421-427.
    16. 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.
    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. Yulle G. F. Borges & Vinícius L. Lima & Flávio K. Miyazawa & Lehilton L. C. Pedrosa & Thiago A. Queiroz & Rafael C. S. Schouery, 2024. "Algorithms for the bin packing problem with scenarios," Journal of Combinatorial Optimization, Springer, vol. 48(4), pages 1-28, November.
    2. Yingying Wang & Feng Xu & Zhe Lin & Jianying Guo & Gang Li, 2024. "Community Group Purchasing of Next-Day Delivery: Bridging the Last Mile Delivery for Urban Residents during COVID-19," Sustainability, MDPI, vol. 16(16), pages 1-20, August.
    3. Mohamed Amr Sultan & Tomaž Kramberger & Mahmoud Barakat & Ahmed Hussein Ali, 2023. "Barriers to Applying Last-Mile Logistics in the Egyptian Market: An Extension of the Technology Acceptance Model," Sustainability, MDPI, vol. 15(17), pages 1-25, August.
    4. Borja Ena & Alberto Gomez & Borja Ponte & Paolo Priore & Diego Diaz, 2022. "Homogeneous grouping of non-prime steel products for online auctions: a case study," Annals of Operations Research, Springer, vol. 315(1), pages 591-621, August.
    5. Farahani, Amirreza & Genga, Laura & Schrotenboer, Albert H. & Dijkman, Remco, 2024. "Capacity planning in logistics corridors: Deep reinforcement learning for the dynamic stochastic temporal bin packing problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 191(C).
    6. Epstein, Leah, 2024. "Tighter bounds for the harmonic bin packing algorithm," European Journal of Operational Research, Elsevier, vol. 316(1), pages 72-84.
    7. Maria Björklund & Niklas Simm, 2019. "Roles and Perspectives When Estimating Energy and Environmental Potentials of Urban Consolidation," Energies, MDPI, vol. 12(24), pages 1-17, December.
    8. 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).
    9. John Olsson & Daniel Hellström & Henrik Pålsson, 2019. "Framework of Last Mile Logistics Research: A Systematic Review of the Literature," Sustainability, MDPI, vol. 11(24), pages 1-25, December.
    10. Wang, Jianxin & Lim, Ming K. & Zhan, Yuanzhu & Wang, XiaoFeng, 2020. "An intelligent logistics service system for enhancing dispatching operations in an IoT environment," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 135(C).
    11. Rohit Kumar Singh & Sachin Modgil & Padmanav Acharya, 2019. "Assessment of Supply Chain Flexibility Using System Dynamics Modeling," Global Journal of Flexible Systems Management, Springer;Global Institute of Flexible Systems Management, vol. 20(1), pages 39-63, December.
    12. Wu, Haotian & Savelsbergh, Martin & Huang, Yixiao, 2022. "Planning the city operations of a parcel express company," Omega, Elsevier, vol. 107(C).
    13. Jiu, Song & Wang, Dan & Ma, Zujun, 2024. "Benders decomposition for robust distribution network design and operations in online retailing," European Journal of Operational Research, Elsevier, vol. 315(3), pages 1069-1082.
    14. Khir, Reem & Erera, Alan & Toriello, Alejandro, 2023. "Robust planning of sorting operations in express delivery systems," European Journal of Operational Research, Elsevier, vol. 306(2), pages 615-631.
    15. Riccardo Giusti & Chiara Iorfida & Yuanyuan Li & Daniele Manerba & Stefano Musso & Guido Perboli & Roberto Tadei & Shuai Yuan, 2019. "Sustainable and De-Stressed International Supply-Chains Through the SYNCHRO-NET Approach," Sustainability, MDPI, vol. 11(4), pages 1-26, February.
    16. Sakshi Aggarwal & Deepti Aggrawal, 2024. "Performance Evaluation of Sustainable Downstream Logistics: a Hybrid Multi Criteria Decision Making Framework," SN Operations Research Forum, Springer, vol. 5(4), pages 1-34, December.
    17. Sergio Maria Patella & Gianluca Grazieschi & Valerio Gatta & Edoardo Marcucci & Stefano Carrese, 2020. "The Adoption of Green Vehicles in Last Mile Logistics: A Systematic Review," Sustainability, MDPI, vol. 13(1), pages 1-29, December.

    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. John Olsson & Daniel Hellström & Henrik Pålsson, 2019. "Framework of Last Mile Logistics Research: A Systematic Review of the Literature," Sustainability, MDPI, vol. 11(24), pages 1-25, December.
    2. Wang, Xin & Huang, George Q., 2021. "When and how to share first-mile parcel collection service," European Journal of Operational Research, Elsevier, vol. 288(1), pages 153-169.
    3. Wanjie Hu & Jianjun Dong & Bon-gang Hwang & Rui Ren & Zhilong Chen, 2019. "A Scientometrics Review on City Logistics Literature: Research Trends, Advanced Theory and Practice," Sustainability, MDPI, vol. 11(10), pages 1-27, May.
    4. Sergio Maria Patella & Gianluca Grazieschi & Valerio Gatta & Edoardo Marcucci & Stefano Carrese, 2020. "The Adoption of Green Vehicles in Last Mile Logistics: A Systematic Review," Sustainability, MDPI, vol. 13(1), pages 1-29, December.
    5. Mishra, Sabyasachee & Sharma, Ishant & Pani, Agnivesh, 2023. "Analyzing autonomous delivery acceptance in food deserts based on shopping travel patterns," Transportation Research Part A: Policy and Practice, Elsevier, vol. 169(C).
    6. Dumez, Dorian & Lehuédé, Fabien & Péton, Olivier, 2021. "A large neighborhood search approach to the vehicle routing problem with delivery options," Transportation Research Part B: Methodological, Elsevier, vol. 144(C), pages 103-132.
    7. Alfandari, Laurent & Ljubić, Ivana & De Melo da Silva, Marcos, 2022. "A tailored Benders decomposition approach for last-mile delivery with autonomous robots," European Journal of Operational Research, Elsevier, vol. 299(2), pages 510-525.
    8. Schwerdfeger, Stefan & Boysen, Nils, 2020. "Optimizing the changing locations of mobile parcel lockers in last-mile distribution," European Journal of Operational Research, Elsevier, vol. 285(3), pages 1077-1094.
    9. Lemardelé, Clément & Estrada, Miquel & Pagès, Laia & Bachofner, Mónika, 2021. "Potentialities of drones and ground autonomous delivery devices for last-mile logistics," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 149(C).
    10. Fernanda Alves de Araújo & João Gilberto Mendes dos Reis & Marcia Terra da Silva & Emel Aktas, 2022. "A Fuzzy Analytic Hierarchy Process Model to Evaluate Logistics Service Expectations and Delivery Methods in Last-Mile Delivery in Brazil," Sustainability, MDPI, vol. 14(10), pages 1-18, May.
    11. Giulio Mangano & Giovanni Zenezini & Anna Corinna Cagliano, 2021. "Value Proposition for Sustainable Last-Mile Delivery. A Retailer Perspective," Sustainability, MDPI, vol. 13(7), pages 1-15, March.
    12. Farahani, Amirreza & Genga, Laura & Schrotenboer, Albert H. & Dijkman, Remco, 2024. "Capacity planning in logistics corridors: Deep reinforcement learning for the dynamic stochastic temporal bin packing problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 191(C).
    13. Roohnavazfar, Mina & Manerba, Daniele & De Martin, Juan Carlos & Tadei, Roberto, 2019. "Optimal paths in multi-stage stochastic decision networks," Operations Research Perspectives, Elsevier, vol. 6(C).
    14. 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.
    15. Manerba, Daniele & Mansini, Renata & Perboli, Guido, 2018. "The Capacitated Supplier Selection problem with Total Quantity Discount policy and Activation Costs under uncertainty," International Journal of Production Economics, Elsevier, vol. 198(C), pages 119-132.
    16. Zhang, Yuankai & Sun, Lijun & Hu, Xiangpei & Zhao, Chen, 2019. "Order consolidation for the last-mile split delivery in online retailing," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 122(C), pages 309-327.
    17. Marta Viu-Roig & Eduard J. Alvarez-Palau, 2020. "The Impact of E-Commerce-Related Last-Mile Logistics on Cities: A Systematic Literature Review," Sustainability, MDPI, vol. 12(16), pages 1-19, August.
    18. Lin, Yun Hui & Wang, Yuan & He, Dongdong & Lee, Loo Hay, 2020. "Last-mile delivery: Optimal locker location under multinomial logit choice model," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 142(C).
    19. Jacek Buko & Marek Bulsa & Adam Makowski, 2022. "Spatial Premises and Key Conditions for the Use of UAVs for Delivery of Items on the Example of the Polish Courier and Postal Services Market," Energies, MDPI, vol. 15(4), pages 1-17, February.
    20. Srinivas, Sharan & Ramachandiran, Surya & Rajendran, Suchithra, 2022. "Autonomous robot-driven deliveries: A review of recent developments and future directions," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 165(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:ejores:v:274:y:2019:i:3:p:990-999. 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.