Handling Turn Restrictions in Routing Graphs

Accurate route calculation depends heavily on how well a routing graph models real-world driving constraints. While edge weights capture distance, speed limits, and terrain gradients, handling turn restrictions in routing graphs determines whether a calculated path is legally and physically traversable. For logistics engineers, GIS developers, and urban planners, ignoring turn prohibitions leads to invalid delivery routes, compliance violations, and costly operational inefficiencies. This guide provides a production-ready workflow for parsing, mapping, and enforcing turn restrictions within directed network graphs, building directly on foundational concepts in OSM Graph Architecture & Network Modeling.

Prerequisites & Data Foundations

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

  • Python 3.9+ with osmnx, networkx, pandas, geopandas, and shapely installed
  • Clean OSM PBF extract covering your operational area (e.g., Geofabrik, BBBike, or Metro Extracts)
  • Directed graph representation where each physical road segment is split into inbound/outbound edges
  • Familiarity with OSM relation schemas, specifically type=restriction and type=restriction:hgv
  • Routing engine awareness (OSRM, GraphHopper, Valhalla, or custom Dijkstra/A* implementations) to understand how transition matrices are consumed during pathfinding

If you are starting from raw extracts, review the pipeline for Building Directed Graphs from OSM PBF Files to ensure your base topology correctly represents one-way streets, intersection nodes, and edge geometries before layering restriction logic. A malformed base graph will propagate invalid turn constraints downstream, regardless of how robust your restriction parser is.

The OSM Turn Restriction Data Model

OpenStreetMap encodes turn restrictions using relations with three mandatory roles:

  • from: The incoming edge (approach road)
  • via: The intersection node or intermediate edge(s) where the turn occurs
  • to: The outgoing edge (departure road)

The restriction tag defines the maneuver type: no_left_turn, no_right_turn, no_u_turn, no_straight_on, or conditional variants like no_left_turn:conditional @ (06:00-22:00). Heavy vehicle restrictions use restriction:hgv or restriction:bus to separate freight routing from passenger navigation. Complex intersections may chain multiple via edges to model multi-segment prohibitions (e.g., crossing a median before turning).

For authoritative schema details, consult the OpenStreetMap Wiki: Relation:restriction. Understanding this structure is critical because routing engines do not natively “see” relations during traversal; they require explicit edge-to-edge transition rules mapped to the graph’s adjacency structure. Relations must be resolved into a lookup table or edge attribute that dictates valid successor edges for any given incoming edge.

Step-by-Step Implementation Workflow

1. Extract and Preprocess the Directed Graph

Load your OSM extract and construct a directed MultiDiGraph. Ensure all edges contain osmid, geometry, length, and oneway attributes. Filter out non-drivable features unless your use case explicitly requires pedestrian or bicycle routing.

import osmnx as ox
import networkx as nx
import pandas as pd

def build_base_graph(pbf_path: str, network_type: str = "drive") -> nx.MultiDiGraph:
    # ox.graph_from_xml accepts .osm XML files; for PBF use osmnx >= 1.3 or pre-convert
    graph = ox.graph_from_xml(pbf_path, network_type=network_type)
    # Graphs from osmnx are already MultiDiGraph — remove any isolated nodes
    isolates = list(nx.isolates(graph))
    graph.remove_nodes_from(isolates)
    return graph

Validate that every node has at least one incoming and one outgoing edge. Isolated or dangling nodes often indicate extraction boundaries or topology errors that will break restriction mapping.

2. Parse Restriction Relations into Edge Transitions

Relations must be extracted from the OSM dataset and resolved to graph edge IDs. This requires joining relation members with graph nodes/edges using OSM IDs.

def parse_turn_restrictions(graph: nx.MultiDiGraph, relations_df: pd.DataFrame) -> dict:
    """
    Returns a dict: {(from_edge_id, via_node_id): [blocked_to_edge_ids, ...]}
    """
    import ast

    restrictions = {}
    
    # Filter only restriction relations
    rels = relations_df[relations_df["type"] == "restriction"].copy()
    
    for _, rel in rels.iterrows():
        # Use ast.literal_eval instead of eval() for safe deserialization
        members = ast.literal_eval(rel["members"]) if isinstance(rel["members"], str) else rel["members"]
        
        from_edge = next((m["ref"] for m in members if m["role"] == "from"), None)
        via_node = next((m["ref"] for m in members if m["role"] == "via"), None)
        to_edge = next((m["ref"] for m in members if m["role"] == "to"), None)
        
        if not (from_edge and via_node and to_edge):
            continue
            
        # Map OSM IDs to NetworkX edge tuples
        from_edges = list(graph.edges(keys=True, data=True))
        from_key = None
        for u, v, k, d in from_edges:
            if d.get("osmid") == from_edge and v == via_node:
                from_key = (u, v, k)
                break
                
        if not from_key:
            continue
            
        to_edges = list(graph.edges(keys=True, data=True))
        to_keys = [(u, v, k) for u, v, k, d in to_edges 
                   if d.get("osmid") == to_edge and u == via_node]
                   
        restrictions.setdefault(from_key, []).extend(to_keys)
        
    return restrictions

