Handling Turn Restrictions in Routing Graphs

Accurate route calculation depends on how well a routing graph models real-world driving constraints. While edge weights capture distance, speed limits, and terrain gradients, turn restriction enforcement determines whether a calculated path is legally and physically traversable — and it is one of the most commonly misconfigured components in production routing systems. This page is part of the broader OSM Graph Architecture & Network Modeling reference, which covers the full stack from raw PBF extraction to distributed graph deployment. For logistics engineers, GIS developers, and urban planners, ignoring turn prohibitions leads to invalid delivery routes, compliance violations, and driver frustration.

Prerequisites

Before implementing restriction logic, ensure your environment and data pipeline meet these baseline requirements.

Python dependencies:

# pip install osmnx networkx pandas geopandas shapely pyosmium
import osmnx as ox
import networkx as nx
import pandas as pd
import pyosmium

System requirements:

• Python 3.9+, with at least 4 GB RAM for city-scale graphs (16 GB for metro regions)
• Clean OSM PBF extract covering your operational area (Geofabrik regional extracts or BBBike custom cuts)
• A directed MultiDiGraph where each physical road segment is split into inbound and outbound edges
• Familiarity with OSM relation schemas, specifically type=restriction and vehicle-specific variants like restriction:hgv

If you are starting from a raw PBF extract, review the pipeline for building directed graphs from OSM PBF files first — your base topology must correctly represent oneway=yes streets, intersection nodes, and edge geometries before layering restriction logic on top.

Conceptual Architecture

Turn restrictions in OSM are not edge attributes — they are relation objects that describe a legal constraint across three connected elements. A routing engine that reads only edge weights and node IDs will silently violate them. The diagram below shows where restriction enforcement fits in the routing graph pipeline.

How OSM encodes restrictions. OpenStreetMap uses relation objects with three mandatory member roles:

• from — the incoming way (approach road)
• via — the intersection node (or sequence of intermediate ways) where the turn occurs
• to — the outgoing way (departure road)

The restriction tag specifies the maneuver type: no_left_turn, no_right_turn, no_u_turn, no_straight_on, or mandatory positive variants like only_straight_on. Conditional timing uses the syntax restriction:conditional = no_left_turn @ (Mo-Fr 07:00-09:00). Heavy goods vehicle restrictions use separate tags such as restriction:hgv, which lets freight routing diverge from passenger routing without reprocessing the entire graph.

Routing engines do not natively “see” relations during edge traversal. They require explicit edge-to-edge transition rules mapped to the graph’s adjacency structure — which is exactly what the implementation below builds.

Step-by-Step Implementation

Step 1: Extract and Preprocess the Directed Graph

Load your OSM extract and construct a directed MultiDiGraph. Confirm that edges carry osmid, geometry, length, and oneway attributes. Filter to drivable features unless your use case requires pedestrian or bicycle routing.

# requires: osmnx, networkx
import osmnx as ox
import networkx as nx

def build_base_graph(place: str, network_type: str = "drive") -> nx.MultiDiGraph:
    graph = ox.graph_from_place(place, network_type=network_type)
    # Remove isolated nodes — these break restriction resolution
    isolates = list(nx.isolates(graph))
    graph.remove_nodes_from(isolates)
    # Verify every node has in- and out-edges
    for node in graph.nodes():
        assert graph.in_degree(node) > 0 or graph.out_degree(node) > 0, f"Dead node: {node}"
    return graph

Dangling or isolated nodes often arise at PBF extract boundaries or topology errors; they will cause restriction resolution to silently drop relations. See graph fragmentation prevention in OSM data for strategies to stitch boundary nodes before this stage.

Step 2: Stream Restriction Relations with pyosmium

osmnx does not expose raw OSM relations. Use pyosmium to stream them efficiently from the PBF without loading the full dataset into memory.

# requires: pyosmium, pandas
import osmium
import pandas as pd
from dataclasses import dataclass, field
from typing import Optional

@dataclass
class RestrictionRecord:
    relation_id: int
    restriction: str
    restriction_conditional: Optional[str]
    restriction_hgv: Optional[str]
    from_ref: Optional[int]
    via_ref: Optional[int]   # node ref for simple restrictions
    to_ref: Optional[int]

