💻 computer science

A Graph-based Decomposition Framework for Flow-based Charging Station Location Problems

This paper proposes a graph-based decomposition framework that enhances the computational efficiency and scalability of solving flow-based charging station location problems on large-scale transportation networks by partitioning the network into smaller subproblems, solving them individually, and refining the aggregated results.

Original authors: Jingyu Xiang, Paula Carroll, Annunziata Esposito Amideo

Published 2026-08-25

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Jingyu Xiang, Paula Carroll, Annunziata Esposito Amideo

Original paper licensed under CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The transition to electric vehicles is one of the most significant shifts in modern transportation, promising to clear the air and reduce the carbon footprint of daily travel. Yet, for this transition to succeed, drivers need a reliable network of charging stations. Unlike filling a gas tank, which takes minutes and is available at nearly every corner, recharging an electric vehicle requires time and a specific location. If a driver cannot find a charger when the battery runs low, the vehicle becomes useless, creating a phenomenon known as range anxiety. This anxiety is particularly acute for long-distance travel, where the vehicle must traverse vast stretches of road without the safety net of a nearby fueling point. Consequently, city planners and engineers face a complex puzzle: where exactly should these stations be built to serve the most people efficiently, without wasting money on redundant infrastructure?

This question is not merely about picking spots on a map; it is a massive mathematical challenge. The transportation network is a web of roads connecting thousands of towns and intersections, with millions of potential trips happening every day. To find the perfect solution, computers must analyze every possible route, every possible charging technology, and every possible combination of station locations. As the size of the road network grows, the number of calculations required explodes, often overwhelming even the most powerful supercomputers. Traditional methods that try to solve the entire problem at once often get stuck, unable to find a good answer within a reasonable amount of time. Researchers at University College Dublin have developed a new way to tackle this problem by breaking the massive network into smaller, manageable pieces, allowing them to find high-quality solutions for large-scale highway systems that were previously too difficult to solve.

The researchers focused on the Irish highway network, a system of 90 key nodes representing major towns and intersections. Their goal was to determine the optimal locations for new charging stations, balancing two competing goals: keeping the cost of building and operating the stations as low as possible, and minimizing the extra time drivers spend charging or taking detours to reach a charger. They used a sophisticated model that accounts for different types of charging, such as slow plug-in chargers, fast chargers, and battery-swapping facilities, as well as the fact that drivers might take slightly longer routes to reach a station if it saves them time overall. When they attempted to solve this problem using standard, direct methods on a powerful computer, the system struggled. Even after running for five hours, the computer could not find a solution that was both cheap and efficient, often leaving the cost of the proposed network significantly higher than necessary.

To overcome this hurdle, the team introduced a graph-based decomposition framework. Instead of trying to solve the entire highway network as one giant block, they used mathematical techniques to slice the network into smaller, distinct sub-networks. Imagine the highway system as a large, tangled ball of string; the researchers' method carefully untangles it into several smaller, neat bundles. They tested three different ways of cutting these bundles: one method that grouped towns based on administrative boundaries, another that used a high-quality algorithm to balance the traffic flow between groups, and a third that clustered towns based on how close they were to one another. Once the network was divided, the researchers solved the charging station problem for each small bundle independently. They then stitched these local solutions back together, adding a few extra stations to handle the traffic that moved between the different bundles. Finally, they ran a refinement process to remove any unnecessary stations and ensure the entire system worked smoothly as a whole.

The results of this approach were striking. By breaking the problem down, the researchers were able to find solutions that were not only faster to compute but also significantly better than those found by the direct method. In their tests, the decomposition framework produced charging station networks that cost substantially less to build and operate while still meeting the time constraints for drivers. For instance, in one scenario where the direct method failed to find a good solution after five hours, the decomposition method found a superior solution in less than an hour. The study showed that the way the network was cut mattered greatly. The method that balanced the traffic flow between the smaller groups performed the best, suggesting that a good solution depends on understanding how people actually move across the landscape, not just on how the roads are physically connected.

The researchers also discovered that simply making the pieces smaller was not always better. If they cut the network into too many tiny fragments, the connections between the pieces became too weak, and the final solution suffered. The most effective approach was a moderate division that preserved the natural flow of traffic while keeping the individual problems small enough to solve quickly. This finding offers a clear path forward for planners: the key to solving these massive infrastructure puzzles lies in respecting the underlying structure of the network and the patterns of human travel. By using this decomposition framework, planners can now tackle large-scale charging station problems that were previously out of reach, ensuring that the electric vehicle revolution is supported by a robust, efficient, and well-planned network of charging infrastructure.

Technical Summary: A Graph-based Decomposition Framework for Flow-based Charging Station Location Problems

Problem Statement

The Charging Station Location Problem (CSLP) is critical for supporting the widespread adoption of Electric Vehicles (EVs) and achieving carbon neutrality targets. While advanced flow-based CSLP models have been developed to account for realistic constraints—such as heterogeneous charging technologies, capacity limits, routing deviations, and multi-objective trade-offs between infrastructure cost and user travel time—solving these models on large-scale transportation networks remains computationally prohibitive.

Existing decomposition techniques for CSLP typically partition the optimization model by separating variables, constraints, or scenarios. However, these methods often fail to leverage the underlying topological structure of the transportation network. Consequently, there is a gap in the literature regarding graph-based decomposition approaches that preserve network connectivity and spatial flow distributions, particularly for bi-objective flow-based models where global trade-offs are difficult to maintain when subproblems are solved independently.

Methodology

