← Past problems · 2014 set

2014 · Problem A — Unloading Commuter Trains

Read the official problem page →

The prompt, restated

A commuter train pulls into a busy urban station. The train has $n$ cars, each of length $d$, and stops along a platform of length $p$. Every car holds roughly $C$ seated and standing passengers, all of whom need to step off, walk along the platform, and climb a staircase of some width $q$ to reach the street. The team is asked: (1) Build a model that estimates the total time from "doors open" to "last passenger reaches the street" for a single train. (2) Extend the model to a second train that arrives on the opposite platform a short time later — passengers from both trains now compete for the same vertical egress capacity. (3) Determine the optimal number, width, and placement of stairways given a budget on total stair footprint. (4) Discuss how robust the recommendation is to assumptions about passenger walking speed, age distribution, luggage, and platform crowding. (5) Provide a one-page non-technical summary that a transit authority manager could hand to the city council.

The structure of the prompt is deliberately operational: the judges want a model that ingests $(n,\,d,\,p,\,q)$ and a few behavioral parameters, then returns a defensible egress time and a clear "build $k$ stairways at positions $x_1,\dots,x_k$" recommendation.

Key modeling idea

Egress is the composition of three serial-but-overlapping flows: door discharge → platform walking → staircase climb. The bottleneck is almost always the staircase, so the right mental model is a network of M/G/1 (or M/G/c) queues fed by deterministic batch arrivals from each car. Throughput is capped by Fruin's stair flow capacity ($\approx 1.0\text{–}1.3$ passengers per metre of stair width per second under crowded conditions); the platform itself only matters when its density crosses the "jam" threshold around 4 ped/m². The optimization reduces to: place stairways so that the maximum walking distance from any door is short and the per-stair queue length stays under the platform's density ceiling.

Suggested approach

• Step 1 — Parameterize the egress chain. Door discharge $\approx 60$ pax/min/door (two doors per car, both used) [illustrative]; free walking speed $\approx 1.34$ m/s with crowding decay following the Greenshields-style density–velocity curve. Stair capacity from Fruin's pedestrian planning handbook (see technique 13).
• Step 2 — Build a 1D agent-based simulation. Discretize the platform into 0.5 m cells; each passenger is an agent with origin (car door), destination (nearest stair), and a desired speed drawn from a truncated normal $\mathcal{N}(1.34, 0.25^2)$ m/s. Pedestrian dynamics via a simplified social-force or Kerner–Klenov cellular model.
• Step 3 — Treat each staircase as an M/G/c queue. Service rate $\mu = w \cdot 1.1$ pax/s where $w$ is stair width in metres. Compute the expected egress time analytically as a sanity check on the simulation (technique 9 for the steady-state queue length).
• Step 4 — Optimize stairway placement. With $k$ stairs and door positions $\{x_j\}$, place stairs to minimize the max walking distance — this is the classical $k$-center problem on a line, solvable in $O(n\log n)$ by binary search on the radius (technique 11).
• Step 5 — Two-train extension. Add a second batch of arrivals offset by the inter-train headway $\Delta t$. Sweep $\Delta t$ from 0 to 300 s; the worst case occurs when both trains' crowds hit the stair queue simultaneously.

Data sources to consider

Common pitfalls

• Modeling discharge as instantaneous. Doors don't dump 200 people in one tick — they discharge at a finite rate that interacts with the platform's density. Use a per-door arrival process, not a single big batch.
• Ignoring counter-flow. On a real platform, some passengers are still boarding or walking the wrong direction. A one-way assumption can shave 20–30% off egress time [illustrative]; state it explicitly.
• Optimizing stair count without a budget. The trivial answer is "infinity stairs". Impose a footprint constraint (e.g., total stair area ≤ 10% of platform area) and optimize the trade-off.
• Treating walking speed as a constant. Above ~2 ped/m² speed drops sharply; below 0.3 ped/m² it's basically free-flow. A piecewise speed–density curve is essential.
• No validation. Sanity-check against published NFPA 130 numbers — a 10-car train with 1,500 passengers and two 3-m stairs should clear the platform in roughly 4 minutes. If your model says 30 seconds or 30 minutes, something is wrong.

Python sketch

1D platform simulation: passengers spawn at door positions, walk toward their nearest staircase under a density-dependent speed law, then queue at the stair.

import numpy as np

PLATFORM_LEN = 200.0          # metres
CAR_LEN      = 20.0           # metres
N_CARS       = 10
PAX_PER_CAR  = 150
DOORS_PER_CAR = 2
DOOR_RATE    = 1.0            # pax/sec/door (Fruin-style)
V_FREE       = 1.34           # m/s
STAIR_RATE   = 1.1            # pax/sec per metre of stair width
STAIR_WIDTH  = 3.0            # metres
STAIR_POS    = [50.0, 150.0]  # candidate stair locations (m)
DT           = 0.5            # sec

def speed(density):           # Greenshields-style v(rho)
    rho_jam = 4.0             # ped/m^2
    return max(0.1, V_FREE * (1.0 - density / rho_jam))

def simulate():
    rng = np.random.default_rng(0)
    doors = [c * CAR_LEN + d * (CAR_LEN / (DOORS_PER_CAR + 1))
             for c in range(N_CARS) for d in range(1, DOORS_PER_CAR + 1)]
    pending = {x: PAX_PER_CAR // DOORS_PER_CAR for x in doors}
    walking = []              # list of (position, target_stair)
    queues  = {s: 0 for s in STAIR_POS}
    t = 0.0
    while pending or walking or any(queues.values()):
        # discharge doors
        for x in list(pending):
            if rng.random() < DOOR_RATE * DT and pending[x] > 0:
                pending[x] -= 1
                target = min(STAIR_POS, key=lambda s: abs(s - x))
                walking.append([x, target])
                if pending[x] == 0: del pending[x]
        # walk
        density = len(walking) / max(PLATFORM_LEN, 1.0)
        v = speed(density)
        new_walking = []
        for pos, tgt in walking:
            step = v * DT * (1 if tgt > pos else -1)
            pos += step
            if abs(pos - tgt) < 0.5:
                queues[tgt] += 1
            else:
                new_walking.append([pos, tgt])
        walking = new_walking
        # stair service
        for s in queues:
            served = min(queues[s], int(STAIR_RATE * STAIR_WIDTH * DT))
            queues[s] -= served
        t += DT
    return t

print(f"egress time = {simulate():.1f} s   # ~ 240 s baseline [illustrative]")

Sensitivity & validation checklist

• Vary stair count $k \in \{1, 2, 3, 4\}$ at fixed total width — diminishing returns should appear past $k=3$.
• Sweep walking-speed distribution mean from 1.0 to 1.5 m/s — egress time should change by ~15% [illustrative], not more.
• Two-train scenario: sweep headway 0–300 s and plot worst-case egress; the curve should be V-shaped with a sharp peak near $\Delta t = 0$.
• Sanity-check against NFPA 130's 4-minute platform clearance for a similarly-sized station.
• Check that doubling stair width $w$ roughly halves the queue length — confirms the M/G/c capacity scaling is implemented correctly.

Related pages

• Techniques — Agent-based simulation
• Techniques — Markov chains & queueing
• Techniques — Optimization ($k$-center)
• Anatomy of a winning paper