Caching Strategies for Repeated Network Queries

A durable cache layer turns repeated drive-time and travel-matrix lookups into a near-free operation, so a routing engine only ever solves each unique origin-and-profile combination once across an entire retail portfolio.

In retail site selection automation, evaluating drive-time accessibility, demographic catchments, and competitor proximity requires thousands of network queries against the same road graph. Scaling from a handful of pilot stores to regional portfolios exposes raw routing engines to severe latency, API throttling, and unpredictable cloud spend, because the same corridors and candidate sites are recomputed run after run. Caching the network responses eliminates redundant graph traversals, stabilizes solver throughput, and accelerates scenario modeling without altering the underlying isochrone polygon geometry. This page covers the spatial key design, storage topology, invalidation rules, and Python integration patterns needed to run a cache safely inside a production location intelligence pipeline.

Concept: Why Network Queries Are Cacheable #

A routing query is a pure function of its inputs. Given a fixed road graph, a fixed routing profile, and a fixed departure assumption, the same origin coordinate always yields the same travel-time surface. That referential transparency is what makes caching correct rather than merely convenient: the cached value is not an approximation of the solver, it is the solver’s exact output replayed.

Two properties of geospatial inputs complicate that ideal. First, coordinates carry far more floating-point precision than the network resolves — a candidate store at -73.9857421 and the “same” point at -73.98574 snap to the identical graph node, yet differ as raw cache keys. Second, the graph itself drifts: OpenStreetMap edits, speed-limit revisions, and live-traffic matrices all change the answer over time. A workable cache therefore needs a key that is invariant to meaningless input jitter, and an expiration policy keyed to how fast each profile’s answer actually goes stale.

The cache hit ratio is the single metric that governs whether the layer pays for itself. If $H$ is the hit ratio, $c_\text{miss}$ the cost of a solver call, and $c_\text{hit}$ the cost of a cache read, the effective per-query cost is:

$$c_\text{eff} = H \cdot c_\text{hit} + (1 - H) \cdot c_\text{miss}$$

Because $c_\text{hit}$ for an in-memory store is three to four orders of magnitude below $c_\text{miss}$ for a routing solve, even a modest hit ratio of 0.6 collapses portfolio-wide query cost, and the deterministic key work in the next section is what pushes $H$ toward its ceiling.

Architecture Overview #

The cache sits as a thin interception layer between the pipeline and the routing engine. Every request is normalized into a deterministic key, checked against the store, and only forwarded to the solver on a miss — after which the result is written back with a profile-appropriate time-to-live (TTL) before being returned to the caller.

The interception point matters: place it at the routing-module boundary, not inside the solver, so that batch jobs, ad-hoc notebooks, and scheduled DAGs all share one cache and one key contract. Misses on this layer are the natural feed into the batch path described in Optimizing Batch Isochrone Generation with OSRM, where deferred misses are coalesced into a single high-throughput /table call instead of many synchronous lookups.

Configuration Parameters #

The behaviour of the cache is governed by a small set of parameters. Standardize these as defaults in a shared config module so notebooks, CI suites, and production workers cannot drift apart.

The graph_version field is the most important and most often forgotten: folding the graph build identifier into the key means a fresh extract produces a fresh key namespace automatically, so stale geometry can never be served after a network rebuild.

Deterministic Spatial Key Generation #

Network solvers expect exact inputs, but GIS preprocessing introduces floating-point drift, coordinate reference system (CRS alignment) transformations, and dynamic traffic assumptions. A naive string concatenation fails under production loads because minor coordinate shifts or reordered profile parameters generate cache misses for what is semantically the same query. The key must normalize coordinates to a fixed precision, optionally snap to the nearest network node, and serialize routing parameters into a canonical byte sequence before hashing.

import hashlib
import json
from typing import Optional, Tuple

import pyproj
from shapely.geometry import Point
from shapely.ops import transform

# Geographic input CRS for OSM-aligned routing engines (lon/lat).
WGS84 = pyproj.CRS.from_epsg(4326)


def generate_cache_key(
    origin: Tuple[float, float],
    profile: str,
    graph_version: str,
    departure_time: Optional[str] = None,
    max_time: int = 900,
    coord_precision: int = 5,
    crs: pyproj.CRS = WGS84,
) -> str:
    """Generate a deterministic SHA-256 cache key for a network routing query.

    `origin` is (lon, lat). We assert the CRS explicitly so the key can never be
    built from re-projected coordinates that would silently shatter the hit ratio.
    """
    # Routing engines key on lon/lat; refuse anything that is not WGS84.
    assert crs.to_epsg() == 4326, f"origin must be EPSG:4326, got {crs.to_epsg()}"

    lon, lat = origin
    payload = {
        "origin": [round(lon, coord_precision), round(lat, coord_precision)],
        "profile": profile,
        "departure": departure_time or "static",
        "max_time": max_time,
        "graph": graph_version,  # rebuild -> new namespace -> automatic invalidation
    }
    # sort_keys + compact separators ensure a canonical byte representation
    canonical = json.dumps(payload, sort_keys=True, separators=(",", ":"))
    return hashlib.sha256(canonical.encode("utf-8")).hexdigest()

