Graph-Based Routing System

Phase 1 — Dynamic graph & core queries

Foundations: a Dijkstra implementation that respects time-dependent edge costs via 96-slot daily speed profiles (15-minute resolution traffic simulation), and two KNN strategies — Euclidean with a grid-based spatial index, and shortest-path KNN that early-terminates an expanding Dijkstra.

• Adjacency list as vector<vector<AdjEdge>> for cache locality.
• Dynamic remove_edge / modify_edge in O(1) via a precomputed edgePos reverse map.
• Constraint support — forbidden nodes, restricted road types — handled in-loop without changing the core algorithm.

Phase 2 — K-shortest paths, exact and approximate

A simplified Yen's algorithm for exact K-shortest paths, with spur-node generation backed by bidirectional A*. The simplification: per spur node, suppress only the immediate prefix-edge rather than all conflicting edges — fewer book-keeping correctness concerns, slightly more candidate paths to deduplicate, faster in practice.

The interesting addition is the heuristic K-shortest variant: rather than purely shortest, candidates are scored by a composite

• Wlen · path_length + Wdiv · (overlap_penalty × distance_penalty)

targeting diverse alternatives within a 20–80% overlap band — i.e. the Google-Maps-style "here are three different ways to get there." Runs under a strict 5–15 second time budget; an approximate mode hits the same answers within 5–15% error with a 10–20× speedup via aggressive Dijkstra pruning.

Phase 3 — Delivery scheduling (TSP variant)

The hardest phase: a vehicle-routing problem with multiple orders, pickup/dropoff pairs, and dynamic disruptions (driver accidents, order cancellations, priority re-shuffles). Classical heuristics — nearest-neighbour, sweep, Clarke-Wright, parallel cheapest insertion — handled the static case well but crumbled under disruptions.

The simulation itself is deterministic so results are reproducible: cooking time is id mod 15 minutes, cancellations land on every 20th order (≈5%), priority flags on every 10th (≈10%), drivers travel at an assumed 17 m/s (~60 km/h), and an accident scenario fires at t = 0. Initial driver assignment uses K-means-style clustering around depots before per-driver routing kicks in.

The final solver is Large Neighborhood Search with a ruin-and-recreate operator:

• Ruin — remove 15–20% of orders (as full pickup-dropoff pairs) from the current route.
• Recreate — re-insert via parallel cheapest insertion, sorted by order price so high-value orders claim the best slots.
• Disruption hooks — driver failure triggers a full-route ruin; order cancellation triggers a targeted removal.

Initial construction is O(N²); LNS iterations are O(K·N). Completes within the 15-second budget on graphs up to ~5000 nodes.

I/O & build

JSON in, JSON out via nlohmann/json. A single SampleDriver.cpp dispatches all three phases through a phase-specific Make target, with exception guards around per-query handling.

What I'd carry forward

The Phase 3 work shifted how I think about optimisation problems. Classical heuristics give a strong static-case answer, but the real complexity is robustness under change — disruptions arrive and the schedule needs to survive them. Ruin-and-recreate turned out to be the cleanest framework: it gives you escape from local minima for free, and it composes naturally with arbitrary disruption events.