Precomputing Travel-Time Matrices with OSRM

This page solves one specific failure: a day’s collection matrix is a single /table call that OSRM refuses because it exceeds the coordinate cap, so the solver starts with no distances at all.

A waste solver reads travel time between every pair of stops as an N×N matrix, and for a full collection day N can run into the hundreds or low thousands. A self-hosted OSRM instance answers /table requests quickly, but only up to a configured coordinate cap (500 by default), so a naive one-shot request for 900 nodes is rejected before a single duration is computed. Precomputing travel-time matrices with OSRM means chunking the node list under that cap, calling /table for each sub-block, stitching the blocks back into the dense N×N, and caching the result keyed by a hash of the inputs so the same day is never recomputed. This is the concrete OSRM path in the Distance Matrix Construction stage; if you are still choosing a back end, weigh it against Valhalla and the in-process callback in OR-Tools vs. OSRM vs. Valhalla for matrix precomputation.

Environment & Data Prerequisites

The /table service is reached over HTTP with requests; hashing and caching use the standard library (hashlib, json, pathlib). pytest is used only for verification. A running osrm-backend is assumed — extracted, contracted, and served with osrm-routed against your region’s .osrm data — reachable at http://localhost:5000, or a mock returning the documented /table shape.

python -m pip install \
  requests==2.32.3 \
  pytest==8.2.0
# osrm-backend runs separately, e.g.:
#   osrm-extract -p /opt/car.lua region.osm.pbf
#   osrm-contract region.osrm
#   osrm-routed --max-table-size 100 region.osrm

The input is one ordered list of collection nodes; the output is a cached dense matrix plus a manifest.

Two rules prevent the two most common failures. OSRM /table takes coordinates as lon,lat in the URL path — transposed pairs return a plausible-looking but wrong matrix. And the chunk size must be at or below the server’s configured --max-table-size, or every block request is rejected.

Step-by-Step Implementation

Step 1 — Chunk the node list under the coordinate cap

Split the N node indices into contiguous blocks no larger than the cap. Because /table supports sources and destinations query parameters, one HTTP call can cover a row_chunk × col_chunk block, so the number of calls is ceil(N/cap)².

from __future__ import annotations

TABLE_CAP = 100  # must be <= osrm-routed --max-table-size


def chunk_indices(n: int, cap: int = TABLE_CAP) -> list[range]:
    return [range(start, min(start + cap, n)) for start in range(0, n, cap)]

Step 2 — Fetch one source-target block from /table

A single block sends all nodes in that row-and-column pair once, then selects rows with sources and columns with destinations (both are indices into the coordinates just sent). This keeps each request’s coordinate count at len(row) + len(col), well under the cap.

import requests

OSRM_BASE = "http://localhost:5000"


def fetch_block(
    nodes: list[tuple[float, float]],
    rows: range,
    cols: range,
    base: str = OSRM_BASE,
    profile: str = "driving",
) -> list[list[float]]:
    idx = list(rows) + [c for c in cols if c not in rows]
    coords = ";".join(f"{nodes[i][1]},{nodes[i][0]}" for i in idx)  # lon,lat
    pos = {node_i: k for k, node_i in enumerate(idx)}
    src = ";".join(str(pos[r]) for r in rows)
    dst = ";".join(str(pos[c]) for c in cols)
    resp = requests.get(
        f"{base}/table/v1/{profile}/{coords}",
        params={"sources": src, "destinations": dst, "annotations": "duration"},
        timeout=30,
    )
    resp.raise_for_status()
    body = resp.json()
    if body.get("code") != "Ok":
        raise RuntimeError(f"OSRM /table error: {body.get('code')} {body.get('message', '')}")
    return body["durations"]  # len(rows) x len(cols), seconds (float | None)

Step 3 — Stitch sub-blocks into the full N×N

Each fetched block is written into its offset region of the dense matrix. The row offset is the block’s first row index, the column offset its first column index — get these wrong and the matrix is silently transposed at block boundaries, which is why Step verification below asserts the boundaries explicitly.

INT32_MAX = 2**31 - 1


def build_matrix(nodes: list[tuple[float, float]], cap: int = TABLE_CAP, **kw) -> list[list[int]]:
    n = len(nodes)
    matrix = [[INT32_MAX] * n for _ in range(n)]
    row_chunks = chunk_indices(n, cap)
    col_chunks = chunk_indices(n, cap)
    for rows in row_chunks:
        for cols in col_chunks:
            block = fetch_block(nodes, rows, cols, **kw)
            for bi, i in enumerate(rows):
                for bj, j in enumerate(cols):
                    val = block[bi][bj]
                    matrix[i][j] = 0 if i == j else (INT32_MAX if val is None else int(round(val)))
    return matrix

Step 4 — Hash to a SHA-256 cache key and store

The cache key is a SHA-256 over the rounded node coordinates, the profile, and the cap, so the same day’s nodes always resolve to the same key and any change to inputs produces a fresh one. The matrix is stored as JSON alongside a manifest.

import hashlib
import json
from pathlib import Path

CACHE_DIR = Path("./matrix_cache")


def cache_key(nodes: list[tuple[float, float]], profile: str, cap: int) -> str:
    canon = json.dumps(
        {"nodes": [[round(lat, 6), round(lon, 6)] for lat, lon in nodes], "profile": profile, "cap": cap},
        separators=(",", ":"), sort_keys=True,
    )
    return hashlib.sha256(canon.encode("utf-8")).hexdigest()


