Smart Grid Routing
Shortest Path · Network Optimization · Polynomial
Distribution losses account for 5–8% of total electricity delivered, costing utilities €200–€500M annually for mid-size grids. Every hour, a distribution management system must decide how to route power through the distribution network to minimize losses and maintain voltage stability. This is a shortest-path / minimum-cost flow problem — solvable in polynomial time — where switching topology and distributed generation create dynamic routing opportunities.
Where This Decision Fits
Energy sector decision chain — the highlighted step is what this page optimizes
The Problem
Minimizing distribution losses across a dynamic power network
Consider a distribution network modelled as a directed graph with 12 nodes (substations, feeders, and distributed energy resources) connected by 18 edges (transmission lines), each with a capacity limit and a loss rate proportional to the power flowing through it. The network has 3 supply points (substations connected to the high-voltage grid or local generators) and 6 load points (residential and commercial feeders drawing power).
The objective is to route power from supply to demand while minimizing total distribution losses. Each edge has a per-unit loss coefficient that depends on line resistance, length, and current thermal conditions. The challenge intensifies when line outages force reconfiguration, or when distributed solar generation creates reverse power flows with negative effective costs on certain segments.
This maps directly to the Shortest Path and Min-Cost Flow problems from network optimization. Unlike NP-hard combinatorial problems, these admit polynomial-time exact algorithms — Dijkstra's algorithm runs in O((V+E) log V) and Bellman-Ford in O(VE) — making real-time re-optimization feasible even for large distribution grids.
subject to
Σj fij − Σj fji = bi // flow conservation at each node i
0 ≤ fij ≤ uij // capacity constraints on each edge
// bi > 0 supply, bi < 0 demand, bi = 0 transit
Try It Yourself
Route power through the distribution grid — toggle lines on/off, select algorithms
Grid Topology Solver
12 Nodes · 18 Edges| Supply → Load | Path | Loss (%) | Flow (MW) |
|---|---|---|---|
| Click Solve to compute routes | |||
The Algorithms
Three approaches to finding minimum-loss routes through the distribution grid
1. Dijkstra's Algorithm
GreedyDijkstra's algorithm (1959) finds the shortest path from a single source to all reachable nodes by greedily expanding the closest unvisited node. It maintains a priority queue of tentative distances and relaxes edges in order of increasing cost.
Grid application: Ideal for normal operating conditions where all line loss coefficients are non-negative. Finds the minimum-loss path from each substation to every load point in a single pass.
Limitation: Cannot handle negative edge weights, which arise when distributed energy resources (solar, batteries) inject power that effectively reduces losses on certain segments.
2. Bellman-Ford Algorithm
Dynamic ProgrammingThe Bellman-Ford algorithm (1958) relaxes all edges V−1 times, guaranteeing shortest paths even with negative edge weights. An additional pass detects negative-weight cycles.
Grid application: Essential for the High DER Penetration scenario where solar feed-in creates negative effective costs on certain lines. The algorithm correctly routes power through segments where DER injection reduces net losses below zero.
Trade-off: Slower than Dijkstra by a factor of O(V / log V), but necessary when the grid has negative-cost edges from distributed generation.
3. Min-Cost Flow (Successive Shortest Paths)
Network OptimizationThe min-cost flow formulation considers the entire network simultaneously, respecting capacity constraints on every edge while minimizing total weighted loss. It uses successive shortest-path augmentation with Johnson's potential technique to handle capacitated multi-commodity flows.
Grid application: Provides the globally optimal solution by jointly routing power from all supply points to all demand points, accounting for shared line capacity. This is the gold standard for distribution management systems.
Advantage: Unlike per-source shortest paths, min-cost flow prevents capacity violations when multiple supply-demand pairs share lines, producing a feasible and optimal network-wide routing.
Complexity Summary
- Dijkstra: O((V+E) log V) — fastest for non-negative weights; real-time capable for grids with 10,000+ nodes
- Bellman-Ford: O(VE) — handles negative costs from DER feed-in; detects negative cycles indicating unstable configurations
- Min-Cost Flow: O(V · E · log V) — globally optimal multi-source multi-sink routing respecting all capacity limits
- All polynomial: Unlike facility location or unit commitment (NP-hard), shortest-path problems admit exact polynomial-time solutions, enabling real-time grid re-optimization every few seconds
Key References
Foundational works on shortest-path algorithms and network optimization
- (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1(1), 269–271. doi:10.1007/BF01386390
- (1958). On a routing problem. Quarterly of Applied Mathematics, 16(1), 87–90. doi:10.1090/qam/102435
- (1987). Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM, 34(3), 596–615. doi:10.1145/28869.28874