The rapid adoption of electric vehicles, particularly in China, has underscored the need for efficient energy replenishment infrastructure. Electric car swap stations, which allow for quick battery replacement, offer a promising solution to challenges such as long charging times and limited driving range. In China, the EV market has seen explosive growth, with over 20.74 million electric cars on the road by mid-2024, yet the number of swap stations remains limited at just 3,878. This disparity highlights the urgency of optimizing the location of swap stations to maximize coverage and minimize costs. The location problem for electric car swap stations is a classic NP-hard problem, meaning that unless P equals NP, no polynomial-time exact algorithm exists. This paper addresses this issue by developing a mathematical model based on real-world constraints and profit maximization goals, followed by a backtracking algorithm with reduction techniques to efficiently solve the problem.
The problem involves selecting optimal sites from a set of candidate locations to establish swap stations, considering factors like demand points, station capacities, distance constraints, and construction costs. For instance, in China EV deployments, stations are often co-located with parking lots, residential areas, or transportation hubs to leverage existing infrastructure. The objective is to minimize operational costs, such as the total distance traveled for battery swaps, while adhering to constraints like budget limits and minimum distances between stations. This paper introduces a reduction-based backtracking algorithm that leverages mathematical properties to prune the search space, along with sub-algorithms for allocation, upper bounds, and lower bounds. The approach is validated through random and real-world case studies, demonstrating its effectiveness in solving the electric car swap station location problem.
Problem Description and Mathematical Model
The electric car swap station location problem can be formalized using a bipartite graph $G = (V, X)$, where $V = E \cup F$. Here, $E = \{e_i \mid i = 1, 2, \dots, m\}$ represents the set of demand points (e.g., areas with high electric car usage), and $F = \{f_j \mid j = 1, 2, \dots, n\}$ denotes the candidate locations for swap stations. Each demand point $e_i$ has a demand $D_i$, indicating the number of battery swaps required, and each candidate station $f_j$ has a capacity $t_j’$, representing the maximum number of swaps it can handle daily. The distance between $e_i$ and $f_j$ is $d_{ij}$, and the minimum distance between any two stations is $d_{\text{min}}$. The goal is to select a subset of stations to open, subject to constraints, such that the total operational cost is minimized.
The mathematical model is defined as follows:
Objective function: minimize the total operational cost, which is proportional to the distance traveled for swaps:
$$ \min Z = \sum_{i=1}^{m} \sum_{j=1}^{n} y_{ij} \cdot d_{ij} $$
Subject to:
1. Budget constraint: the total construction cost of selected stations must not exceed a threshold $T$:
$$ \sum_{j=1}^{n} c_j x_j \leq T $$
2. Number of stations constraint: at most $H$ stations can be selected:
$$ \sum_{j=1}^{n} x_j \leq H $$
3. Minimum distance constraint: for any two stations $f_i$ and $f_j$, if both are open, the distance between them must be at least $d_{\text{min}}$:
$$ x_i \cdot x_j \cdot d(f_i, f_j) \geq x_i \cdot x_j \cdot d_{\text{min}} \quad \forall i, j $$
4. Capacity constraint: the total demand assigned to a station must not exceed its capacity:
$$ \sum_{i=1}^{m} y_{ij} \leq t_j’ \quad \forall j $$
5. Demand satisfaction constraint: the total assignment to a demand point must meet its demand:
$$ \sum_{j=1}^{n} y_{ij} = D_i \quad \forall i $$
6. Binary variable constraint: $x_j \in \{0, 1\}$ indicates whether station $f_j$ is open, and $y_{ij} \geq 0$ represents the allocation from station $f_j$ to demand point $e_i$.
This model captures the essence of the electric car swap station location problem, balancing cost efficiency with practical constraints. In China EV contexts, parameters like $d_{\text{min}}$ and $H$ are influenced by urban planning policies and energy grid capabilities.
Mathematical Properties for Problem Reduction
To reduce the problem size and computational complexity, several mathematical properties are derived and utilized in the algorithm. These properties help in pre-processing the problem by identifying stations that must be opened or closed, thereby shrinking the search space.
Property 1: Let the stations be sorted in descending order of capacity. If the sum of capacities of the top $L-1$ stations is less than the total demand, and the sum of the top $L$ stations meets or exceeds the total demand, then at least $L$ stations must be opened to cover all demand. This is fundamental for determining the minimum number of stations required in China EV networks.
Property 2: If the number of opened stations (from sets $F_1 \cup FF_1$) exceeds $H$, the solution is infeasible. Similarly, if after reduction, the number of opened stations is less than the minimum required $L$, the solution is infeasible. This property ensures that constraints are adhered to during the search.
Property 3: If a demand point $e_i$ has $D_i = 0$, it can be removed from the graph. Similarly, if a station $f_j$ has no remaining capacity, it can be removed. This simplifies the problem instance dynamically.
Property 4: If the total capacity of all candidate stations is less than the total demand, the problem is infeasible. This checks for basic feasibility in electric car swap station planning.
Property 5: If a demand point $e_i$ is connected to only one station $f_j$, then $f_j$ must be opened to satisfy $e_i$’s demand. This is critical for ensuring demand coverage in sparse networks.
Property 6 and 7: If a station $f_i$ is opened, any station $f_j$ within distance $d_{\text{min}}$ must be closed. This enforces the minimum distance constraint and reduces the candidate set.
Property 8: If a station $f_j$ cannot meet the demand of its exclusively connected demand points, the solution is infeasible. This prevents overloading of stations.
Property 9 and 10: During backtracking, if assuming a station is opened or closed leads to a lower bound exceeding the upper bound, the opposite decision is enforced. This prunes non-promising branches.
Property 11: If station $f_j$ is dominated by another station $f_h$ (i.e., $f_h$ has higher capacity, lower cost, and covers more demand points at shorter distances), then $f_j$ can be closed. This leverages efficiency comparisons to reduce options.
These properties are integrated into the algorithm to pre-process the problem and guide the search, making it feasible to handle large-scale instances typical in China EV deployments.
Algorithm Design
The proposed algorithm combines reduction techniques with a backtracking search, enhanced by sub-algorithms for allocation, lower bounds, and upper bounds. The main steps are outlined below, with a focus on how they address the electric car swap station location problem.
Allocation Sub-Algorithm
Once the set of opened stations is determined, the allocation sub-algorithm assigns demand points to stations using a minimum-cost flow approach. The bipartite graph is transformed into a flow network where:
- A super-source $S$ connects to each demand point $e_i$ with capacity $D_i$ and cost 0.
- Each station $f_j$ connects to a super-sink $T$ with capacity $t_j’$ and cost 0.
- Edges between $e_i$ and $f_j$ have capacity $\min(t_j’, D_i)$ and cost $d_{ij}$.
The Bellman-Ford algorithm is used to compute the minimum-cost flow. If the flow from $S$ does not saturate all demand edges, the solution is infeasible. This ensures optimal allocation given the opened stations, which is crucial for minimizing operational costs in electric car networks.
Lower Bound Sub-Algorithm
The lower bound sub-algorithm provides an optimistic estimate of the objective value by combining greedy assignment with mathematical properties. Steps include:
- Initialize sets and apply Properties 5 and 11 to reduce the problem.
- Sort demand points in ascending order of index and assign each to the nearest station with available capacity.
- If a station cannot fully meet demand, allocate partially and move to the next nearest station.
- Compute the lower bound as the sum of assigned distances: $lb = \sum_{i=1}^{m} \sum_{j=1}^{n} y_{ij} \cdot d_{ij}$.
This approach ensures a feasible but potentially suboptimal allocation, helping to prune branches in backtracking.
Upper Bound Sub-Algorithm
The upper bound sub-algorithm generates a feasible solution to set an initial upper bound. Steps include:
- Apply reduction properties and sort demand points by descending demand.
- Select stations based on capacity and proximity, ensuring no more than $H$ stations are opened.
- Assign demand to stations greedily, and refine the solution by checking for better allocations using a pairwise exchange condition: if $d_{kj} + d_{ih} < d_{ij} + d_{kh}$ for stations $f_j, f_h$ and demand points $e_i, e_k$, update the allocation.
- Compute the upper bound: $ub = \sum_{i=1}^{m} \sum_{j=1}^{n} y_{ij} \cdot d_{ij}$.
This provides a quick, good-quality solution that guides the backtracking search.
Reduction Backtracking Algorithm
The core algorithm integrates reduction and backtracking. Key steps are:
- Pre-processing: Build the bipartite graph and initialize sets. Use Properties 1, 5, 6, and 11 to reduce the problem. Compute the initial upper bound.
- Reduction: Iteratively apply reduction properties (e.g., Properties 9 and 10) to update sets $F_0$ (closed stations) and $F_1$ (opened stations).
- Backtracking: Perform a depth-first search on the reduced set $FF_5$ (undecided stations). At each node, assume a station is opened or closed, apply properties, compute bounds, and prune if $lb > ub$.
- Termination: When all stations are decided, call the allocation sub-algorithm to compute the final solution and update the best objective value.
The algorithm ensures optimality by exploring all feasible combinations in the reduced space, making it suitable for China EV scenarios where problem sizes can be large.
Example Analysis
To illustrate the algorithm, consider a small-scale example with 7 candidate stations and 10 demand points. Parameters include $H = 4$, $d_{\text{min}} = 3$, and $T = 20$. Stations have capacities and costs, and demand points have specific demands. The reduction phase applies Properties 5 and 6, forcing station $f_1$ to open and $f_4$ to close. Property 11 eliminates $f_7$ due to dominance. The backtracking search then explores the reduced set, with the optimal solution opening stations $\{f_1, f_2, f_3, f_6\}$ and achieving an objective value of 2260.
For larger-scale validation, random instances were generated with demand $D_i \in [50, 300]$ and station capacity $t_j’ \in [500, 1500]$. The table below summarizes results for 20 instances, showing the reduction rate (percentage of stations removed pre-backtracking) and pruning rate (percentage of leaf nodes skipped during backtracking).
| Instance (n,m) | H | Reduction Rate | Theoretical Leaves | Actual Leaves | Pruning Rate |
|---|---|---|---|---|---|
| (5,6) | 3 | 40.00% | 8 | 5 | 37.50% |
| (5,6) | 3 | 20.00% | 16 | 12 | 25.00% |
| (5,6) | 4 | 20.00% | 16 | 7 | 56.25% |
| (8,11) | 5 | 37.50% | 32 | 13 | 59.38% |
| (14,20) | 9 | 35.71% | 512 | 54 | 89.45% |
| (22,30) | 14 | 31.82% | 32768 | 2988 | 90.88% |
The algorithm consistently reduces problem size and prunes effectively, with pruning rates exceeding 90% for larger instances. This demonstrates scalability for electric car swap station planning in China EV contexts.
Algorithm Comparison
The proposed algorithm was compared against branch-and-bound (BBA), ant colony optimization (ACO), and genetic algorithm (GA). ACO and GA parameters were set to 200 and 50 iterations, respectively. The table below shows the number of leaf nodes visited and time taken for each instance, with a timeout of 60 seconds.
| Instance (n,m) | Proposed Leaves | Proposed Time (s) | BBA Leaves | BBA Time (s) |
|---|---|---|---|---|
| (5,6) | 5 | 0.054 | 67 | 0.153 |
| (8,11) | 13 | 0.267 | 96 | 1.113 |
| (14,20) | 54 | 1.128 | 872 | 5.832 |
| (22,30) | 2988 | 21.962 | 53474 | 57.264 |
The proposed algorithm visits fewer nodes and runs faster than BBA. For solution quality, the deviation from optimality was computed for ACO and GA. The table below shows the objective values and deviation percentages for selected instances.
| Instance (n,m) | GA Objective | GA Deviation | ACO Objective | ACO Deviation |
|---|---|---|---|---|
| (5,6) | 1089 | 4.51% | 1042 | 0.00% |
| (8,11) | 1646 | 38.79% | 1186 | 0.00% |
| (14,20) | 2121 | 17.90% | 2452 | 36.30% |
| (22,30) | 2728 | 6.98% | 3022 | 18.51% |
The proposed algorithm always finds the optimal solution, while ACO and GA show significant deviations for larger instances, highlighting the importance of exact methods in critical planning for China EV infrastructure.
Real-World Case Study
A case study in the Qinhuai District of Nanjing, China, involved 20 candidate stations (e.g., parking lots and residential areas) and 31 demand points. Parameters included $H = 14$, $T = 2000$ (in 10,000 CNY), and $d_{\text{min}} = 0.5$ km. Station capacities ranged from 60 to 200 swaps per day, and demands were derived from population data. The reduction phase decreased the problem size by 20%, and backtracking achieved a pruning rate of 86.93%. 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 value of 3371.18. This demonstrates the algorithm’s practicality in urban planning for electric car swap stations in China EV networks.
Conclusion
This paper presents a reduction-based backtracking algorithm for the electric car swap station location problem, incorporating mathematical properties to minimize operational costs while adhering to constraints. The algorithm efficiently reduces problem size and prunes the search space, ensuring optimality for practical instances. Case studies confirm its effectiveness in both random and real-world settings, such as those relevant to China EV deployments. Future work will focus on enhancing the model with dynamic factors like traffic flow and diverse electric car types, and improving algorithm efficiency through hybridization with heuristic methods. This approach provides a robust tool for optimizing swap station networks, supporting the sustainable growth of electric mobility.