An algorithm for garbage truck routing in cities with a fixation on container filling level

• Autorzy: Oliskevych Myroslav , Danchuk Victor

Identyfikatory

DOI

10.20858/tp.2023.18.1.07

• Języki publikacji: EN

Abstrakty

EN

An algorithm for optimizing the routes of a set of vehicles used for the collection and removal of municipal solid waste in a metropolis is proposed. The algorithm eliminates the problem of applying heuristic methods for multi-agent optimization, which is NP non-deterministic polynomial-time-hard. The application of the algorithm leads to a guaranteed exact solution. Through the application of restrictions on the carrying capacity of vehicles, the size of the input matrix representing the transport network can be reduced to an adequate size. This process uses statistical information about the filling levels of container waste bins. The algorithm is applied to an example of two megacities. The shortest routes are built for different numbers of points (from 12 to 72) on the route. The dependence of the total mileage on the number of involved vehicles is studied.

Słowa kluczowe

EN

routing; lexical search; garbage collection; capacity limitation

PL

trasowanie; wyszukiwanie leksykalne; zbieranie śmieci; ograniczenie pojemności

• Wydawca: Wydawnictwo Politechniki Śląskiej
• Czasopismo: Transport Problems
• Rocznik: 2023
• Tom: T. 18, z. 1
• Strony: 75--87
• Opis fizyczny: Bibliogr. 28 poz.

Twórcy

autor

Oliskevych Myroslav

• L’viv National University of Nature management; V. Velykogo Str. 1, 80381, Dubliany L’viv Region, Ukraine

• https://orcid.org/0000-0001-6237-0785

autor

Danchuk Victor

• National Transport University; 1, M. Omelianovycha-Pavlenka Str. Kyiv, 01010, Ukraine

• https://orcid.org/0000-0003-3936-4509

Bibliografia

