Travel-Distance & Pick-Path Cost Modeling

Almost every slotting decision is justified by a travel saving, and almost every travel saving is computed from a distance metric that is quietly wrong. Straight-line distance between two bin coordinates is the default in most spreadsheets, and it can understate a real pick walk by half — because a picker cannot walk through racking. This guide is part of the Pick-Path Optimization & Space Utilization architecture, and it builds the component every other stage depends on: the travel-cost model that turns a facility into a weighted aisle graph and converts a route into a defensible labour-time number. Get this layer right and the sequencer, the congestion router, and the assignment solver all inherit a distance they can trust; get it wrong and every downstream saving is measured against a fiction.

What Travel-Distance Cost Modeling Is

Travel-distance cost modeling is the discipline of computing, for any pair or set of pick locations, the labour time a picker actually spends traversing between them — and doing it consistently enough that two candidate slot layouts can be compared on the clock, not on a guess. It has two halves: a distance metric (how far apart two locations are, given the racking the picker must walk around) and a cost function (how many seconds that distance costs, given walk speed, turns, and congestion).

The distance metric is where most models fail. Three metrics are in common use, in increasing order of fidelity:

• Euclidean distance — the straight line between coordinates, sqrt(dx**2 + dy**2). Fast and completely wrong for a racked facility: it walks diagonally through solid steel. Useful only as a lower bound or for open bulk-floor storage with no aisles.
• Rectilinear (Manhattan) distance — abs(dx) + abs(dy), which respects that travel happens along orthogonal aisles and cross-aisles. A large improvement, but it still assumes you can turn anywhere, ignoring that aisles have entry points only at their ends.
• Aisle-graph distance — the shortest path over a graph whose nodes are aisle ends, cross-aisle intersections, and pick faces, and whose edges are the walkable segments between them. This is the only metric that models a real single-block or multi-block layout, because it forces travel up an aisle to a cross-aisle before it can reach the next aisle.

On top of the metric sits a routing heuristic that decides the order in which a batch of picks is visited within an aisle structure, because the picker rarely visits one location and stops:

• Traversal (S-shape) — the picker enters an aisle at one end, walks its full length, exits the far end, and snakes into the next aisle. Simple, near-optimal when most aisles contain a pick, and trivially cheap to compute.
• Return — the picker enters an aisle, walks only as far as the deepest pick, and returns to the same cross-aisle. Wins when aisles are sparsely visited, because it avoids traversing an aisle for a single front pick.
• Midpoint — a hybrid that splits each aisle at its midline: picks in the front half are served from the front cross-aisle, picks in the back half from the rear. It bounds worst-case backtracking and is the practical default for mixed pick densities.

The cost model must know which heuristic the floor uses, because the same slot layout produces different travel under each. A layout tuned for traversal can be actively bad under return routing.

Input Data Requirements

The model consumes a location topology plus a pick list. The topology is static and cached; the pick list changes per wave. Missing coordinates silently collapse the aisle graph into disconnected components, so treat every field below as a hard precondition, not a nice-to-have.

from __future__ import annotations

from dataclasses import dataclass


@dataclass(frozen=True)
class GraphNode:
    """One node in the aisle graph: an aisle end, cross-aisle junction, or pick face."""
    node_id: str
    x: float
    y: float
    kind: str          # "pick" | "aisle_end" | "cross_junction"


@dataclass(frozen=True)
class GraphEdge:
    """A walkable segment between two nodes, weighted by physical length."""
    a: str
    b: str
    length_m: float

The quality gate that matters most is connectivity: before any distance is computed, assert the graph is a single connected component. An orphaned aisle — one whose cross-aisle edge was never added — produces inf distances that poison every route that touches it, and the failure is silent unless you check for it explicitly.

Step-by-Step Implementation

The pipeline has three passes: build the aisle graph from topology, precompute shortest-path distances over it, then wrap those distances in a labour-time cost function. Each pass is a pure function so the whole thing is testable and cacheable.

