Hybrid tabu search algorithm for mobile charging stations serving electric vehicles under road traffic conditions

Abstract

The large scale deployment of electric vehicles (EVs) aimed at improving transport systems in smart cities, can be found as an alternative to eliminate $C O_{2}$ emissions and sonorous pollution. However, the need for high power charging stations, the limited range of EV batteries, and travel times heavily influenced by road traffic conditions, raise new operational challenges. In this context, this paper focuses on the planning of mobile charging station (MCS) routes to serve EVs requesting charging at their location. This problem is modeled as a variant of the vehicle routing problem with time windows (VRPTW), enriched by constraints related to road traffic and electric mobility. Thus, a hybrid Tabu Search metaheuristic algorithm is proposed to solve the problem, integrating road mobility through traffic-dependent travel times. The performance of the proposed solution and the importance of considering road conditions are evaluated using a set of $\mathbf{5 6}$ Solomon reference instances. The results are analyzed by instance groups, C1, C2, R1, R2, RC1, and RC2, highlighting the effectiveness and robustness of the proposed approach.