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.
