Caching and Invalidating Travel-Time Matrices

Recomputing the same travel times every morning is the largest avoidable cost in most matrix pipelines. Delivery manifests overlap heavily day to day, traffic profiles change on a schedule rather than continuously, and the graph itself changes weekly at most — so the great majority of cells a dispatch run needs were computed at some point in the recent past. This page covers caching them safely, as part of async route matrix automation within Routing API Automation & Fleet Integration.

The word doing the work in that sentence is “safely”. A travel-time cache that serves a value computed against a graph that has since been rebuilt is worse than no cache, because the resulting plan is confidently wrong and nothing downstream can tell.

When to use this approach

Cache when stop sets overlap between runs — recurring delivery rounds, fixed service points, depot-to-customer legs that repeat. Do not bother when every run is a fresh set of one-off coordinates, which is the case for some on-demand workloads and for nothing in scheduled logistics.

The economics are unusual because reuse scales quadratically. A manifest sharing 90 % of yesterday’s stops shares 81 % of the pairs; one sharing 70 % shares only 49 %. That curve is steep enough that a modest improvement in manifest stability produces a large improvement in hit rate, which is worth knowing when someone proposes reshuffling territories.

Implementation

The key is the whole design. Everything that can change the answer must be in it.

# requires: none beyond the standard library
import hashlib


def pair_key(origin_id: str, dest_id: str, *, graph_version: str,
             profile: str, time_bucket: str) -> str:
    """A cache key that becomes wrong exactly when the value does."""
    raw = f"{origin_id}|{dest_id}|{graph_version}|{profile}|{time_bucket}"
    return "tt:" + hashlib.blake2b(raw.encode(), digest_size=16).hexdigest()

graph_version is the content hash or build id of the routing artefact currently serving, taken from the same versioning used in incremental graph rebuilds without full reprocessing. Including it means a rebuild invalidates everything atomically and without an eviction sweep — the old entries simply become unreachable and age out.

time_bucket covers time-dependent costs. Where the engine serves a traffic layer or a time-of-day profile, a matrix computed for the 08:00 bucket is not valid for the 14:00 one, and omitting the bucket is the second most common way to serve a wrong value.

# requires: redis, numpy (pip install redis numpy)
import numpy as np
import redis


class MatrixCache:
    """Pair-granular travel-time cache over Redis."""

    def __init__(self, client: redis.Redis, ttl_s: int = 14 * 86400) -> None:
        self.r = client
        self.ttl = ttl_s

    def get_many(self, keys: list[str]) -> list[int | None]:
        vals = self.r.mget(keys)
        return [None if v is None else int(v) for v in vals]

    def put_many(self, pairs: dict[str, int]) -> None:
        # Pipeline so a few thousand writes are one round trip
        pipe = self.r.pipeline(transaction=False)
        for k, v in pairs.items():
            pipe.set(k, int(v), ex=self.ttl)
        pipe.execute()

The TTL is a safety net rather than the invalidation mechanism. With the graph version in the key, entries for a superseded graph are already unreachable; the TTL just stops them occupying memory forever.

Assembly then becomes: look up everything, compute the misses, merge.

# requires: numpy (pip install numpy)
import numpy as np


def matrix_with_cache(ids: list[str], cache, fetch_missing, **key_parts) -> np.ndarray:
    """Assemble a matrix from cached pairs plus a fetch for the remainder."""
    n = len(ids)
    keys = [[pair_key(a, b, **key_parts) for b in ids] for a in ids]
    flat = [k for row in keys for k in row]
    cached = cache.get_many(flat)

    out = np.full((n, n), -1, dtype="int32")
    misses: list[tuple[int, int]] = []
    for idx, val in enumerate(cached):
        i, j = divmod(idx, n)
        if val is None:
            misses.append((i, j))
        else:
            out[i, j] = val

    if misses:
        fetched = fetch_missing(ids, misses)          # engine call, chunked
        writes = {}
        for (i, j), v in zip(misses, fetched):
            out[i, j] = v
            writes[keys[i][j]] = v
        cache.put_many(writes)

    np.fill_diagonal(out, 0)
    if (out < 0).any():
        raise RuntimeError("matrix still has holes after fetch — a chunk failed")
    return out

The final assertion matters. A cache that silently leaves -1 in the array hands a sentinel to the solver, which is exactly the failure described in feeding a travel-time matrix into OR-Tools.

Key parameters and tuning

Integration points

With the fetch layer. Misses are handed to the chunking and concurrency machinery in chunking large origin-destination matrices. Because misses are scattered rather than contiguous, it is usually cheaper to fetch the bounding sub-matrix of the missing rows and columns than to request individual pairs.

With the graph pipeline. The graph version must be readable at request time. Exposing it on the engine’s health endpoint, and reading it once per run rather than per pair, keeps the coupling loose without letting the two drift.

With dispatch. Warm the cache before the dispatch window rather than during it. A scheduled pre-run over the expected manifest turns dispatch-time matrix computation from a bottleneck into a lookup, which is often the difference between a thirty-second solve budget and a five-minute one.

Validation checklist

• A graph rebuild produces a full miss. Bump the graph version and confirm the hit rate drops to zero on the next run. If it does not, the version is not reaching the key.
• No sentinel survives assembly. Assert that the returned matrix contains no -1. A hole means a fetch chunk failed and was not retried.
• Hit rate is reported per run. Log hits, misses and the resulting engine call count. A quiet drop in hit rate is the earliest signal that graph versions are churning unexpectedly.
• Cached and fresh values agree. Periodically recompute a random sample of cached pairs and compare. Any disagreement within one graph version is a key collision.
• Memory is bounded. Track key count against the theoretical ceiling of distinct locations squared. Growth beyond it means the key includes something that varies per request.

Related

• Async route matrix automation — the pipeline this cache sits in front of
• Chunking large origin-destination matrices — fetching the misses efficiently once the cache has been consulted
• Feeding a travel-time matrix into OR-Tools — why a hole left by a cache miss is dangerous downstream
• Incremental graph rebuilds without full reprocessing — the graph versioning this cache keys on