Road Networks and Map Matching
Map matching infers which network elements may have generated a sequence of noisy movement observations. Snapping every point to its nearest line is not enough: parallel roads, bridges, one-way restrictions, sparse sampling, topology gaps, and off-network movement require sequence-aware reasoning and explicit uncertainty.
Prerequisites
Complete GPS trajectories and movement data, shortest paths and distance, and spatial indexes. You should distinguish observation error from network cost.
Learning goals
- Model road edges with stable IDs, endpoints, direction, impedance, and topology quality.
- Generate bounded spatial candidates before scoring observation and transition compatibility.
- Preserve ties, unmatched fixes, off-network states, and known graph gaps.
- Evaluate against independent ground truth rather than treating a model score as correctness.
From candidates to paths
Candidate generation finds edges within an observation-specific search radius, often using a spatial index. An emission term can score distance from a fix to an edge relative to measurement uncertainty. A transition term can compare network path distance or travel time with observed displacement and elapsed time. Direction, turn restrictions, access, temporal closures, and transport mode may change feasibility.
These scores express a model under stated assumptions. A score is not ground truth. Hidden Markov approaches choose a likely sequence across observations, but results depend on noise and transition models, candidate radius, sampling rate, graph completeness, and parameter calibration. Report alternatives or posterior uncertainty when decisions are close; allow an unmatched/off-network state instead of forcing every point onto a road.
The fixture contains two parallel eastern edges exactly 50 m from its ambiguous observation and a north-gap edge that is intentionally disconnected by 200 m. Silently snapping endpoints would fabricate topology. Repair requires provenance and domain evidence, not a tolerance chosen only to make routing succeed.
Worked example
import json
from pathlib import Path
from shapely.geometry import shape
from shapely.strtree import STRtree
fixture = Path("tests/fixtures/geospatial-data-science")
roads_doc = json.loads((fixture / "road-network.geojson").read_text(encoding="utf-8"))
trace_doc = json.loads((fixture / "movement-trace.geojson").read_text(encoding="utf-8"))
edges = roads_doc["features"]
lines = [shape(feature["geometry"]) for feature in edges]
tree = STRtree(lines)
ambiguous = next(feature for feature in trace_doc["features"] if feature["properties"]["status"] == "ambiguous")
point = shape(ambiguous["geometry"])
radius = ambiguous["properties"]["accuracy_m"]
candidate_positions = tree.query(point.buffer(radius))
candidates = []
for position in candidate_positions:
distance = point.distance(lines[position])
if distance <= radius:
candidates.append((edges[position]["properties"]["edge_id"], distance, -(distance / radius)))
candidates.sort()
gap_edges = sorted(feature["properties"]["edge_id"] for feature in edges if not feature["properties"]["connected"])
print(f"candidate_edges={[edge_id for edge_id, _, _ in candidates]} distances_m={[round(distance) for _, distance, _ in candidates]}")
print(f"emission_scores={[round(score, 3) for _, _, score in candidates]} decision=ambiguous ground_truth=unknown")
print(f"known_topology_gaps={gap_edges} forced_snap=False missing_observations=unmatched")
Expected output:
candidate_edges=['east-a', 'east-b'] distances_m=[50, 50]
emission_scores=[-0.833, -0.833] decision=ambiguous ground_truth=unknown
known_topology_gaps=['north-gap'] forced_snap=False missing_observations=unmatched
The example stops at candidate and emission scoring because equal candidates cannot be resolved honestly from one fix. A full matcher would add sequence transitions and an off-network state, then validate choices against separately collected route truth. The missing observation remains unmatched.
Limitations and common mistakes
- Nearest-edge snapping ignores sequence feasibility and can jump between parallel roads.
- Euclidean distance, network distance, and travel time are different transition signals.
- An incomplete or stale road graph can dominate apparent matching error.
- Ground truth must be independent; matched output cannot validate itself.
- Aggregate accuracy can hide failures by road class, sampling interval, urban form, device, or protected group.
Practice
Extend the contract with a third candidate, an off-network state, and transition costs. State how one-way rules, a disconnected edge, a 90-second gap, and equal scores are surfaced. Define the independent labels and metrics needed before claiming accuracy.
Next steps
Next, define neighborhoods and a randomization null before measuring dependence in spatial autocorrelation.
Primary sources
Checked 2026-10-18: Newson and Krumm, Hidden Markov Map Matching through Noise and Sparseness; NetworkX, weighted shortest paths; Shapely, STRtree candidate queries; OGC, Moving Features standards.