The paper proposes a graph-based decomposition framework designed to solve large-scale, bi-objective flow-based CSLP models. The framework is illustrated using the Capacitated Multi-Path Refuelling Location Model with Multiple Types of Charging Stations (CMPRLM-MTCS), a bi-objective Mixed-Integer Linear Program (MILP) that minimizes:

$z_1$ : Total investment and operational costs of new stations and expansions.
$z_2$ : Total additional travel time (charging time + deviation time) experienced by EV users.

The framework operates through a four-stage process:

1. Network Decomposition

The original transportation network $G=(N, A)$ is decomposed into $P$ disjoint subnetworks using graph partitioning or clustering techniques. The study evaluates three specific methods:

KaHIP: A high-quality graph partitioning tool that minimizes edge cuts while balancing node weights (traffic flow).
Geographical Partitioning: Decomposition based on administrative regions (e.g., Irish provinces), further refined using KaHIP.
Hierarchical Clustering: Agglomerative clustering based on inter-cluster distances, with variants for unweighted and flow-weighted O-D pairs.

2. Traffic Flow Decomposition and Subproblem Solving

Traffic demand is categorized into three components:

Intra-subnetwork flows: O-D pairs within the same subnetwork. These are solved as independent CSLP subproblems.
Aggregated inter-subnetwork flows: O-D pairs crossing subnetwork boundaries. To avoid reintroducing the full computational burden, these flows are aggregated into representative O-D pairs connecting subnetworks. The selection of representatives is based on distance metrics (mean, median, flow-weighted mean/median) relative to the EV driving range.
Unserved flows: Residual O-D pairs that remain uncovered after solving the first two stages.

The framework solves the intra-subnetwork subproblems first, fixing the resulting station locations as existing facilities. It then solves a subproblem for the aggregated inter-subnetwork flows.

3. Recovery and Integration

Since solving decomposed subproblems independently does not guarantee a feasible solution for the original global problem (specifically regarding the global time constraint $z_2$ ), a recovery step is introduced. A relaxed version of the original model ( $M''$ ) is solved to identify any unserved O-D pairs. A penalty term is added to the objective function to force the selection of additional stations to cover these residual flows.

4. Final Refinement

A post-processing refinement algorithm (Algorithm 1) is applied to the integrated solution. This stage:

Assigns the most efficient charging type to selected locations.
Iteratively removes redundant stations if feasibility is preserved.
Performs charging-type exchanges (e.g., swapping station types between locations) to reduce total cost while maintaining feasibility.

Key Contributions

Novel Framework: The paper introduces a decomposition strategy that partitions the network topology rather than just the optimization variables, preserving essential spatial and topological features of the original large-scale instance.
Bi-Objective Adaptation: The framework specifically addresses the challenges of bi-objective optimization in decomposition. It employs a recovery mechanism and a global constraint preservation strategy (using the $\epsilon$ -constraint method) to ensure that local subproblem solutions integrate into a high-quality global solution without losing the intended trade-off between cost and time.
Aggregation Strategy: It proposes a method for aggregating inter-subnetwork flows using representative O-D pairs, balancing computational efficiency with the need to capture spatial distribution features better than single-node medoid approaches.
Empirical Evaluation: The study provides a systematic evaluation of different decomposition configurations (varying methods, number of subnetworks $P$ , and weighting schemes) using both graph-based indicators (e.g., edge cuts, subnetwork diameter) and flow-based indicators (e.g., flow load imbalance, inter-subnetwork flow ratio).

Experimental Results

The framework was tested on a 90-node Irish highway network instance. Computational experiments compared the decomposition framework against solving the original model directly using the Gurobi optimizer (with a 18,000-second time limit).

Computational Efficiency: The decomposition framework consistently achieved solutions with lower cost-related objective values ( $z_1$ ) in substantially shorter computation times (typically under 4,000 seconds) compared to the Gurobi benchmark.
Solution Quality: For challenging instances (e.g., tighter time constraints with $\alpha=0.9$ or larger deviation allowances), Gurobi often failed to find high-quality feasible solutions within the time limit, returning high costs or large integrality gaps. The decomposition framework successfully found feasible, lower-cost solutions.
Method Comparison: KaHIP-based decompositions generally yielded the best CSLP outcomes, outperforming both geographical partitioning and hierarchical clustering. This suggests that maintaining balanced traffic loads and minimizing edge cuts is more critical for CSLP performance than purely spatial compactness.
Impact of $P$ : Increasing the number of subnetworks ( $P$ ) did not linearly improve performance. Overly fine decompositions (e.g., $P=13$ or $18$) fragmented the network, increased the proportion of inter-subnetwork flows, and degraded solution quality. Moderate decomposition levels (e.g., $P=6$ or $9$) proved optimal.
Weighting Schemes: Incorporating edge weights and O-D flow weights into the decomposition process generally improved CSLP results, highlighting the importance of reflecting both network structure and traffic demand intensity in the partitioning process.

Significance and Claims

The paper claims that the proposed framework offers an effective and scalable solution strategy for bi-objective flow-based CSLP models on large-scale transportation networks. Its significance lies in:

Bridging the Gap: It connects network decomposition analysis with CSLP optimization, demonstrating that preserving topological features and flow patterns is crucial for solution quality.
Practical Applicability: The framework supports a progressive planning logic (local deployment $\to$ inter-regional support $\to$ system-wide refinement) that mirrors real-world infrastructure deployment strategies.
Performance: It demonstrates that decomposition based on network topology can outperform direct optimization and variable-based decomposition methods in terms of both computational time and solution cost for complex, large-scale EV infrastructure planning problems.

The authors conclude that while the framework is promising, future research should explore adaptive rules for selecting the number of subnetworks, advanced strategies for inter-subnetwork flow handling, and the integration of meta-heuristics into the framework stages.