Waste Collection Vehicle Routing Problem: Literature Review

  • Hui Han
  • Eva Ponce Cueto
Keywords: waste collection, vehicle routing problem, commercial waste, residential waste, industrial waste,

Abstract

Waste generation is an issue which has caused wide public concern in modern societies, not only for the quantitative rise of the amount of waste generated, but also for the increasing complexity of some products and components. Waste collection is a highly relevant activity in the reverse logistics system and how to collect waste in an efficient way is an area that needs to be improved. This paper analyzes the major contribution about Waste Collection Vehicle Routing Problem (WCVRP) in literature. Based on a classification of waste collection (residential, commercial and industrial), firstly the key findings for these three types of waste collection are presented. Therefore, according to the model (Node Routing Problems and Arc Routing problems) used to represent WCVRP, different methods and techniques are analyzed in this paper to solve WCVRP. This paper attempts to serve as a roadmap of research literature produced in the field of WCVRP.

Author Biographies

Hui Han
Hui Han is a PhD student at Department of Industrial Engineering, Business Administration and Statistic E.T.S. Industrial Engineering, Technical University of Madrid. She is funded by the China Scholarship Council (CSC) from the Chinese Ministry of Education.
Eva Ponce Cueto
E. Ponce-Cueto received her PhD in Industrial Engineering from Carlos III University of Madrid in 2002. Her dissertation has received two awards with special distinction in the Spanish context. She is currently an Associate Professor at the Department of Industrial Engineering, Business Administration and Statistics, Technical University of Madrid (UPM), Madrid, Spain. Her current research interest includes supplier relationship, supply management, integrated supply chains and closed-loop supply chains.

References

Blumenthal K, Issn LB, Union E, States EUM. Waste indicators on generation and landfilling measuring sustainable development 2004-2010. 2013;(June 2012):1–12.

Mazzanti M, Zoboli R. Municipal Waste Kuznets Curves: Evidence on Socio-Economic Drivers and Policy Effectiveness from the EU. Environmental and Resource Economics. 2009 Mar 20;44(2):203–30.

Atasu A, Wassenhove LN. An Operations Perspective on Product Take-Back Legislation for E-Waste: Theory, Practice, and Research Needs. Production and Operations Management. 2011 May 7;21(3):407–22.

Ponce-Cueto E, González-manteca JA. Impact of Emerging Environmental Regulations on the Reverse Logistics System for Portable Batteries in Spain. In: Golinska P, Romano CA, editors. Environmental Issues in Supply Chain Management. Berlin, Heidelberg: Springer Berlin Heidelberg; 2012. p. 155–70.

Mayers CK, France CM, Cowell SJ. Extended Producer Responsibility for Waste Electronics: An Example of Printer Recycling in the United Kingdom. Journal of Industrial Ecology. 2005 Jul 8;9(3):169–89.

OECD. OECD Glossary of Environment Statistics, Studies in Methods. 1997.

Beltrami EJ, Bodin LD. Networks and vehicle routing for municipal waste collection. Networks. Wiley Subscription Services, Inc., A Wiley Company; 1974;4(1):65–94.

Ronen R, Kellerman A, Lapidot M. Improvement of a solid waste collection system: the case of Givatayim, Israel. Applied Geography. 1983 Apr;3(2):133–44.

Chang N-B, Wei YL. Siting recycling drop-off stations in urban area by genetic algorithm-based fuzzy multiobjective nonlinear integer programming modeling. Fuzzy Sets and Systems. 2000 Aug;114(1):133–49.

Torres OAC, Antón FR. A Continuous Approximation Model for Vehicle Routing in Solid Waste Management Systems. Investigación Operativa. 1999;8:109–53.

Sniezek J, Bodin L, Levy L, Ball M. Capacitated Arc Routing Problems with Vehicle-Site Dependencies: The Philadelphia Experience. In: Toth P, Vigo D, editors. The Vehicle Routing Problem: Discrete mathematics and its applications. Philadelphia; 2001. p. 247–54.

Angelelli E, Speranza MG. The application of a vehicle routing model to a waste-collection problem: two case studies. In: Klose A, Speranza MG, Van Wassenhove LN, editors. Quantitative Approaches to Distribution Logistics and Supply Chain Management. Berlin, Heidelberg: Springer Berlin Heidelberg; 2002. p. 269–86.

