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

Optimizing location-routing and demand allocation in the household waste collection system using a branch-and-price algorithm

Author

Listed:
  • Han, Jialin
  • Zhang, Jiaxiang
  • Guo, Haoyue
  • Zhang, Ning

Abstract

In catering to the rapid development of urbanization and the growing urban population, it is essential to design an efficient and effective household waste collection system for guaranteeing a favorable ecological environment in cities. This paper focuses on a location-routing and demand allocation problem (LRDAP) in the household waste collection system where the household waste is initially allocated and transported to a set of intermediate transfer stations using a category of small garbage vehicles, and subsequently a fleet of large garbage vehicles visits each transfer station and transports the collected household waste to the waste disposal center for harmless treatment. The purpose is to simultaneously determine the location of transfer stations, the demand allocation of household waste collection and the routing plan of garbage vehicles while maximizing the efficiency of household waste collection within the whole system. Then, we formulate the proposed LRDAP into a mixed integer program. To solve our LRDAP, an exact branch-and-price (B&P) algorithm is developed along with several acceleration strategies involving column generation (CG) stabilization and heuristic dynamic programming (DP). Finally, we illustrate the proposed model and solution methodology by dealing with real-world problem instances with respect to household waste collection in China. Computational results are presented that explore the performance of our proposed B&P algorithm, analyze the optimized location-routing and demand allocation plan, discuss the impact of selected parameters, and gain some managerial insights in designing an efficient and effective household waste collection system under different decision-making conditions.