• 1. Про Програму поводження з твердими побутовими відходами у м. Львові на 2014-2018 роки УХВАЛА № 4132 Україна Львівська Міська Рада. Available at: https://city-adm.lviv.ua/public-information/waste-management/1484/visit?cf_id=35. [In Ukrainian: About the Solid Household Waste Management Program in the City of Lviv for 2014-2018 Resolution No. 4132 Ukraine L’viv City Council].
• 2. Фесіна, Ю.Г. & Дзюбинська, О.В. Перспективи формування циклічної моделі економіки у сфері поводження з побутовими відходами регіону. Економічні науки. Серія "Регіональна економіка". 2019. No. 16(63). P. 149-162. [In Ukrainian: Fesina, J.G. & Dziubynska, O.V. Prospects for formation of a circular model of the economy in the sphere of municipal solid waste management of the region. Economic sciences. “Regional Economy” series].
• 3. Стан довкілля у Львівській області (за результатами моніторингових досліджень) інформаційно – аналітичний огляд I квартал 2022 року. Available at: https://mepr.gov.ua/files/docs/EkoMonitoring/2022. [In Ukrainian: The state of the environment in the Lviv region (according to the results of monitoring studies) informational and analytical review 1st quarter of 2022].
• 4. Książek, R. & Gdowska, K. & Korcyl, A. Recyclables collection route balancing problem with heterogeneous fleet. Energies. 2021. Vol. 14. No. 21. Paper No. 7406. P. 1-16.
• 5. Мельниченко, Г.М. & et al. Cтруктура утворення та стан поводження з відходами в івано-франківській області (Інформаційно-аналітичний огляд). Екологія і виробництво. No. 7. 2020. 170 p. [In Ukrainian: Melnychenko, G.M. & et al. Structure of formation and state of waste management in the Ivano-Frankivsk region (Informative and analytical review). Ecology and production].
• 6. Azevedo, B.D. & et al. Improving urban household solid waste management in developing countries based on the German experience. Waste Management. 2021. No. 120. P. 772-783.
• 7. Bektas, T. The multiple traveling salesman problem: an overview of formulations and solution procedures. Omega. 2006. Vol 34(3). P. 209-219.
• 8. Villanueva, R.S. A pragmatic approach to improve the efficiency of the waste management system in Stockholm through the use of Big Data. Heuristics and open source VRP solvers: A real life waste collection problem. Stockholm’s waste collection system and inherent vehicle routing problem. VRP. 2020.
• 9. Erdoğan, Güneş. An open source spreadsheet solver for vehicle routing problems. Computers & operations research. 2017. Vol. 84. P. 62-72.
• 10. Dixit, A. & Mishra, A. & Shukla, A. Vehicle routing problem with time windows using meta-heuristic algorithms: a survey. In: Harmony search and nature inspired optimization algorithms. Springer, Singapore. 2019. P. 539-546.
• 11. Hahn, A. & Frühling, W. & Schlüter, J. Determination of optimised pick-up and drop-off locations in transport routing-a cost distance approach. Transport Problems. 2021. Vol. 17. No. 1. P. 17-28.
• 12. Borowska-Stefańska, M. & et al. The use of the roadload application in geographical studies of flows generated by individual modes of transport. Transport Problems. 2020. Vol. 15. No. 4. Part 2. P. 227-240.
• 13. Korcyl, A. & Książek, R. & Gdowska, K. A MILP Model for the municipal solid waste selective collection routing problem. Decision Making in Manufacturing and Services. 2019. Vol. 13. Nos. 1-2. P. 17-35.
• 14. Abdirad, M. & Krishnan, K. & Gupta, D. A two-stage metaheuristic algorithm for the dynamic vehicle routing problem in Industry 4.0 approach. Journal of Management Analytics. 2021. Vol. 8. Part 1. P. 69-83.
• 15. Goeke, D. & Roberti, R. & Schneider, M. Exact and heuristic solution of the consistent vehicle-routing problem. Transportation Science. 2019. Vol. 53. No. 4. P. 1023-1042.
• 16. Archetti, C. & Boland, N. & Grazia Speranza, M. A matheuristic for the multivehicle inventory routing problem. INFORMS Journal on Computing. 2017. Vol. 29. No. 3. P. 377-387.
• 17. Wang, Y., et al. Collaborative multidepot vehicle routing problem with dynamic customer demands and time windows. Sustainability. 2022. Vol. 14. No. 6709. P. 1-37.
• 18. Ky Phuc, P.N. & Phuong Thao, N.L. Ant colony optimization for multiple pickup and multiple delivery vehicle routing problem with time window and heterogeneous fleets. Logistics. 2021. Vol. 5(2). No. 28. P. 1-13.
• 19. Adi, T.N. & Bae, H. & Iskandar, Y.A. Interterminal truck routing optimization using cooperative multiagent deep reinforcement learning. Processes. 2021. Vol. 9(10). No. 1728. P. 1-23.
• 20. Baldacci, R. & Mingozzi, A. A unified exact method for solving different classes of vehicle routing problems. Mathematical Programming. 2009. Vol. 120(2). P. 347-380.
• 21. Fitzek, D. & et al. Applying quantum approximate optimization to the heterogeneous vehicle routing problem. Bulletin of the American Physical Society. 2022. Vol. 67. No. 3. P. 1-17.
• 22. Bernal, J. & Escobar, J.W. & Linfati, R. A simulated annealing-based approach for a real case study of vehicle routing problem with a heterogeneous fleet and time windows. International Journal of Shipping and Transport Logistics. 2021. Vol. 13(1-2). P. 185-204.
• 23. Setiawan, F. & Novialdo, K.H. Heterogeneous vehicle routing problem with vehicle dependent travel time for urban freight transportation. Proceedings of the Second Asia Pacific International Conference on Industrial Engineering and Operations Management Surakarta. Indonesia, September 14-16. 2021. P. 1732-1743.
• 24. Ahmeda, Z.H. & Al-Dayelb, I. An exact algorithm for the single-depot multiple travelling salesman problem. IJCSNS. 2020. Vol. 20(9). P. 65.
• 25. Darwiche, M., et al. A local branching heuristic for solving a graph edit distance problem. Computers & Operations Research., 2019. 106: 225-235.
• 26. Ramos, T.R.P. & De Morais, C.S. & Barbosa-Póvoa, A.P. The smart waste collection routing problem: Alternative operational management approaches. Expert Systems with Applications. 2018. Vol. 103. P. 146-158.
• 27. Pandit, S.N.N. & Srinivas, K.A. Lexisearch algorithm for traveling Salesman problem. In: 1991 IEEE International Joint Conference on Neural Networks. IEEE. 1991. P. 2521-2527.
• 28. Map of containers for organics Lviv. 2022. Available at: https://www.google.com/maps/d/u/0/viewer?mid=1ASrSdBmfCY6_JYm0guIBbbA4JXTPRgqe&l l=49.82819962654997%2C24.02545760000001&z=11.