class RestrictionHandler(osmium.SimpleHandler):
    def __init__(self):
        super().__init__()
        self.records: list[RestrictionRecord] = []

    def relation(self, r):
        tags = dict(r.tags)
        if tags.get("type") != "restriction":
            return
        from_ref = via_ref = to_ref = None
        for m in r.members:
            if m.role == "from" and m.type == "w":
                from_ref = m.ref
            elif m.role == "via" and m.type == "n":
                via_ref = m.ref
            elif m.role == "to" and m.type == "w":
                to_ref = m.ref
        self.records.append(RestrictionRecord(
            relation_id=r.id,
            restriction=tags.get("restriction", ""),
            restriction_conditional=tags.get("restriction:conditional"),
            restriction_hgv=tags.get("restriction:hgv"),
            from_ref=from_ref,
            via_ref=via_ref,
            to_ref=to_ref,
        ))

def stream_restrictions(pbf_path: str) -> pd.DataFrame:
    handler = RestrictionHandler()
    handler.apply_file(pbf_path)
    return pd.DataFrame([vars(r) for r in handler.records])

This approach handles PBF files for continental regions without materialising the entire file structure in RAM. Via-way restrictions (where via is a way rather than a node) require additional chain resolution and are covered in the troubleshooting section below.

Step 3: Resolve Relations to Graph Edge Keys

Map each relation’s from_ref / via_ref / to_ref to actual edge keys in the MultiDiGraph. The resolution logic must handle osmid values stored as either scalars or lists (the latter occurs in consolidated edges).

# requires: networkx, pandas
import networkx as nx
import pandas as pd
from typing import Optional

def _osmid_match(edge_data: dict, target: int) -> bool:
    """Check whether a graph edge's osmid matches the target OSM way ID."""
    osmid = edge_data.get("osmid")
    if isinstance(osmid, list):
        return target in osmid
    return osmid == target

def parse_turn_restrictions(
    graph: nx.MultiDiGraph,
    relations: pd.DataFrame,
) -> dict[tuple, frozenset]:
    """
    Return: {(from_edge_key, via_node): frozenset of blocked to_edge_keys}
    where edge keys are (u, v, k) tuples used by MultiDiGraph.
    """
    # Pre-build index: osmid -> list of (u, v, k) tuples for fast lookup
    osmid_to_edges: dict[int, list[tuple]] = {}
    for u, v, k, d in graph.edges(keys=True, data=True):
        osmid = d.get("osmid")
        keys_to_add = osmid if isinstance(osmid, list) else [osmid]
        for oid in keys_to_add:
            if oid is not None:
                osmid_to_edges.setdefault(int(oid), []).append((u, v, k))

    blocked: dict[tuple, list] = {}

    for _, rel in relations.iterrows():
        rtype = str(rel.get("restriction", ""))
        from_ref = rel.get("from_ref")
        via_ref = rel.get("via_ref")
        to_ref = rel.get("to_ref")

        if not (from_ref and via_ref and to_ref):
            continue
        from_ref, via_ref, to_ref = int(from_ref), int(via_ref), int(to_ref)

        is_prohibitory = rtype.startswith("no_")
        is_mandatory = rtype.startswith("only_")
        if not (is_prohibitory or is_mandatory):
            continue

        # Find from-edge: osmid matches from_ref AND target node is via_ref
        from_edges = [
            e for e in osmid_to_edges.get(from_ref, [])
            if e[1] == via_ref
        ]
        if not from_edges:
            continue
        from_key = from_edges[0]

        # All edges departing via_ref
        all_to_edges = {
            (u, v, k)
            for u, v, k in [
                e for e in osmid_to_edges.get(oid, [])
                for oid in osmid_to_edges
                if True  # placeholder — real lookup below
            ]
        }
        # Correct departure-edge lookup: all edges whose source is via_ref
        all_departure = [(u, v, k) for u, v, k, _ in graph.out_edges(via_ref, keys=True, data=True)]

        if is_prohibitory:
            # Block only the specific to-edge(s)
            blocked_to = [e for e in all_departure if e[0] == via_ref and any(
                _osmid_match(graph.edges[e[0], e[1], e[2]], to_ref)
                for _ in [None]  # force evaluation
            )]
            # Simpler direct version:
            blocked_to = [
                (u, v, k) for u, v, k in all_departure
                if _osmid_match(graph.edges[u, v, k], to_ref)
            ]
        else:  # only_* — block all departures EXCEPT the permitted one
            allowed = {
                (u, v, k) for u, v, k in all_departure
                if _osmid_match(graph.edges[u, v, k], to_ref)
            }
            blocked_to = [(u, v, k) for u, v, k in all_departure if (u, v, k) not in allowed]

        if blocked_to:
            blocked.setdefault((from_key, via_ref), []).extend(blocked_to)

    return {k: frozenset(v) for k, v in blocked.items()}

