A multi-depot periodic vehicle routing model for petrol station replenishment

The petrol station replenishment problem consists in delivering fuel oils from a set of storage depots to a set of petrol stations during a few days planning horizon. This problem is addressed by an oil company which, for example, has to decide simultaneously the weekly fuel oil replenishment plan for each station, and, for each day of the week, the tank truck (vehicle) routes from depots to stations, in order to deliver the planned fuel oil replenishment amounts to petrol stations. Assuming a fleet of homogeneous tank trucks, the aim is to minimize the total distance travelled by tank trucks during the week, while loading tank trucks possibly near to their capacity in order to maximize the resource utilization. We model the problem as a generalization of the Multi-Depot Periodic Vehicle Routing Problem (MDPVRP) and provide a mathematical formulation. Due to the large size of the real instances which the company has to deal with, we solve the problem heuristically. We propose a hybrid genetic algorithm that successfully address the problem. The algorithm is derived from a known hybrid genetic algorithm for the MDPVRP, and adopts additional techniques and features tailored for the particular fuel oil distribution problem. It is specifically designed to deal with real instances derived from the fuel oil distribution in the European context that are profoundly different from the MDPVRP instances available from the literature. The proposed algorithm is evaluated on a set of real case studies and on a set of randomly generated instances that hold the same characteristics of the former.