Viotti P, Polettini A, Pomi R, Innocenti C. Genetic algorithms as a promising tool for optimisation of the MSW collection routes. Waste Management & Research. 2003 Aug 1;21(4):292–8.

Bautista J, Pereira J. Ant algorithms for urban waste collection routing. Ant Colony Optimization and Swarm Intelligence, Proceedings. 2004;3172:302–9.

Bianchessi N, Righini G. Heuristic algorithms for the vehicle routing problem with simultaneous pick-up and delivery. Computers & Operations Research. 2007 Feb;34(2):578–94.

Ghiani G, Guerriero F, Improta G, Musmanno R. Waste collection in Southern Italy: solution of a real-life arc routing problem. International Transactions in Operational Research. 2005 Mar;12(2):135–44.

Ghose MK, Dikshit a K, Sharma SK. A GIS based transportation model for solid waste disposal--a case study on Asansol municipality. Waste management (New York, NY). 2006 Jan;26(11):1287–93.

Karadimas N V., Kolokathi M, Defteraiou G, Loumos V. Ant Colony System vs ArcGIS Network Analyst: The Case of Municipal Solid Waste Collection. 5th WSEAS International Conference on Environment, Ecosystems and Development. 2007;128–34.

Alagöz AZ, Kocasoy G. Improvement and modification of the routing system for the health-care waste collection and transportation in Istanbul. Waste management (New York, NY). 2008 Jan;28(8):1461–71.

Apaydin O, Gonullu MT. Route optimization for solid waste collection: Trabzon (Turkey) case study. GlobalNEST. 2007;9(1):6–11.

Bautista J, Fernández E, Pereira J. Solving an urban waste collection problem using ants heuristics. Computers & Operations Research. 2008 Sep;35(9):3020–33.

Ombuki-Berman BM, Runka A, Hanshar F. Waste collection vehicle routing problem with time windows using multi-objective genetic algorithms windows using multi-objective genetic algorithms. International Association of Science and Technology for Development Proceedings of the Third IASTED International Conference on Comutational Intelligence. 2007;91–7.

Santos L, Coutinho-Rodrigues J, Current JR. Implementing a multi-vehicle multi-route spatial decision support system for efficient trash collection in Portugal. Transportation Research Part A: Policy and Practice. 2008 Jul;42(6):922–34.

Ustundag A, Cevikcan E. Vehicle route optimization for RFID integrated waste collection system. International Journal of Information Technology & Decision Making. World Scientific Publishing Company; 2008 Dec 20;07(04):611–25.

Kim H, Yang J, Lee K-D. Vehicle routing in reverse logistics for recycling end-of-life consumer electronic goods in South Korea. Transportation Research Part D: Transport and Environment. 2009 Jul;14(5):291–9.

Maniezzo V. Algorithms for large directed CARP instances: urban solid waste collection operational support. UBLCS Technical Report University of Bologna. Bologna; 2004 p. 29.

Archetti C, Speranza MG. Collection of waste with single load trucks: A real case. In: Fleischmann B, Klose A, editors. Distribution Logistics. Berlin, Heidelberg: Springer Berlin Heidelberg; 2005. p. 105–19.

Sniezek J, Bodin L. Using mixed integer programming for solving the capacitated arc routing problem with vehicle/site dependencies with an application to the routing of residential sanitation collection vehicles. Annals of Operations Research. 2006 May 24;144(1):33–58.

Karadimas N, Kolokathi M, Defteraiou G, Loumos V. Municipal Waste Collection of Large Items optimized with arc GIS network analyst. Proceedings 21st European Conference on Modelling and Simulation. 2007;4–9.

Muttiah RS, Engel BA, Jones DD. Waste disposal site selection using GIS-based simulated annealing. Computers & Geosciences. 1996 Nov;22(9):1013–7.

Cheng S, Chan CW, Huang GH. An integrated multi-criteria decision analysis and inexact mixed integer linear programming approach for solid waste management. Engineering Applications of Artificial Intelligence. 2003 Aug;16(5-6):543–54.