Convert the result to frozenset immediately — during Dijkstra expansion, membership tests against a frozen set are O(1) versus O(n) for a list.

Step 4: Apply Conditional and Vehicle-Class Filters

Real fleets rarely operate under purely static rules. Time-of-day restrictions, gross weight limits, and vehicle class exceptions all require dynamic evaluation during the lookup phase.

# requires: re, datetime
import re
from datetime import datetime, time as dtime

# Handles semicolon-delimited conditions: "no @ (Mo-Fr 07:00-09:00); no @ (16:00-18:00)"
_TIME_WINDOW_RE = re.compile(r"\((\d{2}:\d{2})-(\d{2}:\d{2})\)")

def _parse_time(s: str) -> dtime:
    h, m = map(int, s.split(":"))
    return dtime(h, m)

def is_restriction_active(tag_value: str, query_time: datetime) -> bool:
    """
    Returns True if any condition window is active at query_time.
    A tag with no time window is unconditionally active.
    """
    windows = _TIME_WINDOW_RE.findall(tag_value)
    if not windows:
        return True  # no condition = always active
    t = query_time.time()
    for start_s, end_s in windows:
        start, end = _parse_time(start_s), _parse_time(end_s)
        if start <= end:
            if start <= t <= end:
                return True
        else:  # crosses midnight (e.g. 22:00-06:00)
            if t >= start or t <= end:
                return True
    return False

def filter_for_vehicle_class(
    relations: pd.DataFrame,
    vehicle_class: str = "car",
) -> pd.DataFrame:
    """
    For freight routing, use restriction:hgv; for passenger, use restriction.
    Discards rows where the class-specific tag is empty.
    """
    tag_col = "restriction_hgv" if vehicle_class == "hgv" else "restriction"
    subset = relations[relations[tag_col].notna() & (relations[tag_col] != "")]
    return subset.copy()

When integrating with freight or commercial routing, align restriction evaluation with your vehicle profile. Heavy goods vehicles often bypass passenger-only turn bans but encounter dedicated restriction:hgv rules. For strategies on balancing turn penalties, fuel consumption, and compliance routing alongside access restrictions, see configuring edge weights for freight logistics.

Step 5: Integrate the Blocked Set into Pathfinding

Standard NetworkX shortest-path algorithms do not accept an edge-transition filter. Implement a constrained Dijkstra that carries the predecessor edge through the expansion and checks the blocked set at each step.

# requires: networkx, heapq
import heapq
import networkx as nx
from typing import Optional

def dijkstra_with_restrictions(
    graph: nx.MultiDiGraph,
    source: int,
    target: int,
    blocked: dict[tuple, frozenset],
    weight: str = "length",
) -> Optional[list[int]]:
    """
    Constrained Dijkstra returning a node-ID path, or None if no valid path exists.
    blocked: {(from_edge_key, via_node): frozenset of blocked to_edge_keys}
    """
    dist = {source: 0.0}
    prev: dict[int, tuple] = {}   # node -> (predecessor_node, edge_key)
    heap = [(0.0, source, None)]   # (cost, node, arriving_edge_key)

    while heap:
        cost, u, arriving_key = heapq.heappop(heap)
        if u == target:
            # Reconstruct path
            path = [u]
            while u in prev:
                u, _ = prev[u]
                path.append(u)
            return list(reversed(path))

        if cost > dist.get(u, float("inf")):
            continue

        for u2, v, k, d in graph.edges(u, keys=True, data=True):
            to_key = (u2, v, k)
            # Check turn restriction: is this departure blocked given our arrival?
            if arriving_key is not None:
                via_node = u
                restriction_key = (arriving_key, via_node)
                if restriction_key in blocked and to_key in blocked[restriction_key]:
                    continue  # blocked transition — skip

            edge_cost = cost + d.get(weight, 1.0)
            if edge_cost < dist.get(v, float("inf")):
                dist[v] = edge_cost
                prev[v] = (u, to_key)
                heapq.heappush(heap, (edge_cost, v, to_key))

    return None  # no path found

