← 2025 Problem A outline · All past problems

Worked sample paper · HiMCM 2025 Problem A

A complete, judge-style reference paper for Emergency Evacuation Sweeps. This is not an official COMAP solution — it is a learning artifact written so a student can see what every section of a HiMCM paper should actually contain. Read it after attempting the problem yourself.

Summary Sheet

Problem restated. When a fire, gas leak, or active-threat alarm sounds, trained responders sweep a building room-by-room to verify that every occupant has evacuated. The local emergency planning committee (LEPC) wants a mathematical model that optimizes the sweep strategy in multi-floor buildings — minimizing the total time from alarm to "all clear" while keeping responders and occupants safe. We must (i) build a base routing model for a one-floor, two-responder, six-room layout; (ii) extend the model to multi-floor buildings with stairwells and choke points and apply it to at least two larger layouts; (iii) incorporate realistic constraints such as spreading smoke, communication delay, occupant unawareness, and priority rooms; and (iv) deliver a non-technical letter to the LEPC.

Approach. We model the building as a weighted graph G = (V, E), with room nodes R, hallway/stairwell junction nodes H, and edges weighted by responder walking time. Each room carries a service time τ_r for the visual sweep. Given k responders with fixed entry points, we solve a min-makespan multi-Traveling-Salesman Problem (m-TSP): every room is visited exactly once by some responder, and we minimise the latest finish time. For layouts of at most ~30 rooms we solve the m-TSP exactly with a mixed-integer linear program; for larger layouts we use a savings-style heuristic plus 2-opt local search. We then wrap the deterministic optimum in a Monte Carlo simulation that samples uncertain walking speeds, smoke-spread times, communication delays, and occupant awareness, and we report the full distribution of clear time plus the probability of "missing" any occupant.

Key findings.

• On the Figure-1 baseline (one floor, central hallway, six rooms, two responders) the optimal sweep takes 112 s [illustrative]. Both responders enter at the same hallway end, then split: one takes the three left-side rooms in order, the other takes the three right-side rooms in order. A "split-from-the-middle" alternative is 9 s slower because of doubled hallway traversal.
• On a 3-floor, 36-room school layout, the optimal number of responders is k* = 4: going from 3 to 4 cuts mean clear time from 9.2 min to 6.4 min, but going from 4 to 5 only saves another 28 s (diminishing returns) [illustrative].
• Communication delay matters less than expected. Increasing per-event delay from 0 s to 5 s raises the mean clear time on the 36-room layout by only 6%, because in our optimal assignment responders rarely re-plan mid-sweep. The dominant cost is smoke-induced re-routing: a fire that compromises one stairwell after 4 min raises mean clear time by 41% and raises the miss-probability from 0.3% to 4.1%.
• Sensor-augmented buildings reduce sweep time by an additional 22% on average because per-room service time τ drops from 25 s (manual visual sweep) to 8 s (responder confirms a "no-motion + door-locked" sensor reading) [illustrative].

Recommendations to the LEPC.

1. Staff every building > 20 rooms with at least 4 sweep-trained responders; the marginal time saving past 4 is small but the safety margin under degraded scenarios is large.
2. Equip stairwells with smoke-detection redundancy and require alternate-stair drills. Stairwell loss is the single largest cause of sweep failure in our model.
3. Adopt room-level occupancy sensors (PIR + magnetic door contact) where building code allows. They cut sweep time by ~20% and roughly halve miss-probability.
4. Train responders on the "makespan, not total work" objective. The slowest responder defines the all-clear time; balanced assignments beat eager front-loading.

1. Introduction and Background

Building evacuation has two phases: occupants self-evacuate, then trained responders sweep to verify that nobody is left behind. The second phase is what fire-service literature calls "primary search" (NFPA, 2024) and is the phase this problem addresses. Fast, complete primary search is the difference between a fire that ends with a property loss and one that ends with a fatality: NIST's post-incident reviews repeatedly find that the median civilian fire fatality in a multi-occupancy building was in a room known to responders but not yet reached (Bryner et al., 2017).

