Optimal en-route charging station locations for electric vehicles: A new modeling perspective and a comparative evaluation of network-based and metanetwork-based approaches

• Analyze the connection and difference between for the network-based and metanetwork-based approaches for the optimal en-route charging station location problem. • Introduce subpaths and station-subpath metanetworks for modeling en-route charging station location problems; • Establish the solution equivalence between the proposed node-link network-based model and station-subpath metanetwork-based model; • Prove analytically the network cost monotonicity property with charging station addition, budget limit increase and distance limit increase; • Justify numerically the metanetwork-based algorithm outperforming the network-based algorithm in the branch-and-bound framework; and. • Reveal the impacts of budget limit and distance limit on individual route-and-charge choice and network performance and accessibility. In many regions across the world, the distribution density of electricity-charging stations is yet sufficient for taming the range anxiety concern of electric vehicle drivers. In such driving circumstances, making detours to find alternative charging opportunities is often an operational remedy to accomplish long-distance trips. To reduce the frequency and extra mileage of detouring, public charging infrastructures should be coordinately sited and constructed in a regional network. With the goal of minimizing the possible detour mileage, this paper describes an optimal charging station location problem for intercity highway networks and develops two approaches for modeling and solving it. Specifically, two mixed linear integer programming models are constructed in different network modeling paradigms: The first one is formed and solved on the basis of the original node-link network topology , with newly introduced integer variables such as path and subpath activation indicators to quantify the utilization status of paths and subpaths, respectively. The classic branch-and-bound algorithm encapsulating a bi-criteria label-correcting algorithm is designed for solving this network-based model. The other one is formulated and solved relying on the station-subpath metanetwork topology , as the result of a two-phase process that decomposes an individual routing and charging decision into two parts. The two phases are conducted on the node-link network and station-subpath metanetwork levels, respectively, where the first phase is done by solving a network-based, distance-constrained minimum-cost path problem, while the second phase collapses to a metanetwork-based, simple minimum-cost path problem. The findings we obtained through conducting this research are twofold: First, analytical and computational studies clearly identify the effectiveness of the two modeling and solution approaches, while the metanetwork-based approach exhibits its appealing computing advantage for solving problems of large size; second, the application of the solution approaches for a real-world network instance reveals how budget limit and distance limit impact the charging station locations, individual routing and charging decisions, and network cost and accessibility levels.