rapidroute

RapidRoute

ML-driven ambulance placement and shortest-path dispatch

Author: Ashiq Hameed Live demo: https://ashiqhameed.github.io/rapidroute/RapidRoute.html Stack: Python · scikit-learn · NetworkX · OSMnx · JavaScript Focus: Applying shortest-path algorithms (Dijkstra, A*) to emergency response, with machine learning driving placement, dispatch and edge weights.

1. Problem statement

In an emergency, the time it takes an ambulance to arrive often decides the outcome. That response time depends on three decisions:

  1. Where ambulances wait (depot placement)
  2. Which ambulance is sent (dispatch)
  3. Which route it takes (shortest path)

Classical systems make all three decisions with static rules: fixed stations, “send the nearest unit,” and routes that minimise distance. But a city doesn’t behave statically. Demand moves by hour and neighbourhood, and the same road takes very different times at 3 AM and 6 PM.

RapidRoute replaces each static rule with a learned one, and keeps a shortest path algorithm at the core of every decision.

Decision Static baseline RapidRoute
Where to wait Uniformly spread depots K-means weighted by predicted demand
Edge cost for routing Road length (metres) Travel time scaled by a learned congestion factor for each zone and hour
Which unit to send Nearest available unit Nearest unit, or a Q-learning dispatch policy
Route Dijkstra on distance Dijkstra / A* on predicted travel time

Objective: minimise mean ambulance response time and maximise the share of incidents reached within 8 minutes, especially critical calls.

2. Headline result

All 63,806 real Manhattan EMS calls from Nov–Dec 2024 (never used for training) were replayed through a calibrated discrete-event simulator with 110 ambulances and 8 depots.

Scenario Mean RT (min) P90 RT (min) % ≤ 8 min % critical ≤ 8 min
A · Static baseline: uniform depots, distance routing, nearest unit 11.35 15.19 46.9 47.7
B · + plain K-means depots 11.35 13.90 46.7 46.3
C · + demand-weighted K-means + ML travel-time routing 8.96 12.15 56.8 56.7
D · C + Q-learning dispatch 9.28 12.94 55.4 56.7
Observed, real FDNY, same period 12.33 25.23 37.2 58.7

Going from A to C cuts mean response time by 2.4 minutes, adds 9.9 percentage points of calls reached within 8 minutes, and adds 9.0 points for critical calls.

What drives the gain (ablation, % of calls within 8 minutes):

Placement Distance routing ML travel-time routing
Uniform grid 46.9 48.4
K-means (plain) 46.7 48.0
K-means (demand-weighted) 55.1 56.8
K-means (risk-weighted) 52.3 54.1

The gains hold across fleet sizes and are largest when the fleet is stretched: at 100 ambulances, C reaches 44.3% of calls within 8 minutes against A’s 33.5%.

3. Why this is an ML project, not just a routing project

Shortest path is the engine. ML decides everything it runs on: the edge weights, the source nodes, which calls are risky, and which unit is sent.

            ┌──────────────── ML LAYER ───────────────────┐
 EMS calls ─┤ Demand forecast   → where calls will come   │
            │ Travel-time model → congestion factor/edge  │
            │ Late-risk model   → which calls are at risk │
            │ Weighted K-means  → depot (source) nodes    │
            │ Q-learning agent  → which depot dispatches  │
            └──────────────────────┬──────────────────────┘
                                   ▼
            ┌──────────── SHORTEST PATH CORE ─────────────┐
            │ Multi-source Dijkstra  → coverage map       │
            │ A* (admissible heuristic) → single route    │
            │ Dijkstra / Bellman–Ford from scratch,       │
            │ verified against NetworkX                   │
            └─────────────────────────────────────────────┘

How it maps to the lab experiments

Exp Topic Where it is used
1 Preprocessing, discretisation, feature engineering Phase 1: cleaning, ZIP-to-zone reduction, cyclic encoding, time bands, fleet-load features
2 Naïve Bayes Phase 4: Categorical NB on discretised features
3 Decision Tree Phases 2, 3, 4: regressor and classifier, depth tuned
4 SVM Phase 4: RBF SVM, C and γ tuned
5 Gradient descent and feature scaling Phase 2: linear regression from scratch, scaled vs unscaled loss curves
6 K-means and K selection Phase 5: depot placement, K chosen with Elbow, Silhouette, Davies–Bouldin and Calinski–Harabasz
7 Q-learning Phase 7: dispatch agent
8 RL hyperparameter tuning Phase 7: sweep over α, γ and ε-decay

4. Data

Source Use Link
NYC Open Data · EMS Incident Dispatch Data (76xm-jjuj) 395,488 Manhattan incidents in 2024 dataset page
OpenStreetMap drive network (Overpass API) 4,545 nodes and 9,750 directed edges scripts/get_osm.sh
US Census 2024 ZCTA Gazetteer ZIP centroids zip

5. Phases and what each found

Phase 0: Data acquisition

src/data/download.py fetches the EMS incidents and the ZCTA file. The road network comes from scripts/get_osm.sh, which tries four Overpass mirrors with retries; this was needed because the macOS system Python cannot connect to Overpass. The script builds data/raw/manhattan_drive.graphml.

