OR-Tools vs. OSRM vs. Valhalla for Matrix Precomputation

This page answers one decision: for the travel-time matrix a waste solver consumes, do you compute distances inside OR-Tools with a Haversine callback, precompute them from an OSRM /table service, or precompute them from a Valhalla sources_to_targets matrix?

The choice is not cosmetic. A collection solver optimizes against whatever matrix you feed it, so if the matrix says two stops are a straight-line 400 m apart when the truck must actually drive a one-way loop of 2.1 km between them, every route built on it is wrong in the same direction. The three common sources trade precompute cost against road-network fidelity and truck-restriction awareness in very different ways, and picking the wrong one shows up as either infeasible routes or an hours-long precompute stage. This page compares them head to head and gives you runnable code for each, so the Distance Matrix Construction stage feeding the OR-Tools implementation rests on a matrix you chose deliberately.

The comparison at a glance

Read the table as three tiers of fidelity. OR-Tools’ own callback is a shape — good enough to prototype or to seed a solve, never good enough to dispatch on. OSRM gives you accurate car-grade road distances cheaply. Valhalla is the only one of the three that natively understands that a 26-tonne rear-loader cannot take a road a sedan can.

Use OR-Tools’ Haversine callback when you are prototyping, unit-testing the solver wiring, or you have no road-network service available and stops are far enough apart that straight-line ordering is an acceptable seed you will re-cost later.

Use OSRM /table when you need accurate, fast, car-grade road times, your trucks broadly follow the drivable network, and you do not need height or weight restrictions baked into the matrix. It is the pragmatic default for most municipal fleets and is covered in depth in precomputing travel-time matrices with OSRM.

Use Valhalla sources_to_targets when truck restrictions are load-bearing — low bridges, weight-limited streets, hazmat corridors for a hazardous-waste manifest run — and you accept a heavier precompute for a matrix that will not route a truck somewhere it legally cannot go.

Environment & Data Prerequisites

The two service back ends are reached over HTTP with requests; the OR-Tools callback needs only the standard library. Runnable code below assumes a locally reachable osrm-backend (default port 5000) and a Valhalla server (default port 8002), or mock endpoints returning the documented JSON shapes.

python -m pip install \
  requests==2.32.3 \
  ortools==9.11.4210 \
  pytest==8.2.0

Every source consumes the same input — an ordered list of (lat, lon) collection nodes — and every source must emit the same output contract.

One rule dominates every service call below: OSRM and Valhalla both take coordinates as lon,lat, not lat,lon. Transposing them is the single most common way to get a matrix that looks plausible but places every node in the wrong hemisphere.

Step-by-Step Implementation

Step 1 — OR-Tools Haversine callback

The cheapest source computes great-circle time on demand. Distance uses the Haversine formula,

$$d = 2r\,\arcsin\!\sqrt{\sin^2\!\left(\tfrac{\varphi_2-\varphi_1}{2}\right) + \cos\varphi_1\cos\varphi_2\,\sin^2\!\left(\tfrac{\lambda_2-\lambda_1}{2}\right)}$$

where $\varphi$ is latitude and $\lambda$ longitude in radians, $r = 6{,}371{,}000\text{ m}$. Dividing by an assumed collection speed turns metres into the seconds the contract wants.

import math

EARTH_M = 6_371_000.0
ASSUMED_MPS = 8.0  # ~29 km/h effective urban collection speed


def haversine_seconds(a: tuple[float, float], b: tuple[float, float]) -> int:
    lat1, lon1 = map(math.radians, a)
    lat2, lon2 = map(math.radians, b)
    dlat, dlon = lat2 - lat1, lon2 - lon1
    h = math.sin(dlat / 2) ** 2 + math.cos(lat1) * math.cos(lat2) * math.sin(dlon / 2) ** 2
    metres = EARTH_M * 2 * math.asin(math.sqrt(h))
    return int(round(metres / ASSUMED_MPS))


def ortools_matrix(nodes: list[tuple[float, float]]) -> list[list[int]]:
    n = len(nodes)
    return [[haversine_seconds(nodes[i], nodes[j]) for j in range(n)] for i in range(n)]

Step 2 — OSRM /table request

OSRM returns a durations block of floats in seconds. Coordinates go into the URL path as lon,lat pairs joined by semicolons.

import requests

OSRM_BASE = "http://localhost:5000"