1. Build the Aisle Graph with networkx

Model the facility as an undirected weighted graph. Nodes are pick faces, aisle ends, and cross-aisle junctions; edges are the walkable segments, weighted by physical length. Intra-aisle edges connect consecutive bays; junction edges connect aisle ends to the cross-aisles that join them. Using networkx gives you battle-tested shortest-path routines and a clean place to assert connectivity.

from __future__ import annotations

import logging

import networkx as nx

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


def build_aisle_graph(nodes: list[GraphNode], edges: list[GraphEdge]) -> nx.Graph:
    """Assemble the weighted aisle graph and assert it is fully connected."""
    g: nx.Graph = nx.Graph()
    for n in nodes:
        g.add_node(n.node_id, x=n.x, y=n.y, kind=n.kind)
    for e in edges:
        g.add_edge(e.a, e.b, weight=e.length_m)

    if not nx.is_connected(g):
        components = nx.number_connected_components(g)
        logger.error("Aisle graph is disconnected: %d components", components)
        raise ValueError(f"aisle graph has {components} disconnected components")

    logger.info("Built aisle graph: %d nodes, %d edges", g.number_of_nodes(), g.number_of_edges())
    return g

2. Precompute Shortest-Path Distances

Routing over the graph on every candidate route is wasteful — the topology is static within a wave, so precompute an all-pairs distance table for the pick faces once and read from it. For a few thousand nodes, floyd_warshall or repeated Dijkstra runs in well under a second; for larger graphs, restrict the all-pairs computation to pick-face nodes only. The precomputed matrix is the artifact every downstream stage consumes, and building it well is the whole subject of the child guide How to Build a Travel-Time Distance Matrix for a Warehouse.

def shortest_distance(g: nx.Graph, source: str, target: str) -> float:
    """Aisle-graph shortest walking distance in metres between two locations."""
    try:
        dist: float = nx.dijkstra_path_length(g, source, target, weight="weight")
    except nx.NetworkXNoPath:
        logger.warning("No path %s -> %s; returning inf", source, target)
        return float("inf")
    return dist

3. Convert Distance to a Labour-Time Cost

Metres are not the unit slotting cares about — seconds of picker labour are. The cost function divides distance by walk speed, adds a fixed penalty per aisle change (a 180-degree turn with a loaded cart is not free), and multiplies by a congestion factor that rises with aisle density. The congestion multiplier is the seam where this model meets the congestion router; here it is a parameter, computed in full downstream.

from dataclasses import dataclass


@dataclass
class CostParams:
    walk_speed_mps: float = 1.2
    turn_penalty_s: float = 4.0
    congestion_multiplier: float = 1.0


def travel_time_s(distance_m: float, turns: int, cfg: CostParams) -> float:
    """Convert an aisle-graph distance into a congestion-adjusted labour-time cost."""
    base = distance_m / cfg.walk_speed_mps + turns * cfg.turn_penalty_s
    cost = base * cfg.congestion_multiplier
    logger.debug("dist=%.1fm turns=%d -> %.1fs (x%.2f)", distance_m, turns, cost, cfg.congestion_multiplier)
    return cost

Composing the three passes gives you a single call — graph, distance, cost — that any candidate layout or wave plan can be scored against consistently. Because the distance table is precomputed, scoring a route is a lookup and a multiply, cheap enough to evaluate thousands of candidate batchings per wave.

Tuning & Calibration

The single most consequential parameter is walk_speed_mps, because it scales every route time linearly — a 15% calibration error biases every comparison by 15% in the same direction, which is invisible precisely because it is uniform. Do not use a vendor default; fit it from timestamped pick confirmations by regressing observed inter-pick time against modeled aisle-graph distance. The turn_penalty_s matters most in dense small-item picking where turns are frequent; the congestion_multiplier matters most at peak.