Phase 1: Preprocessing and EDA (Exp 1)

Phase 2: Demand forecasting (Exp 3, 5)

Target: calls per zone per hour.

Model RMSE R² (zone-hour) R² (citywide)
Historical mean 1.060 0.315 0.715
Linear regression (GD from scratch) 1.059 0.316 0.720
Decision tree 1.064 0.310 0.715
Gradient boosting (Poisson) 1.058 0.318 0.732

Zone-hour counts average about 1 call, so random (Poisson) noise caps R² at 0.367. Gradient boosting reaches 87% of that ceiling. For Exp 5: gradient descent with scaled features converges, the same learning rate on unscaled features diverges within 12 iterations, and a tiny learning rate on unscaled features is still slow after 300.

Phase 3: Travel time and learned congestion

Phase 4: Late-response risk classifier (Exp 2, 3, 4)

Target: whether the response will take longer than 8 minutes, predicted from information known when the call arrives.

Model Accuracy F1 ROC-AUC
Majority class 0.576 – 0.500
Naïve Bayes 0.671 0.685 0.747
Decision tree 0.680 0.688 0.757
SVM (RBF) 0.675 0.679 0.745
Gradient boosting (reference) 0.695 0.710 0.771

Phase 5: Depot placement (Exp 6)

Placement Mean travel (min) Demand within 8 min
Random (mean of 20) 10.34 43.2%
Uniform grid 7.51 62.2%
K-means (plain) 7.46 55.8%
K-means (demand) 6.93 65.0%
K-means (risk-weighted) 6.99 63.9%

Phase 6: Shortest path engine (core algorithm)

Phase 7: Q-learning dispatcher (Exp 7, 8)

Phase 8: Simulation, calibration and evaluation

Phase 9: Visuals and web interface

6. Project structure

rapidroute/
├── README.md
├── RapidRoute.html
├── requirements.txt
├── config.yaml
├── run_all.py
├── scripts/
│   └── get_osm.sh
├── data/
│   ├── raw/
│   └── processed/
├── src/
│   ├── config.py
│   ├── data/
│   │   ├── download.py
│   │   ├── manhattan_drive.overpassql
│   │   └── preprocess.py
│   ├── models/
│   │   ├── gd_linear.py
│   │   ├── demand.py
│   │   ├── travel_time.py
│   │   └── risk.py
│   ├── placement/
│   │   └── kmeans_depots.py
│   ├── routing/
│   │   ├── graph.py
│   │   ├── dijkstra.py
│   │   ├── astar.py
│   │   └── router.py
│   ├── rl/
│   │   └── qlearning.py
│   └── evaluate/
│       ├── style.py
│       ├── eda.py
│       ├── routing_eval.py
│       ├── simulate.py
│       ├── scenarios.py
│       ├── export_web.py
│       └── build_standalone.py
├── reports/
│   ├── figures/
│   └── *.csv
└── web/
    ├── index.html
    ├── style.css
    ├── app.js
    └── data.js

7. Tech stack

Python 3.9+, pandas, NumPy, scikit-learn, OSMnx, NetworkX, holidays, matplotlib, PyArrow and PyYAML. The web interface is plain HTML, CSS and JavaScript with no libraries.

8. How to run

Just viewing: double-click RapidRoute.html in the project root. It is the whole interface in one file, with the data and charts embedded, and can be shared on its own. web/index.html is the same interface but needs the rest of the folder next to it.

Full pipeline:

cd rapidroute
python3 -m pip install -r requirements.txt
bash scripts/get_osm.sh
python3 -m src.data.download
python3 run_all.py
open web/index.html

9. Key design decisions

Decision Why
Predict late-response risk instead of severity Severity is assigned from the call type, so predicting it would be leakage
Add fleet-load features (open incidents, calls waiting) They are known to a dispatcher in real time and raised AUC from 0.759 to 0.771
Learn congestion from quiet-fleet critical calls Busy-fleet calls mix up road traffic with ambulance availability and produced a reversed daily pattern
K = 8 Elbow method, and close to the number of real FDNY EMS stations
Fleet = 110 and κ = 2.95 Both calibrated on October so the simulator reproduces real median travel, median response and P90
Demand-weighted over risk-weighted placement Chosen on October validation (53.5% vs 50.9% of calls within 8 minutes)
Critical calls always get the nearest unit Never trade time on life-threatening calls; RL decides only for lower-priority calls

10. Transfer to Mumbai

11. Assumptions and limitations

12. References

  1. NYC Open Data. EMS Incident Dispatch Data (76xm-jjuj). https://data.cityofnewyork.us/d/76xm-jjuj
  2. Boeing, G. (2017). OSMnx: New methods for acquiring, constructing, analyzing, and visualizing complex street networks. Computers, Environment and Urban Systems, 65.
  3. Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1.
  4. Hart, P., Nilsson, N., Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. SSC, 4(2).
  5. Watkins, C., Dayan, P. (1992). Q-learning. Machine Learning, 8.
  6. Brotcorne, L., Laporte, G., Semet, F. (2003). Ambulance location and relocation models. European Journal of Operational Research, 147(3).