A hybrid variable neighborhood search for a real-world Petrol Station Replenishment Problem with multi-compartment vehicles

Studies on the Petrol Station Replenishment Problem (PSRP) have many challenges because of the limitations in real-world PSRP, including diverse oil products, various vehicle models, multiple compartments in each vehicle, a finite set of vehicles, restricted tank capacities of petrol stations, and the preparation time and cost for discharge. To address those problems, this paper proposes a novel PSRP model considering the following realistic scenarios: each vehicle has multiple compartments and is allowed for multiple trips; vehicles are heterogeneous; petrol stations have hard time windows; external vehicles can be rented when internal vehicles are not enough; after arrival, each vehicle must prepare for a certain time before discharge. The objective is to minimize the overall costs including vehicles’ fixed costs, traveling costs, and preparation costs. A Hybrid Variable Neighborhood Search algorithm (HVNS) combined with a Simulated Annealing-based acceptance criterion is developed to solve the problem. Various experiments are conducted on different scale instances and a practical application of PetroChina. Experimental results show that compared with CPLEX and other heuristics, HVNS can effectively solve the problem in terms of solution quality and computing time.