Abstract: With the increasingly serious situation of environmental protection and energy conservation, electric vehicles (EVs) are becoming an ideal transportation source of many logistic service companies for their outstanding cleanliness and energy efficiency. The battery exchange station location and vehicle routing problem (ELRP) are investigated in this paper. To solve the problem, an integer programming model is established and a two-stage hybrid algorithm for the new problem is proposed. The algorithm first locates battery exchange stations using tabu search with two different tabu criteria. It then determines the routing plan by using a modified Clarke-Wright saving heuristic. The computational experiments firstly compare the two different aspiration criteria. Extensive comparison experiments with CPLEX have been conducted on random generated instances and shows that our algorithm is more efficient to obtain high-quality solutions. Finally, two sensitivity analyses on vehicle capacity and driving range are presented. The results show that the increase in vehicle capacity or the improvement in driving range is beneficial to cut down the total cost. Further more, the sensitivity analysis on the unit construction cost tells that increasing construction cost per station may also lead to less located stations and higher shipping cost number of located stations.

Key words: electric vehicles, location, vehicle routing, heuristic algorithm