Routing Strategies

Routing Strategies#

New in v0.7.0

Pluggable routing strategies allow you to control how the primary distribution network topology is constructed from road network data.

Overview#

Distribution networks are typically routed along public roads. The choice of how to select which road segments become power line paths is a key design decision. SHIFT provides multiple routing formulations drawn from the synthetic distribution grid generation literature.

Each strategy implements the RoutingStrategy interface and can be passed to PRSG via the routing_strategy parameter.

Available Strategies#

`SteinerTreeStrategy` (default)#

Steiner tree approximation with uniform edge weights. This is the original SHIFT algorithm — preserved as the default for backward compatibility.

Algorithm: Mehlhorn approximation of the Steiner tree
Edge weights: All edges weighted equally (weight = 1)
Topology: Minimum-node tree connecting all terminals
Trade-off: Fast, but ignores physical distance → can produce jagged paths

`WeightedSteinerTreeStrategy`#

Steiner tree with geodesic distance as edge weight. Produces more realistic routing by preferring physically shorter paths.

Algorithm: Mehlhorn Steiner tree with distance-weighted edges
Edge weights: Geodesic distance (meters) or user-supplied weight_fn
Topology: Distance-minimizing tree
Trade-off: Slightly slower, but significantly more realistic paths

Custom weight functions

Pass a callable weight_fn(graph, u, v) -> float to implement custom weighting policies such as penalizing road crossings or applying distance-zone penalties [CGdO+26].

References: Ali et al. [APM+23], Caetano et al. [CGdO+26]

`ShortestPathTreeStrategy`#

Dijkstra shortest-path tree from the source node to all other terminals.

Algorithm: Dijkstra’s algorithm from source to each terminal
Edge weights: Geodesic distance or user-supplied weight_fn
Topology: Star-like trunk from substation, with shared path segments
Trade-off: Always follows the true shortest road path; may produce longer total wire length than Steiner tree

Reference: Ali et al. [APM+23]

`MinimumSpanningTreeStrategy`#

MST over terminals using pairwise shortest-path distances in the road graph.

Algorithm: (1) Compute all-pairs shortest paths between terminals, (2) Build complete distance graph, (3) Find MST, (4) Map back to road paths
Edge weights: Geodesic distance or user-supplied weight_fn
Topology: Trunk-branch (feeder backbone with laterals)
Trade-off: Optimal total wire length; more computation for many terminals

`FullRoadGraphStrategy`#

Returns the full road network without reduction — power lines follow all available road paths.

Algorithm: Connected-component extraction (no tree reduction)
Topology: Meshed (may contain cycles)
Trade-off: Most realistic for urban networks with redundant paths; not radial

Reference: Ali et al. [APM+23]

`CostOptimizedStrategy` (placeholder)#

MILP cost-minimization with binary decision variables per candidate edge.

Formulation: Minimize investment cost + operational losses subject to radiality and AC power flow constraints
Status: Interface defined; implementation requires external solver (PuLP/Pyomo)
Use case: Planning-grade synthetic grids matching utility practice

Reference: Trpovski et al. [TRH18]

Usage Examples#

Basic usage (weighted Steiner tree)#

from shift import PRSG, WeightedSteinerTreeStrategy, GeoLocation

builder = PRSG(
    groups=clusters,
    source_location=GeoLocation(-97.3, 32.75),
    routing_strategy=WeightedSteinerTreeStrategy(),
)
graph = builder.get_distribution_graph()

Custom weight function#

from shift import WeightedSteinerTreeStrategy
from shift.utils.split_network_edges import get_distance_between_points
from shift.data_model import GeoLocation

def penalized_weight(graph, u, v):
    """Super-linear distance penalty — discourages long edges."""
    dist = get_distance_between_points(
        GeoLocation(graph.nodes[u]["x"], graph.nodes[u]["y"]),
        GeoLocation(graph.nodes[v]["x"], graph.nodes[v]["y"]),
    ).to("m").magnitude
    return dist ** 1.5

strategy = WeightedSteinerTreeStrategy(weight_fn=penalized_weight)

Full road graph (no reduction)#

from shift import PRSG, FullRoadGraphStrategy, GeoLocation

