Valhalla Meili Map Matching for Telematics

OSRM is fast and simple, but its map-matching service assumes a single, fixed cost model baked into the graph at contraction time. The moment a fleet mixes light vans, 44-tonne articulated trucks, and cargo bikes — or needs the matched path to respect a low bridge — a rigid, precompiled cost profile stops being adequate. Valhalla solves this differently. Its map matcher, Meili, is a hidden Markov model matcher layered on a graph whose costing is evaluated dynamically at request time, so the same tiles serve auto, truck, bicycle, and pedestrian matches with per-request restrictions. That flexibility is exactly what heterogeneous fleets need from the matching stage of a telematics pipeline.

This page covers running Meili from Python end to end: building tiles from an OpenStreetMap extract, calling the /trace_route and /trace_attributes endpoints with shape_match=map_snap, tuning gps_accuracy and search_radius per point, applying truck costing restrictions, and diagnosing the failure modes that produce empty or wrong matches. Meili implements the same hidden Markov model map matching formulation you would otherwise hand-build in Python — emission probability from GPS-to-edge distance, transition probability from network path plausibility, decoded with Viterbi — but ships it as a production service with a full road graph attached.

Why Naive Snapping Fails Here

A geometric nearest-edge snap assigns every ping to the closest road segment independently. On a divided highway with a service road 15 m away, on stacked motorway interchanges, or in an urban grid where three parallel streets sit within GPS error, that independence produces a matched path that zig-zags between roads that no vehicle could physically drive. Meili’s HMM couples consecutive observations: the probability of a candidate edge depends both on how close the ping is (emission) and on whether a legal, low-cost route connects it to the previous chosen edge (transition). The Viterbi decoder then finds the single most probable edge sequence for the whole trace.

The reason to reach for Valhalla specifically — rather than the equivalent OSRM /match service — comes down to two properties. First, dynamic costing: the transition cost between candidates is computed with the same costing model Valhalla uses for routing, so a truck match respects turn restrictions, access tags, and dimensional limits that a car match ignores. Second, multimodal reuse: one tile set answers auto, truck, bicycle, bus, and pedestrian matches, which is the natural fit for the multi-modal route matching that mixed fleets require. If you have not yet decided between engines, the routing engine comparison lays out the trade-offs; this page assumes Valhalla is the chosen matcher.

Prerequisites

Valhalla service. The simplest path is the official Docker image, which bundles the tile-building tools and the HTTP service. Pull ghcr.io/valhalla/valhalla (or build from github.com/valhalla/valhalla). You need a host with enough disk for the tiles — a country-sized extract produces a few gigabytes; a continent produces tens of gigabytes.

OSM data. Download a .osm.pbf extract covering your operational region. Tiles built from that PBF define the geographic extent Meili can match against: a ping outside the extract has no candidate edges and silently drops from the match.

Python environment. Python 3.10+ with requests for the HTTP calls and polyline for encoding/decoding polyline6 shapes. pandas is useful for joining matched_points back to the original ping DataFrame.

Upstream cleaning. Meili is not a substitute for preprocessing. Feed it a trace that has already passed through Kalman filtering for GPS noise reduction and timestamp ordering. Duplicate timestamps, out-of-order pings, and un-rejected outliers all degrade the HMM the same way they degrade a hand-built matcher.

Step-by-Step Workflow

Step 1 — Build the routing tiles

Tile building is a two-stage process: generate a config file, then build the graph from the PBF. Inside the Valhalla container:

import subprocess
from pathlib import Path

TILE_DIR = Path("/data/valhalla_tiles")
CONFIG = Path("/data/valhalla.json")
PBF = Path("/data/region-latest.osm.pbf")

# 1. Generate a default config pointing at the tile directory
subprocess.run(
    [
        "valhalla_build_config",
        "--mjolnir-tile-dir", str(TILE_DIR),
        "--mjolnir-tile-extract", "/data/valhalla_tiles.tar",
    ],
    check=True,
    stdout=CONFIG.open("w"),
)

# 2. Build the routing graph from the OSM extract
subprocess.run(
    ["valhalla_build_tiles", "-c", str(CONFIG), str(PBF)],
    check=True,
)

# 3. (Optional) pack tiles into a single tar for faster startup
subprocess.run(["valhalla_build_extract", "-c", str(CONFIG), "-v"], check=True)

