Multiple Charging Station Location Routing Problem with Time Window of Electric Vehicle
This paper presents the electric vehicle (EV) multiple charging station location routing problem with time window to optimize the routing plan of capacitated EVs and the strategy of charging stations. In particular, the strategy of charging stations includes both infrastructure type selection and station location decisions. The problem accounts for two critical constraints in logistic practice: the vehicle loading capacity and the customer time windows. A hybrid heuristic that incorporates an adaptive variable neighborhood search (AVNS) with the tabu search algorithm for intensification was developed to address the problem. The specialized neighborhood structures and the selection methods of charging station used in the shaking step of AVNS were proposed. In contrast to the commercial solver CPLEX, experimental results on small scale test instances demonstrate that the algorithm can find nearly optimal solutions on small scale instances. The results on large scale instances also show the effectiveness of the algorithm.