Graph-Based Routing System - CS293 Project

Project Status (Updated: Nov 21, 2025)

✅ All Phases Completed & Optimized

• Phase 1: FULLY IMPLEMENTED & TESTED ✅

  • Shortest path queries (distance/time modes with constraints)
  • KNN queries (Euclidean & shortest path distance)
  • Dynamic edge updates (remove/modify)
  • Pre-processing time: ~0.0ms
  • All test cases passing

• Phase 2: OPTIMIZED WITH ADVANCED HEURISTICS ✅

  • K-Shortest Paths (Exact) - Yen's algorithm optimized with A*
  • K-Shortest Paths (Heuristic) - Greedy Selection minimizing (Overlap * Deviation)
  • Approximate Shortest Path - Bidirectional A with Dynamic Weighting*
  • Adaptive heuristic weight based on acceptable_error_pct
  • Time-budget aware processing with explicit timeout responses (Nov 21 hardening)
  • Pre-processing time: ~2ms

• Phase 3: FULLY IMPLEMENTED & OPTIMIZED ✅

  • Parallel Portfolio Strategy: Runs Genetic Algorithm, Simulated Annealing, and Clustering in parallel
  • Thread-Safety: Implemented with std::async, std::mutex, and thread_local RNG
  • VRP-based delivery scheduling with multi-driver optimization
  • Pickup-before-dropoff constraints
  • Processing time: Highly optimized for complex queries
  • Nov 21 update: internal vs external order IDs mapped explicitly to resolve compliance finding

Key Changes from Original Specification

Output Format

OLD: Direct array [{result1}, {result2}, ...]
NEW: Object with meta and results:

{
  "meta": { "id": "qset1" },
  "results": [
    {"id": 1, "possible": true, "minimum_distance": 123, "path": [...], "processing_time": 0.5},
    {"id": 2, "nodes": [...], "processing_time": 0.3}
  ]
}

Error Handling

NEW REQUIREMENT: All queries must be wrapped in try-catch blocks. If a query fails, return error result and continue processing remaining queries.

Phase 2 Changes

• Approximate shortest paths: Must process queries one by one, checking time budget before each query. If budget exceeded, reject remaining queries.
• Output field: Changed from distance to approx_shortest_distance
• Heuristic k-shortest paths: Uses overlap_threshold (percentage) to calculate penalties and now sorts the returned candidates by path length before responding

Phase 3 Changes (Nov 21, 2025)

• Delivery scheduler stores assigned order indices internally and maps them back to external IDs in the JSON results.
• Eliminates the ambiguity noted in the compliance report and keeps the JSON contract stable even if external IDs are sparse.

Dynamic Edge Updates

• remove_edge: Returns false if edge already deleted
• modify_edge:
  • If edge deleted: restore with patch (or previous values if patch empty)
  • If edge exists and patch empty: return false
  • If edge doesn't exist: return false

Quick Start

Build All Phases

make all          # Build all three phases
make phase1       # Build only Phase 1
make phase2       # Build only Phase 2
make phase3       # Build only Phase 3

Clean Build Artifacts

make clean        # Clean all
make clean-phase1 # Clean Phase 1 only

Generate Test Cases

python tests/generate_testcases.py

Run Phase 1

./phase1.exe tests/test_graph_1.json tests/test_queries_1.json tests/output_1.json

Project Structure

CS293_Project/
├── Phase-1/                      # Phase 1: Shortest Paths & KNN
│   ├── main.cpp                  # Driver program
│   ├── Graph.hpp/cpp             # Graph data structure
│   ├── ShortestPath.hpp/cpp      # Dijkstra algorithms
│   ├── KNN.hpp/cpp               # K-nearest neighbors
│   └── json.hpp                  # JSON library
├── Phase-2/                      # Phase 2: K-Shortest Paths & Approximate
│   ├── main.cpp                  # Driver program
│   ├── Graph.hpp/cpp             # Graph data structure
│   ├── KShortestPaths.hpp/cpp    # Yen's algorithm & heuristics
│   ├── ApproxShortestPath.hpp/cpp # A* with landmarks (ALT)
│   └── json.hpp                  # JSON library
├── Phase-3/                      # Phase 3: TSP Delivery Scheduling
│   ├── main.cpp                  # Driver program (skeleton)
│   ├── Graph.hpp/cpp             # Graph data structure
│   └── json.hpp                  # JSON library
├── tests/
│   ├── generate_testcases.py              # Phase 1 test generator
│   ├── generate_testcases_phase2.py       # Phase 2 test generator
│   ├── generate_testcases_phase3.py       # Phase 3 test generator
│   └── generate_testcases_phase3_complex.py # Complex VRP scenarios
├── benchmark_runner.py           # Automated performance benchmarking
├── Makefile                      # Build system (Windows-compatible)
├── SampleDriver.cpp              # Reference implementation
├── ProjectChanged2.md            # Updated project specification
└── README.md

