Kruskal's MST versus ACO-TSP for Mineral Water Distribution Route Optimization in Manado City
DOI:
https://doi.org/10.32492/nucleus.v5i1.5113Keywords:
Optimasi Rute Terpendek, Minimum Spanning Tree, Kruskal, Floyd-Warshall, Ant Colony Optimization, Travelling Salesman Problem, Distribusi Air Mineral, Kota ManadoAbstract
Efficient distribution route planning is a key factor in reducing logistics costs. This study compares the effectiveness of the Minimum Spanning Tree (MST) using Kruskal and Floyd-Warshall algorithms against the Ant Colony Optimization (ACO) approach combined with the Travelling Salesman Problem (TSP) for optimizing mineral water distribution routes in Manado City, Indonesia. Distance data between six distribution points (one depot and five Indomaret outlets) were obtained from digital maps and modeled as a weighted graph. MST was analyzed manually using Kruskal and Floyd-Warshall algorithms, then validated using POM-QM for Windows 5 software. The results show that MST with Kruskal produces the shortest total distance of 9.14 km, consistent with software validation. In contrast, the ACO-TSP approach yields a longer distance of 18.14 km, or 98.5% longer. Computational complexity analysis reveals the superiority of Kruskal with O(E log E) compared to Floyd-Warshall with O(V³) and ACO with O(n²·t). In conclusion, for small-scale distribution networks with simple topology, the deterministic MST method outperforms the ACO metaheuristic. Managerially, for small-scale distribution networks (≤10 nodes), companies can rely on simple MST algorithms without investing in complex metaheuristic parameter tuning, reducing planning time and computational costs.
References
J. E. Rodriguez dan J. S. L. Tan, "Logistics route optimization: A systematic literature review," Transportation Research Part E: Logistics and Transportation Review, vol. 178, hal. 103256, 2023.
M. Christopher, Logistics & Supply Chain Management, 6th ed. Pearson UK, 2022.
N. F. Margini, I. D. Bagus J.B.S., Belia Tatika A.D., Ichwan Wahyu N., N. A. Teguh., Cost Optimization Using Several Transportation Model Solution Methods for Water Distribution in the PDAM Wae Manurung Bone Regency, IJASEIT, hal 41 – 49, 2026.
T. H. Cormen, C. E. Leiserson, R. L. Rivest, dan C. Stein, Introduction to Algorithms, 4th ed. MIT Press, 2022.
V. A. Kalyagin, A. P. Koldanov, dan P. A. Koldanov, "Reliability of maximum spanning tree identification in correlation-based market networks," Physica A: Statistical Mechanics and its Applications, vol. 599, hal. 127456, 2022.
M. Dorigo dan T. Stützle, Ant Colony Optimization: Overview and Recent Advances. Springer, 2019.
D. E. A. Manuputty, C. E. J. C. Montolalu, dan T. Manurung, "Penentuan jalur terpendek distribusi air mineral menggunakan ant colony optimization," Jurnal Matematika dan Aplikasi, vol. 10, no. 2, hal. 76–82, 2021. (Sinta 3)
K. Deb, Multi-Objective Optimization Using Evolutionary Algorithms. Wiley, 2021. (Scopus Q1)
J. Bossek dan C. Grimme, "Generalised Kruskal mutation for the multi-objective minimum spanning tree problem," Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2024), hal. 133–141, 2024.
S. Dhouib, "Innovative method to solve the minimum spanning tree problem: The Dhouib-Matrix-MSTP (DM-MSTP)," Results in Control and Optimization, vol. 14, hal. 100352, 2024.
R. W. Floyd, "Algorithm 97: Shortest path," Communications of the ACM, vol. 5, no. 6, hal. 345, 1962.
E. R. Ningrum, A. Sanwidi, R. Akbarita, H. Qomaruddin, dan N. U. Blitar, "Optimasi rute pendistribusian gas elpiji menggunakan algoritma Floyd Warshall dan algoritma Greedy," Jurnal Ilmiah Matematika dan Terapan, vol. 20, no. 1, hal. 1–14, 2023. (Sinta 4)
L. Wang, Q. Shi, dan J. Zhang, "Hybrid ant colony optimization with local search for capacitated vehicle routing problem," Swarm and Evolutionary Computation, vol. 78, hal. 101279, 2023. (Scopus Q1)
M. Luo, H. Qin, X. Wu, C. Xiong, D. Xia, dan Y. Ke, "Efficient maintenance of minimum spanning trees in dynamic weighted undirected graphs," Mathematics, vol. 12, no. 7, hal. 1021, 2024.
A. Kumar, R. S. Rao, dan S. K. Singh, "Floyd-Warshall algorithm for evacuation route planning under uncertainty," International Journal of Disaster Risk Reduction, vol. 85, hal. 103512, 2023.
N. Izzati, N. A. M. Nawawi, N. A. S. Abdullah, R. A. Rahman, S. S. S. Ahmad, and A. Basir, "Modelling the shortest path for inner warehouse travelling using the Floyd–Warshall algorithm," Mathematics, vol. 12, no. 17, p. 2698, 2024.
T. Hao, Y. Wu, J. Zhang, and J. Zhang, "Study on a hybrid algorithm combining enhanced ant colony optimization and double improved simulated annealing via clustering in the Traveling Salesman Problem (TSP)," PeerJ Computer Science, vol. 9, p. e1609, 2023.
P. Konwar, M. Gogoi, P. Khongkhlad, and D. Sarkar, "Optimized distribution network reconfiguration using hybrid OPF and graph theory techniques," Facta Universitatis, Series: Electronics and Energetics, vol. 38, no. 3, pp. 487–512, 2025.
V. Murugananthan, M. Yehia, R. Srinivasan, and M. Kavitha, "Traveling Salesman Problem with Ant Colony Optimization," in 2023 2nd International Conference on Edge Computing and Applications (ICECAA), 2023, pp. 481–485.
R. Fathurohman and C. Prianto, "Implementasi algoritma Floyd-Warshall pada sistem rute terpendek: Studi kasus perusahaan logistik," Jurnal Teknik Informatika, vol. 17, no. 1, pp. 45–52, 2024.
Y. N. Dili, E. R. Wulan, dan F. Ilahi, "Penyelesaian masalah transportasi untuk mencari solusi optimal dengan pendekatan minimum spanning tree (MST) menggunakan algoritma Kruskal dan algoritma Prim," KUBIK: Jurnal Publikasi Ilmiah Matematika, vol. 6, no. 1, hal. 44–50, 2021.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2026 Nucleus Journal
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
