Chunking Large Origin-Destination Matrices

Both OSRM’s /table endpoint and Valhalla’s /sources_to_targets endpoint enforce a hard cap on how many locations a single matrix request may contain — OSRM through the --max-table-size startup flag and Valhalla through max_locations in valhalla.json’s service_limits. A fleet with 3,000 stops trying to build one 3,000 × 3,000 travel-time matrix will hit that cap immediately, regardless of how the request is dispatched. This page covers the partitioning step that sits underneath async route matrix automation — splitting an oversized origin-destination matrix into engine-safe tiles and stitching the results back together — and assumes the concurrency and worker-pool patterns from the broader routing API automation and fleet integration workflow are already in place. Get the tiling wrong and you either exceed the engine’s limit or waste requests on redundant coordinate pairs.

When to Use This Approach

Chunking is a distinct problem from concurrency. You can have a perfectly tuned async worker pool and still fail every request if a single block exceeds the engine’s location cap. Apply block partitioning whenever:

• n_origins * n_destinations (or n_origins + n_destinations, depending on the engine’s counting rule) exceeds the configured matrix limit for a single call.
• The location set is large enough that a naive one-shot request would allocate an unreasonably large response payload — OSRM and Valhalla both serialize the full matrix as JSON by default, and a 5,000 × 5,000 float matrix is over 200 MB of text before compression.
• Travel cost between two points is symmetric (undirected road cost, no one-way asymmetry) and you want to avoid computing the same pair twice from opposite directions.
• The matrix needs to be assembled incrementally as blocks complete, rather than waiting for every request to finish before any downstream consumer can start.

If your location count already fits comfortably under the engine’s cap in one call, skip chunking — the added bookkeeping only pays off once you are forced to split. Chunking is orthogonal to the fan-out mechanics; see parallel distance matrix requests with aiohttp for the connection pooling and concurrency-cap side of the same pipeline.

Implementation

The logic below is deliberately scoped to the chunking problem: computing block boundaries, deciding which blocks can reuse a transposed neighbor, and writing results into a preallocated matrix. The actual network fan-out — aiohttp connector limits, retries, timeouts — belongs to parallel distance matrix requests with aiohttp; here fetch_block is a stand-in for that call.

# requires: numpy (pip install numpy)
# Python 3.9+

import numpy as np
from typing import Callable, Dict, List, Optional, Tuple

Block = Tuple[int, int, int, int]  # (row_start, row_end, col_start, col_end)


def tile_matrix(n_origins: int, n_destinations: int, max_block: int) -> List[Block]:
    """Partition an n_origins x n_destinations matrix into blocks whose
    row+column count never exceeds max_block, matching OSRM's combined
    sources+destinations accounting."""
    row_edges = list(range(0, n_origins, max_block)) + [n_origins]
    col_edges = list(range(0, n_destinations, max_block)) + [n_destinations]
    row_edges = sorted(set(row_edges))
    col_edges = sorted(set(col_edges))

    blocks = []
    for i in range(len(row_edges) - 1):
        for j in range(len(col_edges) - 1):
            blocks.append((row_edges[i], row_edges[i + 1], col_edges[j], col_edges[j + 1]))
    return blocks


def mirror_key(block: Block) -> Optional[Block]:
    """Return the transposed block that already covers this block's cells,
    or None if this block sits on or below the diagonal and has no earlier
    mirror. Only valid when the cost matrix is symmetric."""
    r0, r1, c0, c1 = block
    if (r0, r1) == (c0, c1):
        return None  # diagonal block — no mirror to reuse
    if r0 > c0:
        return (c0, c1, r0, r1)  # the transposed block was scheduled earlier
    return None


def assemble_matrix(
    n_origins: int,
    n_destinations: int,
    blocks: List[Block],
    fetch_block: Callable[[Block], np.ndarray],
    reuse_symmetric: bool = False,
    dtype: np.dtype = np.float32,
) -> np.ndarray:
    """Fetch each block and write it directly into a preallocated matrix
    slice — avoids building N separate arrays and concatenating them."""
    matrix = np.full((n_origins, n_destinations), np.nan, dtype=dtype)
    computed: Dict[Block, np.ndarray] = {}

    for block in blocks:
        r0, r1, c0, c1 = block
        mirror = mirror_key(block) if reuse_symmetric else None

        if mirror is not None and mirror in computed:
            matrix[r0:r1, c0:c1] = computed[mirror].T
            continue

        result = fetch_block(block)  # shape (r1 - r0, c1 - c0)
        matrix[r0:r1, c0:c1] = result
        if reuse_symmetric:
            computed[block] = result  # keep only for potential mirrors

    return matrix


# --- Example: 3,000-stop fleet, OSRM configured with --max-table-size 500 ---
N = 3000
MAX_BLOCK = 220  # margin below the 250-per-axis budget (rows + cols <= 500)

