A Hybrid Guided Local Search for the Vehicle-Routing Problem with Intermediate Replenishment Facilities

We propose a three–step algorithmic framework for solving a new variant of the vehicle–routing problem (VRP) called the vehicle–routing problem with intermediate replenishment facilities (VRPIRF). The aim of this problem is to determine optimal routes for a fleet of vehicles that can renew their capacity at intermediate replenishment stations. Although this problem is often met in real–life scenarios of transportation logistics, it has not received much attention by researchers. Our proposed framework employs a combination of algorithmic blocks based on powerful metaheuristic methodologies designed to achieve a desirable intensification and diversification interplay. In the first step of the solution approach, the initial solution is obtained by a cost–saving construction heuristic. In the second step, the initial solution is improved by employing tabu search within the variable neighborhood search methodology. Finally, guided local search is applied in the third step, to eliminate low–quality features from the final solution produced. The proposed algorithmic framework was successfully applied to benchmark instances in the literature, generating several new best solutions. To motivate the proposed algorithmic choices and test the robustness of the algorithm, we also developed new classes of VRPIRF benchmark instances with diverse problem characteristics.