⚡ electrical engineering

Exact and Evolutionary Algorithms for Sequential Multi-Objective Transmission Topology Planning

This paper presents an exact block enumeration algorithm and a tailored NSGA-III evolutionary heuristic to solve the sequential multi-objective transmission topology planning problem, demonstrating that the exact method efficiently computes the full Pareto front for real-world Dutch grid data while serving as a ground-truth benchmark for future approaches.

Original authors: Job Groeneveld, Miguel Muñoz, Jan Viebahn, Alessandro Zocca

Published 2026-05-06

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Job Groeneveld, Miguel Muñoz, Jan Viebahn, Alessandro Zocca

Original paper licensed under CC BY 4.0 (http://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

Imagine a massive, high-stakes game of electrical Tetris.

In this game, the "blocks" are electricity flowing through power lines, and the "board" is the national power grid. The goal is to keep the blocks from piling up too high (which causes dangerous overloads) while following strict rules about how the blocks can move.

This paper tackles a specific version of this game: How should a power grid operator rearrange the connections in their network over the next 24 hours to prevent blackouts and overloads, while keeping costs and effort low?

Here is the breakdown of the paper's story, using simple analogies:

The Problem: The Grid is Stressed

Think of the power grid like a busy highway system. Recently, more and more "cars" (electricity from wind and solar farms) have been added to the roads. But the roads haven't been widened fast enough. This causes traffic jams (congestion).

If a road gets too crowded, it can overheat and break. To fix this, operators usually have two choices:

Turn off some cars: Tell wind farms to stop generating power (this costs money and wastes green energy).
Reroute the traffic: Open and close switches in the substations to change the shape of the road network, allowing traffic to flow more smoothly.

The paper focuses on Option 2. The challenge is that you can't just change the roads once; you have to plan a new road map for every single hour of the next day. And you have to balance four competing goals:

Safety: Keep the heaviest traffic load as low as possible (so no lines break).
Simplicity: Don't make the road network too complicated (fewer open switches).
Effort: Don't change the road map too many times (switching gears wears out the machinery).
Stability: Try to keep the "default" road map as much as possible, only changing it when absolutely necessary.

The Solution: Two Different Approaches

The authors built two different "players" to solve this 24-hour planning puzzle.

Player 1: The "Block" Algorithm (The Perfect Planner)

Imagine you are trying to solve a puzzle, but you realize that the puzzle pieces don't need to change every single second. If the traffic is light from 2:00 AM to 4:00 AM, you don't need a new plan for 2:01, 2:02, etc. You can just keep the same plan for that whole block of time.

The Block Algorithm uses this trick. Instead of checking every single hour individually, it groups hours into "blocks" where the plan stays the same.

How it works: It systematically tries every possible combination of these time-blocks and road layouts.
The Result: It finds the perfect list of all possible "best" plans. In math terms, it finds the "Pareto front." This means it shows the operator every possible trade-off: "If you want maximum safety, here is the plan. If you want to switch less, here is the plan. If you want a balance, here is the plan."
Speed: Surprisingly, even though there are millions of possibilities, this algorithm is so smart about grouping time that it solves a full day's plan in under 3 minutes.

Player 2: The Evolutionary Algorithm (The Trial-and-Error Explorer)

This player is like a biological evolution simulator.

How it works: It starts with a random crowd of 1,000 different plans. It lets them "mate" (combine parts of two plans) and "mutate" (randomly change a part of a plan). It keeps the best plans and throws away the bad ones, repeating this process over and over.
The Goal: To eventually "evolve" a set of good plans that look like the perfect list.
The Result: It gets close to the perfect list, but it misses some of the very best options. It's like a hiker trying to find the highest peak in a foggy mountain range; they might find a high peak, but they might miss the absolute highest one because they can't see the whole map.

The Showdown: Who Won?

The authors tested both players using real data from the Dutch power grid (TenneT) on a day when the grid was under extreme stress.

The Perfect Planner (Block Algorithm) won. It found the complete list of 83 "perfect" trade-off strategies in under 3 minutes.
The Explorer (Evolutionary Algorithm) came in second. It found some good strategies, but it missed the very best ones. Specifically, it failed to find any plans that could keep the grid 100% safe without overloading lines, whereas the Perfect Planner found several.

The Big Takeaway

The paper claims that for this specific type of power grid problem, you don't need to guess or use "smart" AI approximations. Because the problem has a special "block" structure (plans stay the same for chunks of time), you can actually calculate the exact, perfect answer very quickly.

Why does this matter?

For Grid Operators: They now have a tool that gives them a complete menu of perfect options to choose from, rather than just a guess.
For Future Research: This "Perfect Planner" now serves as the "Gold Standard" (or ground truth). Any new AI or machine learning method developed in the future can be tested against this list to see if it's actually good or just lucky.

In short: The authors found a way to solve a complex, 24-hour power grid puzzle perfectly and instantly, proving that sometimes the "brute force" method, when done smartly, is better than the "smart" guessing method.

Technical Summary: Exact and Evolutionary Algorithms for Sequential Multi-Objective Transmission Topology Planning

Problem Formulation
The paper addresses day-ahead transmission topology planning as a sequential, multi-objective optimization problem. The goal is to determine a sequence of network topologies over a 24-hour horizon (24 time steps) to manage grid congestion. The problem is defined by four operational objectives reflecting real Transmission System Operator (TSO) decision criteria, all of which are to be minimized:

Worst-case line loading ( $LF_1$ ): The maximum capacity utilization of any transmission line under $N-1$ security contingencies across the entire horizon.
Topological depth ( $d$ ): The maximum number of additional busbars created by opening busbar couplers (node splitting) relative to the reference topology (all couplers closed) at any point in time.
Number of switching actions ( $w$ ): The total count of topology changes (switches) performed over the 24-hour period.
Utilization of non-reference topologies ( $z$ ): The number of time steps where the network operates in a configuration different from the default reference topology.

The study utilizes real operational data from the Dutch high-voltage grid managed by TenneT TSO, focusing on a highly congested day where the reference topology frequently exceeds 100% loading under $N-1$ conditions.

Methodology
The authors propose and compare two complementary algorithms: an exact enumeration method and a tailored evolutionary heuristic.

The Block Algorithm (Exact Method):
- Core Concept: This algorithm exploits the temporal block structure of feasible strategies. Instead of evaluating every time step independently, it partitions the 24-hour horizon into contiguous, non-overlapping intervals (blocks) where the topology remains constant.
- Mechanism: It systematically enumerates all possible block configurations, reference topology assignments, and depth levels. By pre-computing load-flow values for all available topologies per time step, the algorithm evaluates combinations of blocks to identify the complete Pareto front.
- Complexity: For fixed operational bounds on maximum depth ( $d_{max}$ ) and maximum switching count ( $s_{max}$ ), the evaluation count grows polynomially with the planning horizon. The algorithm filters strategies based on non-dominated sorting, leveraging the fact that three of the four objectives are discrete integers to efficiently identify Pareto-optimal solutions.
Multi-Objective Evolutionary Algorithm (MOEA):
- Framework: Based on NSGA-III, selected for its effectiveness in many-objective problems (four objectives).
- Representation: Uses direct variable-length encoding where each gene represents the topology for a specific time step.
- Initialization: Employs a "structure-guided" sampling strategy rather than uniform random initialization. It generates initial populations by balancing specific switch counts and topological depths to ensure diversity in the relevant objective-space dimensions.
- Variation: Uses $k$ -point crossover (with $k=2$ ) to preserve temporal coherence and random-reset mutation to ensure feasibility within the set of available topologies for each time step.

Key Contributions

Formalization: The problem is formally defined as a sequential multi-objective optimization with four specific TSO-relevant objectives, moving beyond single-objective or isolated time-step formulations.
Exact Enumeration: The development of the "block algorithm," which computes the complete Pareto front for a real-world congested day in under three minutes. It provides a ground-truth benchmark for this problem class.
Tailored Heuristic: The design of a specialized MOEA with structure-guided initialization and problem-specific variation operators, evaluated against the exact front using Inverted Generational Distance Plus (IGD+) and a novel multi-front coverage metric.
Empirical Validation: A comparative study using TenneT data demonstrating that exact enumeration is computationally feasible and outperforms evolutionary search in recovering the full set of optimal strategies.

Results

Performance of the Block Algorithm: The exact method successfully enumerated the full Pareto front, identifying 83 unique points in the objective space (representing 163,807,652 distinct strategies). It found that achieving $LF_1 < 100\%$ (full $N-1$ security) requires abandoning the reference topology entirely during congested hours and operating at higher topological depths.
Performance of the MOEA: The evolutionary algorithm converged toward the Pareto front but failed to recover the exact set of solutions.
- The best-performing configuration (population size 1,621, mutation rate 0.10) recovered only approximately 6% of the unique Pareto-optimal points found by the block algorithm.
- The MOEA struggled to find solutions with $LF_1 < 100\%$ , which were identified by the exact method.
- Coverage was particularly low for strategies involving many non-reference topologies (extreme regions of the search space).
Comparison: While the MOEA showed rapid initial convergence (within 5 minutes), it plateaued and could not match the completeness of the block algorithm. The block algorithm's ability to enumerate all feasible strategies allowed it to identify trade-offs that the heuristic missed.

Significance and Claims
The paper claims that the combinatorial complexity of optimizing topological strategies over a 24-hour horizon, often perceived as intractable, can be resolved exactly and efficiently by exploiting the problem's temporal block structure.

Decision Support: The block algorithm provides TSOs with a complete menu of Pareto-optimal strategies, allowing operators to select actions based on specific daily priorities (e.g., minimizing switches vs. maximizing security).
Benchmarking: The exact front serves as a rigorous ground-truth benchmark for evaluating future heuristic and learning-based methods.
Feasibility: The study demonstrates that exact enumeration is not only theoretically possible but practically viable for real-world, highly congested grid scenarios, challenging the assumption that heuristics are strictly necessary for such problems.

The authors acknowledge limitations, including the use of DC power flow approximations, deterministic forecasts, and the reliance on precomputed datasets. They suggest future work could involve stochastic formulations, robust optimization, and the application of imitation learning to bypass the precomputation bottleneck. However, within the scope of the study, the block algorithm is presented as the preferred method for its exactness, speed, and completeness.