A MILP model for the selective solid waste collection routing problem

Authors

  • Antoni Korcyl AGH University of Science and Technology, Krakow, Poland
  • Katarzyna Gdowska AGH University of Science and Technology, Krakow, Poland http://orcid.org/0000-0002-7964-3724
  • Roger Książek AGH University of Science and Technology, Krakow, Poland

DOI:

https://doi.org/10.7494/dmms.2019.13.1-2.3470

Keywords:

selective solid waste collection system, MILP, rich VRP, Solid Waste Management

Abstract

Nowadays, in the European Union selective solid waste management be-longs to important responsibilities of municipalities. In Solid Waste Management (SWM) the main operational task is to set a schedule for solid waste collection and to find optimal routes for garbage trucks so that the total costs of solid waste collection service can be minimized subject to a series of constraints which guarantee not only fulfillment of SWM’s obligations but also desirable level of quality of that service. Optimization problem of garbage trucks routing is a special case of rich Vehicle Routing Problem as it has to cover following constraints: pickup nodes (clients) must be visited during their predefined time windows; the number and capacity of depots and specialized sorting units can-not be exceeded; each garbage truck can be assigned to at most one depot; each route should be dedicated to collecting one type of segregated solid waste, and the route must be served by a garbage truck which can collect that type of solid waste; availability of garbage trucks and their drivers must be respected; each garbage truck must be drained at a specialized sorting unit before going back to the depot. This paper contributes with a new Mixed-Integer Programming (MIP) model for the Selective Solid Waste Collection Routing Problem (SS-WCRP) with time windows, limited heterogeneous fleet, and different types of segregated solid waste to be collected separately. Utilization of MIP for solving small-sized instance of the Fleet Optimization Problem for Selective Solid Waste Collection (FOPSSWC) is and obtained results are reported.

Author Biography

Katarzyna Gdowska, AGH University of Science and Technology, Krakow, Poland

I'm an assistant professor at AGH University of Science and Technology (Faculty of Management, Department of Operations Research) in Krakow, Poland. My scientific interests focus on: optimization in transportation, logistics and manufactoring.
I was a post-doc grantholder in INESC TEC in Porto, Portugal. I worked on "Transportation Models in the Era of the Internet of Things" in the framework of the project TEC4Growth – RL SMILES – Smart, Mobile, Intelligent and Large scale Sensing and analytics (NORTE-01-0145-FEDER-000020) AE2016-0387 (SMILES-8 – CEGI).

References

T. Ambroziak and R. Jachimowski. Wybrane aspekty zagadnienia okien czasowych w problemie trasowania pojazdów. Automatyka, 15(2):51–59, 2011.

H. Asefi, S. Shahparvari, P. Chhetri, and S. Lim. Variable fleet size and mix VRP with fleet heterogeneity in integrated solid waste management. Journal of Cleaner Production, 230:1376–1395, Sept. 2019. doi: 10.1016/j.jclepro.2019.04.250.

N. Ayvaz-Cavdaroglu, A. Coban, and I. Firtina-Ertis. Municipal solid waste management via mathematical modeling: A case study in istanbul, turkey. Journal of Environmental Management, 244:362–369, Aug. 2019. doi: 10.1016/j.jenvman.2019.05.065.

B. Bilitewski, K. Marek, and G. Härdtle. Abfallwirtschaft: Handbuch für Praxis und Lehre. Springer Berlin Heidelberg, Berlin, Heidelberg, dritte, neubearbeitete auflage edition, 2000.

K. Buhrkal, A. Larsen, and S. Ropke. The waste collection vehicle routing problem with time windows in a city logistics context. Procedia - Social and Behavioral Sciences, 39:241–254, 2012. doi: 10.1016/j.sbspro.2012.03.105.

N. Christofides and J. E. Beasley. The period routing problem. Networks, 14(2):237–256, 1984. doi: 10.1002/net.3230140205.

J.-F. Cordeau, G. Laporte, and A. Mercier. A unified tabu search heuristic for vehicle routing problems with time windows. Journal of the Operational Research Society, 52(8):928–936, 2001. ISSN 0160-5682. doi: 10.1057/palgrave.jors.2601163.

J.-F. Cordeau, G. Laporte, M. W. Savelsbergh, and D. Vigo. Chapter 6 vehicle routing. In Transportation, volume 14 of Handbooks in Operations Research and Management Science, pages 367–428. Elsevier, 2007. ISBN 9780444513465. doi:10.1016/S0927-0507(06)14006-2.

T. G. Crainic and G. Laporte. Fleet Management and Logistics. Springer US, Boston, MA, 1998. ISBN 978-1-4613-7637-8. doi: 10.1007/978-1-4615-5755-5.

G. B. Dantzig and Ramser J.H. The truck dispatching problem. Management Science, 6(80–91), 1959.

E. de Oliveira Simonetto and D. Borenstein. A decision support system for the operational planning of solid waste collection. Waste Management, 27(10):1286–1297, Jan. 2007. doi: 10.1016/j.wasman.2006.06.012.

