This project implements a Dynamic Programming-based algorithm for optimizing suburban bus routes using graph theory. The algorithm determines the minimum-cost path while considering various stops and constraints, making it suitable for efficient route planning in urban and suburban areas.
-
Dynamic Programming Algorithm:
- Utilizes recursive memoization to compute the most cost-effective path while handling multiple stops and constraints.
- Ensures computational efficiency, even for complex networks.
-
Graph Representation:
- Models the bus route network as a graph using NetworkX, where nodes represent stops and edges denote connections between them.
-
Visualization:
- Visualizes the optimal routes and the entire graph using NetworkX, providing a clear and interactive view of the network.
- Python: Core programming language.
- NetworkX: For graph creation, manipulation, and visualization.
- Matplotlib: For plotting and visualizing results.
- Dynamic Programming: Applied for route optimization using memoization techniques.
- The algorithm successfully identifies the minimum-cost path for given source and destination stops, accounting for all constraints.
- Visualized routes and graphs demonstrate the efficiency of the model in solving real-world bus route optimization problems.
The project uses a custom dataset representing suburban bus routes. It includes:
- Nodes: Representing bus stops.
- Edges: Representing connections between stops, with associated costs.