builder = PRSG(
    groups=clusters,
    source_location=GeoLocation(-97.3, 32.75),
    routing_strategy=FullRoadGraphStrategy(),
)

API Reference#

class shift.RoutingStrategy#

Abstract base class for routing strategies.

A routing strategy determines how a subset of terminal nodes are connected through a candidate network graph, producing a tree subgraph that connects all terminals.

abstract route(graph: Graph, terminal_nodes: list[str]) → Graph#

Connect terminal nodes through the candidate graph.

Parameters:

graph (nx.Graph) – Candidate network graph with node attributes ‘x’ and ‘y’ representing longitude and latitude respectively.
terminal_nodes (list[str]) – List of node names that must be connected in the result.

Returns:

A connected subgraph (tree) containing all terminal nodes.

Return type:

nx.Graph

class shift.SteinerTreeStrategy#

Bases: RoutingStrategy

Steiner tree with uniform edge weights (current default behavior).

Produces the Steiner tree approximation using the Mehlhorn method with all edges weighted equally at 1. This preserves the original SHIFT behavior for backward compatibility.

route(graph: Graph, terminal_nodes: list[str]) → Graph#

Connect terminal nodes through the candidate graph.

Parameters:

graph (nx.Graph) – Candidate network graph with node attributes ‘x’ and ‘y’ representing longitude and latitude respectively.
terminal_nodes (list[str]) – List of node names that must be connected in the result.

Returns:

A connected subgraph (tree) containing all terminal nodes.

Return type:

nx.Graph

class shift.WeightedSteinerTreeStrategy(weight_fn: Callable[[Graph, str, str], float] | None = None, crossing_penalty: float = 1.0)#

Bases: RoutingStrategy

Steiner tree with distance-based edge weights and optional crossing penalty.

Uses geodesic distance as edge weights for the Steiner tree approximation. Optionally penalizes edges that would cross other edges in the graph, encouraging non-crossing topologies.

Parameters:

weight_fn (Callable[[nx.Graph, str, str], float], optional) – Custom weight function. Defaults to geodesic distance in meters.
crossing_penalty (float, optional) – Multiplicative penalty applied for each crossing detected. Default 1.0 (no penalty). Values > 1 discourage crossings. Typical values: 2.0–5.0 for moderate penalty.

References

Ali et al. 2023: distance-based power line routing
Caetano et al. 2026: distance-zone weighting concept

route(graph: Graph, terminal_nodes: list[str]) → Graph#

Connect terminal nodes through the candidate graph.

Parameters:

graph (nx.Graph) – Candidate network graph with node attributes ‘x’ and ‘y’ representing longitude and latitude respectively.
terminal_nodes (list[str]) – List of node names that must be connected in the result.

Returns:

A connected subgraph (tree) containing all terminal nodes.

Return type:

nx.Graph

class shift.ShortestPathTreeStrategy(weight_fn: Callable[[Graph, str, str], float] | None = None)#

Bases: RoutingStrategy

Shortest-path tree from a source node to all other terminals.

Builds a tree by computing shortest paths (Dijkstra) from the first terminal node (typically the source/substation) to all other terminals, using geodesic distance as edge weights. The result follows roads naturally, producing a star/trunk topology.

Parameters:: weight_fn (Callable[[nx.Graph, str, str], float], optional) – Custom weight function. Defaults to geodesic distance.

References

Ali et al. 2023: full road graph routing where power lines = road paths

route(graph: Graph, terminal_nodes: list[str]) → Graph#

Connect terminal nodes through the candidate graph.

Parameters:

graph (nx.Graph) – Candidate network graph with node attributes ‘x’ and ‘y’ representing longitude and latitude respectively.
terminal_nodes (list[str]) – List of node names that must be connected in the result.

Returns:

A connected subgraph (tree) containing all terminal nodes.

Return type:

nx.Graph

class shift.MinimumSpanningTreeStrategy(weight_fn: Callable[[Graph, str, str], float] | None = None)#

Bases: RoutingStrategy

Minimum spanning tree over terminal nodes using shortest-path distances.

Computes pairwise shortest-path distances between all terminals in the candidate graph, builds a complete distance graph, finds its MST, then maps each MST edge back to the actual shortest path in the original graph. Produces realistic trunk-branch topology.

