What is the 280-year-old algorithm used in Google's travel application?

ByCeleste RC

"Google released on 20th September 2016"Google TripsIs an application that can manage information on travel as a whole and can automatically manage the travel plan based on various information such as the way of traveling to the destination and directions, traveling time, the location of the sightseeing spot and restaurants in the vicinity You can make it. According to Google, the algorithm used for this Google Trips is based on what was 280 years ago, and Google reveals the details on official blog.

Research Blog: The 280-Year-Old Algorithm Inside Google Trips
https://research.googleblog.com/2016/09/the-280-year-old-algorithm-inside.html

Google Trips - Android application on Google Play
https://play.google.com/store/apps/details?id=com.google.android.apps.travel.onthego

Google Trips is an app that can organize a detailed schedule of the day before going to the site and it plays an assistant role of the trip and automatically thinks of the best travel plan, but it is surprising Especially, the algorithm used in this application was invented 280 years ago.

Swiss mathematicianLeonhart EulerI wrote a mathematical paper on the city Königsberg and the seven bridges in the city in 1736, which was in the former East Germany. In this paper it is written that "It is possible to cross all seven bridges with a single stroke?", And the answer that Euler issued is "impossible". To reach the answer impossible Euler knit one method to express the land and bridge layout, later named "Geometriam Situs".


Geometriam Situs invented by Euler is one of modern mathematical theories "Graph theory"is. Graph theory is a theory concerning a graph consisting of nodes (six contact points) and edges (sides connecting contact points), Euler expressed land as a node and a bridge as an edge as shown in the following figure.


Euler notes that "although it does not apply to Königsberg, the stroke is only established if the number of edges that touch the node is the same at each node."


Impressed by Euler's Geometriam Situs, Google Research nicknamed this "travel schedule issue" to solve the question "How can I travel a lot of tourist attractions in a single trip?" . In order to solve this problem, it was necessary to achieve two objectives, "pick up tourist spot" and "to incorporate tourist spot picked up in travel schedule". Especially the second one has issues such as "Short traveling time", "Do not visit when sightseeing spots are closed", "Do not visit similar sightseeing spots such as art museums" and so on, It seems that we had a lot of trouble in building algorithms to search for good routes.

In order to make it possible to search efficient routes, GoogleCristo feed approximation algorithmI used it to solve the problem. By using the Christo feed approximation algorithm, it is possible to present the shortest one among the "travel route connecting multiple destinations" as a search result. The figure below shows how routes are narrowed down using the Christo feed approximation algorithm.


After building an efficient route search algorithm, calculate the merits obtained by visiting sightseeing spots and admission fee of tourist attractions for each tourist attraction. The merit that users can get by visiting sightseeing spots is derived from the popularity of tourist attractions and the difference from sightseeing spots that have already visited. The following figure shows how to build a tourist route in London, the leftmost is "Route to and from Westminster Abbey from Big Ben", but by using algorithm, the most right "Westminster from the temple James Park, Big Ben, Buckingham Palace, Hyde Park route "will be presented.


In Google Trip, "my friend recommended this place and I can only use it for sightseeing in the morning, but I'd like to go for a sightseeing spot in the afternoon in the morning" It incorporates algorithms that can respond to personal demands from users such as.

It is shocking that the latest application was invented 280 years ago. Google Trips, which seems to be useful in traveling because it can be used offline, can only install at the time of article creation, but it does not correspond to Japanese, so it is expected to release Japanese version.