Optimal station locations for en-route charging of electric vehicles in congested intercity networks: A new problem formulation and exact and approximate partitioning algorithms

This paper addresses a new electricity-charging station location problem for congested intercity or regional networks, in which electric vehicles with a limited driving range require recharges for their long-distance trips. When the distribution of charging stations does not sufficiently cover all used routes, some drivers may take a detour to find charging opportunities (or switch to another transportation mode). The goal of this station location problem is to find, under a limited construction budget, an optimal set of charging station locations such that all vehicles finish their trips by choosing a self-optimal route with necessary charging opportunities while the overall network congestion caused by possible detours is minimized. The problem is written as a bi-level mixed nonlinear integer programming model, where the upper level of the model is set to regulate the selection of station locations subject to the construction budget while the lower level is used to characterize the equilibrium flow pattern of electric vehicles with the charging requirement. Selected exact and approximate algorithms, namely, the branch-and-bound algorithm and the nested partitions algorithm are adopted to solve this station location problem. While both algorithms imply a divide-and-conquer strategy, the branch-and-bound algorithm poses a deterministic, exact procedure that utilizes the bounding mechanism to prune impossible solution subspaces, whereas the nested partitions algorithm performs a stochastic search and selection process in terms of the optimality probability for near-optimal solutions. To get numerical insights on the algorithmic performance and solution behavior, we test these algorithms through a couple of benchmark network instances. A performance comparison of the algorithms indicates that, the branch-and-bound algorithm can quickly obtain the global optimum when the driving range is relatively low, while the nested partitions algorithm can find optimal solutions or extremely near-optimal solutions in all cases and typically spend on average only one fourth of the computing time of the branch-and-bound algorithm. The network flow solutions clearly show, compared to gasoline vehicle drivers, how an insufficient driving range or number of charging stations may significantly reduce the number of feasible paths and force electric vehicle drivers to choose more costly paths, which thus reshapes flow patterns and possibly increases congestion levels.