Emergency Evacuation Routing
Maximum Flow / Contraflow Network Optimization
During a natural disaster, a city must route the maximum number of people from the danger zone to safety shelters through the road network. Contraflow—reversing inbound lanes—can double evacuation capacity on critical bottleneck corridors.
Where This Decision Fits
Public safety operations chain — the highlighted step is what this page optimizes
The Problem
From city streets to graph theory
A coastal city has 10 neighbourhoods (nodes) connected by a road network. One neighbourhood is the source zone (red, danger area) and 2 neighbourhoods serve as sink nodes (green, safety shelters). Each road arc has a capacity measured in vehicles per hour.
The objective is to find the maximum evacuation flow from the danger zone to the shelters. The Enable Contraflow toggle reverses 2 inbound arcs, effectively doubling their outbound capacity by converting all lanes to the evacuation direction. This maps directly to the Maximum Flow problem on a directed graph.
| Evacuation Domain | Max-Flow Model | |
|---|---|---|
| Danger zone | Source node s | |
| Safety shelter | Sink node t | |
| Road segment | Directed arc (u,v) | |
| Vehicles/hour capacity | Arc capacity c(u,v) | |
| Contraflow reversal | Reverse arc direction | |
| Evacuee flow | Flow f(u,v) |
Mathematical Formulation
Maximum Flow with optional contraflow arcs
Subject To capacity: 0 ≤ f(u,v) ≤ c(u,v) ∀ (u,v) ∈ E // flow ≤ road capacity
conservation: Σ(u,v)∈E f(u,v) = Σ(v,w)∈E f(v,w) ∀ v ≠ s,t // no accumulation at intersections
contraflow: if ye = 1 ⇒ reverse arc (v,u) → (u,v) with c′(u,v) = c(u,v) + c(v,u) // lane reversal doubles capacity
Interactive Solver
Choose a scenario, toggle contraflow, and watch the evacuation flow
Evacuation Flow Solver
Coastal neighbourhood must evacuate through a single bridge bottleneck to reach two inland shelters.
| Algorithm | Max Flow (veh/hr) | Bottleneck Arc | Contraflow Gain | Time |
|---|---|---|---|---|
| Press Solve to run all algorithms | ||||
Solution Algorithms
Three approaches to maximizing evacuation throughput
Edmonds-Karp (Max-Flow)
The Edmonds-Karp algorithm uses breadth-first search (BFS) to find augmenting paths from the danger zone to shelter nodes. By always selecting the shortest augmenting path, it guarantees a polynomial bound of O(VE²).
Each BFS traversal finds a road route with remaining capacity, pushing as many vehicles through as the bottleneck road allows. The algorithm terminates when no more augmenting paths exist, yielding the maximum evacuation flow.
Max-Flow + Contraflow
This variant first reverses selected inbound arcs (converting all lanes to the evacuation direction), then runs Edmonds-Karp on the modified network. Contraflow is standard practice in hurricane evacuations along coastal highways.
By reversing 2 critical inbound corridors, the effective capacity on those roads doubles, often breaking the bottleneck that limits overall throughput. The cost is that reversed roads can no longer carry inbound traffic.
Greedy Shortest Path (Naive)
A simple baseline that repeatedly finds the shortest path (by hop count) from source to any sink and pushes the bottleneck capacity along it. Unlike Edmonds-Karp, it does not use the residual graph, so it cannot cancel previously routed flow to find better global solutions.
This greedy approach typically achieves 70–90% of optimal flow but can get stuck in suboptimal routing patterns, illustrating why proper max-flow algorithms matter for life-safety applications.
Complexity & Practical Notes
- Edmonds-Karp: O(VE²) — polynomial, finds true maximum flow via BFS augmenting paths
- Contraflow variant: same complexity on modified graph; decision of which arcs to reverse is itself an optimization problem (NP-hard in general, but heuristics work well for 2–5 arcs)
- Greedy shortest path: fast but suboptimal; no residual graph means no flow cancellation
- Max-Flow Min-Cut Theorem: the maximum evacuation flow equals the minimum cut capacity separating the danger zone from shelters (Ford & Fulkerson, 1956)
- Practical note: real evacuation models incorporate time-expanded networks, dynamic demand, and stochastic road degradation; the static max-flow gives an upper bound on steady-state throughput
References
Key literature on network flow and evacuation modeling