Snapping further raises the hit ratio by collapsing every coordinate inside a node’s catchment onto one key. When the routing engine exposes a /nearest endpoint, snap before keying; otherwise snap against a local node index built with scipy.spatial.cKDTree. Refer to the official Python hashlib documentation for thread-safe hashing patterns inside concurrent worker pools.

Step-by-Step: A Cache-Through Routing Wrapper #

Wrap the solver call so callers never see the cache directly. The decorator below reads through to Redis, falls through to the solver on a miss, and writes back with the TTL chosen from the profile. Geometry is stored as GeoJSON text so it survives serialization without losing its CRS.

import json
import time
from typing import Callable, Optional, Tuple

import redis
from shapely.geometry import shape, mapping

TTL_BY_PROFILE = {
    "walking": 604800,   # 7 days  - static pedestrian graph
    "cycling": 604800,   # 7 days  - static bicycle graph
    "driving": 86400,    # 24 h    - base vehicular, no live traffic
    "driving-traffic": 900,  # 15 min - live-traffic matrix
}


def select_ttl(profile: str, departure_time: Optional[str]) -> int:
    """Pick a TTL from profile volatility; traffic-aware calls expire fastest."""
    if departure_time and departure_time != "static":
        return TTL_BY_PROFILE.get("driving-traffic", 900)
    return TTL_BY_PROFILE.get(profile, 86400)


def cached_isochrone(
    client: redis.Redis,
    solver: Callable[..., dict],
    origin: Tuple[float, float],
    profile: str,
    graph_version: str,
    departure_time: Optional[str] = None,
    max_time: int = 900,
) -> dict:
    """Read-through cache around a routing solver that returns a GeoJSON geometry."""
    key = generate_cache_key(
        origin, profile, graph_version, departure_time, max_time
    )

    cached = client.get(key)
    if cached is not None:
        client.hincrby("cache:stats", "hit", 1)
        return json.loads(cached)  # already a GeoJSON-shaped dict

    # Miss: solve, then persist the geometry as canonical GeoJSON text.
    client.hincrby("cache:stats", "miss", 1)
    started = time.perf_counter()
    geometry = solver(
        origin=origin, profile=profile,
        departure_time=departure_time, max_time=max_time,
    )
    elapsed_ms = (time.perf_counter() - started) * 1000

    record = {
        "geometry": mapping(shape(geometry["geometry"])),  # round-trips validity
        "epsg": 4326,
        "graph": graph_version,
        "solver_ms": round(elapsed_ms, 1),
    }
    client.set(key, json.dumps(record), ex=select_ttl(profile, departure_time))
    return record

Storing epsg and graph alongside the geometry lets every downstream reader assert the projection and the graph build it was computed against, which is the cheapest possible guard against silently mixing incompatible results.

Storage Topology and Expiration Policies #

Choose storage by query concurrency, geometry size, and infrastructure constraints. Redis delivers sub-millisecond lookups and native TTL expiration, making it the default for high-throughput portfolio modeling. For air-gapped or cost-constrained deployments, SQLite with R-tree spatial indexing or compressed GeoParquet files on object storage provide reliable persistence with predicate-pushdown reads.

For traffic-aware profiles, bucket departure_time to the hour before keying — minute-level departure stamps would make every request unique and drive the hit ratio to zero. Store precomputed isochrone polygons with their metadata (solver version, graph timestamp, profile hash) so partitions can be invalidated wholesale when the underlying network updates. Redis hashes can attach expiration windows directly to geometry payloads without any external cron job.

Edge Cases and Failure Modes #

Caching introduces a class of correctness bugs that do not exist when every query hits the solver live. Guard against each explicitly:

