Those familiar with the ongoing exploits of Bilbo the Hobbit know that he has set off on a journey to the lonely mountain. However once he reaches there he will want to return. We all do something similar in our daily lives when we journey to a place and return home, and often the route planned by sat nav if driving. But have you ever found that the route home is different from the route there?
Huge growth in satellite navigation
It was the US military that developed GPS in the 1970s and, since then, satellite-based positioning navigation and timing (PNT) have become crucial to all kinds of civilian infrastructure systems. Apart from car sat navs everything from aviation, financial-securities clearing, mining and electricity distribution to mobile telecoms, road tolling and weather forecasting also rely on GPS. It is hard to imagine how delivery vehicles and taxis found their way around before sat navs, although drivers of London black cabs still only use their Knowledge.
The total annual turnover of the global satellite navigation industry has grown from a couple of billion euros in 1995 to over 150 billion euros in 2013 and this growth is continuing as the figure below illustrates.
Between 2004 and 2010 the number of sat navs in cars in the UK grew by 7.5 million and an increasing number of people use their smartphone as navigator.
Secrets behind the route calculation
But how does the route calculation actually work? Naturally the sat nav manufacturers don’t want to reveal this as the algorithm is the heart of their business. But business analysts have a tendency to figure out things so you are in good company reading this blog as we will reveal it!
First let’s look at an example of getting different routes when travelling between the same endpoints but in opposite direction. We use the RAC Route Planner to plan the fastest route between Hunton Bridge in Hertfordshire and Leighton Buzzard in Bedfordshire. As you see below, going there the distance is 20.07 miles and takes 40 minutes while coming back the distance is 24.72 miles and takes 38 minutes and the route is different!
So how can that happen? Let’s look at the calculation process more closely. First, the navigator starts the calculation process by using satellite signals and also other signals such as mobile phone towers to define the positioning of the device and the destination. Until the year 2000 the accuracy of civilian navigators was downgraded by US military to about 100m but nowadays the accuracy is within just a couple of metres. The navigator then calculates the route by using a vector map where each straight part of a road is a vector that has information, such as road name and number and what kind of road it is, attached to it. With the vectors the route calculation becomes a travelling salesman problem where a “city” is a start and end point of each vector. So the task is to define the optimum route from point A to point B visiting all the start and end points of the vectors that make up the road between the points. Relating this to the route example above, let’s assume that all the vectors of the roads between Leighton Buzzard and Hunton Bridge are drawn in the picture below:
With a large number of different possible routes the travelling salesman problem is very hard to solve and would require a long computing time and a lot of memory. Thus the route calculation uses a heuristic or approximation approach where a good enough solution is found in a reasonable time instead of an absolute optimal solution that takes much longer to find. And with the amount of data available ( big data!) and different variables like traffic information, weather and even the emotions of the driver that people are expecting to be incorporated into solutions, the reality is that often the quality of the solution has to be compromised.
In the case of calculating the route from Hunton Bridge to Leighton Buzzard the solution is a local optimum which is close enough to the global optimum so that the algorithm stopped there. To help the algorithm get over the local optimum we added a midpoint, Wing Road, via which the route must go. As you can see below now the travel only takes 37 minutes:
Don’t trust your sat nav blindly
The point here is that even with clever calculation and optimisation techniques, the devices should not be trusted blindly, local knowledge is still very helpful and sometimes you know better than the device! Don’t switch off your logic when using sat nav! And if you are following in Bilbo’s footsteps to go mountain climbing and see a nice place for a break that you want to return to on the way back, make sure you either remember the route or tell your navigator to return via this place because otherwise it may take you back via another route!