Article by: Mike Barrett on 4Sep2012

Having discovered how the basic maps are made and maintained we now turn to some of the more interesting innovations that TomTom have added to their maps. The third article in our series of How TomTom make digital maps looks at routing. In particular I am looking at the IQ Routes technology that TomTom introduced a few years ago in an attempt to ensure that users are provided with the best routes possible.

As mentioned in the MapShare article TomTom have been collecting information from users for a number of years. Partly this data is used to determine and identify changes to the mapping data, but the most important data set is the real speeds over road segments. This means that for the first time routing could be based on real statistically average speeds.

Traditionally when calculating a route the posted speed of the road was used in the calculation. Thus a 1 mile section of road with a speed limit of 30MPH would be assumed to take 2 minutes to travel. The astute amongst you would realise that because a road speed is 30MPH you are unlikely to achieve that so a percentage of the speed limit would be used to calculate the time to drive a segment of the trip. As there was no other data available that was the only way to do it. Indeed going back further in time there were only road classifications with no speed limits associated with them. This made the prediction of arrival times very unreliable. It also meant that a 40MPH dual carriageway could be given the same speed profile as a residential road in some circumstances.

TomTom introduced trip recording way back in 2005 and in the intervening years have managed to record over 5,000,000,000,000 real speed readings on the roads. These speed recordings were averaged and overlaid on the map data for each section of road resulting in real speed profiles for all the roads. This means that when creating a route for each section of road TomTom can ignore the posted speed limits and use the average recorded speeds. The resultant route is statistically the best way to get from A-B. This technology was called IQ Routes and introduced some interesting routes that maybe drivers would not consider.

Now when IQ Routes was originally introduced back in 2008 there was just one 'real' speed associated with each segment of road. This was, of course, a big advantage over traditional routing calculations but did not take into consideration things like morning and evening rush hours, or the quiet periods in the middle of the night. I would be quite happy to drive through the centre of London in the middle of the night, as long as I did not go anywhere near the West End, but would only go there during the day if I had to. To overcome this issue TomTom gathered more time related data and then updated IQ Routes.

IQ Routes now has the capability to determine the average historic speed of a section of road for not just each day of the week, but in 5 minute intervals throughout the day. That represents 2016 speed profiles associated with every single road segment in the map. To put that into some form of context the maps of Europe contain about 120 million road segments so doing the math we get about 242 billion speed profiles in the map data.

With all this data the routing engine has a wealth of information to create a route from A-B so TomTom are now presented with a different problem: how to efficiently process so much information providing the best routes in a timely manner. This is where the TomTom rocket scientists come to the fore… I don't pretend to understand how the routing engine works. You need a degree in applied maths to even talk to the TomTom engineers. However I will try to explain the challenges that they have managed to overcome.

In order to get from A to B the application has to examine a large number of possibilities. The further you travel the more options have to be explored. If you start your trip you normally have 2 options of direction to travel so the routing engine has to look at both of them. If you follow one option you will get to a junction this will then increase the roads you need to examine by 2, or more. Each of these roads need to be examined creating a huge matrix of possible routes. But you cannot just look at roads that take you in the direction of your destination. Sometimes it will be much faster to travel away from your destination to join a faster road.

As I mentioned earlier each road segment has a time related speed associated with it, and this is also taken into consideration for the routing. So if you start your trip at 15:00 on a Wednesday and it takes say 20 minutes to get to a location then the speed for the next road segment will be the Wednesday 15:20 timed one. This becomes more critical when we look at HD Traffic in the next article.

So you can see that the further you travel the longer it will take to calculate the route. In fact for a 60 mile trip the navigation engine has to examine up to 1,000,000 junctions representing about 2.5 million roads. Now this is OK if you are sitting at your desk with the huge resources of a server generating the route, but a PND or SmartPhone just simply does not have that computing power. So obviously steps need to be taken to optimise these calculations.

TomTom have developed technologies that they have called "FAST & EXACT" these are claimed not only to provide you with the best (quickest) routes but also to reduce the time to calculate and more importantly recalculate your trip. I remember back in 2009 when the first TomTom Start came out it took an incredibly long time to re-route and then instantly went into re-routing as soon as the route was generated. The only way to get it to re-calculate properly was to stop and wait the 30 seconds until it recalculated the route. Then you have to turn round at which point it starts recalculating! This was obviously not the user experience that you would expect and the "FAST & EXACT" technologies were created to countered that.

With the FAST and EXACT software TomTom have included pre-calculated routes. This means that the SatNav does not have to calculate or recalculate the entire route each time it is required and the device can use one of the numerous pre-determined routes. I am not entirely certain how this works, but empirical testing provides proof that it does.

The probe data used for IQ Routes also has other value to TomTom. As it represents real data from around 60 million users that data can be analysed in a number of ways, some of them controversial. Last year there was an outcry when TomTom sold the road speed profiles to the Dutch Police. This enabled the Police to target the roads where statistically drivers break the speed limit and at the time that they are most likely to. Note that this was all based on anonymous statistical data collected, not individually identified SatNav owners.

In a more acceptable manner the data is used to analyse the traffic flows. This means that looking at the traces around intersections it is quite easy to determine how the traffic flows at various times of the day. Indeed it is possible to automatically detect the junctions that have stop signs, and differentiate them from those that have traffic lights.

Having mentioned traffic lights, not only is it possible to detect the intersections that have traffic lights, it is also possible to see how the lights affect the movement of traffic through the junction on both sides of the road, including drivers making turns. Given the right analytic software and good data it is possible to profile the junctions and tune the light sequences to provide statistically optimal traffic flows at different times of the day. All this can be achieved from looking at the probe data from the users without any roadside hardware at any of the junctions.

So from this you can see that the technology driving IQ Routes doesn't just benefit the TomTom SatNav community. The probe data provides valuable information to the infrastructure planners as well generating a knock-on effect to all road users. This is really the tip of the iceberg with the wealth of intelligence being collected there will be many more innovative ways to analyse and profile our driving over the coming years. Some may find this intrusive and offensive, others will welcome it with open arms, along with the potential benefits it brings to our busy lives.

Our look at IQ Routes being complete it is easy to see the benefit of better routes and more accurate arrival times. The next article takes a view of TomTom's HD Traffic and how this sits on top of the stack of map infrastructure to provide live dynamic adjustments to the mapping information.

Tweet