Fuel Distribution Route Optimization Model Based On Hybrid Cheapest Insertion–Tabu Search

Purpose – This study aims to optimize the fuel distribution routes of PT Pertamina Patra Niaga Sei Siak by comparing the performance of the Cheapest Insertion Heuristic (CIH) and Tabu Search (TS) algorithms in minimizing total distance, travel time, and operational costs. Methodology– The research employs a quantitative–computational approach using operational data collected from real distribution activities in Pekanbaru, Riau Province. A Vehicle Routing Problem (VRP) model was developed with constraints on vehicle capacity, service time, and depot–station relations. CIH and TS algorithms were implemented using Python for comparative optimization. Validation was performed through correlation analysis between baseline and computational results. Findings – The results demonstrate that the Tabu Search algorithm significantly improved route efficiency, reducing total distance and travel time by 27.2% and 26.6% in Shift 2, and by 5.1% and 4.5% in Shift 1 compared to existing routes. The integration of CIH as an initial heuristic seed improved TS convergence stability, with optimal solutions achieved within the 13th iteration. Cost analysis indicates that the optimization yields daily savings of approximately IDR 119,600 per vehicle, leading to substantial monthly reductions in total logistics expenses. Practical Implications – The hybrid CIH–TS framework provides an adaptive and computationally efficient decision-support tool for PT Pertamina Patra Niaga to design shorter, faster, and more economical delivery routes. The approach is scalable and can be integrated into real-time routing systems to improve service reliability and operational sustainability. Originality– This study is among the first to apply a hybrid heuristic–metaheuristic approach to the Indonesian fuel-distribution industry using real operational data. The novelty lies in the empirical validation of algorithmic optimization within a live logistics network, demonstrating tangible economic and time-based efficiency improvements that support national energy-distribution reliability.