N. A. El-Sherbeny. Vehicle routing with time windows: An overview of exact, heuristic and metaheuristic methods. Journal of King Saud University - Science, 22(3):123–131, 2010. ISSN 10183647. doi: 10.1016/j.jksus.2010.03.002.

European Parliament and EuropeanCouncil. Directive (eu) 2019/904 of the European Parliament and of the Council of 5 june 2019 on the reduction of the impact of certain plastic products on the environment: Pe/11/2019/rev/1, 05.06.2019.

G. Ghiani, D. Laganà, E. Manni, R. Musmanno, and D. Vigo. Operations research in solid waste management: A survey of strategic and tactical issues. Computers & Operations Research, 44:22–32, Apr. 2014. doi: 10.1016/j.cor.2013.10.006.

P. Hanczar. Wspomaganie decyzji w obszarze wyznaczania tras pojazdów. Decyzje, 13:55–83, 2010.

A. Hoff, H. Andersson, M. Christiansen, G. Hasle, and A. Løkketangen. Industrial aspects and literature survey: Fleet composition and routing. Computers & Operations Research, 37(12):2041–2061, 2010. ISSN 03050548. doi: 10.1016/j.cor.2010.03.015.

A. Korcyl, K. Gdowska, and R. Ksiazek. Optymalizacja tras odbioru odpadów komunalnych z wykorzystaniem różnych typów pojazdów i ograniczeniami czasowymi w obsłudze klienta. Logistyka, 4:9202–9211, 2015.

A. Korcyl, R. Ksiazek, and K. Gdowska. A milp model for route optimization problem in a municipal multi-landfill waste collection system. In T. Sawik, editor, ICIL 2016: 13th International Conference on Industial Logistics. 28 September – 1 October, Zakopane, Poland. Conference Proceedings, pages 109–118. AGH University of Science and Technology, International Center for Innovation and Industrial Logistics, Poland, 2016.

G. Laporte. The travelling salesman problem: an overview of exact and approximate algorithms. European Journal of Operational Research, 59:231–247, 1992.

H. C. Lau, M. Sim, and K. M. Teo. Vehicle routing problem with time windows and a limited number of vehicles. European Journal of Operational Research, 148(3): 559–569, 2003. ISSN 03772217. doi: 10.1016/S0377-2217(02)00363-6.

C. Y. Liong, I. Wan Rosmanira, O. Khairuddin, and Z. Mourad. Vehicle routing problem: Models and solutions. Journal of Quality Measurement and Analysis, 4 (1):205–218, 2008. URL http://www.ukm.my/jqma/jqma4_1a.html.

Minister Środowiska. Rozporządzenie ministra środowiska z dnia 7 października 2016 r. w sprawie rozporządzenie ministra środowiska z dnia 7 października 2016 r. w sprawie szczegółowych wymagań dla transportu odpadów, 07.10.2016.

H. Shankar, G. Mani, and K. Pandey. Gis based solution of multi-depot capacitated vehicle routing problem with time window using tabu search algorithm. International Journal of Traffic and Transportation Engineering, 3(2):83–100, 2014. URL http://www.sapub.org/global/showpaperpdf.aspx?doi=10.5923/j.ijtte.20140302.05.

A. Soni, D. Patil, and K. Argade. Municipal solid waste management. Procedia Environmental Sciences, 35:119–126, 2016. doi: 10.1016/j.proenv.2016.07.057.

J. C. Sousa, H. A. Biswas, R. Brito, and A. Silveira. A multi objective approach to solve capacitated vehicle routing problems with time windows using mixed integer linear programming. International Journal of Advanced Science and Technology, 28: 1–8, 2011. http://www.sersc.org/journals/IJAST/vol28/1.pdf.

Statistics Poland. Environment 2018, 2019. https://stat.gov.pl/download/gfx/portalinformacyjny/pl/defaultaktualnosci/5484/1/19/1/ochrona_

srodowiska_2018.pdf.

J. Teixeira, A. P. Antunes, and J. P. de Sousa. Recyclable waste collection planning –– a case study. European Journal of Operational Research, 158(3):543–554, Nov. 2004. doi: 10.1016/s0377-2217(03)00379-5.

P. Toth and D. Vigo. Vehicle Routing. Society for Industrial and Applied Mathematics, Philadelphia, PA, 2014. ISBN 978-1-61197-358-7. doi: 10.1137/1.9781611973594.

W. Xue, K. Cao, and W. Li. Municipal solid waste collection optimization in Singapore. Applied Geography, 62:182–190, Aug. 2015. doi: 10.1016/j.apgeog.2015.04.002.

Downloads

Published

2020-04-27

How to Cite

Korcyl, A., Gdowska, K., & Książek, R. (2020). A MILP model for the selective solid waste collection routing problem. Decision Making in Manufacturing and Services, 13. https://doi.org/10.7494/dmms.2019.13.1-2.3470

Issue

Vol. 13 (2019): No. 1-2

Section

Articles

License

Remeber to prepeare, sign and scan copyright statement

Licencja Creative Commons
The content of the journal is freely available according to the Creative Commons License Attribution 4.0 International (CC BY 4.0)

Received 2019-10-18
Accepted 2020-01-24
Published 2020-04-27