Multi-Modal and Fleet Routing on a Spatial Graph

Two problems sit just past single-vehicle shortest path, and both break the assumptions that made it easy. Multi-modal routing asks for a journey that changes mode — drive to a station, take a train, walk to the door — where the cost of changing is not the cost of any edge and the wait for the next departure depends on when you arrive. Fleet routing asks not for one route but for an assignment: which of forty vehicles serves which of three hundred stops, which needs the cost between every relevant pair before any decision can be made. The first needs the graph to represent transfers honestly; the second needs a cost matrix computed at a scale where issuing one shortest-path query per pair is not an option. This topic covers both, and the place they meet — a fleet whose vehicles are not all the same mode.

Prerequisites

The matrix work uses Graph Data Science; the transfer modelling is plain schema design.

Requirement Minimum version Install
Python 3.11 —
neo4j (async driver) 5.20 pip install "neo4j>=5.20"
Neo4j Server 5.15 native point
Graph Data Science 2.6 gds.allShortestPaths.dijkstra

Core Concept & Mechanism

A transfer is an edge, not an exception. The instinct is to route each mode separately and stitch the legs together in application code, adding a fixed penalty at each join. That produces journeys that are individually optimal and jointly wrong, because the search never had the chance to trade a longer drive against a better connection. Modelling the transfer as a real relationship — (:CarPark)-[:TRANSFER {seconds: 240}]->(:Platform) — puts the cost inside the graph where the algorithm can see it, and the search then optimises the whole journey rather than each leg in isolation.

Mode changes make the graph layered. The clean structure is one node set per mode, connected only at transfer points. A road junction and a station platform are different nodes even when they are the same place, because what you can do next differs entirely. That layering is what stops a search from walking along a railway line or driving down a platform, and it does so structurally rather than by filtering — the same argument that makes an edge-based turn graph preferable to a rule that has to be checked.

A cost matrix is one search per source, not one per pair. This is the observation that makes fleet routing tractable. A single-source Dijkstra settles every reachable node in one pass, so the cost from one depot to all three hundred stops comes from one search rather than three hundred. For $S$ sources and $T$ targets the work is $O(S)$ searches rather than $O(S \times T)$ — on forty vehicles and three hundred stops, forty searches instead of twelve thousand.

Three mode layers joined only at transfer edges A layered graph with a walking layer, a road layer and a rail layer. Each layer holds its own nodes and its own edges, and no edge crosses between layers except an explicit TRANSFER relationship carrying the cost of changing mode — four minutes to park and reach a platform, two minutes to leave a station on foot. Because the layers share no nodes, a search cannot accidentally drive along a railway or walk down a motorway; the restriction is structural rather than a filter that has to be applied and could be forgotten. The transfer cost sits inside the graph, so the search can trade a longer drive against a better connection. One journey, three layers, two transfers road layer junctions and segments j1 j2 P car park rail layer platforms and scheduled services A B 08:30 → 08:44 walking layer footways, both directions w1 w2 TRANSFER 4 min — park, walk to the platform TRANSFER 2 min — leave the station on foot No node is in two layers, so no search can drive along the railway. The restriction is in the shape of the graph.

Schema & Data Model

// Transfers are their own relationship type so a projection can include or
// exclude them, and so their cost is auditable independently of any road edge.
CREATE INDEX transfer_mode_pair IF NOT EXISTS
FOR ()-[t:TRANSFER]-() ON (t.from_mode, t.to_mode);

// A layered graph needs its labels kept honest: a node in the road layer must
// never also be a platform, or the layering has been defeated.
MATCH (n) WHERE n:Junction AND n:Platform
RETURN count(n) AS layering_violations;

// Depots and stops for the fleet side. The matrix is keyed on these ids.
CREATE CONSTRAINT stop_id IF NOT EXISTS
FOR (s:Stop) REQUIRE s.id IS UNIQUE;

Transfers should carry their direction and their asymmetry. Parking a car and walking to a platform takes longer than walking from a platform back to a car, because one includes finding a space; boarding is not the reverse of alighting. Two directed relationships with different costs is the honest model, and collapsing them to one symmetric edge is the same class of error as ignoring gradient.

Step-by-Step Implementation

1. Project the layers the query actually needs. A walking-only journey should not carry the road layer’s memory, and a driving-only fleet problem should not carry rail.

import asyncio
from dataclasses import dataclass

from neo4j import AsyncGraphDatabase

