OPTIMIZATION OF MEDAN CITY WASTE TRANSPORTATION SYSTEM USING MULTIPLE-TRIP VEHICLE ROUTING PROBLEM (MTVRP) MODEL AND SIMULATED ANNEALING
Abstract
Medan generates approximately 2,000 tons of waste daily, yet only 800 tons are successfully transported to landfills, indicating significant inefficiencies in waste transportation. This study addresses the issue by applying the Vehicle Routing Problem with Multiple Trips (VRPMT) combined with the Simulated Annealing (SA) algorithm to optimize waste transport operations. The VRPMT model allows each vehicle to make multiple daily trips, enhancing fleet utilization while ensuring that all service points are visited, vehicle capacities are not exceeded, and vehicles return to the depot after each trip. The study focuses on Tegal Sari Mandala II (TSM II), Medan Denai, a densely populated neighborhood with narrow roads that require bestari pedicabs for flexible waste collection. Data includes waste collection points, vehicle capacities, transport frequencies, and operational costs. The SA algorithm begins with a random route solution, then iteratively evaluates and improves it by minimizing total distance and cost. It also avoids local optima through a controlled temperature reduction process. Results demonstrate significant improvements: total travel distance was reduced from 12,500 meters to 8,646 meters (a 30.8% reduction), and operational costs decreased from IDR 12,000 to IDR 8,946 (a 25.5% reduction). On average, each bestari pedicab completed two daily trips, maximizing capacity utilization and minimizing penalty costs. The system integrates a structured database and Google Maps API for route visualization, enhancing planning and monitoring. Overall, this approach contributes to more efficient, cost-effective, and environmentally friendly waste transportation. It supports climate action goals and provides a scalable, replicable model for sustainable urban waste management in other regions facing similar logistical challenges. However, this study has some limitations. The VRPMT model was applied only in a neighborhood with a limited vehicle type, which may reduce its generalizability to broader urban areas with more complex logistics. Also, the Simulated Annealing algorithm settings were manually tuned and not benchmarked against other metaheuristic methods. Future studies could improve the model by considering dynamic traffic conditions, integrating real-time data, or testing hybrid optimization approaches to enhance its effectiveness and adaptability.
Downloads
References
“WHAT A WASTE 2.0.” [Online]. Available: https://openknowledge.worldbank.org/handle/10986/2174.
K. Sapanli, F. A. D. Putro, S. D. Arifin, A. H. Putra, H. A. Andamari, and U. Anggraini, “PENGELOLAAN SAMPAH RUMAH TANGGA BERBASIS CIRCULAR ECONOMY DI TINGKAT DESA: PENDEKATAN SISTEM DINAMIK,” Jurnal Wilayah dan Lingkungan, vol. 11, no. 2, pp. 141–155, Aug. 2023, doi: https://doi.org/10.14710/jwl.11.2.141-155.
Kompas.id, “KOTA MEDAN HASILKAN 2.000 TON SAMPAH PER HARI, MAYORITAS BELUM TERTANGANI.” Accessed: Apr. 21, 2025. [Online]. Available: https://medankota.bps.go.id/publication/2023/12/01/123456/statistik-lingkungan-hidup-kota-medan-tahun-2023.html
Badan Pusat Statistik Kota Medan, “STATISTIK LINGKUNGAN HIDUP KOTA MEDAN TAHUN 2023.”
J. Cui, Y. Yan, L. Jiang, L. Zhang, and W. Xu, “RESEARCH ON OPTIMIZATION OF WASTE SORTING AND TRANSPORTATION NETWORK IN SMART CITIES BASED ON GARBAGE VOLUME PREDICTION,” Discover Computing, vol. 28, no. 1, Dec. 2025, doi: https://doi.org/10.1007/s10791-025-09537-x
M. Ghahramani, M. Zhou, A. Molter, and F. Pilla, “IoT-BASED ROUTE RECOMMENDATION FOR AN INTELLIGENT WASTE MANAGEMENT SYSTEM,” Jan. 2022, doi: https://doi.org/10.1109/JIOT.2021.3132126.
V. Fischer, M. P. Paneque, A. Legrain, and R. Bürgy, “A CAPACITATED MULTI-VEHICLE COVERING TOUR PROBLEM ON A ROAD NETWORK AND ITS APPLICATION TO WASTE COLLECTION,” Sep. 2022, [Online]. Available: http://arxiv.org/abs/2209.03644
S. Hariyani and C. Meidiana, “OPTIMIZATION OF WASTE TRANSPORTATION ROUTE AT WASTE TRANSFERS POINT IN LOWOKWARU DISTRICT, MALANG CITY,” in IOP Conference Series: Earth and Environmental Science, Institute of Physics Publishing, May 2018. doi: https://doi.org/10.1088/1755-1315/148/1/012031
H. Karimipour, V. W. Y. Tam, H. Burnie, and K. N. Le, “VEHICLE ROUTING OPTIMIZATION FOR IMPROVING FLEET FUEL EFFICIENCY: A CASE STUDY IN SYDNEY, AUSTRALIA,” International Journal of Environmental Science and Development, vol. 8, no. 11, pp. 776–780, 2017, doi: https://doi.org/10.18178/ijesd.2017.8.11.1056
S. Zhu, H. Yu, Y. Zhang, Y. Zhang, and M. Mac Kinnon, “EDITORIAL: AIR POLLUTION AND CLIMATE CHANGE: INTERACTIONS AND CO-MITIGATION,” Dec. 12, 2022, Frontiers Media S.A. doi: https://doi.org/10.3389/fenvs.2022.1105656
P. Álvarez, A. Serrano-Hernandez, I. Lerga, and J. Faulin, “OPTIMIZING FREIGHT DELIVERY ROUTES: THE TIME-DISTANCE DILEMMA,” Transp Res Part A Policy Pract, vol. 190, Dec. 2024, doi: https://doi.org/10.1016/j.tra.2024.104283.
D. R. Zmaranda, C. I. Moisi, C. A. Győrödi, R. Győrödi, and L. Bandici, “An analysis of the performance and configuration features of mysql document store and elasticsearch as an alternative backend in a data replication solution,” Applied Sciences (Switzerland), vol. 11, no. 24, Dec. 2021, doi: https://doi.org/10.3390/app112411590
A. B. P. S. Neto, C. L. Simões, and R. Simoes, “OPTIMIZATION OF MUNICIPAL SOLID WASTE COLLECTION SYSTEM: SYSTEMATIC REVIEW WITH BIBLIOMETRIC LITERATURE ANALYSIS,” Jul. 01, 2024, Springer. doi: https://doi.org/10.1007/s10163-024-01966-y
H. Wu, B. Yang, and F. Tao, “OPTIMIZATION OF VEHICLE ROUTING FOR WASTE COLLECTION AND TRANSPORTATION,” Int J Environ Res Public Health, vol. 17, no. 14, pp. 1–26, Jul. 2020, doi: https://doi.org/10.3390/ijerph17144963.
H. Hidayatulloh, P. Subarkah, R. D. Dermawan, and M. A. Rohman, “OPTIMIZING THE IMPLEMENTATION OF THE GREEDY ALGORITHM TO ACHIEVE EFFICIENCY IN GARBAGE TRANSPORTATION ROUTES,” JTAM (Jurnal Teori dan Aplikasi Matematika), vol. 7, no. 4, p. 1143, Oct. 2023, doi: https://doi.org/10.31764/jtam.v7i4.16612
Wahyukaton and A. Rochaeni, “SHORTEST ROUTE FOR WASTE TRANSPORTATION IN NORTHERN BANDUNG USING VEHICLE ROUTING PROBLEM-CLARKE AND WRIGHT-SAVING METHOD,” Jun. 2019.
B. A. Santoso, M. Surur, S. Syefudin, and G. Gunawan, “APPLICATION OF DIJKSTRA ALGORITHM TO OPTIMIZE WASTE TRANSPORTATION DISTRIBUTION ROUTES IN TEGAL REGENCY,” vol. 13, no. 1, pp. 81–90, 2024, [Online]. Available: https://www.google.co.id/maps
D. Cattaruzza, N. Absi, and D. Feillet, “VEHICLE ROUTING PROBLEMS WITH MULTIPLE TRIPS. 4OR: A,” Springer Verlag, 2016. [Online]. Available: https://hal-emse.ccsd.cnrs.fr/emse-01250603
Y. Wu, H. Du, and H. Song, “AN ITERATED LOCAL SEARCH HEURISTIC FOR THE MULTI-TRIP VEHICLE ROUTING PROBLEM WITH MULTIPLE TIME WINDOWS,” Mathematics, vol. 12, no. 11, Jun. 2024, doi: https://doi.org/10.3390/math12111712
Y. Li, Z. Yang, S. Zhang, and W. Liu, “A STUDY OF THE CAPACITATED VEHICLE ROUTING PROBLEM WITH TIME-WINDOW AND THREE-DIMENSIONAL LOADING CONSTRAINTS IN LAND–SEA TRANSPORT,” Sustainability (Switzerland), vol. 16, no. 23, Dec. 2024, doi: https://doi.org/10.3390/su162310272
P. Zacharia and S. Stavrinidis, “THE VEHICLE ROUTING PROBLEM WITH SIMULTANEOUS PICK-UP AND DELIVERY UNDER FUZZINESS CONSIDERING FUEL CONSUMPTION,” Vehicles, vol. 6, no. 1, pp. 231–241, Mar. 2024, doi: https://doi.org/10.3390/vehicles6010009
S. Guo, H. Hu, and H. Xue, “A TWO-ECHELON MULTI-TRIP CAPACITATED VEHICLE ROUTING PROBLEM WITH TIME WINDOWS FOR FRESH E-COMMERCE LOGISTICS UNDER FRONT WAREHOUSE MODE,” Systems, vol. 12, no. 6, Jun. 2024, doi: https://doi.org/10.3390/systems12060205
Y. Peng, Y. Zhang, D. Z. Yu, S. Liu, Y. Li, and Y. Shi, “A SWAP-BODY VEHICLE ROUTING PROBLEM CONSIDERING FUEL CONSUMPTION MANAGEMENT AND MULTIPLE VEHICLE TRIPS,” Future Transportation, vol. 4, no. 3, pp. 1000–1021, Sep. 2024, doi: https://doi.org/10.3390/futuretransp4030048
W. F. Mahmudy, A. W. Widodo, and A. H. Haikal, “CHALLENGES AND OPPORTUNITIES FOR APPLYING META-HEURISTIC METHODS IN VEHICLE ROUTING PROBLEMS: A REVIEW †,” Engineering Proceedings, vol. 63, no. 1, 2024, doi: https://doi.org/10.3390/engproc2024063012
V. F. Yu, C. H. Lin, R. S. Maglasang, S. W. Lin, and K. F. Chen, “AN EFFICIENT SIMULATED ANNEALING ALGORITHM FOR THE VEHICLE ROUTING PROBLEM IN OMNICHANNEL DISTRIBUTION,” Mathematics, vol. 12, no. 23, Dec. 2024, doi: https://doi.org/10.3390/math12233664.
Y. Wu, H. Du, and H. Song, “AN ITERATED LOCAL SEARCH HEURISTIC FOR THE MULTI-TRIP VEHICLE ROUTING PROBLEM WITH MULTIPLE TIME WINDOWS,” Mathematics, vol. 12, no. 11, Jun. 2024, doi: https://doi.org/10.3390/math12111712
J. Zhou, M. Zhang, and S. Wu, “MULTI-OBJECTIVE VEHICLE ROUTING PROBLEM FOR WASTE CLASSIFICATION AND COLLECTION WITH SUSTAINABLE CONCERNS: THE CASE OF SHANGHAI CITY,” Sustainability (Switzerland), vol. 14, no. 18, Sep. 2022, doi: https://doi.org/10.3390/su141811498.
Badan Pusat Statistik Kota Medan, “KECAMATAN MEDAN DENAI DALAM ANGKA 2023,” Medan, 2023.
Dinas Lingkungan Hidup kota Medan, “RENCANA AKSI DINAS LINGKUNGAN HIDUP KOTA MEDAN TAHUN ANGGARAN 2023,” 2023.
Copyright (c) 2025 Faridawaty Marpaung, Arnita Arnita, Sri Dewi, Marlina Setia Sinaga, Eri Widyastuti
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:
- Author retain copyright and grant the journal right of first publication with the work simultaneously licensed under a creative commons attribution license that allow others to share the work within an acknowledgement of the work’s authorship and initial publication of this journal.
- Authors are able to enter into separate, additional contractual arrangement for the non-exclusive distribution of the journal’s published version of the work (e.g. 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 websites) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published works.
1.gif)
