An Adaptive Large Neighborhood Search for relocating vehicles in electric carsharing services

Abstract We propose an Adaptive Large Neighborhood Search metaheuristic to solve a vehicle relocation problem arising in the management of electric carsharing systems. The solution approach, aimed to optimize the total profit, is tested on three real-like benchmark sets of instances. It is compared with a Tabu Search, ad hoc designed for this work, with a previous Ruin and Recreate metaheuristic and with the optimal results obtained via Mixed Integer Linear Programming. We also develop bounding procedures to evaluate the solution quality when the optimal solution is not available.