Optimization of LPG Gas Cylinder Distribution Costs in the Vehicle Routing Problem Using Dijkstra's Algorithm and Prim's Algorithm

Abstract

This research aims to optimize the distribution costs of 3 kg LPG at PT Irit Gas thru Vehicle Routing Problem modeling. Data for 2024 includes 11 points (1 depot, 10 customers). The cost matrix is formed using Dijkstra's Algorithm on a weighted graph constructed from Haversine distances thru a k-nearest neighbors approach, ensuring that the cost between location pairs reflects the shortest path on the network. Prim's algorithm was then used to build a Minimum Spanning Tree as the basis for distance-efficient customer clustering, which was subsequently cut according to the vehicle capacity limit of 560 tubes per trip, before the visit sequence was reordered based on the shortest distance. The results show three feasible routes: Route 1 (500 tubes) 11.08212 km, Route 2 (550 tubes) 28.11148 km, and Route 3 (480 tubes) 53.13001 km; total 92.32361 km. With an efficiency of 5 km/l and a diesel price of Rp6,800/l, the estimated fuel costs are Rp15,071.68; Rp38,231.61; and Rp72,256.81 respectively (total Rp125,560.11). The findings confirm that the Dijkstra Prim combination effectively produces short, connected, and capacity compliant routes, while also providing realistic operational cost estimates for distribution decision-making.