With the rapid growth of the electric vehicle (EV) market, the demand for efficient charging infrastructure has become a critical challenge. In China EV adoption is accelerating, necessitating smart solutions for charging station allocation to ensure sustainability and user convenience. This paper addresses the optimization of electric vehicle charging distribution in smart cities, focusing on minimizing total charging costs while maximizing resource utilization. We propose a novel model based on a hybrid assignment search procedure (HASP) that efficiently allocates electric vehicles to charging stations by considering driving distance, charging fees, and walking distance. The model integrates real-time communication between electric vehicles and service providers, ensuring dynamic adjustments based on traffic conditions and station occupancy. As electric vehicle penetration increases in urban areas, optimizing charging distribution becomes essential to prevent grid overloads and enhance user experience. This work contributes to the development of smart city infrastructures by providing a scalable solution for electric vehicle charging management.
The core of our approach involves formulating the electric vehicle charging distribution as a generalized assignment problem, where tasks (EVs) are assigned to agents (charging stations) to minimize overall costs. We consider a smart city region with multiple charging stations and destinations, where each electric vehicle communicates its location, battery state, and required charging time. The model ensures that assignments adhere to station capacities and battery constraints, promoting efficient use of resources. In China EV policies emphasize the integration of renewable energy and smart grids, making our model highly relevant. Below, we present the mathematical formulation, followed by a detailed description of the state transition process and queueing model for predicting station availability. The integration of these elements allows for a robust optimization framework that adapts to real-world scenarios.
The electric vehicle charging distribution problem is defined as follows: Let \( S \) be the set of charging stations, \( F \) the set of final destinations, and \( V \) the set of electric vehicles, with \( i \in S \), \( j \in F \), and \( k \in V \). The objective function minimizes the total charging cost, which includes costs related to driving distance, charging fees, and walking distance. The decision variable \( b_{ki} \) is a binary indicator that equals 1 if electric vehicle \( k \) is assigned to charging station \( i \), and 0 otherwise. The objective function is given by:
$$ \min f(x) = \sum_{k=1}^{n} \sum_{i=1}^{m} b_{ki} \left( C_D D_{ki} + C_W \sum_{j=1}^{r} W_{ij} \right) + \sum_{k=1}^{n} \sum_{i=1}^{m} b_{ki} C_i T_{Ck} $$
where \( n \) is the total number of electric vehicles, \( m \) is the total number of charging stations, and \( r \) is the number of destinations. \( C_D \) is the cost coefficient per unit driving distance, \( D_{ki} \) is the driving distance between electric vehicle \( k \) and charging station \( i \), \( C_W \) is the cost coefficient per unit walking distance, \( W_{ij} \) is the walking distance between charging station \( i \) and destination \( j \), \( C_i \) is the charging cost per unit time at station \( i \), and \( T_{Ck} \) is the required charging time for electric vehicle \( k \). This formulation ensures that the model accounts for both monetary and temporal costs, which are crucial for user satisfaction in China EV ecosystems.
The optimization is subject to several constraints. First, each electric vehicle must be assigned to exactly one charging station:
$$ \sum_{i=1}^{m} b_{ki} = 1 \quad \forall k $$
Second, the number of electric vehicles assigned to a charging station cannot exceed its number of charging piles:
$$ \sum_{k=1}^{n} b_{ki} \leq N_{si} \quad \forall i $$
where \( N_{si} \) is the total number of charging piles at station \( i \). Third, an electric vehicle can only be assigned to a charging station if its initial remaining battery charge \( Q_{rk} \) is sufficient to cover the driving distance, considering the energy consumption per unit distance \( \Delta E_k \):
$$ \frac{Q_{rk}}{\Delta E_k} \geq D_{ki} \quad \text{if } b_{ki} = 1 $$
Finally, the decision variables are binary:
$$ b_{ki} \in \{0,1\} $$
These constraints ensure the feasibility of the assignment, addressing key concerns in electric vehicle deployment, such as range anxiety and station congestion. In China EV infrastructure planning often involves similar constraints to balance demand and supply.
To handle the dynamic nature of electric vehicle charging requests, we model the state transition process from charging request to connection. When an electric vehicle enters a predefined allocation region centered around its final destination, a charging request is initiated. The allocation radius is adjusted based on the driver’s remaining battery charge and station occupancy rates. The remaining time \( R_i \) for the driver to reach the destination after charging is computed as:
$$ R_i = t^*(O_i, F_i) – t(O_i, P_i) – \Delta T_{Ji} $$
where \( t^*(O_i, F_i) \) is the estimated travel time from the electric vehicle’s current position \( O_i \) to the final destination \( F_i \), \( t(O_i, P_i) \) is the actual travel time to the assigned charging station \( P_i \), and \( \Delta T_{Ji} \) is a time error due to traffic congestion. If \( R_i \) exceeds the maximum walking time \( T_{wi} \), the driver has sufficient time; otherwise, adjustments are made to prioritize charging stations closer to the destination. This process ensures timely arrivals and efficient allocations, which is vital for promoting electric vehicle adoption in dense urban areas like those in China EV initiatives.
We also develop a queueing model to estimate the availability of charging stations, using a continuous-time Markov process. Each charging station is modeled as an M/M/c/c queue, where EV arrivals and departures follow Poisson processes with rates \( \lambda \) and \( \mu \), respectively, and \( c \) is the number of charging piles. The state \( x(t) \) represents the number of available charging piles at time \( t \). The transition probability matrix \( Q \) defines the rates between states, and the probability of having at least one available charging pile at time \( t + \tau \) is given by:
$$ P(S_j > 0) = 1 – w_0(\tau) $$
where \( w_0(\tau) \) is the probability of zero available charging piles, derived from the initial state distribution \( w_{si} \) and the transition probabilities \( P_{Sij}(\tau) = e^{Q\tau} \). This model helps predict station occupancy, enabling proactive allocations for electric vehicles. The integration of this queueing model with the optimization framework enhances the realism of our approach, particularly for high-demand scenarios in China EV markets.
Our solution method, the hybrid assignment search procedure (HASP), combines a greedy randomized adaptive search procedure (GRASP) for generating high-quality initial solutions with genetic algorithm operators and a Swap algorithm to enhance diversity and convergence. HASP starts by creating an initial population using GRASP, which incorporates heuristic rules to favor assignments with lower costs. The genetic algorithm phase involves selection, crossover, and mutation operations, where parent solutions are combined to produce offspring with inherited traits. The Swap algorithm introduces local search by exchanging assignments between electric vehicles to escape local optima. This hybrid approach balances intensification and diversification, leading to improved solutions for the electric vehicle charging distribution problem. The pseudocode for HASP is summarized in the following table:
| Step | Description |
|---|---|
| 1 | Initialize population using GRASP with cost-based heuristics. |
| 2 | Evaluate fitness (total charging cost) for each solution. |
| 3 | Select parents based on fitness proportional selection. |
| 4 | Apply crossover to generate offspring, inheriting random features. |
| 5 | Perform mutation by swapping assignments between EVs. |
| 6 | Update population and repeat until convergence. |
This method is computationally efficient and scalable, making it suitable for large-scale electric vehicle networks in smart cities. In China EV applications, such algorithms can be deployed in real-time management systems to optimize charging operations.
We evaluate the performance of HASP through simulations based on real-world spatial environments. The test instances are divided into three scenarios with varying numbers of electric vehicles and charging stations, as shown in the table below. These instances are derived from benchmark data to ensure comparability. We compare HASP with other heuristic algorithms, including the bees algorithm (BA), taboo search (TABU), and an improved differential evolution algorithm (DE-SK). The performance metrics are the best fitness (minimum total charging cost) and the percentage of instances where each algorithm achieves the optimal solution.
| Scenario | EV Count | Charging Station Count | Instance Count |
|---|---|---|---|
| 1 | 10–50 | 5–25 | 6 |
| 2 | 100–200 | 5–20 | 6 |
| 3 | 100–400 | 5–40 | 9 |
The results demonstrate that HASP consistently achieves the lowest total charging costs across all instances, outperforming the other algorithms. For example, in Scenario 1, HASP matches the optimal fitness values obtained by DE-SK, but in Scenarios 2 and 3, it shows superior performance, especially in larger instances. The following table summarizes the best fitness values for each algorithm in selected instances, highlighting HASP’s effectiveness. Note that NaN indicates failure to find a feasible solution.
| Scenario | Instance | BA Fitness | TABU Fitness | DE-SK Fitness | HASP Fitness |
|---|---|---|---|---|---|
| 1 | 1 | 1687 | NaN | 1687 | 1687 |
| 1 | 2 | 3224 | NaN | 3224 | 3224 |
| 2 | 1 | 1832 | 1832 | 1832 | 1832 |
| 2 | 5 | 2816 | 2817 | 2816 | 2816 |
| 3 | 7 | NaN | 5598 | 5598 | 5598 |
| 3 | 9 | NaN | 4248 | 4244 | 4242 |
Overall, HASP achieves a 100% success rate in finding the optimal solution across all instances, compared to 90.5% for DE-SK, 80.9% for BA, and 47.6% for TABU. The average computation time for HASP is 254.8 seconds, which is competitive with DE-SK (246.8 seconds) and significantly lower than TABU (745.6 seconds). This efficiency makes HASP suitable for real-time applications in dynamic electric vehicle environments. The robustness of HASP is further validated through fitness-cloud analysis, which shows a positive regression slope, indicating consistent improvement in solution quality over iterations. This analysis confirms that HASP’s operators effectively enhance search capabilities, leading to better allocations for electric vehicles.
In conclusion, we have developed an optimization model for electric vehicle charging distribution in smart cities that minimizes total charging costs while ensuring efficient resource utilization. The model incorporates driving distance, charging fees, and walking distance into a comprehensive objective function, constrained by station capacities and battery levels. The HASP algorithm, with its hybrid approach, demonstrates superior performance in finding optimal assignments compared to other heuristics. This work supports the growth of the electric vehicle market, particularly in China EV contexts, by providing a scalable and adaptive solution for charging infrastructure management. Future research could explore integration with renewable energy sources and dynamic pricing models to further enhance the sustainability of electric vehicle ecosystems.