A MILP Model for the Municipal Solid Waste Selective Collection Routing Problem

• Autorzy: Korcyl Antoni , Książek Roger , Gdowska Katarzyna

Identyfikatory

DOI

10.7494/dmms.2019.13.1-2.3470

• Języki publikacji: EN

Abstrakty

EN

Nowadays, selective solid waste management in the European Union belongs 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 the solid waste collection service can be minimized, subject to a series of constraints which not only guarantee the fulfillment of the SWM’s obligations but also ensure the desirable quality level of that service. The optimization in garbage truck routing belongs to so called rich Vehicle Routing Problems as it aims to cover the following constraints: pickup nodes (clients) must be visited during their predefined time windows; the number and capacity of depots and specialized sorting units cannot 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; the 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 a newly developed Mixed-Integer Programming (MIP) model for the Municipal Solid Waste Selective Collection Routing Problem (MSWSCRP) with time windows, limited heterogeneous fleet, and different types of segregated solid waste to be collected separately. Results obtained for solving small-sized instance of the MSWSCRP are reported.

Słowa kluczowe

EN

municipal solid waste collection system; solid waste segregated collection; MILP; rich VRP; Solid Waste Management

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Decision Making in Manufacturing and Services
• Rocznik: 2019
• Tom: Vol. 13, no. 1-2
• Strony: 17--35
• Opis fizyczny: Bibliogr. 48 poz., tab., rys., wykr.

Twórcy

autor

Korcyl Antoni

• AGH University of Science and Technology, Faculty of Management, Krakow, Poland

autor

Książek Roger

• AGH University of Science and Technology, Faculty of Management, Krakow, Poland

autor

Gdowska Katarzyna

• AGH University of Science and Technology, Faculty of Management, Krakow, Poland

Bibliografia

