Variable Neighborhood Search heuristic for the Inventory Routing Problem in fuel delivery

摘要

In this paper we observe the extension of the vehicle routing problem (VRP) in fuel delivery that includes petrol stations inventory management and which can be classified as the Inventory Routing Problem (IRP) in fuel delivery. The objective of the IRP is to minimize the total cost of vehicle routing and inventory management. We developed a Variable Neighborhood Search (VNS) heuristic for solving a multi-product multi-period IRP in fuel delivery with multi-compartment homogeneous vehicles, and deterministic consumption that varies with each petrol station and each fuel type. The stochastic VNS heuristic is compared to a Mixed Integer Linear Programming (MILP) model and the deterministic “compartment transfer” (CT) heuristic. For three different scale problems, with different vehicle types, the developed VNS heuristic outperforms the deterministic CT heuristic. Also, for the smallest scale problem instances, the developed VNS was capable of obtaining the near optimal and optimal solutions (the MILP model was able to solve only the smallest scale problem instances).