← Past problems

2025 · Problem A — Emergency Evacuation Sweeps

The problem in one paragraph

During emergencies (fires, gas leaks), trained responders sweep a building room-by-room to make sure everyone is out. Your team is asked to design a mathematical model that optimizes the sweep strategy in multi-floor buildings — minimizing total clear time while keeping responders and occupants safe. The problem builds from a simple baseline (two firefighters, one floor, three rooms per side of a central hallway) to more complex layouts, then asks you to extend to realistic constraints like smoke, communication delays, and high-risk areas.

Read the official PDF →

The requirements, restated

1. Identify the key elements that inform your model (room "all-clear" criteria, occupant types, responder expertise, redundancy strategy, emergency type, etc.).
2. Build the base model and apply it to the simple two-firefighter, one-floor scenario in Figure 1.
3. Apply your model to at least two more layouts — vary floors, plans, and occupant types. Report the optimal route, the optimal number of responders, and minimum clear time.
4. Extend the model to handle realistic constraints: communication delays, occupant unawareness, time-varying hazards (spreading fire, reduced visibility), dynamic movement, prioritization of high-risk areas, fewer responders than ideal. Discuss the role of sensors / building automation.
5. Write a 1–2 page letter to the Local Emergency Planning Committee with a concrete evacuation-sweep strategy and recommendations.

How to frame the problem

The natural abstraction is a graph: rooms and hallway junctions are nodes; doors, stairwells, and corridor segments are edges. Edge weight = traversal time. Sweeping a room takes additional time $\tau$ that depends on room size and the verification rule (visual sweep, marking, sensor confirmation).

The core question becomes: given $k$ responders with start nodes and a set of room nodes to visit, what's the minimum-makespan assignment of room visits to responders? That's a multi-agent vehicle-routing problem.

A solution outline

Model 1 — base routing

Represent the building as $G = (V, E)$ with $V = R \cup H$ (rooms + hallway nodes). Edge weight $w_{ij}$ = expected travel time at responder walking speed $v$. Each room $r \in R$ has a service time $\tau_r$ (size-dependent).

For $k$ responders starting at nodes $s_1, \dots, s_k$, find tours $T_1, \dots, T_k$ that collectively visit every room exactly once, minimizing the makespan $\max_j |T_j|$ (since the building isn't clear until the last responder finishes).

For small graphs (≤ 30 rooms) this can be solved exactly with a MIP. For larger graphs use a greedy nearest-room assignment plus 2-opt local search, or a savings heuristic.

Model 2 — adding stairs and floors

Stairs are edges connecting floor-graphs. Stair traversal time should be larger than corridor traversal (and elevator usage is forbidden in fire emergencies). Multi-floor layouts can introduce "choke points" — model these with edge capacities if multiple responders converge.

Model 3 — hazards and dynamics

Now the realism extension:

• Spreading fire / smoke. Mark edges as "compromised" after time $t_{ij}^{\text{cut}}$, after which traversal cost spikes (slower movement, visibility loss) or becomes infeasible. Re-route dynamically.
• Communication delay. A responder doesn't learn that a teammate cleared room $r$ until $\delta$ seconds later. Model with a per-responder belief state.
• Occupant dynamics. Occupants leave rooms at random times once aware; aware-of-emergency probability $p(t) = 1 - e^{-\lambda t}$.
• Priority rooms. Childcare, labs get weight $\alpha_r > 1$ in the objective, pulling responders to visit them earlier.

This is where Monte Carlo simulation takes over from analytic optimization: run $N$ simulated emergencies, sample uncertain inputs, report the distribution of total clear time and the probability of "missing" anyone.

Sensitivity analysis

Vary walking speed (±20%), room-check time (±30%), responder count (k = 2, 3, 4), and communication delay (0–5 s). Report clear time and "miss" probability as a function of each. The judges expect you to identify which lever matters most — that becomes the basis of your recommendations.

The letter

To the Local Emergency Planning Committee. Lead with the headline finding (e.g., "Adding a third responder cuts average clear time by 35%, more than any other change"). Then give 3–4 prescriptive recommendations for different building types: open office, school with childcare, warehouse with dispersed staff, hospital with bed-bound patients.

What to cite

• NFPA emergency-evacuation guidelines (response times, building-code requirements)
• Helbing & Molnár (1995), social-force pedestrian model — for occupant dynamics
• OpenStreetMap or facility floor plans for example buildings
• Studies on firefighter movement speeds in smoke (~30–50% reduction)

Common pitfalls

• Treating the model as deterministic — the judges reward stochastic extension.
• Reporting only one scenario instead of the three the problem asks for.
• No actual map / floor plan in the paper — make sure you draw the buildings.
• "Optimal route" reported without saying optimal for whom (single responder vs. multi-responder makespan).
• Forgetting to discuss sensor / IoT augmentation in part 4(b).