# Disaster Routing — Priority-Aware VRP for Emergency Relief
A Python simulation of a **Vehicle Routing Problem (VRP)** tailored for disaster response scenarios. The system routes multiple relief vehicles across a road/network graph to deliver aid to affected nodes, prioritising high-urgency locations first while minimising travel cost, unreliable edges, and vehicle idle capacity.
---
## What It Does
In disaster scenarios, not all affected areas are equally urgent and not all roads are equally reliable. This project models the problem as a weighted graph VRP where:
- **Nodes** represent locations (depot + affected sites), each with a demand and a priority level.
- **Edges** represent routes between locations with a travel cost and a reliability score (e.g., a damaged road might have low reliability).
- **Vehicles** depart from a depot with limited capacity and must serve as many nodes as possible, prioritising the most critical ones.
The solver minimises a composite objective:
Objective = α · Σ(priority\_i × arrival\_time\_i)
  + β · Σ(1 − reliability of each edge used)
  + γ · Σ(idle capacity per vehicle)
---
## Project Structure
DisasterRouting/
├── graph.py # Undirected weighted graph + Dijkstra SSSP
├── vrp.py # Priority-aware VRP solver + 2-opt local search + evaluation
├── sim.py # Simulation runner (small demo, random demo, scalability test)
├── dp\_exact.py # Exact Dynamic Programming solver (small instances)
├── ga\_vrp.py # Genetic Algorithm solver (alternative heuristic)
├── visualize.py # Route visualisation using Folium (interactive maps)
├── test\_small.py # Unit/integration tests
├── sample.json # Sample graph input
└── requirements.txt # Python dependencies
---
## Algorithms
### Core Solver — vrp.py
**Priority-Aware Greedy VRP** with 2-opt local search:
1. Sorts all customer nodes by priority (descending), then demand.
2. For each node, assigns it to the vehicle with minimum incremental travel cost using Dijkstra shortest paths.
3. Enforces capacity and optional time window (theta) constraints.
4. Falls back to a last-resort assignment for nodes that can't be served within theta.
5. Closes all routes back to the depot.
6. Applies **2-opt local search** to improve each route.
### Graph — graph.py
- Undirected graph with per-edge cost (travel time) and reliability.
- Dijkstra's algorithm with an optional weight\_lambda parameter that adds λ × (1 − reliability) to each edge weight, penalising unreliable routes.
- Supports dynamic edge removal for replanning after road blockages.
### Exact Solver — dp\_exact.py
Dynamic programming solution for small instances (exponential complexity — use only for ≤ ~15 nodes).
### Genetic Algorithm — ga\_vrp.py
Evolutionary heuristic for medium-sized instances as an alternative to the greedy solver.
### Visualisation — visualize.py
Generates interactive HTML maps using **Folium**, plotting vehicle routes on a geographic layout.
---
## Installation
Requires **Python 3.11+**.
\# Clone the repository
git clone https://github.com/your-username/disaster-routing.git
cd disaster-routing
\# Create and activate virtual environment
python -m venv venv
venv\\Scripts\\activate # Windows
\# source venv/bin/activate # Linux/macOS
\# Install dependencies
pip install -r requirements.txt
---
## Usage
Run via sim.py with one of three modes:
### Small Demo (fixed sample instance)
python sim.py --demo-small
Runs a 5-node, 2-vehicle example and prints routes, delivered demand, costs, and priority satisfaction score.
**Sample output:**
Vehicle 1 Route : 0 -> 1 -> 3
Delivered Demand : 7
Total Cost : 9
Vehicle 2 Route : 0 -> 2 -> 4
Delivered Demand : 3
Total Cost : 8
Total Combined Cost : 17
Average Reliability : 0.862
Priority Satisfaction Score : 1.00
### Random Demo (50 nodes, 200 edges)
python sim.py --demo
Generates a random connected graph and runs the greedy solver, printing routes and full metrics.
### Scalability Test
python sim.py --scalability
Runs the solver on graphs of 200, 1000, and 5000 nodes to benchmark performance.
---
## Input Format
Graphs can be loaded from JSON (sample.json):
{
  "nodes": \[
  {"id": 0, "demand": 0, "priority": 0},
  {"id": 1, "demand": 3, "priority": 5}
  ],
  "edges": \[
  {"u": 0, "v": 1, "cost": 4, "reliability": 0.9}
  ]
}
- demand: units of aid required at this node (0 for depot).
- priority: urgency level 1–5 (5 = most critical).
- cost: travel time/distance on this edge.
- reliability: probability the edge is passable (0.0–1.0).
---
## Dynamic Replanning
The replan\_on\_blocked\_edge() function in vrp.py supports real-time rerouting. When a road is reported blocked mid-mission, the edge is removed from the graph and routes are recomputed from the depot for all unserved customers — mimicking operational disaster response.
---
## Dependencies
| Package | Purpose |
|---|---|
| numpy | Numerical operations |
| matplotlib | Static plotting |
| folium | Interactive map visualisation |
| networkx | Graph utilities |
Install all via pip install -r requirements.txt.
---
## Metrics
The evaluate\_solution() function returns:
| Metric | Description |
|---|---|
| alpha\_priority\_time | Weighted sum of priority × arrival time |
| beta\_edge\_unreliability | Total unreliability across all edges used |
| gamma\_total\_idle | Total unused vehicle capacity |
| avg\_reliability | Average edge reliability across all routes |
| objective\_value | Combined objective (lower is better) |
---
## License
MIT License. See LICENSE for details.