With the rapid proliferation of electric vehicles (EVs) globally, the strategic placement and sizing of EV charging stations have become critical to supporting sustainable transportation and smart grid development. The location and capacity determination problem for EV charging stations is inherently nonlinear and multi-objective, involving conflicting goals such as minimizing investment costs for operators while maximizing service quality for users. Traditional single-model approaches often fail to capture the complexity of this problem, leading to suboptimal solutions that either increase operational expenses or result in poor user satisfaction. In this paper, we propose a novel methodology based on a bi-level model to address the EV charging station location and capacity determination challenge. Our approach integrates an upper-level model focused on EV charging station cost optimization and a lower-level model prioritizing user charging efficiency, solved using an immune genetic algorithm to ensure robust and adaptive solutions. By leveraging this framework, we aim to achieve a balanced outcome that reduces overall system costs, optimizes grid resource utilization, and enhances the EV charging experience for end-users.
The core of our methodology lies in the formulation of a bi-level programming model that distinctly separates the perspectives of EV charging station operators and EV users. The upper-level model targets the minimization of comprehensive costs associated with EV charging station deployment, including land acquisition, construction, maintenance, and grid expansion expenses, while simultaneously maximizing service coverage. Conversely, the lower-level model focuses on minimizing user-centric costs, such as charging expenses, travel costs to EV charging stations, and potential losses due to unmet charging demands. This dual-layer structure allows for a holistic optimization that accounts for both economic viability and user convenience. To solve this complex model, we employ an immune genetic algorithm, which incorporates mechanisms like antibody affinity calculation, memory cell updates, and concentration inhibition to avoid premature convergence and maintain population diversity. Through iterative evolution, the algorithm generates a Pareto-optimal solution set, from which the best EV charging station location and capacity plan is selected. Experimental validation on urban datasets demonstrates that our method significantly outperforms existing approaches in terms of cost reduction, grid capacity optimization, and user wait time minimization, establishing its practicality for real-world EV charging infrastructure planning.
Bi-Level Model Formulation for EV Charging Station Location and Capacity Determination
We model the urban road network as a graph to facilitate the EV charging station location and capacity determination process. Let the network be represented as $$ S = (U, I) $$, where $$ U $$ denotes the set of nodes (potential locations for EV charging stations) and $$ I $$ represents the set of edges (paths between nodes). This graph-based approach ensures that the selected EV charging station sites are accessible and aligned with the grid’s expansion capabilities. The bi-level model consists of two interconnected sub-models: the upper-level EV charging station model and the lower-level user model, each with distinct objectives and constraints.
Upper-Level EV Charging Station Model
The upper-level model aims to minimize the total cost for EV charging station operators while maximizing service quality, quantified as the coverage area of EV charging stations. The comprehensive cost minimization objective is defined as follows:
$$ \min D = D_l + D_r + D_g + D_k + D_u $$
Here, $$ D_l $$ is the land cost, $$ D_r $$ is the construction cost, $$ D_g $$ is the maintenance cost for EV charging station equipment, $$ D_k $$ is the grid expansion cost, and $$ D_u $$ is the user cost, which is further elaborated in the lower-level model. For the upper-level, we exclude $$ D_u $$ and focus on the first four components, expressed as:
$$ D_l = \sum_{m \in u} s_l \times z_i \times R_i $$
$$ D_r = \sum_{m \in u} (s_{1l} \times z_i + s_{2l} \times z_i \times R_i) $$
$$ D_g = \sum_{m \in u} (s_{1l} \times z_i + s_{2l} \times z_i \times Z_p) $$
$$ D_k = \sum_{m \in u} [s_{1l} \times z_i \times (Z_p – c_{i,\max}) + s_{2l} \times z_i] $$
In these equations, $$ s_l $$ is the land cost per EV charging station, $$ z_i $$ is a binary variable indicating the selection of node $$ i $$ for an EV charging station, $$ R_i $$ is the daily maintenance cost, $$ s_{1l} $$ and $$ s_{2l} $$ are fixed and variable construction costs, respectively, $$ Z_p $$ is the power load over a specified period, and $$ c_{i,\max} $$ is the maximum power load at node $$ i $$. The index $$ m $$ represents a random factor, and $$ u $$ denotes the rated power load.
To quantify service quality, we define the coverage distance $$ G $$ between adjacent EV charging stations on the same route as:
$$ G = \beta \times \sum_{m \in u} f(r_{i+1}, r_i) $$
where $$ \beta $$ is a distance parameter between neighboring EV charging stations, and $$ f(r_{i+1}, r_i) $$ is the distance between nodes $$ i+1 $$ and $$ i $$. The maximum power supply capacity of a single EV charging station, $$ \max L $$, is constrained by the total charging demand of EVs in the service area:
$$ \max L = \sum_{i=1}^{N} R_{Li} \times G $$
Here, $$ R_{Li} $$ is the charging demand per EV, and $$ N $$ is the number of EVs. Additionally, to ensure practicality, the distance between any two EV charging stations must not exceed the maximum travel distance $$ D_{\max} $$ of EVs, leading to the constraint:
$$ \text{s.t. } G \leq D_{\max} $$
This upper-level model ensures that EV charging stations are economically viable and provide adequate coverage, forming a foundation for the integrated bi-level approach.
Lower-Level User Model
The lower-level model prioritizes the user perspective by minimizing the total cost incurred by EV users when accessing EV charging stations. The objective function is defined as:
$$ \min D_u = D_1 + D_2 + D_3 $$
where $$ D_1 $$ is the charging cost per EV (dependent on the EV charging station’s power rate and the vehicle’s remaining battery), $$ D_2 $$ is the travel cost to reach an EV charging station (based on distance and location), and $$ D_3 $$ is the loss cost due to unmet charging needs. To reflect user accessibility, we impose a constraint on the maximum distance $$ L_{u,\max} $$ that an EV can travel to reach an EV charging station:
$$ \text{s.t. } f(u, i) \leq L_{u,\max} $$
Here, $$ f(u, i) $$ is the distance from user node $$ u $$ to EV charging station node $$ i $$. By integrating this with the upper-level model, we form the complete bi-level model $$ M $$ for EV charging station location and capacity determination:
$$ M = \min D + \max L + \min D_u $$
This model captures the trade-offs between operator costs and user benefits, enabling a balanced solution for EV charging station deployment.
Solution Using Immune Genetic Algorithm
To solve the bi-level model for EV charging station location and capacity determination, we employ an immune genetic algorithm that combines the global search capabilities of genetic algorithms with the adaptive mechanisms of immune systems. This algorithm effectively handles the nonlinearity and multi-objective nature of the problem by maintaining diversity and avoiding local optima. The key steps include antibody encoding, affinity calculation, memory cell updates, and selection, crossover, and mutation operations.
First, we encode antibodies as binary strings representing potential solutions for EV charging station locations. Each antibody corresponds to a set of selected nodes in $$ U $$, with a length equal to the number of decision variables. The initial population is generated randomly, considering constraints such as the maximum distributed generation capacity to ensure feasibility. The fitness of each antibody is evaluated using an adapted function that incorporates both cost and service quality metrics:
$$ p’_f = \frac{f_g \times \left( \sum_{i=1}^{I} n_i + l_s + \kappa \right)}{\sum_{g=0}^{N-1} f_g} $$
In this equation, $$ f_g $$ is the fitness value for antibody $$ g $$, $$ n_i $$ is the number of users served by EV charging station $$ i $$, $$ I $$ is the total number of EV charging station nodes, $$ l_s $$ is the average distance between EV charging stations, and $$ \kappa $$ is the user demand coverage rate. This fitness function ensures that solutions with lower costs and higher service quality are favored.
Next, we compute the antibody affinity $$ K_g $$ to measure similarity between solutions, using the Euclidean distance between antibody vectors:
$$ K_g = \sum_{g=1}^{N} (x_{yg} – x_{ug})^2 $$
where $$ x_{yg} $$ and $$ x_{ug} $$ represent coordinates in the solution space. Antibodies with high affinity are promoted, while those with high concentration are suppressed to maintain diversity. The concentration probability $$ p_d $$ for an antibody is given by:
$$ p_d = \frac{1}{N} \left(1 – \frac{t}{N}\right) $$
where $$ t $$ is the number of similar antibodies. Memory cells are updated periodically to retain high-quality solutions, enhancing the algorithm’s convergence.
The selection, crossover, and mutation operations are then applied. Selection uses a roulette-wheel method based on fitness values, crossover employs multi-point techniques to generate offspring, and mutation introduces random changes to explore new solutions. The steps of the immune genetic algorithm for solving the EV charging station model are summarized as follows:
- Input antigens: Parameters such as distributed generation capacity and number of EV charging stations.
- Generate initial population: Random binary strings representing potential EV charging station locations.
- Calculate fitness: Evaluate each antibody using the adapted fitness function.
- Compute antibody affinity: Measure similarity between solutions.
- Update memory cells: Retain top-performing solutions for future iterations.
- Promote and suppress antibodies: Based on affinity and concentration to avoid premature convergence.
- Perform selection, crossover, and mutation: Evolve the population toward better solutions.
- Merge parent and offspring populations: Form a new generation for the next iteration.
- Check termination conditions: If met, output the optimal EV charging station location and capacity plan; otherwise, repeat from step 3.
This iterative process ensures that the algorithm efficiently navigates the solution space, resulting in a Pareto-optimal set for EV charging station deployment.
Experimental Validation and Analysis
To validate the effectiveness of our proposed method for EV charging station location and capacity determination, we conducted experiments using real-world urban data from a representative city district. The experimental setup involved simulating a network with 1,000 EVs and 100 potential EV charging stations, each with a power rating of 50 kW. The maximum service radius for each EV charging station was set to 5 km, with an average daily charging demand of 30 kWh per EV. We compared our method against two existing approaches: a method based on improved particle swarm optimization (PSO) and another using a simulated annealing-Dijkstra algorithm. Performance was evaluated based on economic costs, grid impact, and user wait times.
The economic costs of EV charging station deployment across seven test zones are summarized in Table 1. Our method consistently achieved lower total costs compared to the benchmark methods, demonstrating its cost-effectiveness in EV charging station planning.
| Test Zone | Proposed Method | PSO-Based Method | Simulated Annealing-Dijkstra Method |
|---|---|---|---|
| 01 | 452 | 550 | 623 |
| 02 | 359 | 428 | 489 |
| 03 | 225 | 360 | 457 |
| 04 | 288 | 417 | 551 |
| 05 | 374 | 699 | 765 |
| 06 | 524 | 874 | 969 |
| 07 | 269 | 335 | 410 |
| Total | 2491 | 3663 | 4264 |
In terms of grid impact, we analyzed the substation capacity and total load under different EV charging station location plans. The substation capacity utilization is a critical indicator of grid stability; our method optimized the capacity to prevent overloading, as shown by the higher allowable capacity in our results. The total load capacity also improved, indicating better resource allocation. The substation capacity $$ C_s $$ and total load $$ T_l $$ can be modeled as:
$$ C_s = \sum_{i=1}^{I} z_i \times P_i \times \eta $$
$$ T_l = \sum_{i=1}^{I} R_{Li} \times \delta_i $$
where $$ P_i $$ is the power capacity of EV charging station $$ i $$, $$ \eta $$ is the efficiency factor, and $$ \delta_i $$ is the load factor. Our method achieved a 15-20% improvement in substation capacity and a 10-15% increase in total load capacity compared to the other methods, reducing the need for costly grid upgrades.
User wait time is another vital metric for EV charging station service quality. We measured the average wait time per user for eight EV charging stations under each method. Our approach significantly reduced wait times, with an average of 5-7 minutes per user, compared to 10-12 minutes for the PSO-based method and 12-15 minutes for the simulated annealing-Dijkstra method. This reduction is attributed to the optimal distribution of EV charging stations, which minimizes congestion and maximizes accessibility. The wait time $$ W_t $$ can be expressed as a function of the number of EVs $$ N_{ev} $$ and the service rate $$ \mu $$ of EV charging stations:
$$ W_t = \frac{N_{ev}}{\mu \times I} $$
By optimizing the location and capacity of EV charging stations, our method ensures a higher service rate, leading to shorter wait times and enhanced user satisfaction.
Conclusion and Future Work
In this paper, we have presented a comprehensive bi-level model for EV charging station location and capacity determination, solved using an immune genetic algorithm. Our approach effectively balances the economic objectives of EV charging station operators with the service needs of EV users, resulting in solutions that minimize costs, optimize grid resources, and reduce user wait times. Experimental results confirm the superiority of our method over existing techniques, making it a valuable tool for urban planners and utility companies in deploying EV charging infrastructure.
For future research, we plan to extend this work by incorporating dynamic traffic flow patterns and real-time electricity pricing into the model. This will enhance the adaptability of EV charging station plans to fluctuating demand and grid conditions. Additionally, we aim to integrate renewable energy sources, such as solar-storage systems, into the EV charging station network to promote sustainability and resilience. By advancing these aspects, we can further improve the efficiency and environmental friendliness of EV charging station deployment, contributing to the broader goals of smart cities and clean energy transitions.