Expected output: a populated valhalla_tiles/ directory (or valhalla_tiles.tar) and a config JSON. Once the service is started against this config, GET /status returns 200 with a JSON body reporting the loaded tileset.

Building tiles is a one-off per data refresh, not per request. Rebuild on a schedule (weekly or monthly) as the underlying OpenStreetMap data changes; self-hosting the whole stack with Docker is covered in more depth for OSRM in self-hosting OSRM with Docker for fleet-scale map matching, and the same operational shape — build container, service container, shared volume — applies to Valhalla.

Step 2 — Encode the trace shape

Meili accepts the trace either as an inline shape array of objects or as an encoded_polyline (polyline6, i.e. six digits of precision — not the polyline5 that OSRM and Google use by default). The inline form is clearer and lets you attach per-point time and accuracy:

import pandas as pd

def build_shape(df: pd.DataFrame) -> list[dict]:
    """
    Convert a cleaned ping DataFrame into a Valhalla shape array.

    df must be sorted by ascending timestamp and contain:
        lon, lat        : WGS84 degrees
        epoch_s         : integer POSIX seconds (monotonic)
        horiz_acc_m     : reported horizontal accuracy in metres (optional)
    """
    shape = []
    for row in df.itertuples(index=False):
        point = {
            "lon": float(row.lon),          # longitude FIRST
            "lat": float(row.lat),
            "time": int(row.epoch_s),       # per-point time sharpens transitions
        }
        # Per-point accuracy overrides the request-level gps_accuracy
        if hasattr(row, "horiz_acc_m") and row.horiz_acc_m == row.horiz_acc_m:
            point["accuracy"] = float(row.horiz_acc_m)
        shape.append(point)
    return shape

Expected output shape: a list of dicts, one per ping, ordered by time. The time field is optional but strongly recommended — it lets Meili reason about how far the vehicle could plausibly have travelled between observations, which sharpens transition scoring on ambiguous stretches.

If you prefer to send an encoded_polyline, remember the precision:

import polyline

# Valhalla uses polyline6 (precision=6), NOT the default polyline5
encoded = polyline.encode([(row.lat, row.lon) for row in df.itertuples(index=False)], precision=6)

Note that polyline.encode takes (lat, lon) tuples, while the inline shape uses lon/lat keys — a classic place to introduce a silent hemisphere swap.

Step 3 — Call /trace_attributes with map_snap

/trace_attributes returns the matched edges and their attributes; /trace_route returns a navigable route over the same match. For analytics, use /trace_attributes. Set shape_match to map_snap to force a full HMM match (as opposed to edge_walk, which assumes the shape already lies exactly on the network and only works for shapes you generated from a prior route):

import requests

VALHALLA_URL = "http://localhost:8002"

def trace_attributes(shape: list[dict], costing: str = "auto",
                     gps_accuracy: float = 8.0, search_radius: float = 40.0) -> dict:
    """
    Run Meili map matching and return matched edges + confidence.

    costing        : 'auto', 'truck', 'bicycle', 'pedestrian', 'bus'
    gps_accuracy   : request-level receiver sigma in metres (per-point 'accuracy' wins)
    search_radius  : candidate edge search radius in metres around each point
    """
    payload = {
        "shape": shape,
        "costing": costing,
        "shape_match": "map_snap",
        "trace_options": {
            "gps_accuracy": gps_accuracy,
            "search_radius": search_radius,
            "interpolation_distance": 10,
        },
        # Ask only for the attributes you need — keeps the response small
        "filters": {
            "attributes": [
                "edge.way_id", "edge.names", "edge.road_class",
                "edge.speed_limit", "edge.surface", "edge.length",
                "matched.point", "matched.type", "matched.edge_index",
                "confidence_score",
            ],
            "action": "include",
        },
    }
    resp = requests.post(f"{VALHALLA_URL}/trace_attributes", json=payload, timeout=30)
    resp.raise_for_status()
    return resp.json()

Expected output shape: a JSON object whose top-level keys include edges (the ordered matched edges with the attributes you requested), matched_points (one per input ping, each carrying edge_index, type, and a snapped lat/lon), and confidence_score (a 0–1 score for the overall match).

Step 4 — Parse edges, matched_points, and confidence

The two arrays serve different purposes. edges is the road-network path — join it to per-edge analytics (speed limits, road class). matched_points is per-ping — join it back to your original DataFrame by index to know which edge each raw ping landed on and how far it moved when snapped:

