Goal: To implement search algorithms for optimal path planning in real-world transit systems.
In this project, I built an AI-based route finder using classic search algorithms on a custom dataset representing the London Underground. The system supports multiple search methods including:
- Breadth-First Search (BFS)
- Depth-First Search (DFS)
- Uniform Cost Search (UCS) with and without line-change penalties
- Heuristic BFS using zone-based heuristics
The system parses real-world Tube data and computes optimal paths considering travel time and line transitions. A custom cost function penalises line changes (+10 minutes) to reflect realistic commuter preferences.
Evaluation: Compared different algorithms based on visited nodes and total travel cost across multiple test routes.
Challenges Solved: Infinite loops, inconsistent zone assignments, optimality vs efficiency tradeoffs.
Tech stack: Python, Pandas, custom graph structures (no external libraries like NetworkX allowed per spec)