Suggested Citation

  • Han, Jialin & Zhang, Jiaxiang & Guo, Haoyue & Zhang, Ning, 2024. "Optimizing location-routing and demand allocation in the household waste collection system using a branch-and-price algorithm," European Journal of Operational Research, Elsevier, vol. 316(3), pages 958-975.
    • Handle: RePEc:eee:ejores:v:316:y:2024:i:3:p:958-975
    DOI: 10.1016/j.ejor.2024.02.029
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221724001619
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2024.02.029?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. Olawale J. Adeleke & M. Montaz Ali, 2021. "An efficient model for locating solid waste collection sites in urban residential areas," International Journal of Production Research, Taylor & Francis Journals, vol. 59(3), pages 798-812, February.
    2. Mohammad Reihaneh & Ahmed Ghoniem, 2018. "A multi-start optimization-based heuristic for a food bank distribution problem," Journal of the Operational Research Society, Taylor & Francis Journals, vol. 69(5), pages 691-706, May.
    3. Blanco, Víctor & Gázquez, Ricardo & Ponce, Diego & Puerto, Justo, 2023. "A branch-and-price approach for the continuous multifacility monotone ordered median problem," European Journal of Operational Research, Elsevier, vol. 306(1), pages 105-126.
    4. Amine Masmoudi, M. & Coelho, Leandro C. & Demir, Emrah, 2022. "Plug-in hybrid electric refuse vehicle routing problem for waste collection," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 166(C).
    5. Glize, Estèle & Roberti, Roberto & Jozefowiez, Nicolas & Ngueveu, Sandra Ulrich, 2020. "Exact methods for mono-objective and Bi-Objective Multi-Vehicle Covering Tour Problems," European Journal of Operational Research, Elsevier, vol. 283(3), pages 812-824.
    6. Wu, Yuehui & Qureshi, Ali Gul & Yamada, Tadashi, 2022. "Adaptive large neighborhood decomposition search algorithm for multi-allocation hub location routing problem," European Journal of Operational Research, Elsevier, vol. 302(3), pages 1113-1127.
    7. Jose Carlos Molina & Ignacio Eguia & Jesus Racero, 2019. "Reducing pollutant emissions in a waste collection vehicle routing problem using a variable neighborhood tabu search algorithm: a case study," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 27(2), pages 253-287, July.
    8. Ghiani, Gianpaolo & Improta, Gennaro, 2000. "An efficient transformation of the generalized vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 122(1), pages 11-17, April.
    9. Roberto Aringhieri & Maurizio Bruglieri & Federico Malucelli & Maddalena Nonato, 2018. "A Special Vehicle Routing Problem Arising in the Optimization of Waste Disposal: A Real Case," Transportation Science, INFORMS, vol. 52(2), pages 277-299, March.
    10. Sebastian Kraul & Markus Seizinger & Jens O. Brunner, 2023. "Machine Learning–Supported Prediction of Dual Variables for the Cutting Stock Problem with an Application in Stabilized Column Generation," INFORMS Journal on Computing, INFORMS, vol. 35(3), pages 692-709, May.
    11. Arslan, Okan & Kumcu, Gül Çulhan & Kara, Bahar Yetiş & Laporte, Gilbert, 2021. "The location and location-routing problem for the refugee camp network design," Transportation Research Part B: Methodological, Elsevier, vol. 143(C), pages 201-220.
    12. Gschwind, Timo & Irnich, Stefan & Rothenbächer, Ann-Kathrin & Tilk, Christian, 2018. "Bidirectional labeling in column-generation algorithms for pickup-and-delivery problems," European Journal of Operational Research, Elsevier, vol. 266(2), pages 521-530.
    13. Olmez, Omer Berk & Gultekin, Ceren & Balcik, Burcu & Ekici, Ali & Özener, Okan Örsan, 2022. "A variable neighborhood search based matheuristic for a waste cooking oil collection network design problem," European Journal of Operational Research, Elsevier, vol. 302(1), pages 187-202.
    14. H. Neil Geismar & Yiwei Huang & Suresh D. Pillai & Chelliah Sriskandarajah & Seokjun Youn, 2020. "Location‐Routing with Conflicting Objectives: Coordinating eBeam Phytosanitary Treatment and Distribution of Mexican Import Commodities," Production and Operations Management, Production and Operations Management Society, vol. 29(6), pages 1506-1531, June.
    15. A Ghoniem & C R Scherrer & S Solak, 2013. "A specialized column generation approach for a vehicle routing problem with demand allocation," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 64(1), pages 114-124, January.
    16. Benjamin Biesinger & Bin Hu & Günther R. Raidl, 2018. "A Genetic Algorithm in Combination with a Solution Archive for Solving the Generalized Vehicle Routing Problem with Stochastic Demands," Transportation Science, INFORMS, vol. 52(3), pages 673-690, June.
    17. Leonardo Lozano & Daniel Duque & Andrés L. Medaglia, 2016. "An Exact Algorithm for the Elementary Shortest Path Problem with Resource Constraints," Transportation Science, INFORMS, vol. 50(1), pages 348-357, February.
    18. Senay Solak & Christina Scherrer & Ahmed Ghoniem, 2014. "The stop-and-drop problem in nonprofit food distribution networks," Annals of Operations Research, Springer, vol. 221(1), pages 407-426, October.
    19. 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.
    20. Drexl, Michael & Schneider, Michael, 2015. "A survey of variants and extensions of the location-routing problem," European Journal of Operational Research, Elsevier, vol. 241(2), pages 283-308.
    21. George B. Dantzig & Philip Wolfe, 1960. "Decomposition Principle for Linear Programs," Operations Research, INFORMS, vol. 8(1), pages 101-111, February.
    22. Yuan, Yuan & Cattaruzza, Diego & Ogier, Maxime & Semet, Frédéric & Vigo, Daniele, 2021. "A column generation based heuristic for the generalized vehicle routing problem with time windows," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 152(C).
    23. Vera C. Hemmelmayr & Karl F. Doerner & Richard F. Hartl & Daniele Vigo, 2014. "Models and Algorithms for the Integrated Planning of Bin Allocation and Vehicle Routing in Solid Waste Management," Transportation Science, INFORMS, vol. 48(1), pages 103-120, February.
    24. Marco E. Lübbecke & Jacques Desrosiers, 2005. "Selected Topics in Column Generation," Operations Research, INFORMS, vol. 53(6), pages 1007-1023, December.
    25. Florio, Alexandre M. & Gendreau, Michel & Hartl, Richard F. & Minner, Stefan & Vidal, Thibaut, 2023. "Recent advances in vehicle routing with stochastic demands: Bayesian learning for correlated demands and elementary branch-price-and-cut," European Journal of Operational Research, Elsevier, vol. 306(3), pages 1081-1093.
    26. Maximilian Schiffer & Michael Schneider & Grit Walther & Gilbert Laporte, 2019. "Vehicle Routing and Location Routing with Intermediate Stops: A Review," Transportation Science, INFORMS, vol. 53(2), pages 319-343, March.
    27. Rabbani, M. & Heidari, R. & Yazdanparast, R., 2019. "A stochastic multi-period industrial hazardous waste location-routing problem: Integrating NSGA-II and Monte Carlo simulation," European Journal of Operational Research, Elsevier, vol. 272(3), pages 945-961.
    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. Gläser, Sina, 2022. "A waste collection problem with service type option," European Journal of Operational Research, Elsevier, vol. 303(3), pages 1216-1230.
    2. Luciano Costa & Claudio Contardo & Guy Desaulniers, 2019. "Exact Branch-Price-and-Cut Algorithms for Vehicle Routing," Transportation Science, INFORMS, vol. 53(4), pages 946-985, July.
    3. Mahmoudi, Monirehalsadat & Shirzad, Khadijeh & Verter, Vedat, 2022. "Decision support models for managing food aid supply chains: A systematic literature review," Socio-Economic Planning Sciences, Elsevier, vol. 82(PB).
    4. Haoqing Wang & Wen Yi & Yannick Liu, 2022. "Optimal Route Design for Construction Waste Transportation Systems: Mathematical Models and Solution Algorithms," Mathematics, MDPI, vol. 10(22), pages 1-13, November.
    5. Akkerman, Renzo & Buisman, Marjolein & Cruijssen, Frans & de Leeuw, Sander & Haijema, Rene, 2023. "Dealing with donations: Supply chain management challenges for food banks," International Journal of Production Economics, Elsevier, vol. 262(C).
    6. Arslan, Okan, 2021. "The location-or-routing problem," Transportation Research Part B: Methodological, Elsevier, vol. 147(C), pages 1-21.
    7. Wang, Mengtong & Zhang, Canrong & Bell, Michael G.H. & Miao, Lixin, 2022. "A branch-and-price algorithm for location-routing problems with pick-up stations in the last-mile distribution system," European Journal of Operational Research, Elsevier, vol. 303(3), pages 1258-1276.
    8. Ogbe, Emmanuel & Li, Xiang, 2017. "A new cross decomposition method for stochastic mixed-integer linear programming," European Journal of Operational Research, Elsevier, vol. 256(2), pages 487-499.
    9. François Clautiaux & Cláudio Alves & José Valério de Carvalho & Jürgen Rietz, 2011. "New Stabilization Procedures for the Cutting Stock Problem," INFORMS Journal on Computing, INFORMS, vol. 23(4), pages 530-545, November.
    10. Ido Orenstein & Tal Raviv & Elad Sadan, 2019. "Flexible parcel delivery to automated parcel lockers: models, solution methods and analysis," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 8(5), pages 683-711, December.
    11. Omid Shahvari & Rasaratnam Logendran & Madjid Tavana, 2022. "An efficient model-based branch-and-price algorithm for unrelated-parallel machine batching and scheduling problems," Journal of Scheduling, Springer, vol. 25(5), pages 589-621, October.
    12. Ghazale Kordi & Parsa Hasanzadeh-Moghimi & Mohammad Mahdi Paydar & Ebrahim Asadi-Gangraj, 2023. "A multi-objective location-routing model for dental waste considering environmental factors," Annals of Operations Research, Springer, vol. 328(1), pages 755-792, September.
    13. Melanie Erhard, 2021. "Flexible staffing of physicians with column generation," Flexible Services and Manufacturing Journal, Springer, vol. 33(1), pages 212-252, March.
    14. Ibrahim Muter & Tevfik Aytekin, 2017. "Incorporating Aggregate Diversity in Recommender Systems Using Scalable Optimization Approaches," INFORMS Journal on Computing, INFORMS, vol. 29(3), pages 405-421, August.
    15. Rigo, Cezar Antônio & Seman, Laio Oriel & Camponogara, Eduardo & Morsch Filho, Edemar & Bezerra, Eduardo Augusto & Munari, Pedro, 2022. "A branch-and-price algorithm for nanosatellite task scheduling to improve mission quality-of-service," European Journal of Operational Research, Elsevier, vol. 303(1), pages 168-183.
    16. Ponce, Diego & Puerto, Justo & Temprano, Francisco, 2024. "Mixed-integer linear programming formulations and column generation algorithms for the Minimum Normalized Cuts problem on networks," European Journal of Operational Research, Elsevier, vol. 316(2), pages 519-538.
    17. Hendri Sutrisno & Chao-Lung Yang, 2023. "A two-echelon location routing problem with mobile satellites for last-mile delivery: mathematical formulation and clustering-based heuristic method," Annals of Operations Research, Springer, vol. 323(1), pages 203-228, April.
    18. Esteban Ogazón & Neale R. Smith & Angel Ruiz, 2022. "Reconfiguration of Foodbank Network Logistics to Cope with a Sudden Disaster," Mathematics, MDPI, vol. 10(9), pages 1-20, April.
    19. Amira Saker & Amr Eltawil & Islam Ali, 2023. "Adaptive Large Neighborhood Search Metaheuristic for the Capacitated Vehicle Routing Problem with Parcel Lockers," Logistics, MDPI, vol. 7(4), pages 1-27, October.
    20. 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.

    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:316:y:2024:i:3:p:958-975. 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.