Parameters:: weight_fn (Callable[[nx.Graph, str, str], float], optional) – Custom weight function for the candidate graph edges. Defaults to geodesic distance.

route(graph: Graph, terminal_nodes: list[str]) → Graph#

Connect terminal nodes through the candidate graph.

Parameters:

graph (nx.Graph) – Candidate network graph with node attributes ‘x’ and ‘y’ representing longitude and latitude respectively.
terminal_nodes (list[str]) – List of node names that must be connected in the result.

Returns:

A connected subgraph (tree) containing all terminal nodes.

Return type:

nx.Graph

class shift.FullRoadGraphStrategy#

Bases: RoutingStrategy

Uses the road network graph directly without reduction.

Instead of computing a Steiner tree or MST, this strategy returns the full candidate graph (typically the road network) as-is. The assumption is that power lines follow road paths directly.

The resulting graph is pruned to only include nodes reachable from the first terminal (connected component), ensuring connectivity.

References

Ali et al. 2023: “power lines follow road paths” — road network = power line topology directly

route(graph: Graph, terminal_nodes: list[str]) → Graph#

Connect terminal nodes through the candidate graph.

Parameters:

graph (nx.Graph) – Candidate network graph with node attributes ‘x’ and ‘y’ representing longitude and latitude respectively.
terminal_nodes (list[str]) – List of node names that must be connected in the result.

Returns:

A connected subgraph (tree) containing all terminal nodes.

Return type:

nx.Graph

class shift.CostOptimizedStrategy#

Bases: RoutingStrategy

Cost-optimized routing via MILP (placeholder).

Based on the formulation by Trpovski et al. 2018, this strategy conceptually uses binary edge-decision variables to minimize investment and operating costs under radiality and power-flow constraints.

This is a placeholder that documents the interface. Full implementation requires an external MILP solver (e.g., PuLP, scipy.optimize, or Pyomo).

References

Trpovski, Recalde, Hamacher. “Synthetic Distribution Grid Generation Using Power System Planning: Case Study of Singapore.” IEEE 2018.

route(graph: Graph, terminal_nodes: list[str]) → Graph#

Connect terminal nodes through the candidate graph.

Parameters:

graph (nx.Graph) – Candidate network graph with node attributes ‘x’ and ‘y’ representing longitude and latitude respectively.
terminal_nodes (list[str]) – List of node names that must be connected in the result.

Returns:

A connected subgraph (tree) containing all terminal nodes.

Return type:

nx.Graph

References#

[APM+23] (1,2,3)

M. Ali, K. Prakash, C. Macana, M.Q. Raza, A.K. Bashir, and H. Pota. Modeling synthetic power distribution network and datasets with industrial validation. Journal of Industrial Information Integration, 31:100407, 2023. doi:10.1016/j.jii.2022.100407.

[CGdO+26] (1,2)

Henrique O. Caetano, Rahul K. Gupta, Cristhian G. da R. de Oliveira, João B.A. London Jr, and Carlos Dias Maciel. Bayesian model-based generation of synthetic unbalanced distribution networks incorporating reliability indices. Electric Power Systems Research, 262:113604, 2026. doi:10.1016/j.epsr.2026.113604.

[TRH18]

Andrej Trpovski, Dante Recalde, and Thomas Hamacher. Synthetic distribution grid generation using power system planning: case study of singapore. In 2018 IEEE PES Innovative Smart Grid Technologies Conference Europe (ISGT-Europe), 1–6. IEEE, 2018. doi:10.1109/ISGTEurope.2018.8571800.

Routing Strategies

Contents

Routing Strategies#

Overview#

Available Strategies#

SteinerTreeStrategy (default)#

WeightedSteinerTreeStrategy#

ShortestPathTreeStrategy#

MinimumSpanningTreeStrategy#

FullRoadGraphStrategy#

CostOptimizedStrategy (placeholder)#

Usage Examples#

Basic usage (weighted Steiner tree)#

Custom weight function#

Full road graph (no reduction)#

API Reference#

References#

`SteinerTreeStrategy` (default)#

`WeightedSteinerTreeStrategy`#

`ShortestPathTreeStrategy`#

`MinimumSpanningTreeStrategy`#

`FullRoadGraphStrategy`#

`CostOptimizedStrategy` (placeholder)#