Route optimisation takes another leap with Google Maps
Many users rely on Google Maps to find the best route to get from one point to another, regardless of the means of transport employed. But, what if you need to go to several places and then return to the original departure point?
The Travelling Salesman Problem (TSP) regarding route optimisation is a well-known issue in computer science due to its widespread nature and usefulness. This problem was first raised in 1930, and can be applied to many fields: logistics, planning, microchip manufacture, and it even appears in DNA sequencing.
It is basically about finding the ideal route to reach a number of locations defined on a map, and then returning to the point of departure, but we are not talking about only visiting a couple of places. Although the approach is simple, TSP is one of the most intensely studied problems by computational mathematics and, despite this, an effective solution for general cases has not been found. In fact, solving it would be worth a 1 million dollar prize offered by the Clay Mathematics Institute, since it would give the answer to the problem of P vs. NP.
Google’s solution to find the best route
Google did not want to miss the chance to contribute their solution to optimising routes and the TSP, and they calculated their proposal using the Google Directions API. To what problem did they actually apply it? The problem was to find the shortest route on foot to about 24,727 pubs in the United Kingdom. And what data source did they use as reference? To identify the places that had to be visited – and to ensure the list was as up-to-date as possible – they used the United Kingdom Pubs Guide, Pubs Galore.
Using the geographical coordinates of the 24,727 pubs, they measured the distance between each pair of them based on the route produced by Google Maps. And how did they pair them? This task is not easy either because combining all the establishments would require no less than 305,699,901 combinations of pairs of pubs.
The conclusion was the following: the optimal route would cover a distance of 45,495,239 metres. Google ensures that there is no shorter path between all of them, using the measurements that Google’s own service provides. According to Google’s experts, calculating the ideal route between pubs is the most complicated and extensive TSP ever calculated, multiplying the stops required in any other previous example calculated by other researchers by 100.
We love challenges at Intelligence Partner, and we found this one, which we have posted on our blog, very interesting. Fortunately, our customers request things that are easier and, you can be sure, our technological expertise allows us to tackle them quickly and effectively. More specifically, in the field of geolocation, as a Google Maps Premier Partner, we apply technologies such as the Google App Engine, Google’s APIs, Android, Google Maps, Force.com, and developments using JAVA, JAVASCRIPT, PYTHON, PHP and .NET.
Contact us if you have a challenge in the fields of logistics, navigation, geo-positioning, advanced map visualisation, etc. and if you need a travel partner to help you solve it.