def parse_match(result: dict, df: pd.DataFrame) -> pd.DataFrame:
    """Attach the snapped edge to each original ping."""
    matched = result.get("matched_points", [])
    if len(matched) != len(df):
        # Meili can drop unmatchable points; align on what came back
        raise ValueError(
            f"matched_points ({len(matched)}) != input pings ({len(df)}); "
            "check for dropped points or duplicated timestamps"
        )

    edges = result.get("edges", [])
    out = df.copy().reset_index(drop=True)
    out["match_type"] = [m.get("type") for m in matched]         # matched | interpolated | unmatched
    out["snap_lon"] = [m.get("lon") for m in matched]
    out["snap_lat"] = [m.get("lat") for m in matched]
    edge_idx = [m.get("edge_index") for m in matched]
    out["edge_index"] = edge_idx
    out["road_class"] = [
        edges[i].get("road_class") if i is not None and i < len(edges) else None
        for i in edge_idx
    ]
    out["speed_limit"] = [
        edges[i].get("speed_limit") if i is not None and i < len(edges) else None
        for i in edge_idx
    ]
    out["match_confidence"] = result.get("confidence_score")
    return out

Expected output: the original DataFrame plus match_type, snapped coordinates, edge_index, road_class, speed_limit, and the trace-level match_confidence. A match_type of interpolated means Meili inferred that point from its neighbours rather than snapping it directly — useful to flag for downstream speed profiling, which should trust interpolated points less. Extracting the full per-edge attribute set (surface, names, turn attributes) is the subject of the companion page on configuring Valhalla trace_attributes for fleet routing.

Step 5 — Set gps_accuracy and search_radius per point

These two knobs control the HMM’s two probability terms. gps_accuracy is the standard deviation (in metres) of the receiver error; it scales the emission probability, so a larger value makes the matcher tolerant of pings that sit far from any road. search_radius is the hard cutoff (in metres) for how far Meili looks for candidate edges around each point — a candidate outside the radius is never considered, no matter how likely.

The relationship that trips people up: search_radius must be large enough to actually contain the correct edge given the real error, but small enough to keep candidate counts manageable. A good default is gps_accuracy ≈ 8 m and search_radius ≈ 40 m for clean automotive GPS, widening both in urban canyons. Set them per point from the receiver’s reported accuracy rather than globally:

def per_point_accuracy(df: pd.DataFrame, base_sigma: float = 8.0,
                       radius_multiplier: float = 5.0) -> list[dict]:
    """Attach a per-point accuracy so degraded fixes get a wider emission."""
    shape = []
    for row in df.itertuples(index=False):
        sigma = float(getattr(row, "horiz_acc_m", base_sigma) or base_sigma)
        shape.append({
            "lon": float(row.lon),
            "lat": float(row.lat),
            "time": int(row.epoch_s),
            "accuracy": max(sigma, 4.0),  # floor: never claim better than 4 m
        })
    return shape

When you provide a per-point accuracy, it overrides the request-level gps_accuracy for that observation. The request-level search_radius still applies as the candidate cutoff, so keep it at roughly radius_multiplier × base_sigma to ensure the true edge stays inside the search window even for the noisiest fixes.

The HMM Behind Meili

Meili is a faithful implementation of the standard HMM map-matching model, the same one described in building an HMM-based map matcher with OSRM and Python. Each GPS observation is emitted by a hidden state — the true road edge — and the matcher decodes the most probable state sequence.

The emission probability falls off with the great-circle distance between the ping and the candidate edge, modelled as a zero-mean Gaussian whose sigma is gps_accuracy:

P_emit(edge | ping) ∝ exp( -0.5 × (dist_ping_to_edge / gps_accuracy)² )

The transition probability compares the network route distance between two candidate edges against the straight-line distance between the two pings; a candidate pair whose road connection is far longer than the GPS displacement is penalised, which is what suppresses the parallel-road zig-zag:

P_trans(edge_j | edge_i) ∝ exp( -| route_dist(edge_i, edge_j) − gps_dist(p_i, p_j) | / β )

Crucially, route_dist here is evaluated with the selected costing model, so an impassable or restricted edge has effectively infinite cost and drops out of the transition. This is the mechanism by which costing=truck produces a truck-legal match. Viterbi then maximises the product of emissions and transitions over the whole trace (in log-space, to avoid underflow), and the resulting per-trace likelihood is surfaced as confidence_score.

Costing Options for Trucks