• CRS mismatch on write. A geometry computed in a projected CRS (e.g. EPSG:3857) but stored without its EPSG tag will be read back as if it were lon/lat, shifting catchments by kilometres. The wrapper above pins epsg in every record; assert it on read.
• Coordinate jitter shattering keys. Upstream geocoders that emit full float precision generate a unique key per call. Always round to coord_precision and snap before keying.
• Stale graph after a rebuild. Without graph_version in the key, a fresh OSM extract serves yesterday’s travel times indefinitely. Bump the version string on every osrm-extract / ORS rebuild.
• API rate limits on cold caches. A first run with an empty cache fires the full solver volume at once. Gate misses behind a semaphore and route them to the batch path rather than synchronous single-point calls; pair with Configuring OpenRouteService for Drive-Time Maps so cache refresh cycles align with profile recalibration.
• Silent solver upgrades. A patched routing engine can return slightly different geometry for an unchanged key. Treat solver version as part of graph_version, or validate cached geometry against a spatial tolerance (below).
• Partial writes under crash. A worker killed between solver() and set() leaves a miss, not a corrupt entry — acceptable. But never write before the geometry validity check passes, or invalid polygons become cache-resident.

Performance and Scaling #

Two levers dominate cache performance: hit ratio and serialization cost. Push the hit ratio up with node snapping, coordinate rounding, and pre-warming. In orchestrated environments (Airflow, Prefect, Dagster), schedule cache-warming DAGs that pre-populate high-traffic corridors and major retail nodes before peak modeling windows, so analysts open a warm cache rather than triggering a thundering herd of misses.

Control serialization cost on the write side. Large isochrone collections can trigger out-of-memory failures if every geometry is deserialized into worker RAM at once. Apply LRU eviction so hot corridors stay resident, store geometries as compact GeoJSON or WKB rather than pickled Python objects, and stream large result sets in chunks. For 10,000+ point workloads where the cache read/write budget must be tuned against the routing memory ceiling, the partitioning techniques in Reducing memory overhead for 10,000+ point batch routing keep heap allocation stable. Route cache misses to the batch-optimized /table path to amortize graph-loading cost across many origins instead of paying it per request.

Validation and QA Gates #

Run these checks before any cached geometry is allowed to flow into the downstream join or scoring stage:

from shapely.geometry import shape, Point


def validate_cached_record(record: dict, origin: tuple, tol_m: float = 50.0) -> list:
    """Return a list of validation failures for a cached routing record."""
    failures = []

    # 1. Projection contract.
    if record.get("epsg") != 4326:
        failures.append(f"unexpected EPSG: {record.get('epsg')}")

    geom = shape(record["geometry"])

    # 2. Geometry validity (catches self-intersections from solver upgrades).
    if not geom.is_valid:
        failures.append("invalid geometry (self-intersection or unclosed ring)")

    # 3. Origin containment: the source point must fall inside its own isochrone.
    if not geom.buffer(0).contains(Point(*origin)):
        failures.append("origin not contained in cached isochrone")

    # 4. Sanity bounds: an isochrone should not span an implausible bbox.
    minx, miny, maxx, maxy = geom.bounds
    if (maxx - minx) > 2.0 or (maxy - miny) > 2.0:  # ~200 km in degrees
        failures.append("bounding box exceeds plausible catchment extent")

    return failures

Emit structured logs that record key hashes, hit/miss ratios, fallback execution times, and solver response codes, and trip an alert when the validation failure rate exceeds 2% per batch. A drifting hit ratio is the earliest signal that an upstream geocoder changed precision or a graph version was bumped without warming the cache.

Integration Notes #

A validated, cached isochrone is the input to the next pipeline stage. Once the geometry clears the QA gates, it feeds the spatial join that attaches demographics to each catchment in Performing Point-in-Polygon Joins for Store Catchments, and from there into suitability scoring. Materialize hot, validated polygons into PostGIS with a GiST index so downstream dashboards query the same geometry the cache served, with no second solver round-trip. For mixed drive-and-walk catchments, key the cache per modal profile and reuse the profiles defined in Implementing Multi-Modal Routing for Urban Retail so vehicular and pedestrian results never collide on a shared key.

Properly architected caching turns network analysis from a computational bottleneck into a predictable service layer: deterministic keys maximize reuse, profile-aligned TTLs keep answers fresh, graph versioning makes invalidation automatic, and validation gates stop corrupt geometry at the door. With those four controls in place, retail planning teams can scale site evaluation across an entire portfolio without linear growth in cost or latency.

Related #

• Configuring OpenRouteService for Drive-Time Maps — keep cache refresh aligned with profile recalibration.
• Optimizing Batch Isochrone Generation with OSRM — coalesce cache misses into high-throughput /table calls.
• Reducing memory overhead for 10,000+ point batch routing — tune read/write budgets against the routing memory ceiling.
• Performing Point-in-Polygon Joins for Store Catchments — the downstream stage that consumes cached catchments.

← Back to Isochrone Generation & Network Analysis