Design of waste management area based on clustering and traveling salesman problem

Year 2025, Volume: 8 Issue: 4, 1007 - 1017, 31.12.2025

Oktaviana Hasna Nabila , Feddy Setio Pribadi

https://doi.org/10.35208/ert.1497379

Abstract

Waste management in rural Indonesia faces significant challenges as the volume of household waste increases. Waste banks are proposed as a solution to overcome this problem. This study aims to design an efficient waste management area in Gondangmanis Village by determining the optimal location of waste collection points and the shortest waste pickup route using clustering and Travelling Salesman Problem (TSP) approaches. The K-Means clustering algorithm is used to form clusters and determine the center point of each cluster, where the K value is first optimized using a genetic algorithm. Furthermore, the genetic algorithm is also applied to optimize the TSP to find the most efficient waste pickup route. The data used includes 1181 coordinate points in the study area, with household waste production of 2.5 kg/day/house and the capacity of the waste collection bin. The results showed that placing a waste collection bin with a capacity of 0.8 m³ with 4 clusters was more effective than 3 clusters with a capacity of 1 m³. TSP optimization resulted in the shortest waste pickup route with 19581 km, thus reducing travel distance and operational time. This approach is expected to increase waste management efficiency in rural areas, support environmental conservation, and optimize waste bank operations.

Keywords

Central point , genetic algorithm , K-Means clustering , traveling salesman problem , waste management

Ethical Statement

This research was conducted following relevant ethical standards. All participants gave informed consent, and the study was conducted in accordance with the ethical guidelines established by Universtias Negeri Semarang

Supporting Institution

This research was supported by the faculty of engineering of Universitas Negeri Semarang through available facilities and resources. Additional support was also provided by the Village Government of Gondangmanis, Kudus, Indonesia who assisted in data collection.

Project Number

This research is part of the final project at Universitas Negeri Semarang and receives no external funding.

Thanks

We would like to thank the Gondangmanis Village Government for their support and cooperation in data collection and community participation in this study

References