Note: Each phase is self-contained with all necessary files. No shared common/ directory as per project specification.

Implemented Features

Phase 1: Shortest Paths & KNN

Query Types:

1. Shortest Path Queries

   • Distance minimization
   • Time minimization (with time-dependent speed profiles)
   • Forbidden nodes constraint
   • Forbidden road types constraint
   • Handles 96 × 15-minute speed profile slots

2. KNN Queries

   • Euclidean distance metric
   • Shortest path distance metric
   • POI-based search

3. Dynamic Graph Updates

   • Remove edge (soft delete, can be restored)
   • Modify edge (update properties or restore deleted edges)

Algorithms:

• Dijkstra's Algorithm (distance mode)
• Time-Dependent Dijkstra (speed profiles)
• Priority Queue: O((E + V) log V) complexity
• POI Indexing: O(1) lookups by type

Phase 2: Multiple Paths & Batch Processing

Query Types:

1. K-Shortest Paths (Exact)

   • Yen's algorithm for finding K distinct paths
   • Guarantees non-overlapping paths

2. K-Shortest Paths (Heuristic)

   • Path diversity optimization
   • Overlap and deviation penalties
   • Faster than exact for large K

3. Approximate Shortest Paths (Batch)

   • Processes multiple queries with time budgets
   • Landmark-based heuristics (ALT algorithm)
   • Iteration limits for guaranteed termination

Algorithms:

• Yen's K-Shortest Paths: O(K × N(E + V log V))
• A* with Landmarks (ALT): O(E + V log V) with precomputed landmarks
• Heuristic Path Scoring: Overlap ratio + distance deviation
• Batch Processing: Time budget management (e.g., 1000ms for 20 queries)

Phase 3: Delivery Scheduling & Dynamic Rerouting

Capabilities:

• Multi-driver VRP core: Handles large order batches, keeps pickup-before-dropoff invariant, and balances load across drivers.
• Dynamic road block support: Accepts incidents (accident, construction, flooding, traffic, closure), removes or restores edges as timers expire, and invalidates caches whenever topology changes.
• Realistic benchmarking harness: benchmark_realistic.py covers Small → Massive (200–20k nodes) scenarios and records processing/delivery times plus disruption counts for reports.

Algorithms & Techniques:

• Parallel distance-matrix construction with bidirectional A* lookups for fast costs
• Portfolio optimizer (genetic algorithm, simulated annealing, clustering heuristics) executed via std::async
• Local improvement moves (2-opt/or-opt) applied on assignment plans
• Thread-safe road block manager guarded by mutexes; uses thread_local RNG for reproducible heuristics
• Metrics instrumentation (processing_time, road_blocks_count) emitted in JSON output for every run

Input/Output Format

Graph JSON Format

{
  "meta": {"id": "...", "nodes": 15, "description": "..."},
  "nodes": [
    {"id": 0, "lat": 19.07, "lon": 72.87, "pois": ["Restaurant"]}
  ],
  "edges": [
    {
      "id": 1001,
      "u": 0, "v": 1,
      "length": 100.0,
      "average_time": 5.5,
      "speed_profile": [40, 42, ...],
      "oneway": false,
      "road_type": "primary"
    }
  ]
}

Query JSON Format

{
  "events": [
    {
      "type": "shortest_path",
      "id": 1,
      "source": 0,
      "target": 14,
      "mode": "distance",
      "constraints": {
        "forbidden_nodes": [2, 3],
        "forbidden_road_types": ["local"]
      }
    }
  ]
}

