Optimization of Urban Waste Collection Routes Using the Held-Karp Algorithm in a Web and Mobile-Based System
Abstract
In 2023, the Environmental Agency of Palu City recorded a total waste production of 97,492 tons, of which 10.4% was plastic waste. The Palu City Government operates a fleet of garbage trucks on a predetermined collection schedule. However, garbage bins frequently overflow before their scheduled pickup, resulting in extended waste accumulation and inefficiency. This study proposes a web and mobile-based system to enhance waste management by integrating bin condition reporting and shortest route calculation for collecting full bins. The Held-Karp algorithm is utilized to address the Travelling Salesman Problem (TSP) for determining optimal collection routes. The system was developed using Golang, Flutter, ReactJS, and a MySQL database. API functionality was validated using Postman, and overall system functionality was tested using the black-box method. A case study involving 8 test points (1 starting point, 10 waste collection points, and 1 endpoint) demonstrated that the proposed system reduces travel time by up to 21.74%, costs by 22.29%, fuel consumption by 21.16%, and distance traveled by 21.16% compared to conventional methods. These results highlight the potential of the system to significantly optimize waste collection operations and support sustainable urban waste management practices.
Downloads
References
M. Ridwan, “DLH Palu: Presentase sampah plastik di Kota Palu 10,4 persen.” [Online]. Available: https://sulteng.antaranews.com/berita/277314/dlh-palu-presentase-sampah-plastik-di-kota-palu-104-persen
E. Utari, M. Fatimatuzzahra, M. Pramaisyella, S. Jaedah, and T. Triana, “Analisis Pengelolaan Sampah Akibat Pertumbuhanpenduduk Dan Perkembangan Pembangunandi Kelurahan Cipare Kota Serang,” vol. 10, no. 1, pp. 556–562, 2022.
Z. Ursani and A. A. Ursani, “Augmented tour construction heuristics for the travelling salesman problem,” vol. 4, no. 2, pp. 131–144, 2023.
J. Nalepa, Smart Delivery System Solving Complex Vehicle Routing Problems. Elsevier, 2020.
A. Izzah, B. A. Nugroho, W. F. Mahmudy, and F. A. Bachtiar, “Optimasi Asymmetric City Tour di Kota Kediri Menggunakan Ant Colony System,” J. Nas. Tek. Elektro dan Teknol. Inf., vol. 9, no. 1, 2020.
M. Kurniawan, Farida, and A. Siti, “Rute Terpendek Algoritma Particle Swarm Optimization Dan Brute Force Untuk Optimasi Travelling Salesman Problem Muchamad,” J. Tek. Inform., vol. 14, no. 2, pp. 191–200, 2021.
A. Held-karp, H. Alfin, K. Diah, and K. Wardhani, “Aplikasi Android Untuk Mencari Jalur Tercepat Pada Pengiriman Barang Dengan Algortma Held-Karp,” J. Appl. Informatics Comput., vol. 4, no. 2, 2020.
G. Righini and G. Righini, “Efficient optimization of the Held–Karp lower bound,” Open J. Math. Optim., vol. 2, pp. 0–17, 2021.
S. Lestari, A. P. Giovani, and D. Dwijayanti, “Dijkstra Algorithm Implementation In Determining Shortest Route To Mosque In Residential Citra Indah City,” J. PILAR Nusa Mandiri, vol. 16, no. 1, pp. 65–70, 2020, doi: 10.33480/pilar.v16i1.1199.
Suardinata, R. Rusmi, and M. A. Lubis, “Determining Travel Time and Fastest Route Using Dijkstra Algorithm and Google Map,” Sist. J. Sist. Inf., vol. 11, no. 1, pp. 496–505, 2022.
D. F. Gimnastian, R. Yasirandi, and D. Oktaria, “Analysis and Design of a Route Recommendation System and Bicycle Rental Fees at Tourist Destinations with Genetic Algorithms,” J. Inform. BUDIDARMA, vol. 6, no. April, pp. 837–847, 2022, doi: 10.30865/mib.v6i2.3749.
M. Arifin, “Genetic Algorithm Approach to Logistics Transportation and Distribution Problems : A Case Study of Parcel Delivery Services,” J. Optimasi Sist. Ind., vol. 14, no. 2, pp. 122–128, 2021.
H. M. Asih, S. A. Rahman, K. Usandi, Q. A. E. Saputra, and A. Della, “Enhancing logistics e fficiency : A case s tudy of genetic algorithm- based route optimization in distribution problem,” J. Optimasi Sist. Ind., vol. 16, no. 2, 2023.
S. Cokrowibowo and A. Irianti, “Model Penentuan Rute Terpendek Penjemputan Sampah Menggunakan Metode MTSP dan Algoritma Genetika,” J. Appl. Comput. Sci. Technol. ( JACOST ), vol. 2, no. 1, pp. 43–48, 2021.
R. Sistem, “Jurnal RESTI Implementasi Golang dan New Simple Queue pada Sistem Sandbox Pihak Ketiga Berbasis REST API,” vol. 1, no. 10, pp. 7–8, 2021.
M. Jindan, H. R. Ngemba, S. Hendra, and R. Laila, “Integrated Web-based Palu City Blood Donor Service Application Model Using ReactJS and ExpressJS,” vol. 5, no. 3, pp. 1–8, 2023.
J. O. Notohamidjojo, K. Blotongan, and K. Sidorejo, “Aplikasi Penjualan Tiket Kelas Pelatihan Berbasis Mobile menggunakan Flutter,” vol. 5, pp. 281–295, 2019.
A. R. Dzikrillah, “Database-Based Gui System To Increase The Effectiveness Of Student Data Management In The Fkip Uhamka Dormitory,” vol. 5, no. 4, pp. 21–31, 2024.
K. Nisa, C. Hapsari, Y. Y. Joefrie, and S. Hendra, “MERN Implementation in Online Quiz Applications to Recognize and Avoid Social Media Hoaxes,” vol. 6, no. 2, pp. 1–8, 2024.
P. D. Atika, A. Yunizar, P. Yusuf, and F. Nidaul, “Android-Based Shortest Path Finding Using A-Star ( A *) Algorithm in Bekasi City,” vol. 9, no. 28, pp. 197–210, 2021.
M. H. Muslim, F. Harvianto, and S. Utama, “Penerapan Metode SCRUM dalam Pengembangan Sistem Informasi Layanan Kawasan,” vol. 6, pp. 365–378, 2020.
R. Sistem, “Pengembangan Aplikasi Tiga-Tingkat Menggunakan Metode Scrum pada Aplikasi Presensi Karyawan Glints Academy,” vol. 5, pp. 169–176, 2022.
Copyright (c) 2025 Tiara Juli Arsita, Nouval Trezandy Lapatta, Yuri Yudhaswana Joefri, Dwi Shinta Angreni, Septiano Anggun Pratama
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Authors who publish with this journal agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License (Attribution-ShareAlike 4.0 International (CC BY-SA 4.0) ) that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