# travel_cost.yaml — one profile per facility
metric: "aisle_graph"        # aisle_graph | rectilinear | euclidean
routing_heuristic: "midpoint" # traversal | return | midpoint
walk_speed_mps: 1.2          # loaded-cart speed; regress from pick timestamps
turn_penalty_s: 4.0          # seconds per aisle change / 180-degree turn
congestion_multiplier: 1.0   # base; raised per aisle by the congestion router
distance_cache: true         # precompute + cache the all-pairs matrix
recompute_on: "layout_change" # rebuild the graph only when racking moves

# Equivalent Python config dict consumed by the cost model
TRAVEL_COST = {
    "metric": "aisle_graph",
    "routing_heuristic": "midpoint",
    "walk_speed_mps": 1.2,
    "turn_penalty_s": 4.0,
    "congestion_multiplier": 1.0,
    "distance_cache": True,
    "recompute_on": "layout_change",
}

Parameter sensitivity is not uniform. walk_speed_mps is a global scale — calibrate it once per facility and per shift pattern. routing_heuristic is a policy choice that must match how the floor actually walks; changing it invalidates the distance cache and must trigger a rebuild. turn_penalty_s is a fine-tuning lever for dense zones. Recalibrate walk speed whenever cart type, staffing mix, or aisle width changes, because each one shifts the metres-to-seconds relationship the whole model rests on.

Validation & Testing

Never trust a distance model you have not asserted against known geometry. Three invariants must hold: the graph is connected, aisle-graph distance is always at least euclidean distance (you can never beat the straight line), and the cost function is monotonic in distance. The pytest checks below encode all three and run before the distance cache is published.

import math

import networkx as nx


def _toy_graph() -> nx.Graph:
    nodes = [
        GraphNode("A", 0.0, 2.0, "pick"), GraphNode("Atop", 0.0, 0.0, "aisle_end"),
        GraphNode("Btop", 6.0, 0.0, "aisle_end"), GraphNode("B", 6.0, 3.0, "pick"),
    ]
    edges = [
        GraphEdge("A", "Atop", 2.0), GraphEdge("Atop", "Btop", 6.0), GraphEdge("Btop", "B", 3.0),
    ]
    return build_aisle_graph(nodes, edges)


def test_graph_is_connected() -> None:
    assert nx.is_connected(_toy_graph())


def test_aisle_distance_never_beats_euclidean() -> None:
    g = _toy_graph()
    aisle = shortest_distance(g, "A", "B")           # 2 + 6 + 3 = 11.0
    euclid = math.dist((0.0, 2.0), (6.0, 3.0))       # ~6.08
    assert aisle >= euclid - 1e-9


def test_cost_is_monotonic_in_distance() -> None:
    cfg = CostParams(walk_speed_mps=1.2, turn_penalty_s=4.0)
    assert travel_time_s(10.0, 0, cfg) < travel_time_s(20.0, 0, cfg)

A healthy run reports the toy graph as connected, an aisle distance of 11.0 against a euclidean ~6.08, and a strictly increasing cost. If test_aisle_distance_never_beats_euclidean ever fails, your coordinates and edge weights disagree — usually a unit mismatch — and every downstream saving is suspect until it is fixed.

Integration Points

The travel-cost model is a source, not a sink. Its output fans out to three sibling systems, and each imposes a contract:

• Space and cube scoring. Travel cost and space cost trade off directly — a layout that minimizes travel can strand cube, and vice versa. The route times computed here are one axis of that trade-off; Space & Cube Utilization Scoring supplies the other, so placement can be scored on both at once rather than optimizing travel into a honeycombed rack.
• Wave and batch sequencing. The sequencer cannot balance labour without a per-route time, and it reads that time straight from this model. Wave & Batch Pick Sequencing consumes the precomputed distance matrix to evaluate thousands of candidate batchings per wave, which is only affordable because distances are cached, not recomputed.
• Slot-assignment optimization. The solver that decides where a SKU lives needs a travel objective to minimize, and this model is that objective. Feeding aisle-graph distances into Solving Slot Assignment with Linear Programming is what lets the assignment layer optimize against real walking distance instead of a euclidean approximation.

