I love this question, because it’s a little open ended topic and I have worked around implementing crowdsourced ETA algorithms for given routes in few of my previous projects.
I have answers to two other versions of this question here:
Aspointed out, this is not a public topic and the open source solutions out there don’t really meet the expectation most of the time. Lots of people would tell you in the field of Geolocation systems and Graph algorithm related solutions, that the set of algorithms used are not hidden. Though, the exact solutions are not common knowledge either.
- The difference is the customer usage and delivering a solution to that required outcome.
Waze is more focused on getting you to Point B in a certain time given to you, meaning that re-routing in each end point of an edge is less problematic and that’s why some users love it.
- While Google Maps, focuses on giving the user an ETA, and using this route with the given ETA is the goal, rather than re-routing to Point B as often as Waze would do.
- Regarding congestion for Waze, the weights on the edges are going to balance itself out meanwhile re-calculating the route on the way.
- The same way Google Maps could rely on Android Phones or other Map User, one of the strength of Waze is the network that is has as well. Using those live streams of data can avoid causing graph diffusion.
For finding a specific Paper, I don’t think there are that many or there will be one specific recipe to answer the best routing algorithm. Because to my personal work experience and perhaps some what limited knowledge, most of the graph algorithms can have hybrid implementations to give better outcomes.
- Using one algorithm to find Upper bound, while another for calculating lower bound, and giving a balanced outcome.
- Other tweaks such as caching the edge weights, for faster updates when looking up a route.
- Machine Learning is a big factor for sure, but it’s not the ultimate answer for giving a route and doing an exact ETA for required destination.
- Using factors such as: Events happening and mostly taken routes.
- Weather as another factor.
- Patterns in city wide driving habit
- All above can give a very good chance for drawing conclusions for a route.
You can use some basic simulators to explore the further implementations of Dijkstra VS the other algorithms for such topic:
Pathfinding JS is an open source library for Grid based games solutions, but the maps can be considered a grid as well for simplification and drawing some conclusion on how one specific algorithm can do a better job in a scenario:
As I was talking about Waze doing a lot more recalculations using the updates weights, here is a thread mentioning how the Highway exits and turns are decided as well:
Checkout Waze’s Wiki, they are more open about some of their approaches:
The usage of the map is the most relevant thing to make a better implementation of a graph algorithm. For example the following post from Uber’s Engineering team called out Google Maps ETA not being as accurate as they wanted it to be many times:
In reality, it works just fine, but not towards the same outcome as Uber product wants it.
The gem here is that better outcome using a Dijkstra or a collection of graph algorithms on the way can be achieved depending on the need of the customer. The curse is that it can go wrong in so many ways, that’s why starting out with a simple straight forward shortest path can work really well. Then diverging to further hybrid implementations, including predictive models for some parts of the algorithms.
If you’re interested in this topic, there are some good reads online:
- (Graph Algo in Vision)
- (Semih Salihoglu and Jennifer Widom @ Stanford)
On top of all of these factors mentioned, Google still have an advantage over lots of other solutions due to the proper technologies used. Using something like BigQuery, underneath it using“ is absolutely a big push to brute force some outcomes if all else fails.
About Author: @yadfaeq, Research Software Engineer, 4th n Town Engineering