Source-linked AI summary
Electric Vehicle Charging Station Placement: Formulation, Complexity, and Solutions
Albert Y. S. Lam, Yiu-Wing Leung, Xiaowen Chu
TL;DR
The paper studies how to place charging stations so EVs can access them within driving range and travel throughout a city after recharging. It formulates EVCSPP, proves NP-hardness, and proposes four solution methods. Simulations show that the methods differ in solution quality and computation time, making them suitable for different situations.
Problem
Charging-station locations must provide EV accessibility and broad city coverage, but the paper identifies a need for a formal placement problem addressing these requirements.
Method
The paper formulates EVCSPP as an optimization problem, analyzes its complexity, and proposes four solution methods.
Results
The decision version is NP-complete, and simulation results show that the four methods have different solution-quality and computation-time characteristics.
Takeaways & Limitations
Method suitability depends on solution quality, algorithmic efficiency, problem size, algorithmic nature, and system prerequisites.
Abstract
from arXiv · showhide
To enhance environmental sustainability, many countries will electrify their transportation systems in their future smart city plans. So the number of electric vehicles (EVs) running in a city will grow significantly. There are many ways to re-charge EVs' batteries and charging stations will be considered as the main source of energy. The locations of charging stations are critical; they should not only be pervasive enough such that an EV anywhere can easily access a charging station within its driving range, but also widely spread so that EVs can cruise around the whole city upon being re-charged. Based on these new perspectives, we formulate the Electric Vehicle Charging Station Placement Problem (EVCSPP) in this paper. We prove that the problem is non-deterministic polynomial-time hard. We also propose four solution methods to tackle EVCSPP and evaluate their performance on various artificial and practical cases. As verified by the simulation results, the methods have their own characteristics and they are suitable for different situations depending on the requirements for solution quality, algorithmic efficiency, problem size, nature of the algorithm, and existence of system prerequisite.
NOMENCLATURE
The paper frames charging-station placement around sustainable EV adoption, driver convenience, and citywide accessibility. It situates EVCSPP alongside grid-focused EV research and facility-location work.
- Motivation: EVs are presented as a means to reduce fossil-fuel dependence and harmful emissions while supporting future transportation systems.
- Problem scope: EVCSPP seeks charging-station locations that minimize construction cost while providing citywide coverage and driver convenience.
- Problem scope: The paper focuses on human factors, including charging ease and driver satisfaction, rather than technological aspects of charging infrastructure.
- Planning scope: A complete charging-station planning framework can separate urban and engineering screening from driver-oriented placement decisions.
- Contributions: The paper contributes a formulation, complexity analysis, and four solution methods for EVCSPP, followed by performance comparisons.
- Related work: Prior EV research largely examines grid operations, while related charging-station studies address location, sizing, costs, environmental factors, and service radius.
- Related work: Facility-location research provides related models involving travel distances or times to facilities such as gas stations and fire stations.
III. PROBLEM FORMULATION
The formulation models a city as a graph and selects charging-station sites to satisfy local demand while preserving reachability and connectivity. A network-flow construction represents connectivity, but the resulting model is a mixed-integer nonlinear program.
- A. System model: The city is modeled as an undirected graph G=(N,E), where nodes are candidate sites and edges connect site pairs.
- A. System model: Each candidate site has charging capacity f_i and local demand requirement F_i, estimated from site conditions, traffic, population, and EV penetration.
- A. System model: A fully charged EV is assumed to traverse average distance D, and selected sites must satisfy reachability conditions based on D and αD.
- A. System model: The reachability conditions require inter-site travel within hop-scaled distance limits and ensure local demand is met by nearby station capacity.
- B. Formulation: The objective minimizes total construction cost using Boolean placement variables x_i and site costs c_i.
- B. Formulation: The model rewrites coverage through node neighborhoods within αD and represents the selected nodes’ connectivity as a connected induced subgraph of ˆG.
- B. Formulation: Virtual flow from a source attached to each selected node is used to verify that selected nodes can reach one another, independently of traffic flow.
- B. Formulation: The formulation combines Boolean placement variables with continuous flow variables, and quadratic constraints prevent it from being a MILP.
IV. COMPLEXITY ANALYSIS
The paper establishes computational hardness by reducing Vertex Cover to the decision version of EVCSPP. The constructed instance preserves the cost bound while encoding coverage and connectivity.
- Decision problem: The decision version asks whether an induced subgraph satisfies demand and connectivity requirements with total construction cost at most C.
- Complexity result: Theorem 1 classifies the decision version as NP-complete, and Corollary 1 states that EVCSPP is NP-hard.
- Reduction: The complexity proof reduces the Vertex Cover Problem to EVCSPP.
- Reduction: The reduction augments the Vertex Cover graph with edge-nodes, assigns unit costs to original vertices, and sets edge-node capacities and demands.
- Reduction: A vertex cover of size at most C yields a connected EVCSPP solution with cost at most C.
- Reduction: Conversely, any feasible EVCSPP solution induces a vertex cover with no more than C selected original nodes.
V. PROPOSED SOLUTIONS
Because EVCSPP is NP-hard, the paper proposes four solution methods with different trade-offs and situational suitability.
- The four methods are designed for different requirements concerning solution quality, computational efficiency, problem size, algorithmic nature, and system prerequisites.
A. Method I: Iterative Mixed-Integer Linear Program
Method I converts the original formulation into a sequence of MILPs by fixing a charging-station node and evaluating all possible fixed nodes. It can guarantee optimality with an optimal solver, but its computation becomes impractical as the problem grows.
- Formulation: Problem (7) fixes node i as selected and formulates the remaining placement problem as an MILP solvable by standard MIP methods.The formulation preserves connectivity and demand constraints while minimizing total cost.
- Solution procedure: Solving Problem (7) for every node i and taking the minimum-cost result determines the solution of Problem (6).The method evaluates n connected subgraphs, each containing a different fixed node.
- Guarantee: Method I guarantees optimality when the solver returns an optimal solution for Problem (7).This guarantee follows because the optimal solution of Problem (6) is among the subgraphs generated across all fixed nodes.
- Solution procedure: The resulting approach is called Iterative MILP because the original mixed-integer nonlinear program becomes n solvable MILPs.The method iterates over all candidate fixed nodes.
- Limitation: Method I is limited to small instances because each MILP grows super-linearly in n and the number of MILPs also increases with n.The combined effect makes computation time accelerate extraordinarily fast.
B. Method II: Greedy Approach
Method II starts from the all-selected feasible solution and greedily removes costly nodes while preserving connectivity and feasibility. It is computationally efficient but generally produces a sub-optimal solution, especially for larger problems.
- Node selection: The greedy algorithm constructs a connected induced subgraph and repeatedly considers removing nodes whose deletion does not disconnect it.The candidate set N contains nodes that can be removed while preserving connectivity.
- Node selection: Within each iteration, the algorithm tests nodes in descending cost order and accepts a removal only when the resulting vector satisfies constraint (6b).If the trial fails, the node is removed from N and the next-highest-cost candidate is tested.
- Termination: The iterations terminate when no nodes remain in N, and the final vector is the best solution found by the greedy algorithm.The method is explicitly described as producing a sub-optimal solution.
- Performance: The greedy solution is usually sub-optimal, particularly when the problem size n becomes larger.Its main advantage is much shorter computation time than the original formulation.
C. Method III: Effective Mixed-Integer Linear Program
Method III reduces the number of MILPs by exploiting the fact that every node must have a selected node in its one-hop neighborhood when all demands are positive. Choosing a minimum-degree node preserves equivalence with Method I.
- Structural result: When every demand requirement Fi is positive, each node i has at least one selected node j in its one-hop neighborhood in the optimal solution.If i is unselected, its positive demand requires a positive coverage term from a neighboring selected node.
- Reduced formulation: Theorem 3 allows Method III to apply Problem (7) only to nodes in a chosen node’s one-hop neighborhood.This avoids solving Problem (7) for every node as in Method I.
- Efficiency: Selecting the node with the smallest degree in ˆG minimizes the number of Problem (7) instances that must be solved.The computational saving depends on the cardinality of the selected node’s neighborhood.
- Guarantee: Methods I and III are equivalent, and Method III guarantees optimality when the solver optimally solves Problem (7).The equivalence follows from the neighborhood property established by Theorem 3.
D. Method IV: Chemical Reaction Optimization
Method IV applies Chemical Reaction Optimization to EVCSPP, representing candidate solutions as molecules that explore the solution space through randomized elementary reactions. Its implementation combines the CRO framework with the greedy approach.
- CRO framework: Chemical Reaction Optimization is a nature-inspired, general-purpose metaheuristic applied to EVCSPP.Each molecule carries a solution, and reactions modify those solutions while exploring the solution space.
- Reaction operators: The method uses four elementary reactions: on-wall ineffective collision, decomposition, inter-molecular ineffective collision, and synthesis.Each reaction has its own rule for modifying solutions carried by the involved molecules.
- Reaction operators: The on-wall ineffective collision applies the greedy approach to an existing solution, producing a nearby modified solution.This reaction makes only small modifications to the molecule’s solution.
- Reaction operators: Decomposition produces two randomly generated solutions by modifying the greedy algorithm’s iteration and node-selection steps.The repeat loop runs a random number of times between 1 and n, with a random node selected from N.
- Implementation detail: The energies stored in molecules depend on the original solution even though the two decomposition solutions are generated independently of it.This distinction is part of the CRO implementation described in the paper.
3) Inter-molecular ineffective collision:
The paper evaluates four solution methods for EVCSPP on artificial, scalable, and Hong Kong cases, comparing solution quality, computation time, convergence, and station distributions. Methods I and III provide the best solutions, while Method II is fastest and Method IV offers a probabilistic alternative with generally strong performance.
- Simulation setup: The simulations compare four methods on artificial and practical cases using solution quality and computation time as evaluation criteria.Methods I and III use CPLEX/YALMIP-based MILP formulations, whereas Method IV is probabilistic and repeated ten times per case.
- Scalability: As problem size n increases, all computation times rise; Method I grows fastest, while Methods I and III become unavailable at n = 200 because of an out-of-memory problem.Method II remains fastest but has the worst solution quality, whereas Methods I and III retain the best solutions when computable.
- Hong Kong case: For the Hong Kong case, the selected charging-station locations are shown in Fig. 4, with roman numerals indicating which methods include each location.The example uses α = 0.6 and D = 45 km; red locations indicate stations selected by the solutions.
- Solution quality: Methods I and III always find the best solutions, while Method IV does so in most cases and Method II does so in some cases.Method IV can produce different solutions across runs because it is probabilistic.
- Computation time: Method II is fastest on average, followed by Method IV, Method III, and Method I.The methods therefore differ substantially in computational efficiency as well as solution quality.
- Computation time: As D increases, computation time generally decreases for Methods I, II, and IV but increases for Method III because its required MILP count grows.A denser graph reduces search effort for Methods I, II, and IV, whereas higher node degrees increase the number of MILPs required by Method III.
B. Discussion
The methods are compared across different perspectives, with Methods I and III producing the best results when the MILP solver guarantees optimality.
- The methods are compared independently across five perspectives.
- 1) Solution quality:: Methods I and III can obtain the best results when the adopted MILP solver guarantees optimality.
- 1) Solution quality:: The optimality claim depends on the MILP solver’s ability to guarantee optimality.
2) Computation time:
The four methods differ in computation time, scalability, determinism, and prerequisites. Method II is fastest, while MILP-based methods are limited to n ≤150 in the stated MATLAB/YALMIP/CPLEX setting.
- Computation time: Method II is the fastest because it uses the simplest design and obtains a usually sub-optimal solution in very limited time.
- Computation time: Method IV follows Method II in speed, while Method III is faster than Method I because it applies MILP to only a subset of nodes.
- Problem size: MILP-based Methods I and III are solvable only for n ≤150 in the stated MATLAB/YALMIP/CPLEX setting, whereas Methods II and IV better resist growing problem size.
- Algorithm nature: Method IV is probabilistic and averaged over repeated simulations, while the other three methods produce identical results across runs.
- Prerequisites: Method III requires the condition in Theorem 3, although the other methods do not require this prerequisite.
- Future direction: Method IV embeds a greedy algorithm in a metaheuristic, and replacing CRO with other metaheuristics remains future work.
APPENDIX AN ILLUSTRATIVE EXAMPLE FOR THE NETWORK FLOW
The illustrative network-flow example shows how flow constraints enforce connectivity among selected charging-station nodes. A disconnected selection violates the flow balance requirements, whereas connected selected nodes satisfy them.
- Illustrative setup: The example uses graph G-hat from Figure 5 to illustrate the network-flow model for charging-station connectivity.
- Connected selection: When nodes 1 and 2 are selected, the flow assignments satisfy the constraints and establish connectivity between the resulting charging-station locations.
- Disconnected selection: Selecting nodes 1 and 3 without node 2 creates a contradiction under the flow constraints, so that construction is disallowed.
- Conclusion: The network-flow model therefore enforces connectivity of the charging-station network.