• [1] Akhtar, M., Hannan M., Begum, R., Basri, H., Scavino, E., 2017. Backtracking search algorithm in CVRP models for efficient solid waste collection and route optimization. Waste Management, 61, pp. 117–128, doi: https://doi.org/10.1016/j.wasman.2017.01.022.
• [2] Ambroziak, T., Jachimowski, R., 2011. Wybrane aspekty zagadnienia okien czasowych w problemie trasowania pojazdów. Automatyka, 15(2), pp. 51–59.
• [3] Asefi, H., Shahparvari, S., Chhetri, P., 2019a. Integrated municipal solid waste management under uncertainty: A tri-echelon city logistics and transportation context. Sustainable Cities and Society, 50:101606, doi: https://doi.org/10.1016/j.scs.2019.101606.
• [4] Asefi, H., Shahparvari, S., Chhetri, P., Lim S., 2019b. Variable fleet size and mix VRP with fleet heterogeneity in integrated solid waste management. Journal of Cleaner Production, 230, pp.1376–1395, doi: https://doi.org/10.1016/j.jclepro.2019.04.250.
• [5] Ayvaz-Cavdaroglu, N., Coban, A., Firtina-Ertis, I., 2019. Municipal solid waste management via mathematical modeling: A case study in Istanbul, Turkey. Journal of Environmental Management, 244, pp. 362–369, doi: https://doi.org/10.1016/j.jenvman.2019.05.065.
• [6] Bilitewski, B., Marek, K., Härdtle, G., 2000. Abfallwirtschaft: Handbuch für Praxis und Lehre, dritte, neubearbeitete auflage edition. Springer, Berlin – Heidelberg.
• [7] Bing, X., de Keizer, M., Bloemhof-Ruwaard, J.M., van der Vorst, J.G., 2014. Vehicle routing for the eco-efficient collection of household plastic waste. Waste Management, 34(4), pp. 719–729, doi: https://doi.org/10.1016/j.wasman.2014.01.018.
• [8] Buhrkal, K., Larsen, A., Ropke, S., 2012. The waste collection vehicle routing problem with time windows in a city logistics context. Procedia – Social and Behavioral Sciences, 39, pp. 241–254, doi: https://doi.org/10.1016/j.sbspro.2012.03.105.
• [9] Christofides, N., Beasley, J.E., 1984. The period routing problem. Networks, 14(2), pp. 237–256, 1984, doi: https://doi.org/10.1002/net.3230140205.
• [10] Cordeau, J.-F., Laporte, G., Mercier, A., 2001. A unified tabu search heuristic for vehicle routing problems with time windows. Journal of the Operational Research Society, 52(8), pp. 928–936, doi: https://doi.org/10.1057/palgrave.jors.2601163.
• [11] Cordeau, J.-F., Laporte, G., Savelsbergh, M.W., Vigo, D., 2007. Vehicle routing. In: Transportation, volume 14 of Handbooks in Operations Research and Management Science, Elsevier, pp. 367–428, doi: https://doi.org/10.1016/S0927-0507(06)14006-2.
• [12] Crainic, T.G., Laporte, G., 1998. Fleet Management and Logistics. Springer US, Boston, MA, doi: https://doi.org/10.1007/978-1-4615-5755-5.
• [13] Dantzig, G.B., Ramser, J.H., 1959. The truck dispatching problem. Management Science, 6, pp. 80–91.
• [14] Das, S., Bhattacharyya, B.K., 2015. Optimization of municipal solid waste collection and transportation routes. Waste Management, 43, pp. 9–18, doi: https://doi.org/10.1016/j.wasman.2015.06.033.
• [15] Delgado-Antequera, L., Caballero, R., Sánchez-Oro, J., Colmenar, J.M., Martí, R., 2020. Iterated greedy with variable neighborhood search for a multiobjective waste collection problem. Expert Systems with Applications, 145:113101, doi: https://doi.org/10.1016/j.eswa.2019.113101.
• [16] El-Sherbeny, N.A., 2010. Vehicle routing with time windows: An overview of exact, heuristic and metaheuristic methods. Journal of King Saud University – Science, 22(3), pp. 123–131 doi: https://doi.org/10.1016/j.jksus.2010.03.002.
• [17] Erfani, S.M.H., Danesh, S., Karrabi, S.M., Shad, R., Nemati, S., 2018. Using applied operations research and geographical information systems to evaluate effective factors in storage service of municipal solid waste management systems. Waste Management, 79, pp. 346–355, doi: https://doi.org/10.1016/j.wasman.2018.08.003.
• [18] European Parliament and European Council. 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.
• [19] Expósito-Márquez, A., Expósito-Izquierdo, C., Brito-Santana, J., Moreno-Pérez, J.A., 2019. Greedy randomized adaptive search procedure to design waste collection routes in La Palma. Computers & Industrial Engineering, 137:106047, doi: https://doi.org/10.1016/j.cie.2019.106047.
• [20] Ferrer, J., Alba, E., 2019. BIN-CT: Urban waste collection based on predicting the container fill level. Biosystems, 186:103962, doi: https://doi.org/10.1016/j.biosystems.2019.04.006.
• [21] Franca, L.S., Ribeiro, G.M., de Lorena Diniz Chaves, G., 2019. The planning of selective collection in a real-life vehicle routing problem: A case in Rio de Janeiro. Sustainable Cities and Society, 47:101488, doi: https://doi.org/10.1016/j.scs.2019.101488.
• [22] Ghiani, G., Laganà, D., Manni, E., Musmanno, R., Vigo, D., 2014. Operations research in solid waste management: A survey of strategic and tactical issues. Computers & Operations Research, 44, pp. 22–32, doi: https://doi.org/10.1016/j.cor.2013.10.006.
• [23] Główny Urząd Statystyczny [Statistics Poland]. Ochrona środowiska 2018 [Environment 2018]. Analizy statystyczne [Statistical Analyses], Główny Urząd Statystyczny [Statistics Poland], Warszawa 2018, https://stat.gov.pl/download/gfx/portalinformacyjny/pl/defaultaktualnosci/5484/1/19/1/ochrona_srodowiska_2018.pdf.
• [24] Hanczar, P., 2010. Wspomaganie decyzji w obszarze wyznaczania tras pojazdów. Decyzje, 13, pp. 55–83.
• [25] Hannan, M., Akhtar, M., Begum, R., Basri, H., Hussain, A., Scavino, E., 2018. Capacitated vehicle-routing problem model for scheduled solid waste collection and route optimization using PSO algorithm. Waste Management, 71, pp. 31–41, doi: https://doi.org/10.1016/j.wasman.2017.10.019.
• [26] Hoff, A., Andersson, H., Christiansen, M., Hasle, G., Løkketangen, A., 2010. Industrial aspects and literature survey: Fleet composition and routing. Computers & Operations Research, 37(12), pp. 2041–2061, doi: https://doi.org/10.1016/j.cor.2010.03.015.
• [27] Jakubiak, M., 2016. The improvement in collection of municipal waste on the example of a chosen municipality. Transportation Research Procedia, 16, pp. 122–129, doi: https://doi.org/10.1016/j.trpro.2016.11.013.
• [28] Korcyl, A., Gdowska, K., Książek R., 2015. Optymalizacja tras odbioru odpadów komunalnych z wykorzystaniem różnych typów pojazdów i ograniczeniami czasowymi w obsłudze klienta. Logistyka, 4, pp. 9202–9211.
• [29] Korcyl, A., Książek, R., Gdowska, K., 2016. A MILP model for route optimization problem in a municipal multi-landfill waste collection system. In: Sawik, T. (ed.), ICIL 2016: 13th International Conference on Industrial Logistics. 28 September – 1 October, Zakopane, Poland. Conference Proceedings. AGH University of Science and Technology, International Center for Innovation and Industrial Logistics, Krakow, pp. 109–118.
• [30] Koushik, P., Subhasish, C., Amit, D., Akhouri, K., Subhabrata, R., 2019. A comprehensive optimization model for integrated solid waste management system: A case study. Environmental Engineering Research, 24(2), pp. 220–237, http://eeer.org/journal/view.php?number=947.
• [31] Laporte, G., 1992. The travelling salesman problem: an overview of exact and approximate algorithms. European Journal of Operational Research, 59, pp. 231–247.
• [32] Lau, H.C., Sim, M., Teo, K.M., 2003. Vehicle routing problem with time windows anda limited number of vehicles. European Journal of Operational Research, 148(3), pp. 559–569, doi: https://doi.org/10.1016/S0377-2217(02)00363-6.
• [33] Liong, C.Y., Wan Rosmanira, I., Khairuddin, O., Mourad, Z., 2008. Vehicle routing problem: Models and solutions. Journal of Quality Measurement and Analysis, 4(1), pp. 205–218, http://www.ukm.my/jqma/jqma4_1a.html.
• [34] Malakahmad, A., Bakri, P.M., Mokhtar, M.R.M., Khalil, N., 2014. Solid waste collection routes optimization via GIS techniques in Ipoh City, Malaysia. Procedia Engineering, 77, pp. 20–27, doi: https://doi.org/10.1016/j.proeng.2014.07.023.
• [35] Nowakowski, P., Szwarc, K., Boryczka, U., 2018. Vehicle route planning in e-waste mobile collection on demand supported by artificial intelligence algorithms. Transportation Research Part D: Transport and Environment, 63, pp. 1–22, doi: https://doi.org/10.1016/j.trd.2018.04.007.
• [36] Oliveira Simonetto, de, E., Borenstein, D., 2007. A decision support system for the operational planning of solid waste collection. Waste Management, 27(10), pp. 1286–1297, doi: https://doi.org/10.1016/j.wasman.2006.06.012.
• [37] Ramos, T.R.P., Morais, de, C.S., Barbosa-Póvoa, A.P., 2018. The smart waste collection routing problem: Alternative operational management approaches. Expert Systems with Applications, 103, pp. 146–158, doi: https://doi.org/10.1016/j.eswa.2018.03.001.
• [38] Rozporządzenie Ministra Środowiska z dnia 7 października 2016 r. w sprawie szczegółowych wymagań dla transportu odpadów, Dz.U. 2016 poz. 1742.
• [39] Shankar, H., Mani, G., Pandey, K., 2014. 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), pp. 83–100, doi: https://doi.org/10.5923/j.ijtte.20140302.05.
• [40] Son, L.H., Louati, A., 2016. Modeling municipal solid waste collection: A generalized vehicle routing model with multiple transfer stations, gather sites and inhomogeneous vehicles in time windows. Waste Management, 52, pp. 34–49, doi: https://doi.org/10.1016/j.wasman.2016.03.041.
• [41] Soni, A., Patil, D., Argade, K., 2016. Municipal solid waste management. Procedia Environmental Sciences, 35, pp. 119–126, doi: https://doi.org/10.1016/j.proenv.2016.07.057.
• [42] Sousa, J.C., Biswas, H.A., Brito, R., Silveira, A., 2011. 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, pp. 1–8, http://www.sersc.org/journals/IJAST/vol28/1.pdf.
• [43] Teixeira, J., Antunes, A.P., Sousa, de, J.P., 2004. Recyclable waste collection planning – a case study. European Journal of Operational Research, 158(3), pp. 543–554, doi: https://doi.org/10.1016/s0377-2217(03)00379-5.
• [44] Toth P., Vigo, D., 2014. Vehicle Routing. Society for Industrial and Applied Mathematics, Philadelphia, PA, doi: https://doi.org/10.1137/1.9781611973594.fm.
• [45] Vecchi, T.P., Surco, D.F., Constantino, A.A., Steiner, M.T., Jorge, L.M., Ravagnani, M.A., Paraíso, P.R., 2016. A sequential approach for the optimization of truck routes for solid waste collection. Process Safety and Environmental Protection, 102, pp. 238–250, doi: https://doi.org/10.1016/j.psep.2016.03.014.
• [46] Vu, H.L., Ng, K.T.W., Fallah, B., Richter, A., Kabir, G., 2020. Interactions of residential waste composition and collection truck compartment design on GIS route optimization. Waste Management, 102, pp. 613–623, https://doi.org/10.1016/j.wasman.2019.11.028.
• [47] Xue, W., Cao, K., Li, W., 2015. Municipal solid waste collection optimization in Singapore. Applied Geography, 62, pp. 182–190, doi: https://doi.org/10.1016/j.apgeog.2015.04.002.
• [48] Yousefloo, A., Babazadeh, R., 2020. Designing an integrated municipal solid waste management network: A case study. Journal of Cleaner Production, 244:118824, doi: https://doi.org/10.1016/j.jclepro.2019.118824.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2020).