Amdavad BRTS is one of the best Apps I’ve created for Windows Phone. It’s a companion App for Ahmedabad’s Janmarg users with features like Route Finder, Fare Calculator, Live Bus times, Station/Line details, and Weather. The App has more than 7,000 downloads, 170 reviews, and ratings averaging at 4.5 stars. Considering its target audience of just one city + the market share of Windows Phone, I think it’s doing really good.
In this post, I’m going to talk about a custom Algorithm I wrote to find Transit Routes for the ‘Route Finder’ feature of the App. I call it ‘UnOxbow’ (Yeah, I’m not very good at naming stuff). The problem was to compute the best possible Transit Route between 2 Stations while considering the criteria of Time, Distance, and Number of Transfers. To Tackle the problem, I created a round-based Algorithm which scans all Routes every round to find a route with or without transfers.
Starting with the Data I could get about the Mass public transit, Janmarg BRTS has 109 Routes and 144 Stations. Routes are a list of Station Ids where a Bus runs from the First station to the Last. The return journey of Bus from that Last station to First is again another Route. All Stations have an id, name, and geo-coordinates.
I pre-processed this Data by listing all Adjacent Junctions for every Station where a Transfer of Route is possible. Any Station on 2 or more Routes is considered as a Junction. All Junctions on the same route of a Station are their Adjacent Junctions.
To discuss this Algorithm, consider the above Route Map. Buses run in the direction shown by the arrows in all 4 Routes while there are 20 stations distributed in 4 routes. We’ll try to find Route from Station S to all three Stations D.
S to D1
In the First round, UnOxbow will try to find a Route with both Stations S & D1. R1 route has both stations and so we have a direct Route S – D1 via R1 without any Transfers.
S to D2
In this case, UnOxbow’s First round will fail because Stations S & D2 are on different Routes. For the second round, UnOxbow will try to find a route between all adjacent Junctions of Station S – J1 & J3 to Station D2. R4 route has both stations J3 & D2. So we have a Route S – J3 – D2 via R1 + R4 with 1 Transfer.
S to D3
In this case, UnOxbow’s First and Second round will fail because Stations S, J1, J3, and D3 are on different Routes. For the Third round, UnOxbow will try to find a route between all adjacent Junctions of Station J1 & J3 to Station D3.
Here it will find two Routes: S – J1 – J2 – D3 via R1 + R3 + R2 OR S – J3 – J4 – D3 via R1 + R4 + R2.
This is when UnOxbow compares other criteria like Distance and Time to calculate the best possible route.
Similarly, in all cases, UnOxbow will continue recursively until it finds a Route between the two Stations with least number of transfers. If it finds 2 or more possible Routes, it will compare the Total Distance & Time to choose a better Route.
Go ahead, download Amdavad BRTS and check out the ‘Route Finder’ feature in the App. I’d also like your comments on how I can improve my approach for Transit Routes.