Optimasi Rute dalam Meminimalkan Jarak Pengiriman Menggunakan Algoritma Boruvka (Studi Kasus: UMKM Matari Nadya, Kota Blitar)

Abstract

Matari chips are traditional snacks by UMKM, including Matari Nadya UMKM in Blitar City, which faces challenges in determining the optimal delivery route to minimize mileage. This research applies Boruvka's algorithm to find a Minimum Spanning Tree (MST) that connects all destination points with the shortest distance. Boruvka's algorithm works with the principle of iterative merging; each component in the graph selects the edge with the most negligible weight until all points are merged into one element with the minimum total weight. The data used includes the geographical coordinates of 21 points connected by 31 edges, and optimization is performed using the Python programming language. The results showed that Boruvka's algorithm successfully formed an MST with a final graph having 21 nodes and 20 edges and a total MST weight of 49.55 km. Applying this algorithm to the delivery route, including the return route, reduced the distance traveled from 60.5 km to 53.74 km, resulting in a savings of 6.76 km. If the delivery cannot be made in one trip, the route is divided into two subroutes with distances of 32.72 km and 22.28 km, respectively, resulting in a total distance of 55 km. Although there is an increase in distance of 1.26 km compared to the MST return route, this division provides an alternative solution if deliveries are made in stages. Thus, the Boruvka algorithm has been proven to help MSMEs design more optimal and structured distribution routes.