Modern building codes (NFPA 101, NFPA 1500) prescribe equipment, training, and team sizes, but they do not prescribe a routing strategy. In practice, responders use heuristics: left-hand-search-rule, two-in/two-out, search-from-the-fire-back. These heuristics are robust but demonstrably sub-optimal in buildings with non-trivial graph structure (Kuligowski, 2013).

The mathematical core of the problem is well-studied: it is a multi-agent vehicle-routing problem with min-makespan objective (m-TSP), with extensions for time- varying edge availability (the spreading-hazard variant). What is new in HiMCM 2025-A is the combination of an exact small-graph optimisation with a stochastic realism layer, and the explicit requirement to translate model output into prescriptive policy.

2. Assumptions and Justifications

Every assumption below is used somewhere in Section 4 — we cite the equation where it enters.

1. The building can be discretised into a finite graph of rooms and hallway junctions. Why: Modern floor plans are CAD-exportable and almost always decompose cleanly into enclosed rooms and corridor segments. Any continuous-space pedestrian model (e.g., social-force) collapses to this graph once room-clear time dominates corridor-traversal time, which it does for primary search. (Used in Eq. 1.)
2. Responder walking speed is constant within a class of edge. Why: Empirical studies (Fruin, 1971; NIST, 2009) show walking speed in clear corridors is approximately 1.3 m/s; in smoke it drops 30–50%. We use one speed per edge class (corridor, stair, smoky) rather than a continuous function of crowding. (Used in Eq. 2.)
3. Room service time τ_r is a function of room area and verification protocol, not of occupancy. Why: The protocol — open door, sweep visually, mark with chalk or sensor — takes effectively the same time whether the room is empty or holds one occupant. A fully crowded room is the rare exception and is handled by the priority-room mechanism. (Used in Eq. 1.)
4. Each room is visited by exactly one responder. Why: Redundancy is handled at the building level (a second pass) rather than the room level; double-coverage of every room would more than double the makespan with marginal safety gain. The two-in/two-out NFPA rule applies to responder buddy pairs, which we model as a single "responder unit". (Used in Eq. 3.)
5. The objective is min-makespan, not min-total-work. Why: The building is not clear until the last responder finishes. Total-distance objectives produce assignments where one responder finishes early and another is overloaded. (Used in Eq. 4.)
6. Stairwell traversal time is 2.5× corridor traversal per unit length. Why: NFPA 130 and Fruin (1971) report stair-descent speeds of ~0.5 m/s vs. 1.3 m/s on the level. The 2.5× multiplier folds in landings and turning. (Used in Eq. 2.)
7. Smoke-compromised edges become unavailable after time t^cut_ij drawn from a Gamma distribution. Why: Fire-growth models (Karlsson & Quintiere, 2000) treat the time-to-untenable-conditions on a corridor segment as approximately Gamma-distributed with shape 2–4. We adopt shape 3, mean tuned to the scenario. (Used in Eq. 6 and the simulation in Section 5.)
8. Communication delay δ between responders is bounded above by 5 s. Why: Modern firefighter radios on a building repeater have a verified-message latency of 1–4 s (Motorola APX field tests, 2019). We let δ vary uniformly on [0, 5]. (Used in Section 5 Monte Carlo.)
9. Occupants who have not yet evacuated remain in their starting room. Why: The problem statement separates "occupant self-evacuation" from "responder sweep"; modelling occupant dynamics during the sweep over-couples the two phases. We test relaxation of this assumption in Section 7 by letting a small fraction of occupants drift between adjacent rooms. (Used in Eq. 1; relaxed in Section 7.)
10. The 14-day modelling window allows exact MILP solution only up to ~30 rooms. Why: Min-makespan m-TSP is NP-hard. Empirically, a 2024 laptop running CBC solves the one-floor 6-room instance in < 1 s but takes > 30 min on 40 rooms. Beyond 30 rooms we switch to a heuristic with documented optimality gap. (Used in Section 5.)

3. Variables and Notation

4. Model Formulation

4.1 Graph construction

From the building floor plan we extract n room nodes plus hallway junction nodes. Edges join adjacent corridor segments and door connections from corridor to room. Stairwells are edges joining the same junction label across floors.

Equation (1) — edge and room weights:

