Abstract
The increasing concern over global warming has led to the rapid development of the electric vehicle industry. Electric vehicles (EVs) have the potential to reduce the greenhouse effect and facilitate more efficient use of energy resources. In this paper, we investigate some optimal EV route planning problems that take into consideration of possible battery charging or swapping operations. Given a road network, the objective is to determine the shortest route that a vehicle with a given battery capacity can take to travel between a pair of vertices or to visit a set of vertices with several stops, if necessary, at battery switch stations. We present polynomial time algorithms for the EV shortest path problem and a fixed tour EV touring problem, where the fixed tour problem requires visiting a set of vertices in a given order. Based on the result, we also propose constant factor approximation algorithms for the EV touring problem, which is a generalization of the traveling salesman problem.