Huang GH, Baetz BW, Patry GG. Trash-Flow Allocation: Planning under uncertainty. Interfaces. 1998;28(6):36–55.

McLeod F, Cherrett T. Quantifying the transport impacts of domestic waste collection strategies. Waste management (New York, NY). 2008 Nov;28(11):2271–8.

Sumathi VR, Natesan U, Sarkar C. GIS-based approach for optimized siting of municipal solid waste landfill. Waste management (New York, NY). 2008 Nov;28(11):2146–60.

Clark RM, Gillean JI. Analysis of Solid Waste Management Operations in Cleveland, Ohio: A Case Study. Interfaces. 1975 Nov;6(1-part-2):32–42.

Aringhieri R, Bruglieri M, Malucelli F, Nonato M. A particular Vehicle Routing Problem arising in the collection and disposal of special waste. Presented at Tristan 2004. Guadeloupe, French West Indies; 2004.

Arribas CA, Blazquez CA, Lamas A. Urban solid waste collection system using mathematical modelling and tools of geographic information systems. Waste management & research : the journal of the International Solid Wastes and Public Cleansing Association, ISWA. 2010 Apr;28(4):355–63.

Benjamin A. Metaheuristics for the waste collection vehicle routing problem with time windows[PhD thesis]. Brunel University; 2011. p. 1–196.

Beliën J, Boeck L De, Ackere J Van. Municipal solid waste collection and management problems: a literature review. Transportation Science. 2012;48(1):78–102.

Dantzig GB, Ramser JH. The Truck Dispatching Problem Stable. Management Science. 1959;6(1):80–91.

Caric T, Gold H. The Vehicle Routing Problem. Toth P, Vigo D, editors. Society for Industrial and Applied Mathematics; 2008.

Golden B, Assad A, Wasil E. Routing vehicles in the real world: applications in the solid waste, beverage, food, dairy, and newspaper industries. In: Toth P, Vigo D, editors. The vehicle routing problem. SIAM; 2002. p. 245–86.

Kim B-I, Kim S, Sahoo S. Waste collection vehicle routing problem with time windows. Computers & Operations Research. 2006 Dec;33(12):3624–42.

Assad A, Golden B. Arc routing methods and applications. Handbooks in operations research and management science. 5 Elsevier. 1995. p. 375–483.

Eiselt H, Gendreau M, Laporte G. Arc routing problems, part I: The Chinese postman problem. Operations Research. 1995;43(2):231–42.

Eiselt AHA, Gendreau M, Laporte G. ARC ROUTING PROBLEMS , PART II : THE RURAL POSTMAN PROBLEM. 1994;43(3):399–414.

Eisenstein D, Iyer A. Garbage collection in Chicago: a dynamic scheduling model. Management Science. 1997;43(7):922–33.

Dror M. Arc routing: theory, solutions, and applications. Springer; 2000.

Tung DV, Pinnoi A. Vehicle routing–scheduling for waste collection in Hanoi. European Journal of Operational Research. 2000 Sep;125(3):449–68.

Faccio M, Persona A, Zanin G. Waste collection multi objective model with real time traceability data. Waste management (New York, NY). Elsevier Ltd; 2011 Dec;31(12):2391–405.

Bonomo F, Durán G, Larumbe F, Marenco J. A method for optimizing waste collection using mathematical programming: a Buenos Aires case study. Waste management & research : the journal of the International Solid Wastes and Public Cleansing Association, ISWA. 2012 Mar;30(3):311–24.

Kulcar T. Optimizing solid waste collection in Brussels. European Journal of Operational Research. 1996 Apr;90(1):71–7.

Sahoo S, Kim S, Kim B, Kraas B, Jr AP. Routing optimization for waste management. Interfaces. 2005;35(1):24–36.

Benjamin A, Beasley J. Metaheuristics for the waste collection vehicle routing problem with time windows, driver rest period and multiple disposal facilities. Computers & Operations Research. 2010;37(12):2270–80.

Liu J, He Y. A Clustering-Based Multiple Ant Colony System for the Waste Collection Vehicle Routing Problems. 2012 Fifth International Symposium on Computational Intelligence and Design. Ieee; 2012. p. 182–5.