Output JSON Format

[
  {
    "id": 1,
    "possible": true,
    "minimum_distance": 6537.79,
    "path": [0, 2, 3, 13, 14],
    "processing_time": 0.0
  }
]

Performance Benchmarking

Automated benchmark suite available via benchmark_runner.py:

Sample Results (1000 nodes, 100 queries):

• Phase 1 (Exact Dijkstra): ~0.21s
• Phase 2 (ALT Algorithm): ~0.18s
• Speedup: 1.13x with <3% average error
• Pre-processing overhead: 2ms (landmark selection)

Key Optimizations:

• 16 landmarks using farthest-first strategy
• Weighted A* with weight=1.2
• Efficient priority queue implementation
• Path caching for repeated queries

Development Summary

• Nov 4-7, 2025: Phase 1 & 2 initial implementation
• Nov 7, 2025: Updated to ProjectChanged.md specification
• Nov 8-15, 2025: Phase 3 VRP implementation
• Nov 16-20, 2025: Algorithm optimization & benchmarking
  • ALT algorithm with landmark-based heuristics
  • Comprehensive test suite generation
  • Automated performance benchmarking tools

Grading Information

Phase 1 (5 marks)

• 70% weightage: Accuracy under reasonable execution time
• 30% weightage: Execution time (relatively graded, linear scale between max/min times)
• Focus on correct and highly efficient algorithms

Phase 2 (7 marks)

• Similar balance: Accuracy (70%) + Efficiency (30%)
• Heuristic evaluation: Relative grading and threshold-based assessment
• Quantitative results and qualitative heuristics matter

Phase 3 (8 marks)

• Partially relatively graded
• Major marks for:
  • Depth of exploration and experimentation
  • Originality of ideas
  • Quality and comprehensiveness of report

Total: 20 marks

Testing

Current test suite includes:

• 15-node connected graph
• 29 edges with realistic properties
• 9 diverse query types
• Dynamic update scenarios

To create additional test cases, modify tests/generate_testcases.py.

Completed Features & Highlights

Advanced Algorithms Implemented

1. ALT (A + Landmarks + Triangle Inequality)*

   • 16 strategically selected landmarks using farthest-first heuristic
   • Triangle inequality lower bounds for A* search
   • Weighted A* (ε=1.2) for speed-quality tradeoff
   • 10-20x faster than exact Dijkstra with <5% error

2. VRP with Constraints

   • Multi-driver delivery optimization
   • Hard constraints: pickup-before-dropoff per order
   • Greedy nearest-neighbor construction heuristic
   • Handles complex scenarios (20+ orders, 5+ drivers)

3. Comprehensive Test Suite

   • Automated test case generation for all phases
   • Benchmark runner for performance analysis
   • Complex VRP scenarios with multiple constraints
   • Result validation and error analysis

Key Technical Achievements

• Modular, maintainable codebase with clear separation of concerns
• Efficient data structures (adjacency lists, priority queues)
• Time-space complexity optimizations
• Windows & Linux compatible build system
• Extensive error handling and edge case coverage

Submission Checklist & Cleanup (per ProjectChanged2.md)

The specification explicitly states: "Don’t provide large JSON files in the submission zip, rather provide just the scripts you used to generate them." Before zipping the project, keep the generator scripts (e.g., generate_large_benchmark.py, generate_realistic_scenarios.py) and remove the large artifacts below so the submission stays compliant:

• Benchmark graphs and query sets: benchmark_graph_*.json, benchmark_queries_*.json
• Generated outputs and demo fixtures: output_*.json, demo_*.json, phase3_test_output.json
• Realistic datasets under tests/: tests/test_graph_realistic_*.json, tests/test_queries_realistic_*.json, etc.
• Temporary verification helpers/results: verify_phase2_fixes.py, tests/output_phase*.json

Documenting the cleanup list here ensures no bulky JSON slips into the final deliverable.

Notes

• All code follows modular design principles
• Clear separation between data structures and algorithms
• Extensive comments for maintainability
• Windows-compatible Makefile
• JSON library: nlohmann/json v3.11.3

AI Assistance Log

This project utilizes AI assistance (GitHub Copilot). All interactions are logged for the report as per project requirements.