Intelligent Route Planner Using Graph Algorithms

A Data Structures & Algorithms project that simulates real-world navigation systems using Graph Algorithms such as Dijkstra, A*, BFS, and DFS to compute optimal routes based on distance, travel time, toll cost, and dynamic traffic conditions.

---

Problem Statement

Modern transportation systems require efficient route optimization to minimize travel time, distance, fuel consumption, and operational costs.

Without intelligent route planning:

• Routes may be longer than necessary
• Travel costs increase
• Traffic congestion causes delays
• Delivery efficiency decreases
• Navigation systems become less reliable

The Intelligent Route Planner solves this problem by modeling a city as a weighted graph and applying advanced graph algorithms to determine optimal routes between locations.

---

Project Overview

The project represents:

• Locations as Nodes
• Roads as Edges
• Distance / Time / Cost as Edge Weights

Users can select a source and destination, and the system computes the most efficient route using different graph algorithms.

Workflow:

Location Selection ↓ Graph Construction ↓ Adjacency List Creation ↓ Route Optimization Algorithm ↓ Shortest Path Calculation ↓ Route Summary & Visualization

---

---

📁 Project Structure

Intelligent-Route-Planner/
├── main.py              ← Entry point
├── requirements.txt
├── .gitignore
├── README.md
│
├── src/
│   ├── data_builder.py  ← Generates city graph CSV
│   ├── graph_loader.py  ← Loads graph + cost functions
│   ├── router.py        ← BFS, DFS, Dijkstra, A*
│   ├── dynamics.py      ← Traffic & road closure
│   ├── visualizer.py    ← Matplotlib route rendering
│   └── app.py           ← Flask API + dashboard server
│
├── static/
│   └── index.html       ← Web dashboard UI
│
├── data/                ← Auto-generated CSVs
└── outputs/             ← Generated route images

---

Features

Feature	Description
Graph-Based Road Network	Locations modeled as nodes and roads as edges
Dijkstra Algorithm	Computes optimal shortest path
A* Search Algorithm	Faster heuristic-based routing
BFS Traversal	Fewest-hop route exploration
DFS Traversal	Deep graph exploration
Adjacency List	Memory-efficient graph representation
Priority Queue (Min Heap)	Optimized shortest-path processing
Dynamic Traffic Simulation	Adjust edge costs in real time
Road Closures	Simulate blocked roads
Multi-Criteria Routing	Time, Distance, Toll & Eco Modes
Route Visualization	Graphical route rendering
Route Summary Report	Distance, ETA, Cost Analysis
Interactive Dashboard	Web-based route planner

---

DSA Concepts Implemented

Concept	Purpose
Graphs	Road Network Representation
Directed Graph	One-Way Roads
Weighted Graph	Distance and Time Modeling
Adjacency List	Efficient Graph Storage
BFS	Breadth-First Traversal
DFS	Depth-First Traversal
Dijkstra's Algorithm	Shortest Path
A* Algorithm	Heuristic Route Optimization
Priority Queue	Efficient Node Selection
Path Reconstruction	Route Recovery
Multi-Criteria Optimization	Realistic Route Selection

📊 Screenshots

Route Visualization

Route Comparison Analysis

Graph Adjacency Representation

---

Algorithms Used

Dijkstra Algorithm

Used for finding the shortest path in weighted graphs with non-negative edge weights.

Time Complexity:

O((V + E) log V)

---

A* Search Algorithm

Enhances Dijkstra by using a heuristic (Haversine Distance) to guide the search.

Time Complexity:

O(E)

Average performance is significantly faster than Dijkstra for large road networks.

---

BFS

Finds routes with the fewest number of hops.

Time Complexity:

O(V + E)

---

DFS

Explores deep graph paths before backtracking.

Time Complexity:

O(V + E)

🎥 Demo Video

👉 Click the image above to watch the full demo

---

Tech Stack

Core Technologies

• Python
• Flask
• NetworkX
• Matplotlib

Data Structures

• Graphs
• Adjacency Lists
• Queues
• Stacks
• Priority Queues (Min Heap)

Algorithms

• BFS
• DFS
• Dijkstra
• A*
• Multi-Criteria Routing

API Endpoints

Method	Endpoint	Description
POST	/api/route	Compute Optimal Route
POST	/api/compare	Compare Route Objectives
POST	/api/traversal	BFS or DFS Traversal
GET	/api/adjacency	Graph Adjacency List
POST	/api/traffic	Apply Traffic Conditions
POST	/api/closure	Close Road
POST	/api/reset	Reset Network
GET	/api/graph_stats	Graph Statistics

---

City Graph Model

The synthetic city contains:

• 15+ Locations
• 30+ Road Connections
• Toll Roads
• One-Way Roads
• Residential Roads
• Highways
• Primary Roads

Sample Locations:

• Airport
• Railway Station
• Hospital
• University
• Shopping Mall
• Tech Park
• City Center

---

Installation & Setup

Clone Repository

git clone https://github.com/Sonia068/Intelligent-Route-Planner.git

cd Intelligent-Route-Planner

Install Dependencies

pip install -r requirements.txt

Run Application

python main.py

Open Browser

http://127.0.0.1:5000

Real-World Applications

• Google Maps Style Navigation
• Ride-Hailing Platforms
• Logistics & Delivery Optimization
• EV Route Planning
• Smart City Transportation
• Fleet Management Systems
• Emergency Response Routing

---

Learning Outcomes

After completing this project, I gained practical experience in:

• Graph Data Structures
• Route Optimization Problems
• BFS and DFS Traversals
• Dijkstra Algorithm
• A* Search Algorithm
• Priority Queues and Heaps
• Adjacency List Representation
• Algorithm Complexity Analysis
• Backend Development with Flask
• Interactive Dashboard Design
• Real-World Transportation Systems

---

Future Enhancements

• OpenStreetMap Integration
• Real-Time Traffic Data
• EV Charging Station Routing
• Multi-Modal Transportation
• Live GPS Tracking
• Route Recommendation Engine
• Machine Learning Based ETA Prediction

Author

Sonia Thakur

GitHub: https://github.com/Sonia068

LinkedIn: https://www.linkedin.com/in/sonia-thakur-6ab93b349/

🎥 Demo Video

👉 Click the image above to watch the full demo

---

---

⭐ If you found this project useful, please consider giving it a star on GitHub.