I can’t say for certain exactly how the Uber routing algorithm works but I have a good idea of the basic method used to optimize routes. At Routible, we optimize routes for multiple stops and multiple vehicles in a few seconds.
Say we have 100 stops and 10 drivers in a given area. We use a maps API provider such as Google Maps or Open Street Maps to calculate a time/distance matrix. We need to calculate the time to travel from point A to the other 99 stops. We also need to calculate the time to travel from the other 99 points to A.
The algorithm brute force calculates possible combinations to reduce the overall travel time. As time goes on, the overall time to complete the route goes lower and lower until it is negligible. The solution is provided when the time to complete the route can no longer be improved by a significant amount.
Uber’s algorithm is likely to include many additional variables that helps optimize the route even further, some could include:
- Current location of online drivers
- Previous trips drivers are on
- Drop off points
- Ratings of drivers
- Ratings of customers
- Surge pricing
- Vehicle type
- and more
Each improvement to the route algorithm improves the Uber’s efficiency and to offer rides faster and more affordable.
I’ll attempt to dissect how the algorithm incorporates Uber Pool in a future post.