ADR-014: transit-strategy — Spiess & Florian (1989) optimal-strategy transit assignment

Status: accepted (implemented) Date: 2026-07-09 Deciders: static-extensions track — the last Phase-1 static model (transit) File: docs/design/adr-014-transit-strategy.md

Context

The remaining Phase-1 model, Spiess & Florian (1989, Transportation Research Part B 23(2):83-102, spiess1989optimal), assigns transit demand by optimal strategies: at each stop a passenger designates a set of attractive lines and boards the first-arriving one, minimizing the expected total travel time (in-vehicle time + expected wait). Under random arrivals the wait at a stop whose attractive lines have combined frequency F is 1/F, and the passenger boards line a with probability f_a/F. This is a convex LP (globally optimal), solved in two label-setting/loading passes — not an iterative equilibrium, and uncongested / frequency-based (costs are flow-independent).

It cannot be a road model. The road Network (core/scenario.py) forbids parallel links (unique (init_node, term_node)) and its costs are flow-dependent BPR — but the whole point of the “common lines” problem is several lines serving the same ordered stop pair, and transit costs here do not depend on volume. ADR-010 already rejected “extend core.Scenario with optional fields” for the less invasive DNL case; transit is further still (it cannot even reuse Network read-only for topology, given the parallel-arc requirement).

Decision

  1. A parallel module src/tabench/transit/ (mirroring src/tabench/dnl/), touching no road code, so no static golden hash can move (the Braess hash cf00f411… is re-asserted in tests/test_transit.py). It has its own frozen, content-hashed scenario, its own solver, and its own certifier.

  2. A directed multigraph as the network (transit/network.py, TransitNetwork): arrays tail/head/time/freq, one entry per arc, with parallel arcs allowed. A finite freq is a boardable line (expected wait 1/freq); freq = inf is a deterministic arc (walk / transfer / in-vehicle continuation, no wait). This directly encodes the common-lines problem without the split-node convention. TransitDemand carries (origin, destination, volume) triples (0-based node ids); TransitScenario wraps them with a domain-separated content_hash() ("tabench-transit-scenario-v1;" prefix). The emitted solution is TransitStrategy (arc volumes + per-destination labels

    • per-pair costs) — the transit analogue of FlowState.

  3. Two-pass solver (transit/strategy.py, optimal_strategy, OptimalStrategyModel, name transit-strategy). Per destination: (a) label-setting over arcs in nondecreasing onward cost u[head]+time, adding arc a=(i,j) to node i’s attractive set iff its onward cost is strictly below u_i, updating u_i ← (f_i u_i + f_a(u_j+c_a))/(f_i+f_a), f_i ← f_i+f_a, with the expected wait seeded as the +1 on the FIRST attractive line (u_i ← 1/f_a + (u_j+c_a)); a deterministic arc that beats the current cost closes the node. (b) Loading nodes farthest-first, splitting by frequency share v_a = (f_a/f_i)V_i. It is standalone (its scenario is a TransitScenario, not the road Scenario), so it is NOT in the road MODEL_REGISTRY — the same parallel-module choice the DNL core made.

  4. Certificate (P1) (metrics/transit_gaps.py, TransitEvaluator). The harness recomputes the LP optimum Z* independently from the scenario (as the road certifier recomputes an all-or-nothing bound), and scores the emitted primal cost Z_emitted — recomputed from the emitted arc volumes as sum_a c_a v_a + sum_i w_i — via optimality_gap = (Z_emitted − Z*)/Z* (≥ 0, 0 iff optimal), the transit analogue of the relative gap. The wait is per commodity: it is per-(node, destination), so the harness certifies the PER-DESTINATION arc-volume decomposition (TransitStrategy.dest_arc_volumes; a single-destination scenario may pass the summed volumes) with per-commodity conservation, and at each node uses the LP-minimal feasible wait w_i = max_a v_a/f_a (every out-arc must satisfy f_a w_i >= v_a) — NOT V_i/F_i over a tolerance-thresholded subset, which would let a sub-tolerance sliver on a near-zero-frequency arc dodge its wait and drive the gap negative. With w_i = max_a v_a/f_a the gap is provably ≥ 0, and a non-proportional split is feasible-but-suboptimal (a larger w_i raises the gap) rather than censored. Certification gates on demand feasibility alone (nonnegative, conserving each destination’s demand); the model’s self-reported labels/costs are never trusted. [Both a multi-destination wait-aggregation bug and the near-zero-frequency negative-gap hole were caught by adversarial review and fixed to this per-destination, max-wait form; regression-pinned in tests/test_transit.py.]

  5. Analytic anchors (transit/builtin.py, both recomputed by the closed form in the tests). The classic common-lines example, two parallel lines to the sink:

    • common_lines_scenario: line 0 (f=1/6, t=21), line 1 (f=1/12, t=18) → combined F=1/4, optimal C* = (1 + 1/6·21 + 1/12·18)/(1/4) = 6/(1/4) = 24 min (wait 4 + ride 20), demand split 2:1 (v0 = 2D/3, v1 = D/3);

    • common_lines_unattractive_scenario: line 0 (1/6, 15) alone gives 21 min, line 1 (1/12, 40) has onward cost 40 ≥ 21 so it is excluded — all demand on line 0, C* = 21. Both satisfy the primal-dual identity Z_emitted = Z* exactly.

Alternatives considered

  • Optional field on the road Scenario (the static house pattern used by evans/br-ue/sc-tap/vi-asym/multiclass): rejected — parallel arcs break Network’s unique-link invariant and BPR costs are the wrong model; a transit hash would also have to live in the road hash space. Same reasoning as ADR-010 for DNL, only stronger.

  • Split-node encoding (separate line-nodes per stop, so all arcs are unique): rejected as unnecessary — the multigraph with per-arc (time, freq) models the common-lines problem directly and more legibly; deterministic in-vehicle continuations are just freq = inf arcs.

  • Registering it in the road MODEL_REGISTRY: rejected — TrafficAssignmentModel.solve is typed to the road Scenario and the runner constructs road scenarios; the DNL core set the precedent that a different scenario type gets its own module/solver/certifier, exercised directly (not through the road CLI/runner).

Consequences

The benchmark gains its first transit model and its first uncongested, frequency-based, hyperpath assignment — a genuinely different domain from road UE, with a sound harness-recomputed optimality certificate and hand-derived common-lines anchors. All changes are additive (a new module + new files only), so every road/DNL hash and the 517-test road suite are untouched. Follow-ups: the congested transit extension (De Cea & Fernández 1993, decea1993transit, already tier-2 in-canon), transfer/boarding penalties, and CLI/experiment-matrix integration for the transit scenario type.

Sourcing

Spiess & Florian (1989, Transportation Research Part B 23(2):83-102, spiess1989optimal, DOI 10.1016/0191-2615(89)90034-9, Crossref-verified) is the primary; it was already in the verified reference canon. The two-pass algorithm, the common-lines expected-cost formula, and both analytic anchors are hand-derived here (the expected wait 1/F, the frequency-share split, and the attractiveness threshold c_l < C), checked for internal consistency (Z_emitted = Z*); no number from the paper is reproduced. It must not be confused with Spiess (1990) spiess1990gradient, the OD-adjustment gradient method already shipped as the T2 estimator spiess.