PROJECT_MODES = """
CALL gds.graph.project.cypher(
  $graph,
  'MATCH (n) WHERE any(l IN labels(n) WHERE l IN $labels) RETURN id(n) AS id',
  'MATCH (a)-[r]->(b) WHERE type(r) IN $types
   RETURN id(a) AS source, id(b) AS target, r.seconds AS seconds',
  {parameters: {labels: $labels, types: $types}}
)
YIELD graphName, nodeCount, relationshipCount
RETURN nodeCount, relationshipCount
"""


@dataclass(frozen=True)
class ModeSet:
    labels: list[str]
    types: list[str]

    @staticmethod
    def driving() -> "ModeSet":
        return ModeSet(labels=["Junction"], types=["SEGMENT"])

    @staticmethod
    def park_and_ride() -> "ModeSet":
        # TRANSFER is included deliberately: without it the layers are three
        # disconnected components and every cross-mode query returns no path.
        return ModeSet(
            labels=["Junction", "Platform", "Footway"],
            types=["SEGMENT", "SERVICE", "WALK", "TRANSFER"],
        )

2. Build the matrix with one search per source.

MATRIX = """
MATCH (src:Stop {id: $source_id})
CALL gds.allShortestPaths.dijkstra.stream($graph, {
  sourceNode: src, relationshipWeightProperty: 'seconds'
})
YIELD targetNode, totalCost
WITH gds.util.asNode(targetNode) AS t, totalCost
WHERE t:Stop AND t.id IN $target_ids
RETURN t.id AS target_id, totalCost AS seconds
"""


async def cost_matrix(driver, graph: str, sources: list[str],
                      targets: list[str]) -> dict[tuple[str, str], float]:
    """One single-source search per SOURCE, not one per pair.

    Dijkstra settles every reachable node in a single pass, so the row for a
    source is a by-product of one search. Issuing a point-to-point query per
    cell instead does the same work |targets| times over and throws away
    everything it learned each time.
    """
    matrix: dict[tuple[str, str], float] = {}
    async with driver.session() as session:
        for source_id in sources:
            result = await session.run(
                MATRIX, graph=graph, source_id=source_id, target_ids=targets
            )
            async for record in result:
                matrix[(source_id, record["target_id"])] = float(record["seconds"])
    return matrix

3. Hand the matrix to an assignment step, which is no longer a graph problem — it is an optimisation one, worked through in assigning deliveries to vehicles from a cost matrix.

Query Patterns & Variants

Bounding the search so it stops at the useful radius. A single-source Dijkstra over a continental graph settles millions of nodes to find three hundred. Capping the cost turns that into a local search.

CALL gds.allShortestPaths.dijkstra.stream($graph, {
  sourceNode: src, relationshipWeightProperty: 'seconds'
})
YIELD targetNode, totalCost
WHERE totalCost <= $max_seconds
RETURN gds.util.asNode(targetNode).id AS target_id, totalCost;

Penalising transfers beyond their time cost. Passengers dislike changing more than the clock says. Adding a fixed dislike to every TRANSFER — expressed in seconds so it stays in one unit — biases the search toward fewer legs without needing a second objective.

Asymmetric matrices. On a one-way network the cost from A to B is not the cost from B to A, so the matrix has no symmetry to exploit and both directions must be computed. Assuming symmetry to halve the work is a common and quiet error.

Performance Tuning

The matrix dominates everything, and its cost has a shape worth knowing:

$$C_{\text{matrix}} \approx S \cdot \big(|V’| \log |V’| + |E’|\big)$$

where $V’$ and $E’$ are the settled portion of the graph, not the whole of it. That is why the cost bound matters so much: without it, each of $S$ searches explores the entire reachable network; with it, each explores a disc around its source. On a national graph with a two-hour bound, that is often two orders of magnitude.

Three further levers. Reuse one projection for the whole matrix — building it per source is the single most common way to make this slow, and the projection sizing guidance applies with force here because the projection is held for the duration of many searches. Run the sources concurrently, bounded by a semaphore, since they are independent reads. And cache the matrix by its inputs: a fleet’s depot set changes rarely and its stop set changes daily, so yesterday’s matrix is mostly still valid and only the new stops need rows.

For a genuinely large fleet problem — thousands of stops, matrices recomputed continuously — the shape that scales is a contraction hierarchy over a static network, where the preprocessing is paid once and every matrix cell afterwards is a bounded bidirectional search.