def osrm_matrix(nodes: list[tuple[float, float]], base: str = OSRM_BASE) -> list[list[int]]:
    coords = ";".join(f"{lon},{lat}" for lat, lon in nodes)  # lon,lat order
    url = f"{base}/table/v1/driving/{coords}"
    resp = requests.get(url, params={"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', '')}")
    durations = body["durations"]  # list[list[float | None]] seconds
    return _normalize(durations)

Step 3 — Valhalla sources_to_targets request

Valhalla takes a JSON body with sources, targets, and a costing model. Passing the full node list as both sources and targets yields the dense square matrix; costing: "truck" is what makes the result respect height and weight restrictions.

VALHALLA_BASE = "http://localhost:8002"


def valhalla_matrix(nodes: list[tuple[float, float]], base: str = VALHALLA_BASE) -> list[list[int]]:
    points = [{"lat": lat, "lon": lon} for lat, lon in nodes]  # explicit keys — no order ambiguity
    payload = {
        "sources": points,
        "targets": points,
        "costing": "truck",
        "costing_options": {"truck": {"height": 4.0, "weight": 26.0}},  # metres, tonnes
    }
    resp = requests.post(f"{base}/sources_to_targets", json=payload, timeout=60)
    resp.raise_for_status()
    rows = resp.json()["sources_to_targets"]  # list[list[{time, distance, ...}]]
    durations = [[cell["time"] for cell in row] for row in rows]  # seconds or None
    return _normalize(durations)

Compliance Output

All three back ends must produce a byte-identical contract so the solver, and the audit around it, cannot tell which source was used. The normalizer rounds to int32 seconds, enforces the square shape, zeroes the diagonal, and replaces None (unreachable) with an explicit sentinel rather than a silent zero.

INT32_MAX = 2**31 - 1


def _normalize(durations: list[list[float | None]]) -> list[list[int]]:
    n = len(durations)
    if any(len(row) != n for row in durations):
        raise ValueError(f"matrix is not square: {n} rows, ragged columns")
    out: list[list[int]] = []
    for i, row in enumerate(durations):
        norm_row = []
        for j, val in enumerate(row):
            if i == j:
                norm_row.append(0)
            elif val is None:
                norm_row.append(INT32_MAX)  # unreachable, never a silent 0
            else:
                norm_row.append(int(round(val)))
        out.append(norm_row)
    return out

The record that travels with a solved plan names which source built its matrix — this is a compliance fact, because a route dispatched from a truck-costed Valhalla matrix carries a different legal assurance than one built on a car-grade OSRM matrix:

{
  "matrix_source": "valhalla",
  "costing": "truck",
  "restrictions": {"height_m": 4.0, "weight_t": 26.0},
  "n_nodes": 1000,
  "unit": "int32_seconds",
  "unreachable_sentinel": 2147483647,
  "matrix_sha256": "b31c…e0"
}

• matrix_source and costing — which back end and cost model produced the matrix, so an auditor knows whether truck restrictions were honoured or a car-grade approximation was used.
• restrictions — the exact height and weight the matrix was computed under; if these do not match the dispatched vehicle’s specification the plan is not defensible.
• unreachable_sentinel — the documented value the solver treats as no-arc, so a 0-versus-INT32_MAX ambiguity can never be read as a free connection.
• matrix_sha256 — a hash pinning the exact matrix, letting the audit report generation stage prove the solved route was built on this matrix and no other.

Verification

The tests prove the property every back end must share: the normalized matrix is square, its diagonal is zero, and a symmetric mock source stays symmetric through normalization. Directed real-world matrices are not assumed symmetric, so that check is scoped to the symmetric mock only.

import pytest

MOCK = [
    [0.0, 120.4, 240.9],
    [118.7, 0.0, 95.2],
    [242.1, 96.0, 0.0],
]


def test_normalize_is_square_and_int32():
    m = _normalize(MOCK)
    n = len(m)
    assert all(len(row) == n for row in m)
    assert all(isinstance(v, int) for row in m for v in row)


def test_diagonal_is_zero():
    m = _normalize(MOCK)
    assert all(m[i][i] == 0 for i in range(len(m)))


def test_haversine_source_is_symmetric():
    nodes = [(40.70, -74.01), (40.71, -74.00), (40.69, -74.02)]
    m = ortools_matrix(nodes)
    assert all(m[i][j] == m[j][i] for i in range(3) for j in range(3))


def test_none_becomes_sentinel_not_zero():
    m = _normalize([[0.0, None], [None, 0.0]])
    assert m[0][1] == INT32_MAX and m[1][0] == INT32_MAX

Common Errors

OSRM table error: TooBig table request — the /table request exceeds OSRM’s coordinate cap (500 by default, max-table-size at launch). Root cause: sending all 1,000 nodes in one call. Fix: chunk the node list under the cap and stitch the sub-blocks into the full N×N, exactly as precomputing travel-time matrices with OSRM does, or relaunch osrm-routed with a higher --max-table-size.

Valhalla returns time: null for reachable-looking pairs, or a No costing method found error. Root cause: an unset or misspelled costing, or a truck costing whose height/weight excludes every road near a stop so no path exists. Fix: always send an explicit costing, and when debugging restrictions, re-run with costing: "auto" to confirm the pair is reachable at all before blaming the network — a null under truck but a value under auto means the restriction, not the map, blocked it.

Every route is nonsensical although each service returned Ok. Root cause: coordinates passed as lat,lon to OSRM’s path or ambiguously to Valhalla, so nodes landed in the wrong place. Fix: OSRM path segments are lon,lat; Valhalla points use explicit {"lat": …, "lon": …} keys, as in Steps 2 and 3. Assert a known pair’s travel time is within a plausible band before trusting the whole matrix.

FAQ

Can I mix sources — Haversine to seed, OSRM to re-cost?

Yes, and it is a common pattern. Because all three emit the same int32-seconds contract, you can build a cheap Haversine matrix to get a first feasible solution fast, then re-cost the accepted arcs against OSRM or Valhalla and re-solve. The matrix is interchangeable; only the matrix_source in the audit record changes.

Why store an unreachable sentinel instead of a very large float?

The solver expects integer arc costs, and a documented INT32_MAX sentinel is unambiguous where an arbitrary large float invites rounding drift and “is this reachable or just expensive?” confusion. Recording the sentinel value in the manifest lets any consumer distinguish a true no-arc from a merely costly one.

Up: Distance Matrix Construction

Related

• Distance Matrix Construction — the stage this comparison lives in and feeds.
• Precomputing Travel-Time Matrices with OSRM — the deep dive on chunking and caching the OSRM path.
• OR-Tools Implementation — the solver that consumes whichever matrix you choose.
• CP-SAT vs. Guided Local Search for Large Fleets — the companion decision on which search strategy runs on this matrix.