Slotting Architecture · 9 min read

How to Build a Travel-Time Distance Matrix for a Warehouse

You need to score thousands of candidate pick routes per wave, and computing a shortest path over the aisle graph on every scoring call is far too slow. The fix is to pay the graph-search cost once: precompute an all-pairs travel-time matrix over the warehouse aisle graph, cache it keyed to the layout, and reduce every later route score to a dictionary lookup and a sum. This page shows exactly how to build that matrix with networkx, convert metres to seconds, and persist it. It is the concrete implementation behind the Travel-Distance & Pick-Path Cost Modeling cluster, which explains why aisle-graph distance is the only defensible metric in the first place.

Pipeline from aisle graph to a cached travel-time matrix A left-to-right pipeline of four stages feeding a matrix. The aisle graph of nodes and edges feeds an all-pairs shortest-path pass computed with floyd_warshall, producing a distance matrix in metres, which is multiplied by a cost function of walk speed and turn penalties to produce a travel-time matrix in seconds. The final artifact is a three-by-three symmetric matrix with a zero diagonal and sample values of eighteen, thirty-three, and twenty-one seconds, held as a cached lookup. Building the travel-time distance matrix Aisle graph nodes + edges All-pairs SPL floyd_warshall() Distance matrix metres (m) × cost function speed + turns travel-time (s) 01833 18021 33210 cached lookup

Prerequisites

Confirm each of these before building the matrix:

  • Python 3.10+ — the implementation uses dict[...] generics, X | None unions, and a dataclass config.
  • networkx 3.0+ — for the aisle graph and floyd_warshall_numpy / all_pairs_dijkstra_path_length.
  • A connected aisle graph — built and validated per the parent cluster, Travel-Distance & Pick-Path Cost Modeling; a disconnected graph yields inf cells.
  • A calibrated walk speed — walk_speed_mps regressed from timestamped pick confirmations for this facility, not a vendor default.
  • A writable cache path — a local directory or object-store prefix to persist the matrix, plus a topology hash so a stale cache is never reused after a rack move.

Configuration Block

Everything tunable lives in one externalized profile. The topology_hash is the cache key: change the racking and the hash changes, forcing a rebuild.

# travel_matrix.yaml — one profile per facility
walk_speed_mps: 1.2          # calibrated loaded-cart speed
turn_penalty_s: 4.0          # seconds added per aisle change
algorithm: "floyd_warshall"  # floyd_warshall | dijkstra
pick_faces_only: true        # restrict all-pairs to pick nodes, not junctions
cache_path: "cache/travel_time.json"
topology_hash: "layout-2026-07-a1"  # bump on any rack move to invalidate cache
# Equivalent Python config dict consumed by the builder
TRAVEL_MATRIX = {
    "walk_speed_mps": 1.2,
    "turn_penalty_s": 4.0,
    "algorithm": "floyd_warshall",
    "pick_faces_only": True,
    "cache_path": "cache/travel_time.json",
    "topology_hash": "layout-2026-07-a1",
}

Implementation

The builder runs all-pairs shortest paths over the aisle graph, converts each distance to seconds, and writes the result to a cache keyed by the topology hash. On a warm cache with a matching hash it loads instead of recomputing, so the expensive graph search happens once per layout, not once per wave.

from __future__ import annotations

import json
import logging
from pathlib import Path

import networkx as nx

logger = logging.getLogger("pickpath.matrix")

TravelMatrix = dict[str, dict[str, float]]


def build_travel_time_matrix(g: nx.Graph, cfg: dict) -> TravelMatrix:
    """Precompute an all-pairs travel-time matrix (seconds) over the aisle graph.

    Loads from cache when the stored topology hash matches; otherwise runs
    all-pairs shortest paths, converts metres to seconds via walk speed, and
    persists the result. Returned as a nested dict: matrix[a][b] = seconds.
    """
    cache = Path(cfg["cache_path"])
    if cache.exists():
        stored = json.loads(cache.read_text())
        if stored.get("topology_hash") == cfg["topology_hash"]:
            logger.info("Cache hit (%s); loaded %d source nodes",
                        cfg["topology_hash"], len(stored["matrix"]))
            return stored["matrix"]
        logger.warning("Cache stale: %s != %s; rebuilding",
                       stored.get("topology_hash"), cfg["topology_hash"])

    faces = [n for n, d in g.nodes(data=True)
             if not cfg["pick_faces_only"] or d.get("kind") == "pick"]
    speed = cfg["walk_speed_mps"]
    matrix: TravelMatrix = {}
    for src, dist_map in nx.all_pairs_dijkstra_path_length(g, weight="weight"):
        if src not in faces:
            continue
        matrix[src] = {dst: round(dist_map[dst] / speed, 2)
                       for dst in faces if dst in dist_map}

    cache.parent.mkdir(parents=True, exist_ok=True)
    cache.write_text(json.dumps({"topology_hash": cfg["topology_hash"], "matrix": matrix}))
    logger.info("Built travel-time matrix: %d x %d faces -> %s",
                len(matrix), len(faces), cache)
    return matrix