Meulemeester L De, Laporte G. Optimal sequencing of skip collections and deliveries. Journal of the operational Research Society. 1997;48(1):57–64.

Bodin L, Mingozzi A, Baldacci R, Ball M. The Rollon–Rolloff Vehicle Routing Problem. Transportation Science. 2000 Aug;34(3):271–88.

Baldacci R, Bodin L, Mingozzi A. The multiple disposal facilities and multiple inventory locations rollon–rolloff vehicle routing problem. Computers & Operations Research. 2006 Sep;33(9):2667–702.

Fukasawa R, Longo H, Lysgaard J, Reis MP de AM, Uchoa E, F.Werneck R. Robust branch-and-cut-and-price for the capacitated vehicle routing problem. Mathematical Programming. 2006;106(3):491–511.

Wy J, Kim B-I. A hybrid metaheuristic approach for the rollon–rolloff vehicle routing problem. Computers & Operations Research. Elsevier; 2013 Aug;40(8):1947–52.

Wy J, Kim B-I, Kim S. The rollon–rolloff waste collection vehicle routing problem with time windows. European Journal of Operational Research. Elsevier B.V.; 2013 Feb;224(3):466–76.

Bommisetty D, Dessouky M, Jacobs L. Scheduling collection of recyclable material at Northern Illinois University campus using a two-phase algorithm. Computers & industrial engineering. 1998;35(98):435–8.

Shih L, Chang H. A routing and scheduling system for infectious waste collection. Environmental Modeling & Assessment. 2001;6:261–9.

Baptista S, Oliveira R, Zúquete E. A period vehicle routing case study. European Journal of Operational Research. 2002;139:220–9.

Teixeira J, Antunes AP, de Sousa JP. Recyclable waste collection planning––a case study. European Journal of Operational Research. 2004 Nov;158(3):543–54.

Karadimas N, Kouzas G. Urban solid waste collection and routing: The ant colony strategic approach. International Journal of Simulation. 2005;6(12):45–53.

Nuortio T, Kytojoki J, Niska H, Braysy O. Improved route planning and scheduling of waste collection and transport. Expert Systems with Applications. 2006 Feb;30(2):223–32.

Schultmann F, Zumkeller M, Rentz O. Modeling reverse logistic tasks within closed-loop supply chains: An example from the automotive industry. European Journal of Operational Research. 2006 Jun;171(3):1033–50.

Simonetto E de O, Borenstein D. A decision support system for the operational planning of solid waste collection. Waste management (New York, NY). 2007 Jan;27(10):1286–97.

Krikke H, le Blanc I, van Krieken M, Fleuren H. Low-frequency collection of materials disassembled from end-of-life vehicles. International Journal of Production Economics. 2008 Feb;111(2):209–28.

Aguiar M. Optimization techniques for the mixed urban rural solid waste collection problem. 2010[PhD thesis]. p. 1–90.

Buhrkal K, Larsen A, Ropke S. The Waste Collection Vehicle Routing Problem with Time Windows in a City Logistics Context. Procedia - Social and Behavioral Sciences. 2012;39:241–54.

Carrasco-Gallego R, Ponce-Cueto E, Dekker R. Closed-loop supply chains of reusable articles: a typology grounded on case studies. International Journal of Production Research. 2012 Oct;50(19):5582–96.

Otoo D. Capacitated arc routing problem: collection of solid waste at Kwadaso estate, Kumasi [PhD thesis]. 2012. p. 1–95.

Ferreira J, Quintas A, Oliveira J. Solving the Team Orienteering Problem: Developing a Solution Tool Using a Genetic Algorithm Approach. Soft Computing in Industrial Applications. 2012. p. 1–10.

Markov I, Varone S, Bierlaire M. Vehicle Routing for a Complex Waste Collection Problem. 14th Swiss Transport Research Conference [Internet]. 2014 [cited 2014 Nov 27]. p. 1–25. Available from: http://www.strc.ch/conferences/2014/Markov_EtAl.pdf

Mourão MC, Almeida MT. Lower-bounding and heuristic methods for a refuse collection vehicle routing problem. European Journal of Operational Research. 2000 Mar;121(2):420–34.

