🗺️ Map-Based Delivery Routing & Scheduling Engine

A high-performance routing and delivery scheduling system built in C++, implementing advanced graph algorithms on real-world map data. Inspired by the core infrastructure behind services like Zomato, Swiggy, and Blinkit.

Course Project | IIT Bombay | CS 293: Data Structures & Algorithms | August 2025
Team: Varshika Cheemala · Shrijani Korepaka · Vyshnav Thumu

---

🚀 What This Does

Given a city road network (graph), this system can:

• Find shortest paths by distance or time with dynamic constraints
• Handle real-time road closures and edge modifications
• Find K-nearest Points of Interest (hospitals, restaurants, etc.)
• Compute K alternate routes between two points
• Schedule multi-driver delivery fleets across hundreds of orders — solving a TSP variant under real-world constraints

---

🧠 Algorithms Implemented

Phase 1 — Core Routing

Algorithm	Use Case	Complexity
A* (modified Dijkstra)	Shortest path by distance with forbidden nodes/road types	O((V+E) log V)
Dijkstra	Shortest path by time with speed profiles	O((V+E) log V)
Soft Deletion	O(1) dynamic edge removal/modification	O(1)
KNN with Max-Heap	K nearest POIs by Euclidean distance	O(V·(P + log k))
Dijkstra with early exit	K nearest POIs by road network distance	O((V+E) log V) worst

Phase 2 — Advanced Path Finding

Algorithm	Use Case	Complexity
Yen's K-Shortest Paths	Exact K loopless shortest routes	O(K·L·(V+E) log V)
Iterative Penalty Method	Heuristic diverse K-shortest paths (faster)	O(K·(V+E) log V)
Landmark-Based Triangulation	Approximate shortest path with √V landmarks via Farthest Point Sampling	O(√V) per query after precomputation

Phase 3 — Fleet Scheduling (TSP Variant)

Solves a multi-agent, deadline-constrained Travelling Salesman Problem — the same core problem faced by instant delivery companies.

• Greedy Cheapest Insertion Heuristic with multi-objective cost function
• Priority queue-based driver selection (availability + load factor)
• Fatigue modeling — quadratic penalty for drivers nearing 8-hour shift limit
• Constraint validation — capacity (max 10 orders), time windows, batch compatibility
• Landmark-cached distance lookups for sub-second scheduling across large fleets

---

📊 Key Design Decisions

Why soft deletion for edge removal?
Physical removal from vectors is O(N) and invalidates iterators. Soft deletion (boolean flag) is O(1) and keeps routing algorithms fast during batch updates.

Why A* for distance but Dijkstra for time?
A* needs an admissible heuristic. Euclidean distance works perfectly for spatial distance. For time, variable speed limits make it impossible to derive a consistent heuristic — so standard Dijkstra is more correct.

Why Landmark-Based Approximate Paths?
Running full Dijkstra for every delivery cost estimate in Phase 3 would be too slow. Precomputing √V landmarks with Farthest Point Sampling reduces per-query cost to O(√V) — enabling real-time scheduling across hundreds of orders.

---

🗂️ Project Structure

├── Phase-1/          # Core routing: A*, Dijkstra, KNN, dynamic updates
│   ├── Algorithm.cpp/.hpp
│   ├── Graph.cpp/.hpp
│   ├── main.cpp
│   └── tests/        # Python-generated + manual test cases
├── Phase-2/          # Advanced: Yen's, Heuristic K-paths, Approximate routing
│   ├── Algorithm.cpp/.hpp
│   ├── Graph.cpp/.hpp
│   ├── main.cpp
│   └── tests/
├── Phase-3/          # Fleet scheduling: TSP heuristic, multi-driver, deadlines
│   ├── Algorithm.cpp/.hpp  (GraphAdapter, Driver, Scheduler classes)
│   ├── Graph.cpp/.hpp
│   ├── main.cpp
│   └── tests/
└── Makefile

---

⚙️ How to Run

Prerequisites: g++ with C++17 support

# Build all phases
make all

# Run Phase 1
./phase1 Phase-1/tests/test_graph.json Phase-1/tests/test_queries.json output.json

# Run Phase 2
./phase2 Phase-2/tests/test_graph.json Phase-2/tests/test_queries.json output.json

# Run Phase 3
./phase3 Phase-3/tests/test_graph.json Phase-3/tests/test_queries.json output.json

# Clean build
make clean

Input format: JSON files for graph (nodes, edges, speed profiles) and queries
Output: output.json with results for each query

---

🧪 Test Infrastructure

• Phase 1: Python-generated synthetic graphs (100 nodes, 300 edges) modelled on Mumbai coordinates (lat 19.0–19.3, lon 72.8–73.0) with 96-slot time-dependent speed profiles, rush hour simulation, and random POI placement
• Phase 2: Manual edge cases — overlapping paths, cycles, approximation accuracy
• Phase 3: Deadline stress tests, dwell time tests, multi-driver scenarios

---

📄 Full Report

See Report.pdf for detailed complexity analysis, algorithm explanations, and test case documentation.