Optimization of Urban Waste Collection Routes Using the Held-Karp Algorithm in a Web and Mobile-Based System - Arsita, Tiara Juli; Lapatta, Nouval Trezandy; Joefri, Yuri Yudhaswana; Angreni, Dwi Shinta; Pratama, Septiano Anggun (Journal of Applied Informatics and Computing, 2025)
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.