Kruskal's MST versus ACO-TSP for Mineral Water Distribution Route Optimization in Manado City - Nastasia F. Margini; Rizqa Azhaara; Sulistyo Wati; Tsabita Imania (Universitas Darul Ulum, 2026)
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.