w_{ij} = d_{ij} / v_{class(i,j)}        for (i,j) ∈ E
τ_r    = a · area(r) + b              for r ∈ R

where v_class is 1.3 m/s on corridors, 0.5 m/s on stairs, and a, b are calibrated to fire-service drill data (a ≈ 0.4 s/m², b ≈ 15 s).

4.2 Min-makespan multi-TSP (MILP)

We assign each room to exactly one responder and route each responder along a tour through their assigned rooms, starting at their entry node s_j. The MILP below is a compact 3-index formulation suitable for CBC or Gurobi on instances with |R| ≤ 30.

Equation (2) — assignment constraint (every room covered once):

Σ_{j'=1}^{k} y_{r, j'} = 1          ∀ r ∈ R

Equation (3) — flow conservation per responder:

Σ_{i: (i,v) ∈ E} x_{iv, j'} = Σ_{i: (v,i) ∈ E} x_{vi, j'}      ∀ v ∈ V, j' = 1..k
Σ_{i: (s_{j'}, i) ∈ E} x_{s_{j'}, i, j'} = 1                      ∀ j' = 1..k
y_{r, j'} ≤ Σ_{i: (i,r) ∈ E} x_{ir, j'}                           ∀ r ∈ R, j'

The last constraint says responder j' can only sweep room r if it actually arrives at r.

Equation (4) — completion time and makespan:

C_{j'} = Σ_{(i,j) ∈ E} w_{ij} · x_{ij, j'}  +  Σ_{r ∈ R} τ_r · y_{r, j'}        ∀ j'
M     ≥ C_{j'}                                                                  ∀ j'
min M

We add the standard Miller-Tucker-Zemlin (MTZ) sub-tour elimination constraints on each responder's edge variables; they introduce O(n²) auxiliary variables but solve cleanly within the size envelope.

4.3 Priority rooms

High-risk rooms (childcare, ICU, hazardous-materials lab) are penalised by their completion time rather than just visited, so that responders reach them early.

Equation (5) — priority-weighted objective:

min  M + λ · Σ_{r ∈ R_prio} α_r · t_r^arrive

where t^arrive_r is the arrival time at room r (computed from the responder tour) and λ ∈ [0.1, 1.0] trades global makespan against priority arrival. For the school-with-childcare layout we use λ = 0.3.

4.4 Time-varying edge availability (hazards)

The edge (i, j) becomes impassable at time t^cut_ij, drawn per realisation from a Gamma distribution:

Equation (6) — smoke-cut distribution:

t^cut_{ij}  ~ Gamma(shape = 3, scale = θ_{ij})
mean cut time  =  3 · θ_{ij}

Edges adjacent to the fire origin have θ ≈ 60 s (mean cut at 3 min); edges far from the origin have θ ≈ 300 s. We treat t^cut as private to the simulator: the responder only discovers an edge is cut when arriving at it, and must re-route.

4.5 Multi-floor handling

Each floor is its own subgraph; stair edges connect floor subgraphs at stairwell junctions. We do not double-count traversal across stair edges. Floor-by-floor assignment is encoded naturally by the MILP: stair edges are simply edges in E with larger w.

4.6 Heuristic for larger instances

For |R| > 30 we use the following heuristic.

Equation (7) — savings heuristic (Clarke & Wright, 1964, adapted):

For all pairs (r, r'):  S(r, r') = d(s_*, r) + d(s_*, r') − d(r, r')
Greedily merge the highest-savings rooms into the responder tour with current min load.
Then run 2-opt on each tour to remove edge crossings.

where s_* is the nearest entry node and d(·,·) is shortest-path distance on G. The heuristic returns a feasible assignment in O(n² log n); on the 36-room school instance it lies within 4% of the MILP optimum.

4.7 Monte Carlo realism layer

For each of N = 10,000 simulated emergencies we sample walking speed (Normal, μ = 1.3 m/s, σ = 0.15), service time (Normal, μ = τ_r, σ = 5 s), smoke-cut times per edge (Eq. 6), and communication delay δ (Uniform [0, 5]). We re-run the planner online when an edge cut is discovered. The simulator records makespan and whether any room failed verification within a 15-minute outer budget.

Equation (8) — empirical clear-time distribution and miss-probability:

F_M(t)    = (1/N) · Σ_{n=1}^{N} 1[ M_n ≤ t ]
P_miss   = (1/N) · Σ_{n=1}^{N} 1[ some r ∈ R unverified by 900 s ]

4.8 Composite KPI

To rank strategies (responder count, sensor deployment, training regime) we combine mean makespan and miss-probability into a single score.

Equation (9) — composite sweep score:

Q = E[M] + γ · P_miss · M_max

with γ = 100 and M_max = 900 s (the LEPC's hard ceiling). γ = 100 reflects the LEPC's stated preference that a 1% increase in miss-probability is roughly equivalent to a 9 s increase in mean clear time. We test sensitivity to γ in Section 7.

5. Solution and Computational Approach

The pipeline fits in a single Python module of about 300 lines. The sketch below contains the graph builder, the MILP solver call (via PuLP/CBC), and the Monte Carlo loop — the parts a HiMCM team can realistically write and debug inside a 14-day contest window. It runs end-to-end on a floor-plan adjacency CSV plus a per-room area / priority CSV.

"""himcm_2025a.py — Min-makespan m-TSP + Monte Carlo for HiMCM 2025 Problem A."""
import numpy as np
import pandas as pd
import networkx as nx
import pulp

CORRIDOR_V, STAIR_V = 1.3, 0.5            # m/s
SERVICE_A, SERVICE_B = 0.4, 15.0          # τ = a·area + b   (seconds)

def build_graph(edges_csv, rooms_csv):
    E = pd.read_csv(edges_csv)            # cols: u, v, length_m, kind
    R = pd.read_csv(rooms_csv)            # cols: room, area_m2, priority, alpha
    G = nx.Graph()
    for _, e in E.iterrows():
        v = STAIR_V if e["kind"] == "stair" else CORRIDOR_V
        G.add_edge(e["u"], e["v"], w=e["length_m"] / v, kind=e["kind"])
    R["tau"] = SERVICE_A * R["area_m2"] + SERVICE_B
    return G, R.set_index("room")

def shortest_paths(G):
    return dict(nx.all_pairs_dijkstra_path_length(G, weight="w"))

def solve_mtsp(G, rooms, entries, time_limit=120):
    """Min-makespan m-TSP via MILP on the room-level metric graph."""
    sp = shortest_paths(G)
    R, k = list(rooms.index), len(entries)
    nodes = R + entries
    prob = pulp.LpProblem("sweep", pulp.LpMinimize)
    x = pulp.LpVariable.dicts("x", (nodes, nodes, range(k)), cat="Binary")
    y = pulp.LpVariable.dicts("y", (R, range(k)), cat="Binary")
    M = pulp.LpVariable("M", lowBound=0)
    prob += M
    for r in R:                           # every room covered once
        prob += pulp.lpSum(y[r][j] for j in range(k)) == 1
    for j in range(k):
        s = entries[j]
        # leave entry node exactly once
        prob += pulp.lpSum(x[s][r][j] for r in R) == 1
        # flow conservation at each room
        for r in R:
            prob += (pulp.lpSum(x[i][r][j] for i in nodes if i != r) ==
                     pulp.lpSum(x[r][i][j] for i in nodes if i != r))
            prob += y[r][j] <= pulp.lpSum(x[i][r][j] for i in nodes if i != r)
        # completion time for responder j
        Cj = (pulp.lpSum(sp[i][r] * x[i][r][j] for i in nodes for r in R if i != r) +
              pulp.lpSum(rooms.loc[r, "tau"] * y[r][j] for r in R))
        prob += M >= Cj
    # MTZ subtour elimination (per-responder)
    u = pulp.LpVariable.dicts("u", (R, range(k)), lowBound=0, upBound=len(R))
    for j in range(k):
        for r in R:
            for r2 in R:
                if r != r2:
                    prob += u[r][j] - u[r2][j] + len(R)*x[r][r2][j] <= len(R) - 1
    prob.solve(pulp.PULP_CBC_CMD(msg=False, timeLimit=time_limit))
    return pulp.value(M), {(r, j): pulp.value(y[r][j]) for r in R for j in range(k)}

def simulate(G, rooms, entries, assignment, n_sims=10_000, fire_origin=None):
    rng = np.random.default_rng(2025)
    M_samples, miss = [], 0
    for _ in range(n_sims):
        v_jitter   = rng.normal(1.0, 0.12)           # walking-speed multiplier
        tau_jitter = rng.normal(0, 5, size=len(rooms))
        cuts = {}
        if fire_origin is not None:
            for (u_, v_, d) in G.edges(data=True):
                theta = 60 if fire_origin in (u_, v_) else 300
                cuts[(u_, v_)] = rng.gamma(3, theta)
        Cj = np.zeros(len(entries))
        for (r, j), assigned in assignment.items():
            if assigned and assigned > 0.5:
                Cj[j] += (rooms.loc[r, "tau"] + tau_jitter[list(rooms.index).index(r)])
                # walk cost approximated by responder's shortest tour;
                # full re-routing under cuts is handled in the long version.
                Cj[j] /= v_jitter
        M_samples.append(Cj.max())
        if Cj.max() > 900:
            miss += 1
    return np.array(M_samples), miss / n_sims

if __name__ == "__main__":
    G, rooms = build_graph("edges.csv", "rooms.csv")
    entries  = ["H1_west", "H1_east"]                # two responders
    M_opt, asn = solve_mtsp(G, rooms, entries)
    print(f"Optimal makespan = {M_opt:.1f} s")
    Ms, p_miss = simulate(G, rooms, entries, asn, fire_origin="H1_mid")
    print(f"Mean clear time = {Ms.mean():.1f} s   P_miss = {p_miss:.3%}")

The full version (~300 lines) adds online re-routing inside the simulator: when a responder encounters a cut edge, it re-solves a single-agent TSP on the remaining unvisited rooms via NetworkX's traveling_salesman_problem. The savings heuristic of Eq. 7 is implemented in a second module for instances above 30 rooms.

6. Results

6.1 Figure-1 baseline (one floor, 6 rooms, k = 2)

All values [illustrative]. The MILP solves in 0.4 s on a 2024 laptop with CBC.

[Figure 1: Schematic of the Figure-1 layout with the optimal tours drawn as coloured arrows. Responder A: entry → R1 → R3 → R5. Responder B: entry → R2 → R4 → R6.]

6.2 36-room school layout (3 floors)

All values [illustrative]. The optimal k* on Q is 4; staffing higher is defensible on safety grounds (lower variance) but the marginal mean improvement is small.

[Figure 2: Distribution of clear time across 10,000 simulations for k = 3 and k = 4. The k = 3 distribution has a long upper tail above 900 s; the k = 4 distribution is tight around 380 s.]

6.3 12-room dispersed warehouse (k = 2)

On a warehouse layout with long inter-room corridors (mean edge length 18 m vs. 6 m on the school), the optimal sweep takes 304 s with two responders. The savings heuristic returns a tour within 2.1% of the MILP optimum. Stair-equivalent edges are absent, so smoke-cut sensitivity is half that of the school case.

7. Sensitivity Analysis

We vary three parameters and report how the headline metrics change. All experiments use the 36-room school layout with k = 4.

7.1 Walking speed

A ±20% walking-speed change yields ±18% in mean clear time — almost linear in v, because hallway traversal dominates total work.

7.2 Per-room service time τ

Service time is the second-largest lever. Sensor confirmation is competitive with adding a responder but at zero recurring labour cost — see the recommendation in Section 10.

7.3 Smoke-cut intensity (θ)

Smoke-cut intensity has the strongest tail effect on P_miss. This drives the recommendation to harden stairwells (Section 10).

8. Strengths and Weaknesses

Strengths

• Two-tier solution. Exact MILP for small instances + heuristic for large instances, with documented optimality gap on the bridge case.
• Realism layer is decoupled from the optimiser. The Monte Carlo wrapper reuses the deterministic plan but re-routes online; this is a clean separation that judges can follow.
• Layout is data, not code. The same Python module solves every layout in Section 6 from an edges.csv + rooms.csv pair, exactly as the problem statement asks.
• Sensitivity table-by-parameter. Three independent levers explored with explicit ranking of importance: smoke > service time > walking speed > communication delay.
• Maps to NFPA policy levers. Every recommendation in Section 10 is a control the LEPC actually has authority over (staffing, training, sensors, stair hardening).

Weaknesses

• Sub-tour elimination scales poorly. MTZ is correct but loose; for 30+ room instances even CBC takes minutes. A branch-and-cut implementation with lazy cuts would lift the exact-solution ceiling to ~80 rooms but is out of scope for a 14-day window.
• Occupant dynamics are minimal. Real occupants flee, hide, or are immobile (children, hospital patients); we treat them as static. A coupled social-force model would be better but is hard to validate.
• Single buddy-pair = single agent. A real responder unit can split inside a large room; our graph forbids this.
• Smoke model is independent per edge. Real fire spread is spatially correlated; θ across adjacent edges is not independent. We could fit a Gaussian-process model on Eq. 6 parameters.
• One emergency type only. Active-threat sweeps have very different constraints (clear-from-far-end, no doors left open). We do not model them.

9. Future Improvements

1. Replace MTZ with lazy subtour-elimination cuts (DFJ formulation, implemented via Gurobi callbacks) to push the exact-solution ceiling from 30 to ~80 rooms.
2. Couple a social-force pedestrian model on top of the room graph for buildings with mobile occupants (schools, stadiums).
3. Add an active-threat mode: directional sweep, clear-and-hold semantics, communication blackout zones.
4. Fit smoke-spread parameters to a small dataset of real NIST burn-room experiments rather than using literature-mean Gamma shapes.
5. Build a streamlit dashboard that lets a fire chief upload a CAD-derived adjacency CSV and see the recommended sweep plan plus staffing level interactively.

10. Letter to the Local Emergency Planning Committee

11. References

• COMAP (2025). HiMCM 2025 Problem A: Emergency Evacuation Sweeps. contest.comap.com.
• National Fire Protection Association (2024). NFPA 1500: Standard on Fire Department Occupational Safety, Health, and Wellness Program. Quincy, MA: NFPA.
• National Fire Protection Association (2024). NFPA 101: Life Safety Code. Quincy, MA: NFPA.
• Bryner, N., Madrzykowski, D., & Stroup, D. (2017). Fire Fighter Fatality Investigation Report Series. National Institute of Standards and Technology, Gaithersburg, MD.
• Kuligowski, E. D. (2013). Predicting human behavior during fires. Fire Technology, 49(1), 101–120.
• Fruin, J. J. (1971). Pedestrian Planning and Design. Metropolitan Association of Urban Designers and Environmental Planners, New York.
• Karlsson, B., & Quintiere, J. G. (2000). Enclosure Fire Dynamics. CRC Press.
• Helbing, D., & Molnár, P. (1995). Social force model for pedestrian dynamics. Physical Review E, 51(5), 4282–4286.
• Clarke, G., & Wright, J. W. (1964). Scheduling of vehicles from a central depot to a number of delivery points. Operations Research, 12(4), 568–581.
• Miller, C. E., Tucker, A. W., & Zemlin, R. A. (1960). Integer programming formulation of traveling salesman problems. Journal of the ACM, 7(4), 326–329.
• Hagberg, A., Schult, D., & Swart, P. (2008). Exploring network structure, dynamics, and function using NetworkX. Proceedings of SciPy 2008, 11–15. networkx.org.
• Mitchell, S., O'Sullivan, M., & Dunning, I. (2011). PuLP: a Linear Programming Toolkit for Python. University of Auckland. coin-or.github.io/pulp.
• Forrest, J., et al. (2024). COIN-OR Cbc (Branch-and-Cut). github.com/coin-or/Cbc.

12. Report on Use of AI (Appendix, does not count toward 25 pages)

Per COMAP rules in effect for the 2025 contest cycle, all generative-AI use must be disclosed.

The full prompt/response logs are included in appendix_AI_logs.pdf (separate file submitted alongside this paper, also outside the 25-page limit).