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

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.

Automated summary

The distribution density of electricity-charging stations is insufficient in many regions, and there is a need to coordinate the construction of public charging infrastructures in regional networks. This paper presents two approaches for solving the optimal charging station location problem in intercity highway networks. The findings show the effectiveness of the modeling and solution approaches, with the metanetwork-based approach demonstrating computational advantages for large-scale problems. The application of these approaches in a real-world network instance reveals the impact of budget and distance limits on charging station locations and network cost.