Our backend lead has left for a lucrative job in Dubai, but we are moving onward. I don’t have much software engineering experience so I’m building our tech with Parse as a backend-as-a-service in JavaScript together with a client android app for beta testing. We’ve brought two additional developers into the Savaree team to help refine and polish the android app as well as create a complete web front-end for Pakistan’s first ride sharing app.
I began focusing on business development around June this year, but have retained responsibility for the backend and associated APIs. The most interesting part of this was the search algorithm that returned the set of feasible routes for any carpooler needing a ride.
The spatial search of two overlapping or closely lying paths is complex enough in itself, and the added constraints of reasonable accommodation by the driver and the passenger as well as human behavior (I’m less likely to drop you off two blocks down if I’m going cross-country than if I’m going three blocks down) make the question even more challenging.
My initial solution was based on traversing each route posted in the database, and determining the closest distance between that route and the pickup and drop-off points of the passenger – an elementary brute-force algorithm. Once this spatial matching was completed, the next search would match the required time.
My next task was to create an appropriate framework on which spatiotemporal queries could be run.
Dr. Sohaib Khan, a professor and mentor of mine, pointed me towards the excellent paper An Opportunistic Client-User Interface to Support Centralized Ride-Share Planning by Rigby et al. which confirmed my suspicion that pickup and drop-off points ought to be discretized for maximum efficiency. In addition, because a carpool should be at least a sizable proportion of the total length of the driver’s route, a hierarchical approach would be best to reduce the search space based on the passenger’s pickup and drop-off.
To further flesh out the idea, I decided to look at a company known for its engineering prowess – Google. My problem of significance based on scale was analogous to Google Maps’ of displaying the most relevant and significant landmarks at each magnification. I was able to decompile their android Maps application and reverse-engineered their hierarchical grid-based approach.
Representing routes not by points along the path but instead by the cells of the grid they follow enables a much faster search. Simplifying this approach was easy using the routeboxer algorithm.
What’s more, if the resolution of the grid is determined by the length of the route, and searches are done at the corresponding resolutions, the search space is automatically narrowed down to only the area of interest.
If each tile of the grid stores information about the routes that pass through it, then the problem of finding a matching route becomes one of a simple lookup. This, combined with a few other optimizations, is a robust enough search algorithm with very fast response times. Partial lookups are also supported by this representation, so now we’re rolling out the ability to match a pickup or drop-off along the driver’s route.
With the ride sharing algorithm in place for now, I am able to move on to the business development end of things.
In the meanwhile, with the help of my team, I’ve been able to secure several strategic ride sharing partnerships with medium-size companies, greatly improving our bottom line. As of today, Savaree has completed approximately PKR 20 million worth of rides, and saved about 5 tons of vehicle emissions in doing so. Here’s to greater heights!
For more on what I’ve done, do check out my resume
Get in touch with me at: qasimzafar AT outlook DOT com
Leave a Reply