A MILP model for the selective solid waste collection routing problem

Antoni Korcyl, Katarzyna Gdowska, Roger Książek

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.

Keywords


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

Full Text:

PDF

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.




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

Refbacks

  • There are currently no refbacks.