Optimal en-route charging station locations for electric vehicles with heterogeneous range anxiety

This paper addresses a new optimal charging station location problem for intercity highway networks where electric vehicles are of heterogeneous driving ranges and usually need to be charged multiple times in their long-haul trips. Driving range heterogeneity can be measured in practice by sampling the driving population under a variety of physical, environmental and psychological conditions and is characterized in this study by a continuous distribution of some appropriate forms. The behavioral assumption underlying this problem is that all individual drivers choose their optimal route-and-charge choices if they can make a trip by driving an electric vehicle or cancel their trips or switch to other transportation modes if they cannot. By explicitly taking into account the impact of limited driving ranges on both route and trip/mode choices, we constructed a mixed integer linear programming model for formulating the charging station location problem, the goal of which is to maximize the networkwide travel efficiency and preference subject to a limited infrastructure investment budget. To tackle this integer programming model, we developed a branch-and-bound algorithm and a neighborhood search heuristic, in both of which a multi-criterion label-correcting algorithm is embedded for deriving the underlying route-and-charge flow pattern. For justifying the effectiveness and efficiency of the proposed algorithms, a synthetic network and two real-world networks are employed as numerical examples. The computational results obtained from the numerical analysis show that the heuristic is capable of obtaining optimal solutions in most test scenarios and is much more computationally efficient than the branch-and-bound algorithm, with a computing time that is only about one tenth of the latter.