Minciardi R, Paolucci M, Trasforini E. A new procedure to plan routing and scheduling of vehicles for solid waste collection at a metropolitan scale. Odysseys, Palermo, Italy. 2003;

Amponsah SK, Salhi S. The investigation of a class of capacitated arc routing problems: the collection of garbage in developing countries. Waste management (New York, NY). 2004 Jan;24(7):711–21.

Koushki PA, Al-Duaij U, Al-Ghimlas W. Collection and transportation cost of household solid waste in Kuwait. Waste management (New York, NY). 2004 Jan;24(9):957–64.

Ismail Z, Loh SL. Ant Colony Optimization for Solving Solid Waste Collection Scheduling Problems. Journal of Mathematics and Statistics. 2009 Mar 1;5(3):199–205.

Bodin L, Fagin G, Welebny R, Greenberg J. The design of a computerized sanitation vehicle routing and scheduling system for the town of oyster bay, new york. Computers & Operations Research. 1989 Jan;16(1):45–54.

Ong HL, Goh TN, Poh KL, Lim CC. A computerised vehicle routing system for refuse collection. Advances in Engineering Software (1978). 1990 Apr;12(2):54–8.

Chang N, Lu H, Wei Y. GIS technology for vehicle routing and scheduling in solid waste collection systems. Journal of environmental engineering. 1997;123(9):901–10.

Smith Korfmacher K. Solid Waste Collection Systems in Developing Urban Areas of South Africa: an Overview and Case Study. Waste Management & Research. 1997 Oct;15(5):477–94.

Ismail Z bin H, Nurhadi I, Zainuddin ZM. Development of heuristic methods based on genetic algorithm (GA) for solving vehicle routing problem. 2008 p. 1–166.

Hansmann RS, Zimmermann UT. Integrated Vehicle Routing and Crew Scheduling ( IVRCS ) in Waste Management Part I. Dagstuhl Seminar Proceedings 09261 Models and Algorithms for Optimization in Logistics. 2009. p. 1–8.

O’Connor DL. Solid Waste Collection Vehicle Route Optimization for the City of Redlands, California[PhD thesis]. 2013. p. 1–77.

Fooladi S. Waste collection vehicle routing problem considering similarity pattern of trash can and garbage unloading. International Journal of Modern Management and Foresight. 2014;1(7):245–54.

Benavent E, Campos V, Corberán A, Mota E. The capacitated arc routing problem: lower bounds. Networks. 1992;22(7):669–90.

Tasgetiren MF. A Genetic Algorithm with an Adaptive Penalty Function for the Orienteering Problem. 4(2):1–26.

Glover F, Kochenberger GA. Handbook of Metaheuristics. Internatio. Springer; 2003.

Gendreau M, Potvin J-Y, Bräumlaysy O, Hasle G, Løkketangen A. Metaheuristics for the Vehicle Routing Problem and Its Extensions: A Categorized Bibliography. In: Golden B, Raghavan S, Wasil E, editors. The Vehicle Routing Problem: Latest Advances and New Challenges. Boston, MA: Springer US; 2008. p. 143–69.

Cordeau J-F, Gendreau M, Laporte G, Potvin J-Y, Semet F. A guide to vehicle routing heuristics. Journal of the Operational Research Society. 2002 May;53(5):512–22.

Lin C, Choy KL, Ho GTS, Chung SH, Lam HY. Survey of Green Vehicle Routing Problem: Past and future trends. Expert Systems with Applications. 2014 Mar;41(4):1118–38.

Sbihi A, Eglese RW. Combinatorial optimization and Green Logistics. 4OR: A Quarterly Journal of Operations Research, Springer Verlag (Germany). 2007 Jun 1;5(2):99–116.

Eksioglu B, Vural AV, Reisman A. The vehicle routing problem: A taxonomic review. Computers & Industrial Engineering. Elsevier Ltd; 2009;57(4):1472–83.

Published
2015-08-31
How to Cite
1.
Han H, Cueto EP. Waste Collection Vehicle Routing Problem: Literature Review. PROMET [Internet]. 2015Aug.31 [cited 2020Oct.21];27(4):345-58. Available from: http://traffic.fpz.hr/index.php/PROMTT/article/view/1616
Section
Articles