Optimizing Staple Food Distribution Efficiency using the Traveling Salesman Problem in Local Government
DOI:
https://doi.org/10.47776/nuai.v1i2.1679Keywords:
Traveling salesman problem, Distribution route optimization, Python programming, Distance matrix, Route search algorithmAbstract
The equitable distribution of essential goods in Indonesia’s remote and archipelagic regions faces significant logistical challenges, primarily due to geographical complexity, limited transportation infrastructure, and unpredictable weather conditions. This study adopts the Travelling Salesman Problem (TSP) model to optimize inter-island aid distribution routes, with delivery locations modeled as a complete weighted graph. Inter-location distances are calculated using the Haversine formula based on actual geographical coordinates. The Path Cheapest Arc heuristic algorithm, implemented via Google OR-Tools, is employed to efficiently generate near-optimal routes. The optimization results show a reduction in travel distance by 22.7% (from 256.7 km to 198.4 km), accompanied by a decrease in estimated travel time from 10.27 hours to 7.94 hours, and a reduction in fuel consumption from 102.7 liters to 79.4 liters. These findings empirically demonstrate that TSP optimization can significantly reduce travel distance and distribution time in the context of maritime logistics. The integration of graph theory, optimization algorithms, and interactive route visualization not only enhances computational efficiency but also provides practical benefits for policymakers in the public sector. This methodological framework has the potential to be replicated for distribution scenarios in other remote regions, while also strengthening data-driven decision-making in governmental logistics planning.
References
[1] P. E. Syaputra, “Kajian Integrasi Transportasi Multi Moda Untuk Menekan Biaya Logistik Pada Wilayah Kepulauan: Studi Kasus Pada Pulau Bawean,” J. Transp., vol. 24, no. 1, pp. 49–61, 2024.
[2] E. Nurjati, “Peran dan tantangan e-commerce sebagai media akselerasi manajemen rantai nilai produk pertanian,” in Forum Penelitian Agro Ekonomi, 2021, pp. 115–133.
[3] M. I. Irmansyah and R. Takaya, “Optimalisasi Pengiriman Last-Mile Di Rantai Pasokan Perkotaan Menggunakan Algoritma Heuristik,” J. Ilm. Multidisiplin Terpadu, vol. 8, no. 7, 2024.
[4] A. Sumarsa and M. Widyastiti, “Penerapan Traveling Salesman Problem with Time Windows dalam Pendistribusian Produk,” in Prosiding Seminar Nasional Pendidikan Matematika, 2022, pp. 1–6.
[5] S. Nurminarsih, “Pengembangan Model dan Algoritma Dynamic-Inventory Ship Routing Problem (D-ISRP) dengan Mempertimbangkan Tingkat Kesibukan Pelabuhan.” Surabaya: Institut Teknologi Sepuluh Nopember, 2015.
[6] H. M. Asih, R. A. C. Leuveano, A. Rahman, and M. Faishal, “Traveling Salesman Problem With Prioritization for Perishable Products in Yogyakarta, Indonesia,” J. Adv. Manuf. Technol., vol. 16, no. 3, 2022.
[7] H. Fachrudin, “Optimasi Penentuan Rute Perjalanan Sales pada UD. Aster.” Universitas Islam Majapahit, 2019.
[8] C. Chen et al., “Perbandingan Implementasi Evolutionary Algorithm (EPO, FHO, dan CFA) pada Kasus Travelling Salesman Problem untuk Tempat Pariwisata di Surabaya,” INSYST J. Intell. Syst. Comput., vol. 5, no. 1, pp. 23–38, 2023.
[9] I. N. Wardhana, “Optimasi Rute Distribusi Gas Transport Module (Gtm) Menggunakan Vehicle Routing Problem (Vrp).” Institut Teknologi Sepuluh Nopember, 2018.
[10] R. H. Solehudin, Business Intelligence dan Analisis Kuantitatif-Damera Press. Damera Press, 2025.
[11] H. W. N. S. Nazry, F. Riza, F. Rizky, Z. A. Gultom, M. Haris, and M. D. B. Barus, “Model Optimasi Model Optimasi Rute Transportasi Berbasis Pemrograman Linear,” J. Sist. Inf. Triguna Dharma (JURSI TGD), vol. 4, no. 1, pp. 75–81, 2025.
[12] A. P. Peranginangin, “Analysis of Graph Theory in Transport Network Optimisation : A Mathematical Approach and Its Applications,” vol. 10, no. 4, pp. 1431–1439, 2025.
[13] A. Amin and B. Hendrik, “Analisis Penerapan Algoritma Dijkstra dalam Optimasi Penentuan Rute: Sebuah Kajian Literatur Sistematis,” J. Educ. Res., vol. 6, no. 1, pp. 100–106, 2025.
[14] J. Ahmad and M. Nadhir Ab Wahab, “Enhancing the safety and smoothness of path planning through an integration of Dijkstra’s algorithm and piecewise cubic Bezier optimization,” Expert Syst. Appl., vol. 289, p. 128315, 2025, doi: https://doi.org/10.1016/j.eswa.2025.128315.
[15] M. Iqbal, A. Damayanti, N. T. Maulani, N. L. P. Wardhani, and M. G. Rahman, “Implementasi Graf Hamilton pada Travelling Salesman Problem dari Kantor Walikota ke Setiap Kantor Kecamatan di Kota Salatiga,” Realis. J. Educ. Math. Sci., vol. 2, no. 2, pp. 84–91, 2024.
[16] R. Nasiboglu, “Dijkstra solution algorithm considering fuzzy accessibility degree for patch optimization problem,” Appl. Soft Comput., vol. 130, p. 109674, 2022, doi: https://doi.org/10.1016/j.asoc.2022.109674.
[17] W. Y. Oeitama, W. Y. Oeitama, F. F. Sitandi, and S. Mas’ ud, “Optimasi Rute Pendistribusian Barang Menggunakan Kombinasi Algoritma Branch and Bound dan Cheapest Insertion Heuristic,” Sq. J. Math. Math. Educ., vol. 6, no. 2, pp. 89–104, 2024.
[18] C. R. Gunawan, “Optimization of the Travelling Salesman Problem Based on Genetic Algorithm with Adaptive Crossover and Mutation Probabilitie,” J. Ilmu Komput. dan Sist. Inf., vol. 3, no. 3, pp. 234–242, 2024.
[19] A. Y. Nugroho, A. Suyitno, and R. Arifudin, “Perbandingan Algoritma Branch And Bound Dan Algoritma Genetika Untuk Mengatasi Travelling Salesman Problem (Tsp)(Studi Kasus Pt. Jne Semarang),” UNNES J. Math., vol. 5, no. 2, pp. 135–143, 2016.
[20] R. Ramadhan, L. R. Kristiana, and H. K. Pambudi, “Perancangan Rute Distribusi Produk Pestisida Dengan Menggunakan Software or Tools Untuk Meminimasi Jarak Tempuh Dan Biaya Transportasi Di PT ABC,” eProceedings Eng., vol. 12, no. 2, pp. 3223–3230, 2025.
[21] T. D. Arsyad, M. D. C. Nababan, R. K. Imburi, and P. Harliana, “Implementasi Algoritma Dijkstra dalam Mencari Rute Terpendek dari Universitas Negeri Medan ke Museum Negeri Sumatera Utara,” JATI (Jurnal Mhs. Tek. Inform., vol. 9, no. 1, pp. 235–242, 2025.
[22] D. B. Paillin and J. M. Tupan, “Model Integer Liniear Programming (ILP) dalam Pemecahan Traveling Salesman Problem (TSP)(Studi Kasus: PT. Paris Jaya Mandiri Ambon),” ALE Proceeding, vol. 3, pp. 40–47, 2020.
Downloads
Published
Issue
Section
License
Copyright (c) 2025 Moh Jufri, Nasrullah, Asyatir Rodiyah
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
© 2025 The Author(s). Published by Faculty of Engineering and Computer Science, Universitas Nahdlatul Ulama Indonesia. This is an open access article under the CC BY-NC-ND license, which permits use and distribution in any medium, provided the original work is properly cited, the use is non-commercial, and no modifications or adaptations are made.
