In recent years, the rapid growth of electric vehicle (EV) adoption has highlighted the need for efficient energy replenishment infrastructure. Battery swap stations (BSS) offer a promising solution by enabling quick battery replacement, reducing downtime compared to traditional charging. In China, the EV market has expanded significantly, with over 20.74 million electric vehicles on the road as of mid-2024. However, the development of BSS infrastructure lags, with only 3,878 stations nationwide. This disparity underscores the importance of optimizing BSS location planning to maximize coverage and minimize costs. We address the electric vehicle battery swap station location problem (BSSLP), which is NP-hard, by proposing a reduction-based backtracking algorithm that ensures optimal solutions while improving computational efficiency.
The BSSLP involves selecting sites for battery swap stations from candidate locations to serve demand points, such as residential areas or transportation hubs. The objective is to minimize total operational costs, including distance-based expenses, while adhering to constraints like construction budgets, station capacity, and minimum distance requirements between stations. Given the complexity of this problem, traditional methods like genetic algorithms or particle swarm optimization often fail to guarantee optimality. Our approach integrates mathematical properties with a backtracking algorithm to reduce problem size and enhance solution speed. This method is particularly relevant for China EV infrastructure development, where efficient planning can accelerate EV adoption and support sustainable transportation.
In this paper, we first formulate a mathematical model for the BSSLP based on real-world scenarios. We then derive key mathematical properties that allow for problem size reduction. Subsequently, we design sub-algorithms for allocation, upper bounds, and lower bounds, which are embedded into a reduction-based backtracking algorithm. Finally, we demonstrate the algorithm’s effectiveness through random and real-case studies, showing its superiority over existing methods like branch-and-bound, ant colony optimization, and genetic algorithms.
Problem Description
The electric vehicle battery swap station location problem focuses on strategically placing stations to meet EV users’ demands while minimizing costs. We consider a bipartite graph where demand points (e.g., urban centers) and candidate BSS locations are connected based on proximity and capacity. The goal is to select a subset of candidate sites to open, ensuring that all demand is satisfied without exceeding station capacities or violating distance constraints. Key factors include construction costs, operational expenses, and user convenience, which are critical for China EV infrastructure planning.
Mathematical Model
Let \( E = \{e_1, e_2, \ldots, e_m\} \) be the set of demand points with demands \( D_i \), and \( F = \{f_1, f_2, \ldots, f_n\} \) be the set of candidate BSS locations with capacities \( t_j’ \) and construction costs \( c_j \). The decision variable \( x_j \) equals 1 if station \( f_j \) is opened, and 0 otherwise. The allocation variable \( y_{ij} \) represents the demand from \( e_i \) served by \( f_j \). The model is formulated as follows:
Minimize the total operational cost:
$$ Z = \sum_{i=1}^{m} \sum_{j=1}^{n} y_{ij} \cdot d_{ij} $$
Subject to:
$$ \sum_{j=1}^{n} c_j x_j \leq T \quad \text{(Budget constraint)} $$
$$ \sum_{j=1}^{n} x_j \leq H \quad \text{(Number of stations constraint)} $$
$$ x_i \cdot x_j \cdot d(f_i, f_j) \geq d_{\text{min}} \cdot x_i \cdot x_j \quad \forall i, j \quad \text{(Minimum distance constraint)} $$
$$ \sum_{i=1}^{m} y_{ij} \leq t_j’ \quad \forall j \quad \text{(Capacity constraint)} $$
$$ \sum_{j=1}^{n} y_{ij} = D_i \quad \forall i \quad \text{(Demand satisfaction)} $$
$$ x_j \in \{0,1\} \quad \forall j $$
Here, \( d_{ij} \) is the distance between demand point \( e_i \) and candidate station \( f_j \), and \( d(f_i, f_j) \) is the distance between stations. The parameter \( T \) is the total budget, \( H \) is the maximum number of stations, and \( d_{\text{min}} \) is the minimum allowable distance between any two stations.
Notations and Symbols
| Set | Description |
|---|---|
| \( E \) | Set of demand points, \( E = \{e_i \mid i=1,2,\ldots,m\} \) |
| \( F \) | Set of candidate BSS locations, \( F = \{f_j \mid j=1,2,\ldots,n\} \) |
| \( G = (V, X) \) | Bipartite graph of demand points and candidate stations |
| \( N(v_i) \) | Neighbor set of node \( v_i \) in the graph |
| \( F_0, FF_0 \) | Sets of stations that are closed or assumed closed |
| \( F_1, FF_1 \) | Sets of stations that are open or assumed open |
| \( F_5, FF_5 \) | Sets of undecided stations |
| \( E_1, E_3, E_5 \) | Sets of demand points based on allocation status |
| Parameter | Description |
|---|---|
| \( d_{\text{min}} \) | Minimum distance between stations |
| \( L \) | Minimum number of stations required |
| \( H \) | Maximum number of stations allowed |
| \( D_i \) | Demand at point \( e_i \) |
| \( d_{ij} \) | Distance between \( e_i \) and \( f_j \) |
| \( t_j’ \) | Capacity of station \( f_j \) |
| \( t_j \) | Remaining capacity of station \( f_j \) |
| \( \text{best\_q} \) | Best objective value found |
| \( ub, lb \) | Upper and lower bounds |
| Variable | Description |
|---|---|
| \( x_j \) | 1 if station \( f_j \) is open, 0 otherwise |
| \( y_{ij} \) | Allocation from \( e_i \) to \( f_j \) |
Mathematical Properties
We derive several mathematical properties to reduce problem size and improve algorithm efficiency. These properties help identify stations that must be open or closed, thereby simplifying the solution space.
Property 1: Let stations be sorted in descending order of capacity. If the sum of the first \( L-1 \) stations’ capacities is less than total demand, and the sum of the first \( L \) stations’ capacities meets or exceeds total demand, then at least \( L \) stations are required to cover all demand. This is fundamental for China EV networks where demand is high.
Property 2: If the number of open stations \( |F_1 \cup FF_1| > H \), the solution is infeasible. Similarly, if \( |FF_5| = 0 \) and \( |F_1 \cup FF_1| < L \), the solution is infeasible.
Property 3: If a demand point \( e_i \) has \( D_i = 0 \), remove it from the graph. If a station \( f_j \) has no remaining capacity, remove it and its edges.
Property 4: If the total capacity of stations in \( F_1 \cup FF_1 \cup FF_5 \) is less than total demand, the problem is infeasible when \( FF_0 = \emptyset \), or the current branch is invalid otherwise.
Property 5: If a demand point \( e_i \) has only one neighbor \( f_j \), then \( f_j \) must be open to satisfy \( e_i \)’s demand. This is common in sparse regions for electric vehicle infrastructure.
Property 6: If \( f_i \) is open and \( f_j \) is within \( d_{\text{min}} \), then \( f_j \) must be closed. This ensures station dispersion.
Property 7: Similar to Property 6, but applied during backtracking for dynamic pruning.
Property 8: If a station \( f_j \) cannot meet the demand of its exclusive neighbors (those with only \( f_j \) as an option), the solution is infeasible.
Property 9: If assuming \( f_j \) is open leads to a lower bound exceeding the upper bound, then \( f_j \) must be closed.
Property 10: If assuming \( f_j \) is closed leads to a lower bound exceeding the upper bound, then \( f_j \) must be open.
Property 11: If station \( f_h \) dominates \( f_j \) in coverage, capacity, and cost, then \( f_j \) can be eliminated. This is crucial for optimizing China EV station layouts.
Algorithm Design
Our algorithm combines reduction techniques with backtracking to solve the BSSLP efficiently. The main steps include problem size reduction, upper and lower bound computation, and a backtracking search with pruning.
Allocation Sub-Algorithm
After determining station openings, we allocate demand to stations using a min-cost max-flow approach. The steps are:
- Initialize the set of open stations \( F_{\text{temp}} = F_1 \cup FF_1 \).
- Check if stations can cover all demands; if not, return no solution.
- Construct a flow network with a super-source \( S \) connected to demand points (capacity \( D_i \), cost 0), and a super-sink \( T \) connected to stations (capacity \( t_j \), cost 0). Edges between demand points and stations have capacity \( \min(t_j, D_i) \) and cost \( d_{ij} \).
- Compute the min-cost max-flow from \( S \) to \( T \). If arcs from \( S \) are unsaturated, no solution exists.
For example, consider a network with 8 demand points and 3 stations. The allocation sub-algorithm computes the optimal flow, minimizing total distance cost, which is vital for electric vehicle user convenience.
Lower Bound Sub-Algorithm
We compute a lower bound using greedy allocation and mathematical properties:
- Initialize sets \( E_d \) (demand points sorted by index) and \( \text{Flow} \).
- Apply Properties 5 and 11 to update station sets.
- Check feasibility using Property 4.
- For each demand point in \( E_d \), allocate to the nearest station with sufficient capacity. If capacity is insufficient, allocate partially and move to the next nearest station.
- The lower bound \( lb \) is the sum of \( y_{ij} \cdot d_{ij} \).
This approach ensures a feasible lower bound, accelerating the backtracking process for China EV applications.
Upper Bound Sub-Algorithm
We derive an upper bound via a greedy heuristic and local improvement:
- Initialize sets \( F_u \) and \( E_u \).
- Apply reduction sub-algorithm.
- Sort demand points by descending demand and stations by descending capacity.
- While \( |F_u| < H \), select the station with the highest capacity and allocate to nearest demand points. Update capacities and demands.
- If \( |F_u| = H \), compute the objective using the allocation sub-algorithm.
- Apply a local search: for any two stations and demand points, if swapping allocations reduces cost, update the solution.
- Return the upper bound \( ub \).
This method provides a tight upper bound, essential for pruning in electric vehicle station planning.
Reduction Backtracking Algorithm
The core algorithm integrates reduction and backtracking:
Reduction Sub-Algorithm
- Use Property 9 to close stations if assuming openness increases bounds.
- Apply Property 5 to force station openings.
- Use Property 6 to close stations within minimum distance.
- Check feasibility with Properties 4 and 8.
- Apply Property 10 to open stations if assuming closure increases bounds.
- Use Property 11 to eliminate dominated stations.
Backtracking Sub-Algorithm
The backtracking function backtracking(cur_i) operates as follows:
- If \( cur_i > |F_5| \) or \( |FF_5| = 0 \), reach a leaf node. Compute the solution using the allocation sub-algorithm. Update \( \text{best\_q} \) if better.
- Otherwise, for station \( f_{cur_i} \):
- Case 1: Assume \( f_{cur_i} \) is open. Update sets, apply properties, compute lower bound. If \( lb \leq ub \), recurse; else prune.
- Case 2: Assume \( f_{cur_i} \) is closed. Update sets, check feasibility, compute lower bound. If \( lb \leq ub \), recurse; else prune.
- Restore sets after recursion.
Main Algorithm
- Construct the bipartite graph \( G = (V, X) \) for demand points and candidate stations.
- Initialize sets \( F_0, F_1, FF_0, FF_1, F_{\text{best}} \), and \( \text{best\_q} = 0 \).
- Compute \( L \) using Property 1.
- Apply Property 11 to remove dominated stations.
- Use Property 5 to identify mandatory stations.
- Apply Property 6 to close nearby stations.
- Check feasibility with Properties 4 and 8.
- Compute upper bound \( ub \) using the upper bound sub-algorithm.
- Apply the reduction sub-algorithm iteratively until no change.
- Call
backtracking(1)to find the optimal solution \( F_{\text{best}} \) and \( \text{best\_q} \).
Example Analysis
Small-Scale Example
Consider a case with 7 candidate stations and 10 demand points. Parameters: \( H = 4 \), \( d_{\text{min}} = 3 \), \( T = 20 \). Station capacities and costs are given, and distances are listed in a matrix. The algorithm reduces the problem by applying properties: Station \( f_1 \) is forced open, while \( f_4 \) and \( f_7 \) are closed due to distance and dominance. The backtracking search explores 5 leaf nodes (down from 8 theoretically), yielding an optimal solution with stations \( \{f_1, f_2, f_3, f_6\} \) and objective 2260. This demonstrates the algorithm’s efficiency in handling electric vehicle network constraints.
Random Case Analysis
We tested 20 random datasets with varying sizes. The reduction rate (percentage of stations removed before backtracking) ranged from 12.5% to 40.9%. The pruning rate during backtracking reached up to 96.56%, significantly reducing the search space. For instance, in a (22,30) problem, only 13 of 22 stations were considered, with 89.07% of branches pruned. Results confirm the algorithm’s scalability for large-scale China EV planning.
| ID | (n,m) | H | R | Reduction Rate | Theoretical Leaves | Actual Leaves | Pruning Rate |
|---|---|---|---|---|---|---|---|
| 1 | (5,6) | 3 | 3 | 40.00% | 8 | 5 | 37.50% |
| 10 | (14,20) | 9 | 9 | 35.71% | 512 | 54 | 89.45% |
| 20 | (22,30) | 16 | 18 | 18.18% | 262144 | 9020 | 96.56% |
Algorithm Comparison
We compared our algorithm with branch-and-bound (BBA), ant colony optimization (ACO), and genetic algorithm (GA). Our method consistently found optimal solutions faster, with fewer leaf nodes explored. For example, in a (14,20) case, our algorithm visited 54 leaves in 1.128 seconds, while BBA visited 872 leaves in 5.832 seconds. ACO and GA had deviation rates up to 63.72% from optimal, highlighting their suboptimality for electric vehicle station location.
| ID | (n,m) | Our Algorithm Leaves | Our Time (s) | BBA Leaves | BBA Time (s) |
|---|---|---|---|---|---|
| 1 | (5,6) | 5 | 0.054 | 67 | 0.153 |
| 15 | (22,30) | 2988 | 21.962 | 53474 | 57.264 |
| ID | (n,m) | GA Deviation | ACO Deviation |
|---|---|---|---|
| 1 | (5,6) | 4.51% | 0.00% |
| 18 | (22,30) | 9.61% | 63.72% |
Real Case Study
We applied the algorithm to Nanjing’s Qinhuai District, with 20 candidate stations and 31 demand points. Parameters: \( H = 14 \), \( T = 2000 \) (in 10,000 CNY), \( d_{\text{min}} = 0.5 \) km. Station capacities and distances were derived from real data. The reduction phase removed 4 stations (20% reduction), and backtracking pruned 86.93% of branches. The optimal solution opened stations \( \{f_1, f_2, f_3, f_5, f_6, f_{10}, f_{12}, f_{15}, f_{17}, f_{19}, f_{20}\} \) with an objective of 3371.18. This case underscores the algorithm’s practicality for China EV infrastructure development.
| (n,m) | H | R | Reduction Rate | Theoretical Leaves | Actual Leaves | Pruning Rate |
|---|---|---|---|---|---|---|
| (20,31) | 14 | 16 | 20.00% | 65536 | 8568 | 86.93% |
Conclusion
We presented a reduction-based backtracking algorithm for the electric vehicle battery swap station location problem. By leveraging mathematical properties, we reduced problem size and integrated efficient sub-algorithms for allocation and bounds. The algorithm guarantees optimality and demonstrates superior performance through random and real-case studies, making it suitable for China EV network planning. Future work will address dynamic factors and further optimize computational efficiency.
Research Limitations and Future Directions
While our algorithm ensures optimality, its complexity remains high for very large instances. We assumed homogeneous electric vehicles and static demand, which may not hold in real-world scenarios. Future research will incorporate dynamic traffic flows, heterogeneous EV models, and predictive demand patterns. Additionally, we plan to hybridize with heuristic methods to enhance speed and applicability for evolving China EV infrastructure.