Background
Route planning is a search problem in which different algorithms can produce substantially different behaviour depending on what the system is designed to optimise.
Using a graph representation of the London Underground, I implemented and compared classical search algorithms for finding routes between stations. The network included station connections, travel-time costs, Tube lines, and fare-zone information.
Rather than evaluating only whether an algorithm could reach the destination, I compared methods according to two competing objectives:
- how much of the network had to be explored
- the travel cost of the resulting route
The project therefore examined a central search problem: which algorithm should be preferred when computational efficiency and route cost are not necessarily optimised by the same strategy?
Research Goals
- Implement BFS, DFS, Uniform Cost Search, and heuristic-guided search on a real transport network.
- Compare algorithms using both visited-node count and total route cost.
- Extend UCS with an explicit line-change penalty to represent an alternative routing objective.
- Develop a heuristic using London fare-zone information to reduce unnecessary graph exploration.
- Analyse the trade-off between search efficiency, route cost, and the objective encoded by the algorithm.
Dataset
The London Underground data described connections using:
- Starting station
- Destination station
- Tube line
- Average travel time
- Primary and secondary fare zones
I transformed these records into graph structures mapping each station to its neighbouring stations, travel costs, and Tube lines.
A separate zone representation was constructed for use by the heuristic search method.
No external graph library such as NetworkX was used; the search procedures operated on custom Python graph structures.
Methodology
Breadth-First Search
BFS explored the graph level by level.
The algorithm prioritised paths with fewer station transitions rather than explicitly minimising travel time. A visited set prevented repeated exploration and cycles.
Depth-First Search
DFS recursively explored one branch of the network before backtracking.
Visited-node tracking was required to prevent repeated station visits and infinite loops in the cyclic Tube network.
Uniform Cost Search
UCS prioritised paths according to cumulative travel time.
At each stage, the lowest-cost available route was expanded first, making travel cost rather than search depth the primary optimisation criterion.
Cost-Aware UCS with Line Changes
I extended UCS to incorporate an additional 10-minute penalty whenever a route changed Tube lines.
The modified objective therefore represented both:
- travel time
- the additional cost assigned to line changes
This provided a simple example of how the definition of an optimal route changes when the objective function incorporates preferences beyond travel time alone.
Zone-Guided Heuristic Search
I implemented a heuristic search method using fare-zone information to prioritise stations whose zone information appeared closer to that of the destination.
If the current station and destination shared a zone, the heuristic returned zero. Otherwise, their zone sets were compared to guide exploration.
Unlike UCS, this heuristic did not directly optimise cumulative travel time. Its purpose was to reduce unnecessary exploration by directing the search toward parts of the network that appeared more promising according to the available zone information.
Results
The algorithms were compared on four London Underground routes:
| Route | BFS Nodes | DFS Nodes | UCS Nodes | Heuristic Nodes |
|---|---|---|---|---|
| Canada Water → Stratford | 52 | 53 | 51 | 15 |
| New Cross Gate → Stepney Green | 53 | 34 | 17 | 12 |
| Ealing Broadway → South Kensington | 53 | 23 | 48 | 16 |
| Baker Street → Wembley Park | 26 | 101 | 73 | 4 |
The zone-guided heuristic required substantially less graph exploration than BFS across all four routes.
Relative to BFS, visited-node counts were reduced by approximately:
- 71% — Canada Water → Stratford
- 77% — New Cross Gate → Stepney Green
- 70% — Ealing Broadway → South Kensington
- 85% — Baker Street → Wembley Park
The largest contrast occurred between Baker Street and Wembley Park: DFS visited 101 nodes, while the heuristic search visited only 4.
Route Cost
The corresponding travel costs were:
| Route | BFS | DFS | UCS | Heuristic |
|---|---|---|---|---|
| Canada Water → Stratford | 15 | 54 | 14 | 15 |
| New Cross Gate → Stepney Green | 14 | 50 | 14 | 14 |
| Ealing Broadway → South Kensington | 19 | 47 | 19 | 19 |
| Baker Street → Wembley Park | 13 | 68 | 13 | 13 |
UCS achieved the minimum observed travel cost on all four test routes.
The heuristic method produced equally low costs on three routes while exploring substantially fewer nodes, but it was slightly more expensive on Canada Water → Stratford.
DFS consistently produced the weakest routes in this comparison, including a cost of 68 between Baker Street and Wembley Park compared with 13 for BFS, UCS, and heuristic search.
The results therefore exposed a clear trade-off: the method that explored the fewest states was not guaranteed to return the minimum-cost route.
Implementation Challenges
Several implementation issues illustrated practical differences between textbook search algorithms and graph search on a real transport network.
- Cycles and repeated states: DFS could repeatedly revisit stations without explicit visited-node tracking.
- Cumulative-cost tracking: UCS required costs to be propagated correctly across entire paths rather than considering only individual edges.
- Zone representation: Fare-zone information contained multiple representations that had to be normalised before heuristic comparisons.
- Heuristic quality: Zone proximity did not always correspond perfectly to minimum travel time, meaning efficient exploration did not guarantee the lowest-cost route.
- Multiple objectives: Adding line-change penalties changed the meaning of route cost and therefore changed what qualified as an optimal solution.
Contributions
- Implemented BFS, DFS, UCS, cost-aware UCS, and heuristic-guided graph search in Python.
- Built graph representations from London Underground connection, travel-time, line, and zone data.
- Added an explicit 10-minute line-change penalty to represent an alternative routing objective.
- Developed a zone-based heuristic for directing search toward the destination.
- Evaluated algorithms across four routes using both visited-node counts and travel costs.
- Reduced graph exploration by approximately 70–85% relative to BFS using heuristic guidance.
- Demonstrated that UCS consistently achieved the minimum observed travel cost, while the heuristic search often obtained comparable routes with substantially less exploration.
- Analysed implementation and modelling issues involving cycles, heuristic quality, cumulative-cost propagation, and data representation.
Impact
The project demonstrated that there is no single definition of the "best" route-finding algorithm.
UCS was strongest when the objective was minimum observed travel cost, while heuristic guidance substantially reduced search effort. On three of the four tested routes, the heuristic achieved the same minimum observed cost while exploring considerably fewer nodes; on the remaining route, this efficiency came with a slightly higher route cost.
Extending UCS with a line-change penalty also demonstrated how the objective itself can be modified to represent considerations beyond travel time.
The broader lesson was that algorithm selection depends on what the problem is designed to optimise. Computational effort, travel cost, and transfer penalties represent different objectives, and improving one does not necessarily optimise the others.