Evacuation Routing
Max-flow · shortest path · time-expanded networks
A hurricane is making landfall in 18 hours; a wildfire is closing a canyon; a chemical-plant release is moving downwind. The operational question: how fast can we move the endangered population to safety through the available road network? The classical framework is Ford & Fulkerson's 1962 max-flow on a time-expanded network — one copy of the road graph per time step, with capacities on arcs and intermediate vertices (Hamacher & Tjandra, 2002). The literature extends to dynamic, stochastic, and contraflow variants.
Problem context
Max-flow meets the clock
The quickest-flow problem asks: what is the minimum time T such that all evacuees can reach safe zones if arcs are traversed at their given capacities? On a static network this is ill-defined (flow has to respect time); the trick is to build a time-expanded network with one copy of each vertex for each time step, and arcs connecting (v, t) to (u, t+τ) where τ is the travel time on (v, u). Max-flow on this time-expanded network gives the maximum total evacuation throughput by time T; binary search over T finds the quickest flow.
Key contributions include Ford & Fulkerson (1962)'s original dynamic-flow treatment, Burkard, Dlaska & Klinz (1993) on quickest flow, Hamacher & Tjandra (2002)'s canonical earliest-arrival and quickest-transshipment formulations, and Cova & Johnson (2003)'s adaptation to road-network evacuation with intersection capacity. For major-metro evacuation planning (hurricanes, wildfires, nuclear-plant exclusion zones), these tools provide lower-bound feasibility analysis but real operations rely on traffic simulation (Chiu et al. 2007; FEMA planning guidance).
Multi-stakeholder framing
Mathematical formulation
Max-flow on time-expanded network; contraflow extension
| Symbol | Definition | Domain |
|---|---|---|
| G = (V, E) | Road network | directed |
| ce | Capacity of arc e (vehicles/period) | ℝ⁺ |
| τe | Travel time on arc e | ℝ⁺ |
| S ⊆ V | Threat (source) zones; dv evacuees at v | |
| T ⊆ V | Safe (sink) zones (shelters); kv capacity | |
| Tmax | Evacuation deadline (time horizon) | ℕ |
| fe(t) | Flow on arc e starting at time t | ℝ⁺₀ |
arcs ((v, t), (u, t+τe)) for each e = (v, u), capacity ce;
hold-over arcs ((v, t), (v, t+1)) if waiting allowed.
Super-source connects to (s, 0) for each s ∈ S with capacity ds.
Super-sink receives from (t, *) for each t ∈ T with capacity kt.
max total flow from super-source to super-sink // evacuees delivered by T
s.t. flow conservation at every intermediate (v, t)
fe(t) ≤ ce ∀ e, t // capacity
// Quickest flow: binary search on T_max for minimum T such that all d_s are served.
Contraflow extension For each undirected corridor, binary decision to reverse one direction's capacity.
Solution is MILP; often used in hurricane evacuation (Kim, Shekhar & Min 2008).
Complexity Max-flow on time-expanded graph is polynomial in |GT|, but GT has |V| × Tmax vertices — a factor Tmax blow-up.
Ford-Fulkerson O(|E| · max-flow); Dinic's O(V2E); practical for |V| × T up to ~106.
Interactive solver
Max-flow from threat zone to shelters
Evacuation Max-Flow Solver
Solution interpretation
Capacity, bottlenecks, min-cut
Max-flow value is the maximum evacuees/period who can reach safety through the current network. Adding shelters or widening corridors raises this; closing a corridor lowers it.
Min-cut (by max-flow min-cut duality) identifies the set of arcs whose removal disconnects source from sink and whose total capacity equals max-flow. These are the bottlenecks: the highest-leverage arcs for contraflow reversal or capacity augmentation.
Time-expanded extension: once the static max-flow is saturated, a dynamic formulation reveals whether the capacity is reachable in the available evacuation window. If not, the planner is looking at a quickest-flow answer rather than a static one.
Limitations & Critique
What the network-flow model does not see
Household compliance is stochastic
Models assume everyone evacuates when ordered. In practice, compliance is 50-80% (Baker 1991); the people who don't evacuate are disproportionately low-income, elderly, or distrustful of authorities. Static capacity models overstate actual evacuation volume.
Transit-dependent populations
Max-flow on a road network assumes evacuees have vehicles. Hurricane Katrina (2005) demonstrated catastrophic consequences when planning ignored carless households — primarily low-income, elderly, and disabled residents. Modern frameworks explicitly plan bus-based pickups.
Special-needs evacuation
Nursing homes, hospitals, dialysis patients, and disabled residents require medical transport and specialised shelter. These are often the binding constraint on evacuation timing; they do not fit into the generic vehicle-flow model.
Traffic dynamics ≠ static capacity
Real road capacity degrades at high utilisation (queueing, accidents). Static max-flow assumes throughput = capacity, which breaks down exactly when evacuation needs it most. Traffic simulation (DynusT, DYNASMART) is used for operational planning; OR max-flow gives feasibility bounds.
Geographic shelter inequity
Shelter locations and capacities are typically fixed inheritances; low-income neighbourhoods often have fewer nearby shelters. Optimisation over a given network doesn't fix the underlying siting inequity.
Meteorological uncertainty
Hurricane tracks shift; wildfire fronts jump; chemical plumes depend on wind. Static evacuation plans assume known threat geography; real decisions are under forecast uncertainty with short lead times. Robust / stochastic evacuation planning is an active area.
Extensions & variants
Time, uncertainty, and contraflow
Time-expanded max-flow
Full dynamic formulation over Tmax time steps; Hamacher-Tjandra 2002.
Contraflow
Reverse capacity of oppose-direction lanes during evacuation. MILP formulation; Kim-Shekhar-Min 2008.
Stochastic flow under scenario uncertainty
Hurricane-track scenarios; robust / two-stage stochastic formulations. Yao et al. 2009.
Multi-modal evacuation
Cars + buses + special-needs vans; each with distinct capacity and origin.
Phased / staged evacuation
Evacuate highest-risk zones first to spread demand over time; Liu-Lai-Chang 2006.
Shelter-assignment joint design
Joint shelter siting + evacuee assignment; location-allocation MILP.
Pedestrian evacuation
Building / stadium egress; micro-scale flow models with density-velocity relationships.
Simulation-optimisation hybrids
OR bounds + traffic simulation for operational plans. Common in major-metro planning.
Key references
Cited above
Related applications
Network-flow & humanitarian siblings