The truck costing model is where Valhalla earns its place for freight fleets. Populate costing_options.truck with the vehicle’s physical dimensions and Meili will exclude edges the truck cannot legally or physically use during transition scoring:

def truck_trace(shape: list[dict]) -> dict:
    payload = {
        "shape": shape,
        "costing": "truck",
        "shape_match": "map_snap",
        "costing_options": {
            "truck": {
                "height": 4.11,        # metres — excludes low bridges/tunnels
                "width": 2.6,          # metres
                "length": 21.5,        # metres — articulated combination
                "weight": 40.0,        # metric tonnes — excludes weight-limited edges
                "axle_load": 9.0,      # metric tonnes per axle
                "hazmat": False,       # set True to honour hazmat road bans
                "use_highways": 1.0,   # 0..1 preference; trucks usually prefer highways
            }
        },
        "trace_options": {"gps_accuracy": 10.0, "search_radius": 50.0},
    }
    resp = requests.post(f"{VALHALLA_URL}/trace_attributes", json=payload, timeout=30)
    resp.raise_for_status()
    return resp.json()

The dimensional restrictions only bite where OpenStreetMap actually tags maxheight, maxweight, maxaxleload, or hgv access. Coverage varies by region, so treat a truck match as “respects the restrictions that are mapped”, not “guaranteed legal”. A slightly wider search_radius (50 m here) is prudent for trucks because they are frequently on wide multi-carriageway roads where the correct edge sits further from the reported position.

Routing Engine Integration Notes

Coordinate order. Valhalla is [longitude, latitude] everywhere — the inline shape uses lon/lat keys, and any encoded_polyline must decode to that order. This matches OSRM’s [lon, lat] convention but is the opposite of the [lat, lon] that Leaflet, most Python polyline calls, and the haversine metric in scikit-learn expect. A swap does not raise an error; it just returns an empty or nonsensical match.

Polyline precision. Valhalla emits and consumes polyline6. If you round-trip a shape through a library defaulting to polyline5, every coordinate lands off by a factor of ten in the fractional part, placing the trace hundreds of kilometres away. Always pass precision=6.

Rate limits and batching. A self-hosted Valhalla has no external quota, but a single process serialises requests. For fleet-scale backfills, run several valhalla_service workers behind a load balancer and cap client concurrency to match. Each /trace_attributes call is independent, so parallelising across traces is trivial. If you instead call a hosted Valhalla, wrap the client in the retry-and-backoff logic described in handling routing engine rate limits with circuit breakers.

Response size. /trace_attributes can return large payloads on long traces. Use the filters block (as in Step 3) to request only the attributes you consume — requesting every attribute on a multi-hour trace can inflate the response by an order of magnitude.

Operational Troubleshooting

Deployment Checklist

• Tiles built from an OSM PBF whose extent covers the full operational area with margin
• Valhalla service reachable and /status confirms the expected tileset is loaded
• Coordinates sent as [longitude, latitude]; any encoded polyline uses precision 6
• shape_match set to map_snap (not edge_walk) for real GPS traces
• gps_accuracy and search_radius set from real receiver error; per-point accuracy where available
• Costing model matches vehicle class; truck dimensions under costing_options.truck
• filters.attributes trimmed to only the attributes consumed downstream
• matched_points length reconciled with input pings; dropped points handled explicitly
• confidence_score threshold calibrated against a labelled sample and wired to alerting
• Long trips segmented at ignition-off / long-stop boundaries before matching
• Multiple service workers behind a balancer for fleet-scale backfills; client concurrency capped
• Tile rebuild scheduled to track OpenStreetMap data refreshes

Parent topic: Routing Engine Integration for Fleet Telematics

Related

• Configuring Valhalla trace_attributes for Fleet Routing — a self-contained Python class that extracts speed limits, road class, surface, and turn attributes per edge
• Hidden Markov Model Map Matching in Python — the emission/transition/Viterbi formulation that Meili implements as a service
• OSRM Integration for Fleet Map Matching — the faster, single-cost-model alternative and when its rigidity is acceptable
• Choosing a Routing Engine: OSRM vs Valhalla vs GraphHopper — the decision framework across accuracy, costing flexibility, and infra cost
• Multi-Modal Route Matching for Mixed Fleets — why one Valhalla tile set serving many costing models suits heterogeneous fleets
• Valhalla documentation — the official reference for the Meili endpoints, costing models, and trace options