IQ Routes - Using Historic Travel Data for More Efficient Routing
All modern navigation engines use a derivative of the Dijkstra’s Algorithm, a search algorithm developed by Dutch computer scientist Edsger Dijkstra that finds the shortest path tree in any graph tree. To illustrate, you have to think of the road network where every junction is a node. Whenever you ask your personal navigation device for a route, it begins to look outwards from your current location until it comes to a junction, whereby it that ventures out into all the possible routes and continues looking. With this, the navigation engine has to explore up to a million nodes for a typical 100km route.
However, the shortest route from Point A to be Point B may not necessarily be the fastest, that’s because actual travel speed greatly affects the time taken. For that, TomTom introduced IQ Routes, which uses real measured speed data collected anonymously over the past six years from its 70 million users to calculate not just the shortest route, but also the fastest.
First, you might be wondering, how did TomTom obtain this all data? From users of it personal navigation devices of course. These travel data is logged onto the TomTom device and then uploaded to TomTom whenever the user connects the device to his PC to update it.
For years, TomTom has been asking users of its personal navigation devices if they would be willing to share travel data to help make a better product. Admittedly, even TomTom themselves were skeptical at first that users would be willing to share data, but according to them, well over 90% of their users were willing to do so if it would help make a better product.
And as TomTom stressed to us time and time again, the data collected is entirely anonymous. As co-founder Peter-Frans Pauwel said, there’s no point in keeping track of who is going where - what they want is the raw travel data. The data collected is even truncated at both ends, so for every trip made, there’s no knowing where the exact start and end points are.
The result of all those years of data collected, is IQ Routes, which uses real measured speed of roads to determine which is the best route to take. In addition, IQ Routes also takes time into account. For instance, if you request a route during morning peak hours, the device might advise you to stay off the highway because it gets heavily jammed. However, select the same destination in the afternoon and it might tell you to use the highway instead because based on historic speed profiles, the highway is less congested in the afternoon.
What this really means for TomTom is that their maps are not just a regular network of roads, but it is in fact a time-expanded network of roads.
Of course, this all adds complexity to the routing algorithm. In fact, in Europe where there’s 50 million crossings and 120 million roads, a time-expanded network would mean 800 sextillion (8 followed by 23 zeroes) possible routes. Even with modern technology, TomTom says it will take 25 trillion years to process. However, that’s with traditional routing algorithms. To be able to search through TomTom’s time-expanded network of possible routes, TomTom has further refined their search algorithm such that it is much, much more efficient.
Apart from the historical speed and travel data, another benefit from all the data that is logged (which are known internally as "probes"), is that it can also be used to identify where changes in the roads are. As we've seen earlier in Cartopia, probe markings where are there no roads could indicate that there's a new road in the area.
That said, the limitation of IQ Routes is that it is after all based on historic travel data and doesn’t accurately depict present traffic conditions. For example, unforeseen circumstances such as an accident, fallen tree or unexpected road works could cause delays that IQ Routes would never have picked up. And this leads us nicely to TomTom’s latest innovation, HD Traffic.