Transfer Penalties in Multi-Modal Graphs

A journey planner that minimises pure travel time will happily offer a route with four changes that saves ninety seconds over one with a single change, and nobody will take it. Travellers dislike changing far more than the clock says they should — the change carries risk, luggage, unfamiliar platforms and the chance of missing a connection — and a planner that cannot express that dislike produces technically optimal results that read as unusable. The fix is one extra number per transfer, but it has to be the right kind of number, kept separate from the time it takes to change and expressed in the same unit as everything else. This page builds that, and shows how to tune it without corrupting the journey time you report back.

Prerequisites & Versions

The penalty is a relationship property consumed by an ordinary weighted search.

Implementation

Every transfer carries two numbers: how long it takes, and how much it is disliked. The search minimises their sum; the reported journey time uses only the first.

import asyncio
from dataclasses import dataclass

from neo4j import AsyncGraphDatabase

# Two properties, deliberately. `seconds` is a physical duration; `penalty_s` is
# a preference expressed in the same unit so the search can add them. Folding
# them into one number makes the reported journey time a fiction.
SET_PENALTIES = """
UNWIND $rows AS row
MATCH (a)-[t:TRANSFER {id: row.id}]->(b)
SET t.seconds    = row.seconds,
    t.penalty_s  = row.penalty_s,
    t.search_s   = row.seconds + row.penalty_s
RETURN count(t) AS updated
"""

JOURNEY = """
MATCH (o {id: $origin}), (d {id: $destination})
CALL gds.shortestPath.dijkstra.stream($graph, {
  sourceNode: o, targetNode: d, relationshipWeightProperty: 'search_s'
})
YIELD nodeIds, costs, path
WITH [rel IN relationships(path) | rel] AS legs
RETURN
  // What the traveller experiences: the real durations only.
  reduce(s = 0.0, r IN legs | s + coalesce(r.seconds, 0.0))   AS journey_s,
  // What the search minimised: durations plus dislike.
  reduce(s = 0.0, r IN legs | s + coalesce(r.search_s, r.seconds)) AS search_s,
  size([r IN legs WHERE type(r) = 'TRANSFER'])                AS changes
"""


@dataclass(frozen=True)
class TransferPolicy:
    """Dislike of changing, in seconds, by the kind of change it is.

    These are preferences, not measurements. They are expressed in seconds only
    so the search can add them to durations — a 300-second penalty does not mean
    the change takes five minutes, it means a traveller would spend five extra
    minutes travelling to avoid it.
    """
    base_s: float = 300.0
    same_platform_s: float = 60.0        # step across, minimal risk
    cross_station_s: float = 480.0       # street crossing, unfamiliar entrance
    mode_change_s: float = 240.0         # extra on top of base when the mode changes
    accessibility_s: float = 900.0       # stairs-only interchange, if step-free is required

    def for_transfer(self, *, same_platform: bool, cross_station: bool,
                     mode_changes: bool, step_free: bool) -> float:
        if same_platform:
            penalty = self.same_platform_s
        elif cross_station:
            penalty = self.cross_station_s
        else:
            penalty = self.base_s
        if mode_changes:
            penalty += self.mode_change_s
        if not step_free:
            penalty += self.accessibility_s
        return penalty


async def apply(driver, transfers: list[dict], policy: TransferPolicy) -> int:
    rows = [
        {
            "id": t["id"],
            "seconds": t["seconds"],
            "penalty_s": policy.for_transfer(
                same_platform=t["same_platform"],
                cross_station=t["cross_station"],
                mode_changes=t["from_mode"] != t["to_mode"],
                step_free=t["step_free"],
            ),
        }
        for t in transfers
    ]
    async with driver.session() as session:
        result = await session.run(SET_PENALTIES, rows=rows)
        return int((await result.single())["updated"])

How It Works

Three properties of this arrangement matter.

Two numbers, one unit. The penalty is in seconds because the search adds it to seconds, not because a change takes that long. Keeping them separate means the planner can report “48 minutes, one change” while having searched on 53 minutes of effective cost — and the 48 is a real prediction rather than an artefact of the weighting.