• N. Alghanmi, R. Alotaibi, S. Alshammari, A. Alhothali, O. Bamasag, and K. Faisal, “A Survey of Location-Allocation of Points of Dispensing During Public Health Emergencies,” Mar. 10, 2022, Frontiers Media S.A.https://doi.org/10.3389/fpubh.2022.811858.
• A. Hasan and K. Falih, “Using Geographic Information System (GIS) as a Supporting Tool in Public Facilities Planning: A Case Study on the City of Nasiriyah,” European Alliance for Innovation n.o., Mar. 2022. https://doi.org/10.4108/eai.7-9-2021.2315484.
• J. Ortega, S. Moslem, J. Tóth, T. Péter, J. Palaguachi, and M. Paguay, “Using best worst method for sustainable park and ride facility location,” Sustainability (Switzerland), vol. 12, no. 23, pp. 1–18, Dec. 2020, https://doi.org/10.3390/su122310083.
• M. S. Hasibuan, F. Ya, S. Lestari, M. Ariza Eka Yusendra, L. Rahmawati, and Y. S. D. A. Nugroho, “Strategy for Community Empowerment Through an Integrated Waste Bank,” in 2023 International Conference on Smart Applications, Communications and Networking, SmartNets 2023, Institute of Electrical and Electronics Engineers Inc., 2023, https://doi.org/10.1109/SmartNets58706.2023.10215905.
• F. Fatmawati, N. Mustari, H. Haerana, R. Niswaty, and A. Abdillah, “Waste Bank Policy Implementation through Collaborative Approach: Comparative Study—Makassar and Bantaeng, Indonesia,” Sustainability (Switzerland), vol. 14, no. 13, Jul. 2022, https://doi.org/10.3390/su14137974.
• F. C. Mihai, “Waste collection in rural communities: challenges under EU regulations. A case study of Neamt County, Romania,” J Mater Cycles Waste Manag, vol. 20, no. 2, pp. 1337–1347, Apr. 2018, https://doi.org/10.1007/s10163-017-0637-x.
• H. Gutama and F. M. Iresha, “Evaluation of solid waste management effectiveness in Indonesia from 2019-2021: a geographic information system analysis,” in IOP Conference Series: Earth and Environmental Science, Institute of Physics, 2023. https://doi.org/10.1088/1755-1315/1263/1/012067.
• B. Partono, R. Karsidi, M. Yusuf, and Sutarno, “Investigation on the urban and rural students’ behavior for plastic waste management in solo region,” Humanities & Social Sciences Reviews, vol. 8, no. 3, pp. 686–694, Jun. 2020, https://doi.org/10.18510/hssr.2020.8373.
• H. Sanghvi, G. Remesh, and P. M. Korambayil, “Management of accidental thermal burns due to burning of household waste in rural areas of kerala: an institutional study,” Glob J Res Anal, pp. 1–4, Jul. 2020, https://doi.org/10.36106/gjra/3611302.
• Menteri Kehutanan dan Lingkungan Hidup Republik Indonesia, “Peraturan Menteri Lingkungan Hidup dan Kehutanan Republik Indonesia Nomor 14 Tahun 2021 tentang Pengelolaan Sampah pada Bank Sampah,” 2021, Accessed: Nov. 04, 2024. [Online]. Available: https://jdih.maritim.go.id/cfind/source/files/permen-lhk/2021pmlhk014.pdf
• R. Ragiliawati, B. Qomaruddin, and M. A. Rifqi, “Role of Community Leaders as Motivators in Waste Bank Management in Magetan Regency,” Jurnal Promkes: The Indonesian Journal of Health Promotion and Health Education, vol. 8, no. 2, pp. 230–238, 2020, https://doi.org/10.20473/jpk.V8.I2.2020.219-227.
• H. Kamil, F. Akbar, and M. Andriani, “Design of Location-Based Waste Collecting on Enviro Andalas Waste Bank,” JOIV : International Journal on Informatics Visualization, vol. 3, no. 1, pp. 35–40, Jan. 2019, https://doi.org/10.30630/joiv.3.1.212.
• M. Jusman, A. Armin, and N. I. N. Indar, “Determinant Factors Affecting the Implementation and Socio-Economic Impact of Waste Bank Policy in Makassar City,” International Journal Papier Public Review, vol. 2, no. 4, pp. 20–25, Sep. 2021, https://doi.org/10.47667/ijppr.v2i4.108.
• X. Yao and M. Hou, “A study on the investment in the collection and transportation system for domestic waste in rural areas,” in IOP Conference Series: Earth and Environmental Science, Institute of Physics, 2022. https://doi.org/10.1088/1755-1315/1035/1/012011.
• D. Guleryuz, “Evaluation of waste management using clustering algorithm in megacity Istanbul,” Environmental Research and Technology, vol. 3, no. 3, pp. 102–112, 2020, https://doi.org/10.35208/ert.764363.
• D. Ardiatma, P. Lestari, and M. Chaerul, “Real data mapping of DKI Jakarta waste generation using the K-mean Clustering method at final disposal Bantargebang,” in E3S Web of Conferences, EDP Sciences, Feb. 2024. https://doi.org/10.1051/e3sconf/202448502015.
• A. Amalia, M. S. Lydia, S. D. Fadilla, and M. Huda, “Perbandingan Metode Klaster dan Preprocessing Untuk Dokumen Berbahasa Indonesia,” Jurnal Rekayasa Elektrika, vol. 14, no. 1, pp. 35–42, Apr. 2018, https://doi.org/10.17529/jre.v14i1.9027.
• A. E. Amalia, G. Airlangga, and A. N. A. Thohari, “Breast Cancer Image Segmentation Using K-Means Clustering Based on GPU Cuda Parallel Computing,” JURNAL INFOTEL, vol. 10, no. 1, Feb. 2018, https://doi.org/10.20895/infotel.v10i1.344.
• Q. Pu, Q. Wu, and Q. Li, “A K-Means Optimized Clustering Algorithm Based on Improved Genetic Algorithm,” pp. 133–140, 2021, https://doi.org/10.1007/978-981-16-6372-7_16.
• A. K. Tiwari, L. K. Sharma, and G. R. Krishna, “Entropy Weighting Genetic k-Means Algorithm for Subspace Clustering,” Int J Comput Appl, vol. 7, no. 7, pp. 27–30, Oct. 2010, https://doi.org/10.5120/1263-1628.
• T. Parsons, J. Seo, and D. Livesey, “Waste Collection Area Generation Using a 2 Stage Cluster Optimization Process and GIS Data,” IEEE Access, vol. 11, pp. 11849–11859, 2023, https://doi.org/10.1109/ACCESS.2023.3241626.
• A. İ. Karabulut, B. Y. Karabulut, D. Perihan, M. İ. Yeşi̇Lnacar, and H. Pamukçu, “A comparative study on the selection of the most suitable route for the collection and transportation of municipal solid waste,” Environmental Research and Technology, vol. 7, no. 1, pp. 3–12, Mar. 2024, https://doi.org/10.35208/ert.1244707.
• S. Azri, U. Ujang, and N. S. Abdullah, “Within cluster pattern identification: A new approach for optimizing recycle point distribution to support policy implementation on waste management in Malaysia,” Waste Management and Research, vol. 41, no. 3, pp. 687–700, Mar. 2023, https://doi.org/10.1177/0734242X221123489.
• D. P. Kegeografian, I. Artikel, and S. Artikel, “Pengelolaan Sampah di Kota Semarang untuk Menuju Kota Bersih,” 2014, https://journal.unnes.ac.id/nju/JG/article/download/8031/5573.
• S. Laabadi, M. Naimi, H. El Amri, and B. Achchab, “On Solving 0/1 Multidimensional Knapsack Problem with a Genetic Algorithm Using a Selection Operator Based on K-Means Clustering Principle,” Foundations of Computing and Decision Sciences, vol. 47, no. 3, pp. 247–269, Sep. 2022, https://doi.org/10.2478/fcds-2022-0014.
• D. Kučak, V. Juričić, and G. Đambić, “Application of genetic algorithms in higher education area,” in Annals of DAAAM and Proceedings of the International DAAAM Symposium, Danube Adria Association for Automation and Manufacturing, DAAAM, 2019, pp. 343–347. https://doi.org/10.2507/30th.daaam.proceedings.045.
• A. Maghawry, Y. Omar, and A. Badr, “Self-organizing map vs initial centroid selection optimization to enhance k-means with genetic algorithm to cluster transcribed broadcast news documents,” International Arab Journal of Information Technology, vol. 17, no. 3, pp. 316–324, May 2020, https://doi.org/10.34028/iajit/17/3/5.
• Y. C. Cao, Y. Bin Shao, S. L. Tian, and Z. Q. Cai, “A dynamic genetic algorithm for clustering problems,” in Applied Mechanics and Materials, 2013, pp. 1884–1893. https://doi.org/10.4028/www.scientific.net/AMM.411-414.1884.
• J. Liu, Q. Chen, and X. Tian, “Illustration Design Model with Clustering Optimization Genetic Algorithm,” Complexity, vol. 2021, 2021, https://doi.org/10.1155/2021/6668929.
• J. Dai, J. Pang, Q. Luo, and Q. Huang, “Failure Evaluation of Electronic Products Based on Double Hierarchy Hesitant Fuzzy Linguistic Term Set and K-Means Clustering Algorithm,” Symmetry (Basel), vol. 14, no. 12, Dec. 2022, https://doi.org/10.3390/sym14122555.
• J. H. Park, H. S. Moon, H. I. Jung, J. J. Hwang, Y. H. Choi, and J. E. Kim, “Deep learning and clustering approaches for dental implant size classification based on periapical radiographs,” Sci Rep, vol. 13, no. 1, Dec. 2023, https://doi.org/10.1038/s41598-023-42385-7.
• J. Zhao, “An Optimized K-means Algorithm for Text Clustering,” CONVERTER, vol. 2021, no. 3, pp. 545–553, Jul. 2021, https://doi.org/10.17762/converter.85.
• V. Sudarsan and R. Sugumar, “Building a distributed K-Means model for Weka using remote method invocation (RMI) feature of Java,” in Concurrency and Computation: Practice and Experience, John Wiley and Sons Ltd, Jul. 2019. https://doi.org/10.1002/cpe.5313.
• X. Zhou, P. Wang, and Z. Long, “Fault Detection for Suspension System of Maglev Trains Based on Historical Health Data,” IEEE Access, vol. 8, pp. 134290–134302, 2020, https://doi.org/10.1109/ACCESS.2020.3005159.
• T. W. Harjanti, H. Setiyani, J. Trianto, and Y. Rahmanto, “Classification of Mint Leaf Types Based on the Image Using Euclidean Distance and K-Means Clustering with Shape and Texture Feature Extraction,” Tech-E, vol. 5, no. 2, pp. 115–124, Mar. 2022, https://doi.org/10.31253/te.v5i1.940.
• A. Amali and G. T. Pranoto, “Manhattan, Euclidean And Chebyshev Methods In K-Means Algorithm For Village Status Grouping In Aceh Province,” Journal of Applied Intelligent System, vol. 7, no. 3, pp. 211–222, Dec. 2022, https://doi.org/10.33633/jais.v7i3.7037.
• M. A. H. Akhand, S. I. Ayon, S. A. Shahriyar, N. Siddique, and H. Adeli, “Discrete Spider Monkey Optimization for Travelling Salesman Problem,” Applied Soft Computing Journal, vol. 86, Jan. 2020, https://doi.org/10.1016/j.asoc.2019.105887.
• Y. Wang, C. Geng, and Y. Wu, “A Method to Search Traveling Salesman Problem Backbones Based on GA and Frequency Graph”, https://doi.org/10.17706/jcp.14.6.426-437.
• S. Liao, “The Solutions to Traveling Salesman Problem,” Highlights in Science, Engineering and Technology, vol. 47, pp. 136–143, May 2023, https://doi.org/10.54097/hset.v47i.8182.
• S. S. Harahap, P. Sihombing, and M. Zarlis, “Combination of Ant Colony Tabu Search Algorithm with Firefly Tabu Search Algorithm (ACTS-FATS) in Solving the Traveling Salesman Problem (TSP),” Sinkron, vol. 8, no. 1, pp. 212–221, Jan. 2023, https://doi.org/10.33395/sinkron.v8i1.12016.
• N. Boyko and A. Pytel, “Aspects of the Study of Genetic Algorithms and Mechanisms for their Optimization for the Travelling Salesman Problem,” International Journal of Computing, vol. 20, no. 4, pp. 543–550, 2021, https://doi.org/10.47839/ijc.20.4.2442.
• Z. A. Ali, S. A. Rasheed, and N. No’man Ali, “An enhanced hybrid genetic algorithm for solving traveling salesman problem,” Indonesian Journal of Electrical Engineering and Computer Science, vol. 18, no. 2, pp. 1035–1039, 2020, https://doi.org/10.11591/ijeecs.v18.i2.pp1035-1039.
• H. ; Shahrokni, B. ; Van Der Heijde, D. ; Lazarevic, and N. Brandt, “Big Data GIS Analytics Towards Efficient Waste Management in Stockholm,” in Proceedings of the 2014 conference ICT for Sustainability, 2014. https://doi.org/10.2991/ict4s-14.2014.17.
• [44] H. Hmamed, A. Benghabrit, A. Cherrafi, and N. Hamani, “Achieving a Sustainable Transportation System via Economic, Environmental, and Social Optimization: A Comprehensive AHP-DEA Approach from the Waste Transportation Sector,” Sustainability (Switzerland), vol. 15, no. 21, Nov. 2023, https://doi.org/10.3390/su152115372.
• A. N. B. Prasetyo, M. Maimunah, and P. Sukmasetya, “K-Means Clustering Method for Determining Waste Transportation Routes to Landfill,” Jurnal Riset Informatika, vol. 5, no. 3, pp. 277–284, 2023, https://doi.org/10.34288/jri.v5i3.219.
• T. Li, S. Deng, C. Lu, Y. Wang, and H. Liao, “Optimization of Green Vehicle Paths Considering the Impact of Carbon Emissions: A Case Study of Municipal Solid Waste Collection and Transportation,” Sustainability (Switzerland), vol. 15, no. 22, Nov. 2023, https://doi.org/10.3390/su152216128.
• Gubernur Daerah Khusus Ibukota Jakarta, “Peraturan Gubernur Daerah Khusus Ibukota Jakarta Nomor 102 Tahun 2021 Tentang Kewajiban Pengelolaan Sampah di Kawasan dan Perusahaan,” 2021. Accessed: Oct. 04, 2024. [Online]. Available: https://jdih.jakarta.go.id/dokumenPeraturanDirectory/0031/2021PERGUB0031102.pdf
• X. Shen, H. Pan, Z. Ge, W. Chen, L. Song, and S. Wang, “Energy-Efficient Multi-Trip Routing for Municipal Solid Waste Collection by Contribution-Based Adaptive Particle Swarm Optimization,” Complex System Modeling and Simulation, vol. 3, no. 3, pp. 202–219, Sep. 2023, https://doi.org/10.23919/CSMS.2023.0008.