Ghostfleet

A ride-dispatch simulator for Cluj-Napoca, built to explore how far you can push routing, spatial indexing, and assignment optimization before reaching for a distributed-systems solution.

The core problem isn't "find a shortest path" — that part is a solved, well-known algorithm. It's which vehicle should serve which rider, at fleet scale, live, as both sets change every couple of seconds. That's a global optimization problem (min-cost max-flow), not a greedy nearest-match, and it's the part of this project that took the most thought.

Demo

Click the map to drop a car or a ride request — matched pairs get a dashed route line while the vehicle drives it live, in real Cluj-Napoca streets:

Architecture

Two services, split by workload:

• C++ dispatch engine — everything compute-heavy: routing, spatial queries, and the assignment solver. Stateful across ticks (tracks every vehicle/request's lifecycle), exposed over a small HTTP/JSON API.
• Python API layer — the browser-facing surface: forwards requests to the engine, runs the live tick loop, broadcasts state over WebSocket, persists completed trips to MySQL, and will host the ML demand-prediction layer.

They talk over plain HTTP/JSON, not gRPC or shared memory — the tick cadence is ~2s, so there's no latency pressure that would justify the extra complexity.

What's actually going on under the hood

• Road graph — an OSM extract for Cluj-Napoca, parsed into an adjacency-list graph.
• Routing — Dijkstra as the correctness baseline; A* with a straight-line heuristic; and A* ALT (landmarks + triangle inequality) as the one actually used for point-to-point ETAs, since it expands far fewer nodes on the real road graph (see benchmarks below).
• Spatial index — a uniform grid with expanding-ring k-NN search, backing live "nearest idle vehicles" queries. A k-d tree was built and benchmarked as a comparison, not used live (see why below).
• Assignment — vehicle-to-request matching is solved as a sparse min-cost max-flow problem (Dijkstra + Johnson potentials for reduced costs), not a greedy nearest-vehicle match, so the fleet-wide assignment is optimal for the current snapshot rather than locally greedy.
• Live loop — the API layer calls /tick on the engine every ~2s, which advances in-progress trips (assigned → boarding → on-trip → complete) and matches any pending requests against idle vehicles.
• Frontend — MapLibre GL JS; click to drop a single car or ride request, bulk-add up to 1,000 of either at once, erase individual vehicles, or clear the whole map. Watch matches get assigned and animate along their real route live.
• Persistence — completed trip lifecycles land in MySQL, which is the training data source for the upcoming demand-prediction model.
• Metrics — an in-memory rolling window (last 500 samples) of assignment count, pending-request count, and wait-time/ETA stats (avg/min/max), exposed at GET /metrics on the API layer.

Benchmarks

Full write-ups with methodology and result tables live in docs/:

• docs/routing-benchmarks.md — on the real Cluj-Napoca graph, A* ALT expands ~19x fewer nodes than Dijkstra and ~5x fewer than straight-line A*, at the cost of a one-time landmark preprocessing pass per graph load.
• docs/spatial-index-benchmarks.md — the grid's O(1) position update stays flat regardless of fleet size, while the k-d tree's rebuild-per-update cost is ~600x slower than the grid at 10,000 points; the k-d tree's query edge is real but small and never the bottleneck once fleet size dominates.
• docs/fleet-scale-benchmark.md — pushed 10x past the demo below: 10,000 vehicles and 10,000 concurrent requests scripted directly against the engine, 99.7% matched within 40 ticks, ~127 MB peak memory, with the 0.3% that never matched traced to disconnected fragments in the OSM extract rather than a matcher bug.

What that looks like in practice — 1,000 vehicles and 1,000 concurrent requests dispatched live across all of Cluj-Napoca:

Prerequisites

• CMake ≥ 3.16 and a C++17 compiler (GCC/Clang/MSVC)
• Python 3.11+
• Node.js 18+ (npm)
• MySQL 8+
• Bash, for scripts/fetch_osm_extract.sh (Git Bash on Windows)

Running it locally

1. Road graph data (one-time):

scripts/fetch_osm_extract.sh

2. MySQL schema:

mysql -u root -p < db/schema.sql

3. Dispatch engine (C++):

cmake -S dispatch-engine -B dispatch-engine/build
cmake --build dispatch-engine/build --target dispatch_engine
dispatch-engine/build/dispatch_engine.exe

Listens on :8080 by default (DISPATCH_ENGINE_PORT); loads data/cluj-napoca.osm by default (DISPATCH_ENGINE_OSM_PATH).

4. API layer (Python):

cd api
pip install -r requirements.txt
uvicorn app.main:app

Listens on :8000 by default; talks to the dispatch engine via DISPATCH_ENGINE_URL (default http://localhost:8080). MySQL connection is configured via MYSQL_HOST/MYSQL_PORT/MYSQL_USER/MYSQL_PASSWORD/MYSQL_DB — if unreachable at startup, trip persistence is silently disabled and the live simulation keeps running. Interactive API docs (Swagger UI) are auto-generated by FastAPI at http://localhost:8000/docs.

5. Frontend:

cd frontend
npm install
npm run dev

Talks to the API layer via VITE_API_BASE_URL (default http://localhost:8000).

Tests & benchmarks

# C++
cmake --build dispatch-engine/build --target dispatch_engine_tests
dispatch-engine/build/dispatch_engine_tests.exe

# Python
cd api && pytest

Benchmark binaries (benchmark_astar, benchmark_spatial_index, benchmark_dijkstra, graph_stats) build alongside the main tests via the same CMake configure step.

Status

Routing, spatial indexing, assignment, and the live dispatch loop (engine ↔ API ↔ frontend, with MySQL persistence and basic metrics) are done and working end to end. Next up: a demand-prediction model trained on logged trips, feeding "ghost request" nodes into the assignment solver so idle vehicles reposition toward predicted demand instead of only reacting to requests that have already arrived.

License & attribution

Code is licensed under the MIT License.

Map data © OpenStreetMap contributors, available under the Open Database License (ODbL). Map tiles by OpenFreeMap.