blocks = tile_matrix(N, N, MAX_BLOCK)
print(f"{len(blocks)} blocks for a {N}x{N} matrix (vs. 1 oversized request)")


def fetch_block_stub(block: Block) -> np.ndarray:
    """Placeholder for the real OSRM/Valhalla call — see the aiohttp
    fan-out page for the production version with retries and timeouts."""
    r0, r1, c0, c1 = block
    return np.random.uniform(60, 3600, size=(r1 - r0, c1 - c0)).astype(np.float32)


matrix = assemble_matrix(N, N, blocks, fetch_block_stub, reuse_symmetric=True)
assert not np.isnan(matrix).any(), "block partition left uncovered cells"

For truly large fleets — tens of thousands of stops — holding the full matrix in RAM stops being practical even at float32. Replace the np.full(...) allocation with np.memmap(path, dtype=dtype, mode="w+", shape=(n_origins, n_destinations)) and the rest of assemble_matrix works unchanged: NumPy writes each block slice to disk-backed storage instead of a resident array, capping peak memory at roughly the size of one in-flight block.

Key Parameters and Tuning

Block dimensions interact with the engine’s counting rule, not just its raw number: OSRM sums sources and destinations, so a 200×200 block already consumes 400 of an 500-unit budget before any margin is left for retried sub-requests. Valhalla’s max_locations for sources_to_targets is typically counted the same way. Always confirm the exact rule against the deployed server’s configuration rather than assuming OSRM’s and Valhalla’s semantics match.

Integration Points

Feeding a VRP solver. The reassembled matrix is the direct input to OR-Tools’ RoutingIndexManager or any capacitated vehicle routing solver that expects a dense cost matrix. Pass matrix.astype(np.int64) if the solver requires integer costs — OR-Tools’ AddDimension and arc-cost callbacks reject floats.

Upstream engine setup. Block sizing only matters once an engine is actually serving /table requests at scale; see deploying OSRM with Docker for local routing for setting --max-table-size deliberately rather than leaving it at the default, and Valhalla cost matrix generation for urban planners for the equivalent Valhalla-side matrix workflow and its own location limits.

Fan-out layer. assemble_matrix’s fetch_block callback is where the async dispatch plugs in — replace fetch_block_stub with a coroutine that posts each block’s coordinate lists to /table or /sources_to_targets under a semaphore, as covered in parallel distance matrix requests with aiohttp. Wrap the loop in asyncio.gather with a bounded Semaphore rather than fetching blocks strictly sequentially — chunking and concurrency are independent axes and should be tuned separately.

NetworkX fallback. If the OD matrix is small enough to fall back to an in-process graph, nx.single_source_dijkstra_path_length per origin can substitute for engine calls entirely, avoiding chunking altogether at the cost of losing road-snapped accuracy.

Validation Checklist

1. Full coverage, no gaps. After tiling, confirm row_edges and col_edges run from 0 to n_origins/n_destinations with every step covered — sum((r1 - r0) * (c1 - c0) for r0, r1, c0, c1 in blocks) == n_origins * n_destinations.

2. No NaN survivors. np.isnan(matrix).sum() == 0 after assembly. Any remaining NaN means a block boundary calculation skipped cells — check for an off-by-one in range(0, n, max_block).

3. Block size under the engine limit. For every block, assert (r1 - r0) + (c1 - c0) <= configured_limit before dispatch, not after a 400 response — fail fast in the partitioning step.

4. Symmetric reuse correctness. On a graph with genuinely symmetric cost, spot-check 5–10 mirrored cells: abs(matrix[i, j] - matrix[j, i]) < 1.0 (seconds). A larger delta means the graph is not actually symmetric (one-way streets, turn penalties) and reuse_symmetric should be False.

5. Memory budget before allocation. Estimate n_origins * n_destinations * dtype.itemsize bytes and compare against available RAM before calling assemble_matrix; switch to np.memmap once the estimate exceeds a safety threshold (commonly 25–30% of available memory).

6. Diagonal sanity. For matrices where origins and destinations are the same point set, assert the diagonal is near zero: np.allclose(np.diag(matrix), 0, atol=5) — a nonzero diagonal usually indicates a coordinate-order mismatch between the origin and destination lists.

Related

• Async route matrix automation — the parent workflow covering concurrency control and result assembly against OSRM and Valhalla table endpoints
• Parallel distance matrix requests with aiohttp — connection pooling and concurrency caps for the block-fetch layer this page’s fetch_block plugs into
• Valhalla cost matrix generation for urban planners — Valhalla’s sources_to_targets workflow and its own max_locations limits
• Deploying OSRM with Docker for local routing — setting --max-table-size deliberately when standing up the engine this page’s blocks are dispatched against