Abstract:

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, cancel their trips, or switch to other transportation modes if they cannot. The study developed a mixed integer linear programming model to optimize charging station location, considering limited driving ranges and trip/mode choices. The model includes a branch-and-bound algorithm and neighborhood search heuristic, with a multi-criterion label-correcting algorithm for determining the route-and-charge flow pattern. To justify 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.