The penalty varies by what kind of change it is. A cross-platform interchange where the connecting train is already waiting is barely a change at all; one that requires leaving a station, crossing a road and finding another entrance is a different experience entirely, and a single flat penalty cannot distinguish them. Deriving the penalty from the transfer’s own attributes — same platform, cross-station, mode change, step-free — is what makes the planner’s preferences match a traveller’s.

Accessibility is a penalty, not a filter, until it is a filter. A stairs-only interchange should be strongly discouraged for a traveller who needs step-free access and merely noted for one who does not. Modelling it as a large penalty handles the first case gracefully; where the requirement is absolute, the transfer should be excluded from the projection entirely, so no search can return it — the same structural argument that makes a banned turn a missing edge.

Common Failure Patterns

1. Folding the penalty into the transfer’s duration. Setting seconds = 240 + 300 makes the search behave correctly and makes every reported journey time wrong by the total penalty. Worse, the error is invisible — the number looks plausible, and only comparing against a timetable reveals it. Keep the duration honest and add a separate search weight.

2. A penalty large enough to dominate the search. Push it to twenty minutes per change and the planner will route a traveller on a single service for two hours rather than change once, which is as unusable as the no-penalty version in the other direction. The useful range is roughly three to eight minutes for an ordinary change; anything above that is expressing a policy rather than a preference and should be documented as one.

3. The same penalty for every traveller. A commuter with a season ticket and no luggage tolerates changes far better than a family with suitcases. Because the penalty lives on the relationship and the search reads one property, supporting profiles means either a property per profile or a projection per profile — both are cheap, and a single average serves nobody well.

# One weight property per profile, computed once.
for profile, policy in PROFILES.items():
    await apply(driver, transfers, policy)   # writes search_s_<profile>

Performance Notes

The penalty costs nothing at search time — it is already summed into search_s, so the search reads one property exactly as it would without it. What it does change is the shape of the search, and usually favourably: penalising transfers makes routes through interchange-heavy areas more expensive, which prunes a part of the graph that would otherwise be explored, so a penalised search frequently settles fewer nodes than an unpenalised one.

$$w_{\text{search}}(e) = t(e) + \pi(e), \qquad \pi(e) = 0 \text{ for every non-transfer edge}$$

Because $\pi$ is non-negative, the weight stays non-negative and Dijkstra remains correct — a penalty implemented as a negative weight on preferred edges instead would break that, and is the tempting form when someone wants to reward a same-platform change rather than penalise the others. Express the preference as a smaller penalty rather than as a negative one.

One consequence to plan for: journeys optimised on search_s are not sorted by journey_s, so a result set returned in search order will occasionally show a slower journey above a faster one. That is correct behaviour and it looks like a bug to anyone reading the list. Returning both numbers, and labelling the ordering, is what makes the output defensible — the same discipline as reporting the detour cost alongside the distance rather than only the one that was optimised.

It is worth being deliberate about how the penalty is calibrated, because the temptation is to pick a number that produces routes someone likes on a handful of examples. The defensible method is to compare against observed behaviour: take journeys where travellers had a genuine choice between a faster route with more changes and a slower one with fewer, and find the penalty at which the planner’s preference matches the one they actually exercised. On a network with ticketing data that is a direct measurement; without it, a survey question phrased as “how much longer would you travel to avoid one change” gets close enough, and is a far better basis than intuition.

Calibration also has to be revisited when the network changes, because the penalty is partly a proxy for risk. An interchange with a reliable ten-minute frequency carries much less risk of a missed connection than the same interchange at a twenty-minute frequency, and a traveller’s dislike of it moves accordingly. Where the schedule is in the graph already, deriving part of the penalty from the headway of the connecting service — rather than treating every change as equally risky — makes the planner noticeably better at off-peak times, which is exactly when a flat penalty is least accurate.

Related

• Multi-Modal and Fleet Routing on a Spatial Graph — the layered graph these transfers connect.
• Time-Dependent Shortest Paths with Schedule Edges — the waiting cost a transfer’s duration sits on top of.
• Modeling Turn Restrictions as an Edge-Based Graph — when a preference should become a missing edge instead.
• Many-to-Many Cost Matrices with Neo4j GDS — building matrices over a graph whose weights include preferences.

This guide is part of Multi-Modal and Fleet Routing on a Spatial Graph, within Network Routing Algorithms in Python.