Route Optimization for Liquefied Petroleum Gas (LPG) Distribution with the Savings Matrix and Nearest Neighbour Heuristics

This study examines a company that distributes 3 kg LPG cylinders and experiences inefficiencies in its delivery operations due to the absence of systematic route planning. Such inefficiencies contribute to extended travel distances and increased operational costs. To address this issue, heuristic optimization techniques, specifically the Savings Matrix and the Nearest Neighbour algorithms, were applied to design more efficient distribution routes aimed at minimizing travel distance, delivery time, and operational costs. The company’s baseline routes resulted in an average monthly travel distance of 1,330 km with a distribution cost of IDR 6,718,635. Implementation of the Savings Matrix reduced the distance to 1,005 km, a 24.44% reduction, and lowered costs to IDR 6,103,924, equivalent to 9.14% savings. In comparison, the Nearest Neighbour algorithm achieved a distance of 1,067 km, reflecting a 19.77% reduction, and costs of IDR 6,221,569, corresponding to 7.39% savings. Both methods demonstrated efficiency improvements, with the Savings Matrix yielding the greatest reductions in travel distance and operational cost. The results confirm that heuristic optimization can substantially enhance delivery performance. In particular, the Savings Matrix method offers a practical decision-support tool for logistics companies seeking to improve route planning, minimize expenditures, and implement cost-effective distribution strategies.