Configuration Reference

For engine-specific configuration — how OSRM compiles restrictions into the .osrm binary during osrm-extract, and how GraphHopper requires turn_costs=true in its graph-builder config — see setting turn restrictions in GraphHopper vs OSRM.

Production Optimization and Scaling

Pre-build an osmid-to-edge index. The naive approach iterates all edges for each relation. Build the reverse index once at startup (as shown in Step 3) and reuse it for all relation resolutions. For a city graph with ~500k edges, this reduces total resolution time from minutes to seconds.

Vectorise relation filtering. Use pandas boolean indexing to filter by restriction type and vehicle class before entering the edge-resolution loop. Avoid row-level iterrows() in the inner loop — switch to itertuples() at minimum, or better, resolve edge keys in batches after pre-filtering.

# Vectorised pre-filter before edge resolution
prohibitory = relations[relations["restriction"].str.startswith("no_", na=False)]
mandatory = relations[relations["restriction"].str.startswith("only_", na=False)]
active_relations = pd.concat([prohibitory, mandatory], ignore_index=True)

Spatial partitioning for continental graphs. When operating across national or continental PBF files, partition the graph by bounding box or administrative boundary before resolving restrictions. Relations that cross partition boundaries need a reconciliation pass — flag cross-boundary from_ref or to_ref values and resolve them after merging sub-graphs. The implementing multi-modal transit layers page covers analogous partitioning strategies for combined road-transit networks.

Memory layout. The blocked dictionary grows linearly with the number of active restrictions. For graphs with tens of thousands of restrictions, store the blocked set in a compact array-backed structure (e.g. numpy uint64 arrays for edge keys) rather than Python tuples, reducing per-entry memory by 60–70%.

Validation and Testing

After building the blocked-set lookup, run these checks before deploying to production:

1. Synthetic path tests. Generate origin-destination pairs that should trigger known restrictions. Verify the constrained Dijkstra returns an alternative path, not a path through the prohibited turn:

# requires: networkx
def assert_restriction_enforced(
    graph: nx.MultiDiGraph,
    blocked: dict,
    source: int,
    target: int,
    forbidden_node_sequence: list[int],
) -> None:
    path = dijkstra_with_restrictions(graph, source, target, blocked)
    assert path is not None, "No path found — check graph connectivity"
    for i in range(len(forbidden_node_sequence) - 1):
        pair = (forbidden_node_sequence[i], forbidden_node_sequence[i + 1])
        found = any(
            path[j] == pair[0] and path[j + 1] == pair[1]
            for j in range(len(path) - 1)
        )
        assert not found, f"Forbidden turn {pair} appeared in route"

2. Coverage ratio. Compute what fraction of streamed relations were successfully resolved to edge keys. A healthy ratio is above 90% for a well-matched PBF + graph pair. Values below 80% suggest a version mismatch between the PBF used for graph construction and the one used for relation streaming.

total = len(relations)
resolved = len(blocked)
print(f"Resolved {resolved}/{total} relations ({100*resolved/total:.1f}%)")

3. Roundabout smoke test. Roundabouts with no_entry or no_exit tags generate many restrictions around a single set of edges. After resolution, spot-check that the number of blocked transitions per roundabout node matches the expected count from the OSM data (inspect via Overpass or JOSM).

4. Conditional restriction timing. Call is_restriction_active with boundary times — one minute before and after each window boundary — to confirm the time-window parser handles midnight-crossing and multi-condition tags correctly.

Troubleshooting

Related

• Setting turn restrictions in GraphHopper vs OSRM — engine-specific configuration for compiling and querying turn-cost matrices
• Building directed graphs from OSM PBF files — upstream pipeline that produces the MultiDiGraph this page extends
• Configuring edge weights for freight logistics — pairing turn restrictions with restriction:hgv weight strategies for commercial fleets
• Graph fragmentation prevention in OSM data — fixing the isolated-node and disconnected-component issues that break restriction resolution
• OSM Graph Architecture & Network Modeling — parent reference covering the full routing graph stack