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

¹ School of Traffic and Transportation, Beijing Jiaotong University, No. 3 Shangyuancun, Haidian District, Beijing 100044, P.R. China
² Business Administration Division, Seaver College, Pepperdine University, 24255 Pacific Coast Hwy, Malibu, CA 90263, USA

^* Corresponding author: fang.tian@pepperdine.edu

Received: 13 March 2023
Accepted: 12 January 2025

Abstract

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.