Store the resulting mapping as a graph-level attribute or a separate lookup table. During traversal, this structure acts as a negative adjacency filter: when expanding from a given edge, exclude any successor edges present in the restriction lookup.

3. Apply Conditional & Vehicle-Specific Logic

Real-world routing rarely operates under static rules. Time-based restrictions, weight limits, and vehicle class filters require dynamic evaluation. Parse conditional tags using regex or dedicated libraries, then attach them to your restriction dictionary.

import re
from datetime import datetime

CONDITIONAL_RE = re.compile(r"@ \((.+)\)")

def evaluate_condition(tag_value: str, current_time: datetime) -> bool:
    """Returns True if restriction is active at current_time."""
    match = CONDITIONAL_RE.search(tag_value)
    if not match:
        return False  # No condition = always active
        
    time_range = match.group(1)
    start_str, end_str = time_range.split("-")
    start = datetime.strptime(start_str.strip(), "%H:%M").time()
    end = datetime.strptime(end_str.strip(), "%H:%M").time()
    
    if start <= end:
        return start <= current_time.time() <= end
    else:  # Overnight span (e.g., 22:00-06:00)
        return current_time.time() >= start or current_time.time() <= end

When integrating with freight or commercial routing, align restriction evaluation with your vehicle profile configuration. For example, heavy goods vehicles often bypass passenger-only turn bans but encounter dedicated restriction:hgv rules. Properly aligning these constraints with your cost functions is essential; see Configuring Edge Weights for Freight Logistics for strategies on balancing turn penalties, fuel consumption, and compliance routing.

4. Validate and Integrate with Routing Engines

Before deploying to production, validate your restriction graph using synthetic pathfinding tests. Generate origin-destination pairs that should trigger known restrictions, then verify that your routing algorithm returns alternative paths or correctly blocks traversal.

def validate_restrictions(graph: nx.MultiDiGraph, restrictions: dict, 
                          test_pairs: list[tuple]) -> list[dict]:
    results = []
    for u, v in test_pairs:
        try:
            path = nx.shortest_path(graph, u, v, weight="length")
            # Check if path violates any restriction
            violates = False
            for i in range(len(path) - 2):
                from_edge = next((k for u1, v1, k, d in graph.edges(keys=True, data=True) 
                                  if u1 == path[i] and v1 == path[i+1]), None)
                to_edge = next((k for u2, v2, k, d in graph.edges(keys=True, data=True) 
                                if u2 == path[i+1] and v2 == path[i+2]), None)
                if from_edge and to_edge and to_edge in restrictions.get(from_edge, []):
                    violates = True
                    break
            results.append({"path": path, "valid": not violates})
        except nx.NetworkXNoPath:
            results.append({"path": [], "valid": True})
    return results

Different routing engines consume restriction data differently. OSRM uses a Lua preprocessing profile to bake restrictions into the .osrm file, while GraphHopper applies them dynamically via GraphHopperConfig and Weighting implementations. Understanding these architectural differences prevents silent failures during deployment. For a detailed comparison of implementation patterns, review Setting Turn Restrictions in GraphHopper vs OSRM.

Code Reliability & Performance Considerations

Production routing graphs demand rigorous testing and memory-efficient traversal. Restriction lookups can easily become a bottleneck if implemented naively. Consider the following reliability practices:

  1. Precompute Adjacency Filters: Instead of scanning restriction dictionaries during every Dijkstra expansion, convert them into a sparse adjacency mask or use networkx’s subgraph_view to temporarily prune invalid edges during pathfinding.
  2. Handle Multi-Edge Intersections Carefully: OSM frequently models complex junctions with parallel edges (e.g., dedicated turn lanes). Ensure your from/to resolution logic matches the exact edge key, not just the node ID, to avoid false positives.
  3. Graceful Degradation: If a restriction relation references a missing node or edge, log the discrepancy and skip it rather than failing the entire build. Use logging with structured output for pipeline observability.
  4. Unit Test Edge Cases: Validate against known problematic geometries: roundabouts with no_entry rules, slip roads with no_right_turn exceptions, and conditional restrictions crossing midnight boundaries.

For algorithmic reference on constrained shortest path implementations, consult the NetworkX Shortest Paths Documentation. When scaling to continental graphs, consider graph partitioning and hierarchical routing to keep restriction evaluation latency under 50ms per query.

Conclusion

Handling turn restrictions in routing graphs transforms a theoretical network into a legally compliant, operationally viable routing system. By correctly parsing OSM relations, mapping them to directed edge transitions, and enforcing conditional logic during traversal, you eliminate invalid paths before they impact dispatch systems or driver compliance. Integrate this workflow with robust edge weighting, continuous validation, and engine-specific configuration to deliver reliable, production-grade navigation solutions.