A hybrid adaptive large neighborhood search and tabu search algorithm for the electric vehicle relocation problem

• An Electric Vehicle Relocation Problem is studied. • Violations of the triangle inequality are considered. • A hybrid adaptive large neighborhood search and tabu search algorithm is proposed. • A tailored duration computation method is devised. • Computational experiments verify the effectiveness of the proposed algorithm. With the raising environmental worries, the sharing economy and electric vehicles gain popularity rapidly. It is crucial to relocate vehicles to make them available for customers in the car-sharing system. In this paper, we study the electric vehicle relocation problem where the triangle inequality may not hold. The objective is to determine the routing schedules for staffs to re-balance the spatial and temporal distribution of electric vehicles with the highest total profit of the relocated requests. Constraints including time windows, limited durations and charging requirements are considered. To solve this problem, we develop a hybrid adaptive large neighborhood search and tabu search algorithm, where a tailored duration computation scheme is embedded. Extensive computational experiments are conducted based on randomly generated instances. The results demonstrate the competitive performance of our algorithm both in solution quality and solving time.