TY - JOUR
T1 - The fuel replenishment problem: a split-delivery multi-compartment vehicle routing problem with multiple trips
AU - Wang, L.
AU - Kinable, Joris
AU - van Woensel, Tom
PY - 2020/6
Y1 - 2020/6
N2 - The Fuel Replenishment Problem (FRP) is a multi-compartment, multi-trip, split-delivery VRP in which tanker trucks transport different types of petrol, separated over multiple vehicle compartments, from an oil depot to petrol stations. Large customer demands often necessitate multiple deliveries. Throughout a single working day, a tanker truck returns several times to the oil depot to resupply. A solution to the FRP involves computing a delivery schedule of minimum duration, thereby determining for each vehicle (1) the allocation of oil products to vehicle compartments, (2) the delivery routes, and (3) the delivery patterns. To solve FRP efficiently, an Adaptive Large Neighborhood Search (ALNS) heuristic is constructed. The heuristic is evaluated on data from a Chinese petroleum transportation company and compared against exact results from a MILP model and lower bounds from a column generation approach. In addition, we perform sensitivity analysis on different problem features, including the number of vehicles, products, vehicle compartments and their capacities. Computational results show that the ALNS heuristic is capable of solving instances with up to 60 customers and 3 different products in less than 25 minutes with an average optimality gap of around 10%. On smaller instances, the heuristic finds optimal solutions in significantly less time than the exact MILP formulation.
AB - The Fuel Replenishment Problem (FRP) is a multi-compartment, multi-trip, split-delivery VRP in which tanker trucks transport different types of petrol, separated over multiple vehicle compartments, from an oil depot to petrol stations. Large customer demands often necessitate multiple deliveries. Throughout a single working day, a tanker truck returns several times to the oil depot to resupply. A solution to the FRP involves computing a delivery schedule of minimum duration, thereby determining for each vehicle (1) the allocation of oil products to vehicle compartments, (2) the delivery routes, and (3) the delivery patterns. To solve FRP efficiently, an Adaptive Large Neighborhood Search (ALNS) heuristic is constructed. The heuristic is evaluated on data from a Chinese petroleum transportation company and compared against exact results from a MILP model and lower bounds from a column generation approach. In addition, we perform sensitivity analysis on different problem features, including the number of vehicles, products, vehicle compartments and their capacities. Computational results show that the ALNS heuristic is capable of solving instances with up to 60 customers and 3 different products in less than 25 minutes with an average optimality gap of around 10%. On smaller instances, the heuristic finds optimal solutions in significantly less time than the exact MILP formulation.
KW - Adaptive large neighborhood search
KW - Fuel replenishment
KW - Multi-compartment
KW - Multi-trip
KW - Split-delivery
KW - Vehicle routing
UR - http://www.scopus.com/inward/record.url?scp=85079639721&partnerID=8YFLogxK
U2 - 10.1016/j.cor.2020.104904
DO - 10.1016/j.cor.2020.104904
M3 - Article
VL - 118
JO - Computers & Operations Research
JF - Computers & Operations Research
SN - 0305-0548
M1 - 104904
ER -