Optimization of LPG Distribution on VRP Using Cheapest Insertion Heuristics Algorithms and Dynamic Programming

Abstract

Determining the most efficient distribution route often encounters difficulties, especially at the LPG gas agency of PT. Cahaya Mentari Bumi Perkasa, where routes are primarily selected based only on the drivers' intuition. The firm manages 35 distribution sites with 3 fleets, each capable of holding 560 cylinders. This study seeks to identify the most efficient distribution route and assess the distribution costs of the company's existing route in comparison to the proposed route, utilizing the Vehicle Routing Problem (VRP) model, constrained by vehicle capacity and fluctuating demand, known as the Capacitated Vehicle Routing Problem (CVRP). The methodology employs the Cheapest Insertion Heuristics (CIH) algorithm to generate the first solution and utilizes Dynamic Programming (DP) as the precise technique for optimal route refinement. The findings indicate that employing Dynamic Programming to enhance the Cheapest Insertion Heuristics method effectively optimizes distribution routes, resulting in roughly 28% reduction in trip distance, 8.2% decrease in journey time, and 19,9% reduction in distribution expenses. The improvement decreased the number of trips from 9 to 8, resulting in enhanced fleet utilization.