Imagine a traveling salesman with a list of cities he must travel to only once while covering the shortest possible distance, before returning to his starting location. This "traveling salesman problem" has been studied for decades, and its origins can be traced back to a research paper written in 1736. Algorithms used to solve this problem are now helping plot travel itineraries through Google's new travel app, Google Trips.
The app itself seems relatively straightforward. For 200 cities around the world, Google Trips brings up day plans that incorporate attractions, landmarks, things to do, places to eat, and other points of interest. Those basic tours are based on popularity and what other visitors have recommended in the area, but each user can customize their own day plan around their particular interests, how long they have or a particular attraction they may have in mind.
So for example, a visit to Paris wouldn't be complete without seeing the Eiffel Tower, but if you only have an afternoon before jetting off again, Google Trips can adjust its suggestions to recommend other things to do in that area. Then, it builds a plan to get you from each point in the most efficient way possible. Math might not be on most travelers' minds when they're exploring a new city, but it's a vital part of how Google Trips makes sure a vacation isn't wasted fussing over all the little details. And that's where the 280-year old algorithm comes in.
Back in 1736, Swiss mathematician Leonhard Euler pondered a seemingly mundane question: could someone walking around the city of Königsberg cross each of the city's seven bridges only once? In his paper on the subject, Euler developed a general method for plotting out the problem visually, which can be applied to any layout and amount of points and paths between them. He called it the Geometry of Place, but scientists now know it as Graph Theory.
In the case of Königsberg, it was impossible to cross each bridge just once, and the problem lays in the fact that there were seven of them. When presented in an abstract graph, with the landmasses shown as "nodes" and the bridges as "edges" that connect them, Euler noticed that a cycle where each edge is visited just once is only possible with an even number of edges.
So how does this relate to deciding what to see on your day out in Prague? Well, the Google Research team was inspired by this idea, and began investigating how it could be used as the basis for an itinerary algorithm that incorporated as many interesting "edges" as possible and decide which ones to suggest and help direct travelers between them efficiently. This circles back around to the traveling salesman problem mentioned earlier, which the team solves (at least approximately) with the Christofides algorithm.
In any given city, destinations (in the graph terms, nodes) are pulled from existing Google data and then connected according to proximity. Any nodes that have an odd number of connections are then carefully paired up, to avoid the pitfall of Königsberg's seven bridges. That creates an Eulerian route, which loops through each of the given destinations once each (simply ignoring any double-ups), and returns to its starting point.
But a traveler might not want to visit every single place Google suggests automatically. To create a more dynamic algorithm for day trip planning, Google Trips also takes into account the "value" of an attraction relative to the cost of visiting it. Things like the attraction's popularity, location, uniqueness, and the user's interests are all factored in, so if a place is out of the way and too similar to something else on the path, it might be left off. If a visitor specifically wants to see a place that the algorithm ignores (or vice versa), it's flexible enough to build a new itinerary around those preferences.
The Google research team is continuing to work on developing the effectiveness of the app by analyzing data about how people move between places and how long they stay at each. Harnessing this kind of crowd wisdom allows the app to account for times when attractions may be busy or closed, or when certain events are happening that may prioritize one location over another.
Google Trips is available now on Android and iOS.
Source: Google Research