1. Introduction
The rapid proliferation of electric vehicles (EVs) has significantly increased the demand for efficient energy replenishment infrastructure. Electric vehicle swap stations, which enable quick battery replacement, offer a promising solution to address the challenges of short driving ranges and long charging times. However, determining optimal locations for these swap stations is a complex optimization problem, classified as NP-hard, meaning traditional polynomial-time algorithms are infeasible for large-scale instances.
In this paper, we present a novel reduced-order backtracking algorithm tailored to the electric vehicle swap station location problem. Our approach combines mathematical properties, strategic problem reduction, and efficient sub-algorithms to achieve optimal solutions within reasonable computation times. By leveraging problem-specific characteristics and innovative pruning techniques, we demonstrate significant improvements in solving efficiency compared to traditional methods.
2. Literature Review
Numerous studies have tackled EV swap station location problems using various methodologies. For instance:
- Zhang et al. (2023) employed queuing theory and hybrid genetic algorithms (GA) combined with particle swarm optimization (PSO) to address location and capacity problems for electric bus swap stations .
- He (2022) proposed a high-dimensional multi-objective evolutionary algorithm to optimize charging and swapping station locations, integrating adaptive selection strategies to enhance solution efficiency .
- Lin et al. (2022) developed a multi-objective stochastic allocation model for scooter battery swapping stations, focusing on probabilistic demand scenarios .
However, these approaches are predominantly heuristic or approximate, failing to guarantee global optimality. In contrast, our study introduces an exact algorithm framework that systematically explores the solution space while reducing computational complexity through mathematical properties and intelligent pruning.
3. Problem Description
3.1 Problem Formulation
The electric vehicle swap station location problem aims to minimize total operational costs while satisfying constraints on construction costs, station capacity, and spatial distribution. Key considerations include:
- Economic efficiency: Minimizing construction and operational expenses.
- Geographic feasibility: Ensuring adequate spacing between stations to avoid redundancy.
- Service coverage: Meeting demand from EV users within acceptable travel distances.
3.2 Mathematical Model
We define the problem using the following notation (summarized in Table 1):
Table 1. Mathematical Notations
| Symbol | Description |
|---|---|
| \(x_j\) | Binary variable (1 if station j is opened, 0 otherwise) |
| \(y_{ij}\) | Allocation of demand from point i to station j |
| \(d_{ij}\) | Distance between demand point i and station j |
| \(c_j\) | Construction cost of station j |
| \(t_j’\) | Capacity of station j |
| \(D_i\) | Demand at point i |
| H | Maximum number of stations allowed |
| T | Budget constraint for construction costs |
The objective function and constraints are formulated as follows:\(\min Z = \sum_{i=1}^{m} \sum_{j=1}^{n} y_{ij} \cdot d_{ij} \quad \text{(Minimize operational cost)} \quad \text{(1)}\) Subject to:\(\sum_{j=1}^{n} c_j x_j \leq T \quad \text{(Budget constraint)} \quad \text{(2)}\)\(\sum_{j=1}^{n} x_j \leq H \quad \text{(Maximum stations constraint)} \quad \text{(3)}\)\(x_i x_j d(f_i, f_j) \geq d_{\text{min}} \quad \text{(Minimum distance between stations)} \quad \text{(4)}\)\(\sum_{i=1}^{m} y_{ij} \leq t_j’ \quad \text{(Capacity constraint)} \quad \text{(5)}\)\(\sum_{j=1}^{n} y_{ij} = D_i \quad \text{(Demand satisfaction)} \quad \text{(6)}\)\(x_j \in \{0,1\}, \quad y_{ij} \geq 0 \quad \text{(Binary and non-negativity constraints)} \quad \text{(7)}\)
3.3 Key Mathematical Properties
To reduce problem complexity, we derive eleven mathematical properties that enable preprocessing and pruning:
- Minimum Station Requirement: If the total capacity of the first \(L-1\) largest stations is less than the total demand, at least L stations are required .
- Feasibility Check via Station Counts: If the number of mandatory stations exceeds H, the problem is infeasible .
- Demand/ Capacity Exhaustion: Remove demand points with satisfied demand or stations with full capacity .
- Dominance Analysis: If a station \(f_j\) is dominated by \(f_h\) (i.e., \(f_j\) has higher cost, lower capacity, and greater distances to all demand points compared to \(f_h\)), \(f_j\) can be excluded .
4. Algorithm Design
Our approach consists of a reduced-order backtracking algorithm integrated with sub-algorithms for allocation, upper bounds, lower bounds, and problem reduction.
4.1 Allocation Sub-Algorithm
This sub-algorithm solves the demand allocation problem using a minimum-cost maximum-flow network model. Steps include:
- Constructing a bipartite graph with super source/sink nodes.
- Using the Bellman-Ford algorithm to compute the minimum cost for flow allocation.
- Verifying if all demands are satisfied (non-saturated arcs indicate infeasibility) .
Example of Allocation: For a network with 8 demand points and 3 stations (Figure 2 in the original PDF), the minimum-cost flow yields an optimal allocation with a total cost of 1526 .
4.2 Lower Bound Sub-Algorithm
The lower bound is computed using a greedy strategy:
- Sort demand points and allocate to the nearest available station first.
- Use mathematical properties (e.g., dominance, capacity checks) to prune infeasible branches.
- Calculate the lower bound lb as the sum of allocated distances .
4.3 Upper Bound Sub-Algorithm
The upper bound is derived from a feasible solution using sorting and greedy allocation:
- Prioritize demand points with higher remaining demand.
- Select stations with larger capacities and lower costs.
- Refine the solution using swap operations to improve efficiency .
4.4 Reduced-Order Sub-Algorithm
This sub-algorithm preprocesses the problem using mathematical properties to eliminate unnecessary stations:
- Identify mandatory stations (e.g., unique suppliers for certain demand points).
- Exclude stations that violate distance constraints with already opened stations.
- Remove dominated stations to reduce the search space .
4.5 Backtracking Sub-Algorithm
Using a depth-first search (DFS) approach:
- For each station in the reduced set, recursively explore two cases: opening or not opening the station.
- Use upper and lower bounds to prune branches where \(lb > ub\).
- At leaf nodes, validate feasibility using the allocation sub-algorithm and update the optimal solution .
Algorithm Complexity: The worst-case time complexity is \(O(2^Q)\), where Q is the number of stations in the reduced set (\(Q \leq n\)). Through pruning, this is significantly reduced in practice .
5. Empirical Validation
5.1 Small-Scale Example
Consider a problem with 7 stations, 10 demand points, \(H=4\), and \(T=20\). Using our algorithm:
- Reduction: 3 stations are eliminated via dominance and distance checks.
- Optimal Solution: Stations \(\{f_1, f_2, f_3, f_6\}\) with a total cost of 2260 .
5.2 Random Instances
We tested 20 random instances with varying scales (Table 2). Key results include:
- Reduction Rate: Up to 40.91% (Problem 19).
- Pruning Efficiency: Average prune rate of 78.5%, significantly reducing the number of leaf nodes explored .
Table 2. Random Instance Results
| Instance | \((n, m)\) | H | R | Reduction Rate | Theoretical Leaves | Actual Leaves | Prune Rate |
|---|---|---|---|---|---|---|---|
| 1 | (5,6) | 3 | 3 | 40.00% | 8 | 5 | 37.50% |
| 6 | (8,11) | 5 | 5 | 37.50% | 32 | 13 | 59.38% |
| 10 | (14,20) | 9 | 9 | 35.71% | 512 | 54 | 89.45% |
| 20 | (22,30) | 16 | 18 | 18.18% | 262144 | 9020 | 96.56% |
5.3 Algorithm Comparison
Against branch-and-bound (BBA), ant colony optimization (ACO), and genetic algorithms (GA):
- BBA: Our algorithm reduces leaf nodes by 83-97% and computation time by 50-90% (Table 3) .
- ACO/GA: These heuristic methods often yield suboptimal solutions with 偏差 (deviation) up to 63.72%, whereas our exact algorithm always finds the optimal solution (Table 4) .
Table 3. Comparison with Branch-and-Bound
| Instance | Reduced Backtracking | Branch-and-Bound | ||
|---|---|---|---|---|
| Leaves Explored | Time (s) | Leaves Explored | Time (s) | |
| 1 | 5 | 0.054 | 67 | 0.153 |
| 10 | 54 | 1.128 | 872 | 5.832 |
| 15 | 2988 | 21.962 | 53474 | 57.264 |
Table 4. Comparison with Heuristic Algorithms
| Instance | GA | ACO | Optimal Solution | ||
|---|---|---|---|---|---|
| Objective | Deviation | Objective | Deviation | Objective | |
| 4 | 1646 | 38.79% | 1186 | 0.00% | 1186 |
| 14 | 2935 | 12.07% | 3538 | 35.09% | 2619 |
| 18 | 2520 | 9.61% | 3764 | 63.72% | 2299 |
5.4 Real-World Case Study
Using data from Nanjing’s Qinhuai District (20 stations, 31 demand points), our algorithm:
- Reduced the problem size by 20% (from 20 to 16 stations).
- Achieved an optimal solution with 11 stations and a total cost of 3371.18, demonstrating practical viability .
6. Conclusion and Future Work
6.1 Contributions
- Exact Solution Guarantee: The reduced-order backtracking algorithm ensures global optimality, a critical advantage over heuristic methods.
- Efficiency Improvements: Mathematical properties and pruning techniques significantly reduce computational complexity, making large-scale instances tractable.
- Practical Relevance: Empirical results from real-world and synthetic datasets validate the algorithm’s effectiveness in diverse scenarios.
6.2 Limitations and Outlook
While our approach enhances efficiency, solving very large-scale problems still requires substantial computation time. Future research will focus on:
- Integrating dynamic factors (e.g., traffic flow, seasonal demand variations) into the model.
- Hybridizing with heuristic algorithms to further reduce computation time.
- Expanding the model to accommodate different EV types and battery sizes.
By addressing these challenges, we aim to develop a more robust and universally applicable solution for electric vehicle swap station planning, supporting the sustainable growth of EV infrastructure.
References
[List of references from the original PDF, formatted in APA style, ensuring all citations to “electric vehicle” are retained. Due to length, specific citations are omitted here but would follow standard academic formatting.]
This comprehensive study demonstrates the utility of exact algorithms combined with problem-specific reductions for electric vehicle swap station location, offering a foundational framework for optimizing EV charging infrastructure.