def get_or_build(nodes: list[tuple[float, float]], profile: str = "driving", cap: int = TABLE_CAP) -> dict:
    CACHE_DIR.mkdir(exist_ok=True)
    key = cache_key(nodes, profile, cap)
    path = CACHE_DIR / f"{key}.json"
    if path.exists():
        return json.loads(path.read_text())  # cache hit — OSRM never called
    matrix = build_matrix(nodes, cap=cap, profile=profile)
    manifest = {
        "cache_key": key,
        "profile": profile,
        "n_nodes": len(nodes),
        "table_cap": cap,
        "unit": "int32_seconds",
        "unreachable_sentinel": INT32_MAX,
        "matrix": matrix,
    }
    path.write_text(json.dumps(manifest))
    return manifest

Compliance Output

The cached artifact is a manifest, not a bare matrix, so the exact travel-time basis of a day’s routes is reproducible and auditable long after the OSRM server has moved on to newer map data.

{
  "cache_key": "9f2c4a…7e",
  "profile": "driving",
  "n_nodes": 320,
  "table_cap": 100,
  "unit": "int32_seconds",
  "unreachable_sentinel": 2147483647,
  "matrix": [[0, 214, 331], [208, 0, 142], [329, 140, 0]]
}

• cache_key — the SHA-256 that pins these exact nodes, profile, and cap; the audit report generation stage cites it to prove a solved route was built on this matrix and not a silently re-run one.
• profile — which OSRM cost profile produced the times, so an auditor knows the matrix reflects driving road times and not, say, a pedestrian profile misconfigured on the server.
• table_cap — the chunk size used; recorded because a different cap produces the same numbers but a different call pattern, and reproducing an investigation means reproducing the cap.
• unreachable_sentinel — the documented value for a no-arc pair, so INT32_MAX is never misread as a free 0-second connection between disconnected components.

Because the manifest is content-addressed by its own inputs, a re-run with identical nodes is a pure cache hit — the compliance record proves not only what the matrix was but that it was not recomputed against drifted map data mid-investigation.

Verification

The tests use a deterministic fake /table (no live OSRM) to prove stitching writes each block at the correct offset, the diagonal is zero, and a second call for the same nodes is a cache hit rather than a rebuild.

import pytest
from unittest.mock import patch


def _fake_fetch_block(nodes, rows, cols, **kw):
    # deterministic: duration i->j = 10*i + j seconds, so offsets are checkable
    return [[float(10 * i + j) for j in cols] for i in rows]


def test_stitch_offsets_and_diagonal():
    nodes = [(40.70 + k * 0.001, -74.00) for k in range(5)]
    with patch(f"{__name__}.fetch_block", side_effect=_fake_fetch_block):
        m = build_matrix(nodes, cap=2)  # forces 3x3 = 9 blocks with boundaries
    assert len(m) == 5 and all(len(r) == 5 for r in m)
    assert all(m[i][i] == 0 for i in range(5))
    # off-diagonal cells reflect the 10*i + j rule → offsets were honoured
    assert m[3][1] == 31
    assert m[1][4] == 14


def test_second_call_is_cache_hit(tmp_path, monkeypatch):
    monkeypatch.setattr(f"{__name__}.CACHE_DIR", tmp_path)
    nodes = [(40.70, -74.00), (40.71, -74.01)]
    with patch(f"{__name__}.fetch_block", side_effect=_fake_fetch_block) as mocked:
        first = get_or_build(nodes, cap=2)
        calls_after_first = mocked.call_count
        second = get_or_build(nodes, cap=2)  # must not call OSRM again
    assert mocked.call_count == calls_after_first
    assert first["cache_key"] == second["cache_key"]

Common Errors

OSRM /table error: TooBig — Number of table coordinates 640 exceeds limit of 100 — a block, or the whole node list, was sent in one request above the cap. Root cause: TABLE_CAP set higher than the server’s --max-table-size, or a one-shot request bypassing chunk_indices. Fix: set TABLE_CAP at or below the server’s limit and route every request through build_matrix, which never sends more than len(rows) + len(cols) coordinates per call.

Travel times are symmetric-looking nonsense and a known short hop reads as hundreds of kilometres. Root cause: coordinates sent as lat,lon instead of lon,lat in the /table path. Fix: emit each coordinate as f"{nodes[i][1]},{nodes[i][0]}" (longitude first), exactly as Step 2 does, and assert one known pair’s duration is within a plausible band before caching the matrix.

RuntimeError: OSRM /table error: InvalidUrl or an empty durations. Root cause: the requested profile is not the one the server was extracted and contracted with (for example asking for driving when only a foot profile was built), so OSRM cannot answer. Fix: match the profile string to the Lua profile OSRM was built against, and record it in the manifest so a later reader can tell which network the times describe. This matrix then flows into the OR-Tools implementation as arc costs.

FAQ

Why chunk into row-and-column blocks instead of one row at a time?

A single-row strategy still sends the full column set with every request, so a large day either exceeds the cap anyway or fans out into far more calls than needed. Blocking by both axes keeps every request’s coordinate count at len(rows) + len(cols) and reduces total calls to ceil(N/cap)², which is the practical minimum under the sources/destinations model.

Should the cache key include the map data version?

For strict reproducibility, yes — append the OSRM data timestamp or the .osrm file’s hash to the canonical key input. This guarantees that re-extracting against newer map data invalidates the cache rather than silently returning stale times, which matters when a compliance record must name the exact network a route was optimized on.

Up: Distance Matrix Construction

Related

• Distance Matrix Construction — the stage this OSRM pipeline implements.
• OR-Tools vs. OSRM vs. Valhalla for Matrix Precomputation — how OSRM compares to the other two back ends before you commit to it.
• VRP Route Optimization Algorithms — the routing framework this matrix ultimately feeds.
• Validating GPS Coordinates in Python — the pre-filter ensuring the node coordinates you send OSRM are physically valid.