Distribution Planning of LPG to Gas Stations in the Aegean Region

Abstract

This study considers the application of LPG distribution to stations in the Aegean region in Turkey. There is a distribution center in Aliaga which collects the orders and distributes LPG to the gas stations. The problem is to determine the shortest routes with the minimum number of trucks at minimum cost. This problem was modeled as a vehicle routing problem and then extended to capacitated vehicle routing problem with time windows (CVRPTW) to increase the service quality and adapt the problem to real life. The small size models were solved by CPLEX Optimization Studio. It was not possible to obtain optimal solutions for problem instances with 41 stations and larger number of gas stations since respective problems are NP-hard. Therefore several heuristics are applied to solve the problem such as Clarke and Wright algorithm Nearest Neighborhood and The Best Decision (TBD) algorithms. Clarke and Wright and Nearest Neighborhood heuristics are already defined in literature. However TBD heuristics is a novel approach proposed in this study. Computational results shows that Clarke and Wright algorithm is found to give the best results to solve the CVRPTW problem. A user friendly decision support system is developed to implement the heuristics to solve the problem.