One search per source fills a whole row, so the matrix costs S searches and not S times T A cost matrix of 40 depots against 300 stops, which is 12,000 cells. Filling it with a point-to-point query per cell means 12,000 searches, each of which settles most of the same nodes and discards everything it learned about every stop except one. Filling it with a single-source search per depot means 40 searches, each producing a complete row as a by-product. The answer in every cell is identical; the work differs by a factor of 300, which is exactly the number of targets. 40 depots × 300 stops = 12,000 cells a point-to-point query per cell each cell its own search, each discarding the rest 12,000 searches one single-source search per depot a whole row falls out of one settled search 40 searches The factor between them is the target count, so the gap widens exactly as the problem gets interesting. Bounding the search by cost then shrinks each of the 40 from a national exploration to a local one.

Edge Cases & Gotchas

  • Unreachable pairs are not zero cost. A stop on an island, or one whose nearest junction failed to snap, simply never appears in the search’s output. Filling the missing cell with zero makes it the cheapest assignment in the matrix and it will win every time. Fill with infinity, and count the infinities as a data-quality signal.
  • Transfer edges omitted from the projection. Without them the layers are disconnected components, and every cross-mode query returns “no path” rather than an error. The tell is that single-mode queries work perfectly, which sends the investigation in the wrong direction.
  • Mixing units across layers. Walking costs in metres and rail costs in seconds will produce a search that finds paths and orders them by nonsense. Pick one unit — seconds is the only one that survives a mode change — and convert at ingestion.
  • Time-dependent legs in a static matrix. A matrix computed against a schedule is valid only for the departure time it was computed at. Recomputing per departure window is correct and expensive; the cheaper compromise is a matrix per time band, which the time-dependent routing material treats properly.
  • Symmetry assumed on a one-way network. Computing the upper triangle and mirroring it halves the work and produces wrong costs wherever the network is directed, which in a city is everywhere.
  • Projection staleness across a long matrix build. A build that takes twenty minutes is reading a snapshot taken twenty minutes ago; if the graph is being updated concurrently, the matrix is internally consistent but not current. That is usually the right trade, but it should be a decision rather than a surprise.

Verification & Testing

import math
import pytest


@pytest.mark.asyncio
async def test_matrix_has_no_silent_zeros(matrix, sources, targets):
    """An unreachable pair must be infinite, never zero — a zero wins every
    assignment it appears in, and looks like an excellent result."""
    for s in sources:
        for t in targets:
            cost = matrix.get((s, t), math.inf)
            assert cost > 0 or s == t, f"zero cost between distinct nodes {s} → {t}"


@pytest.mark.asyncio
async def test_transfer_edges_are_in_the_projection(session, graph_name):
    """Cross-mode queries fail as 'no path' rather than as an error, so assert
    the connectivity rather than waiting for a support ticket."""
    result = await session.run(
        "CALL gds.graph.relationshipTypes($g) YIELD relationshipType "
        "RETURN collect(relationshipType) AS types", g=graph_name)
    types = (await result.single())["types"]
    assert "TRANSFER" in types, f"layers are disconnected: {types}"

The first of these is the one worth wiring into the pipeline rather than the test suite, because it fails for reasons outside the code — a new stop that did not snap, a depot moved to an address the graph does not reach.

FAQ

Should each mode be a separate graph or separate labels in one graph?

One graph, separate labels. Separate graphs make the transfer a join in application code, which is exactly what putting the cost in the graph avoids. Labels give the same isolation — a projection selects the layers it needs — while keeping transfers as ordinary relationships a search can traverse.

How large can a cost matrix get before this approach stops working?

The limit is the source count, since that sets the search count. A few hundred sources against any number of targets is comfortable with a bounded search and a resident projection. Thousands of sources recomputed continuously is where contraction hierarchies start to pay for their preprocessing.

Do I need the transfer penalty if the transfer time is already modelled?

They answer different questions. The transfer time is how long the change takes; the transfer penalty is how much a passenger dislikes changing at all, which is real and not captured by the clock. Keeping them as separate properties lets you tune the preference without corrupting the journey time you report.

Can the fleet contain vehicles with different modes?

Yes, and it is the case this topic exists for. Build one matrix per mode against the same stop set — a cargo-bike matrix over the cycling layer, a van matrix over the road layer — and let the assignment step choose across them. The rows are directly comparable because both are in seconds.

Why is my many-to-many query slower than the same number of point-to-point ones?

Almost always because the search is unbounded. A single-source Dijkstra with no cost cap settles the entire reachable component, which on a national graph is millions of nodes per source, while a point-to-point search stops as soon as the target is settled. Add the bound and the ordering reverses sharply.

This topic is part of Network Routing Algorithms in Python.

Subtopics

Siblings