def route_seconds(order: list[str], matrix: TravelMatrix) -> float:
    """Score an ordered route as a sum of cached pairwise travel times."""
    return sum(matrix[order[i]][order[i + 1]] for i in range(len(order) - 1))

Step-by-Step Walkthrough

  1. Check the cache first. The builder reads cache_path and compares the stored topology_hash against the configured one. A match returns the cached matrix immediately — the whole point of the exercise, since the all-pairs search is the expensive part. A mismatch logs a warning and falls through to a rebuild, so a rack move can never serve stale distances.
  2. Restrict to pick faces. With pick_faces_only set, the matrix is built only between nodes whose kind is "pick", skipping aisle-end and cross-junction nodes that no task ever targets. On a graph with many junctions this shrinks the matrix quadratically and keeps the cache small.
  3. Run all-pairs shortest paths. nx.all_pairs_dijkstra_path_length yields, for each source, a map of shortest walking distances in metres. For dense graphs where you want a single dense array, swap in floyd_warshall_numpy; the algorithm config key records which you used.
  4. Convert metres to seconds. Each distance is divided by the calibrated walk_speed_mps and rounded, turning the physical matrix into the labour-time matrix slotting actually reasons about. Turn penalties are applied at route-scoring time, since they depend on the visit order, not the pair.
  5. Persist and reuse. The matrix is written with its topology hash so the next process loads instead of recomputing. route_seconds then scores any candidate route as a sum of lookups — cheap enough to evaluate thousands of batchings per wave.

Verification

Assert the matrix invariants directly: the diagonal is zero, the matrix is symmetric over an undirected graph, and a known route sums to the expected time. These run without a live WMS.

import logging

logging.basicConfig(level=logging.INFO)

# Toy graph: A --2m-- J(top) --6m-- K(top) --3m-- B, walk speed 1.0 m/s
g = nx.Graph()
for n in ["A", "J", "K", "B"]:
    g.add_node(n, kind="pick" if n in ("A", "B") else "aisle_end")
g.add_edge("A", "J", weight=2.0)
g.add_edge("J", "K", weight=6.0)
g.add_edge("K", "B", weight=3.0)

cfg = {"walk_speed_mps": 1.0, "turn_penalty_s": 0.0, "algorithm": "dijkstra",
       "pick_faces_only": True, "cache_path": "cache/test_tt.json",
       "topology_hash": "toy-1"}

m = build_travel_time_matrix(g, cfg)
assert m["A"]["A"] == 0.0                       # zero diagonal
assert m["A"]["B"] == m["B"]["A"] == 11.0       # symmetric, 2 + 6 + 3 metres / 1.0
assert route_seconds(["A", "B"], m) == 11.0
print("OK — travel-time matrix verified:", m["A"])

Sample expected output:

INFO:pickpath.matrix:Built travel-time matrix: 2 x 2 faces -> cache/test_tt.json
OK — travel-time matrix verified: {'A': 0.0, 'B': 11.0}

Common Pitfalls

  • Never invalidating the cache. A matrix cached without a topology hash silently outlives the layout that produced it, so a rack move leaves every route scored against distances that no longer exist. Always key the cache on topology_hash and bump it on any physical change.
  • Including junction nodes you never pick from. Building all-pairs over every node, junctions included, bloats the matrix quadratically and slows both the build and the cache load. Set pick_faces_only unless a downstream stage genuinely routes through named junctions.
  • Baking turn penalties into the matrix. Turn cost depends on the order of visits, not on the pair of endpoints, so folding it into the pairwise matrix double-counts or misprices it. Keep the matrix pure distance-time and add turn penalties in the route scorer.
  • An uncalibrated walk speed. Dividing by a guessed walk_speed_mps scales the entire matrix by a constant error that is invisible because it is uniform. Regress speed from real pick timestamps, and rebuild the matrix whenever cart type or staffing shifts it.