Upstream, the coordinates and topology this model consumes are the facility map maintained in the Pick-Path Optimization & Space Utilization architecture; a rack move that is not reflected in the graph produces confidently wrong distances until the topology is rebuilt.

Failure Modes & Edge Cases

• Euclidean distance mistaken for real travel. The most common and most expensive error: a straight-line metric understates travel by 30–60% in a cross-aisle layout and makes every slotting decision optimize a path no one walks. Remediation: default to aisle_graph, and keep test_aisle_distance_never_beats_euclidean in the production path.
• Disconnected aisle graph. A missing cross-aisle edge orphans an aisle, yielding inf distances that silently corrupt any route touching it. Remediation: assert nx.is_connected on every graph build and fail closed.
• Uncalibrated walk speed. A guessed walk_speed_mps biases every route time by the same factor, invisibly. Remediation: regress observed inter-pick times against modeled distance each time labour or equipment changes.
• Heuristic mismatch. Scoring a layout under traversal routing when the floor actually uses return routing produces savings that never materialize. Remediation: set routing_heuristic to match floor practice and rebuild the cache when it changes.
• Stale distance cache. A rack move not reflected in the topology leaves the cached matrix describing a facility that no longer exists. Remediation: gate cache reuse on a topology hash and rebuild on layout_change.

FAQ

When is euclidean distance ever acceptable?

Only when there is genuinely no racking to walk around — open bulk-floor storage, a cross-dock staging area, or a yard. Everywhere aisles exist, euclidean distance walks through steel and understates travel, and the error is worst exactly where it matters most: dense, deep-aisle pick zones. Even as a quick approximation it is dangerous, because the understatement is not uniform across a facility, so it distorts the ranking of candidate layouts, not just their absolute numbers.

Rectilinear or full aisle-graph distance — is the graph worth the complexity?

Rectilinear distance is a reasonable approximation for a simple single-block layout with cross-aisles at both ends, and it needs no graph. The aisle graph earns its keep the moment the layout is non-trivial: multiple cross-aisles, one-way aisles, blocked segments, mezzanines, or non-rectangular footprints. Because networkx makes the graph cheap to build and the distances cheap to cache, the practical default is to model the graph and let it degrade to rectilinear numbers where the layout happens to be simple.

How do I choose between traversal, return, and midpoint routing?

Match the heuristic to pick density. Traversal (S-shape) wins when most aisles contain at least one pick, because you are walking the aisle anyway. Return wins when aisles are sparsely visited, since it avoids traversing a full aisle for a single front pick. Midpoint is the robust default for mixed density because it bounds worst-case backtracking. Whatever you choose must match how the floor actually walks — a model tuned for one heuristic misprices routes under another.

How often should the distance matrix be recomputed?

The topology is static until racking physically moves, so recompute the all-pairs matrix on a layout_change event, not on a schedule. Gate the cached matrix on a hash of the topology so any edit forces a rebuild automatically. Walk-speed recalibration is separate and more frequent: re-fit walk_speed_mps whenever cart type, staffing, or shift pattern changes, since that shifts the metres-to-seconds conversion without changing distances.

Related

• Pick-Path Optimization & Space Utilization — the parent architecture this cost model feeds with trustworthy route times.
• How to Build a Travel-Time Distance Matrix for a Warehouse — precompute and cache the all-pairs matrix this model relies on.
• Space & Cube Utilization Scoring — the space cost that trades off against the travel cost computed here.
• Wave & Batch Pick Sequencing — the sequencer that consumes these route times to balance labour.
• Solving Slot Assignment with Linear Programming — the solver that minimizes this travel objective when placing SKUs.