Pokémon Go and the Traveling Salesman Problem

Gotta catch 'em all? As quickly as possible? There is a math model for that. It's called the traveling salesman problem. You've probably heard that the TSP is a tough nut to crack: it takes forever to check every possible route to pick out the shortest.

Fortunately, the math world has been studying the TSP for over sixty years and the best-known methods can be combined to make short work of finding the shortest possible route for the Pokemon hunter-gatherer. If your Pokemon area has hundreds, or even thousands, of stops, mathematics can both find the best route and prove it is the shortest possible without going through all the candidate solutions, one by one by one.

WCPO in Cincinnati put together a nice map of some 551 Pokestops and Gyms. This is like waving a red flag in front of TSP solvers! The map below shows the optimal way to reach, by foot, all 551 stops.

Cincinnati tour. Click for a full image. For an interactive version Click Here.

You'll need a good pair of shoes to walk the entire route. The tour clocks in at 223 miles. To be precise, the tour takes 358,331 meters, using point-to-point travel distances from Google Maps. The method used to obtain the distances (without asking Google for every pair) is described in the College Tour page.

The tour is not only a good one, it is the best one. That is, given the Google point-to-point distances, this is the shortest possible way to reach all 551 stops and return to your starting point. Here is a list of stops in the optimal order.

The total computation time on a Mac Mini was 101 seconds.

It took a few extra days for the game to come to Canada, but soon afterwards a good map of Toronto appeared. The map includes points well out in Brampton, Mississauga, and Lake Ontario. I pruned these to obtain a set of 109 stops.

Toronto. Click for a larger image. For an interactive version Click Here.

The shortest-possible walking tour covers 148,706 meters. Here is a list of stops in the optimal order. The TSP computation took 0.17 seconds on a Mac Mini.

The Pokemon Go NYC group city is keeping an up-to-date map of rare Pokemon findings. Here is the shorestest waling tour to visit their 68 locations.

New York City. Click for a larger image. For an interactive version Click Here.

The computation time to find this shortest-possible 68-point tour was 0.1 seconds on a Mac Mini. Here is a list of the stops in the optimal tour order.

The total total length of the tour is is 215,060 meters (133.6 miles). I know that is too long for a walk, taking you way out past JFK Airport. Sticking just to Manhattan would give you enough Pokemon and exercise for an afternoon.

There is a great Pokemon map of Boston. You can read about it in Polygon. The optimal tour to vist the 518 stops is given below.

Boston. Click for a larger image. For an interactive version Click Here.

Here is a list of the stops in the optimal tour order. The total computation time was 165 seconds on a Mac Mini. The walk is again on the long side, totaling 351,003 meters (218 miles). It covers the greater Boston area, including Cambridge, home of MIT.

Boston tour visits MIT.

Curbed SF has a very nice map of 99 Pokemon Go stops in San Francisco. Here is the quickest way to see them all.

San Francisco. Click for a full image. For an interactive version Click Here.

The full walking tour would be a long day at 104,503 meters (or 65 miles). Here is a list of stops in the optimal order. It took 0.1 seconds to compute on a Mac Mini.

There is also a Pokemon map of Atlanta, described in the Atlanta Journal Constitution. The optimal walking route through the 988 stops is given below.

Atlanta. Click for a larger image. For an interactive version Click Here.

The stops cover the greater Atlanta area and the tour weighs in at a hefty 900,041 meters (559 miles). But you can still see nice small segments, such as the route through the Georgia Tech campus.

Atlanta tour passes through Georgia Tech. Click for a larger image.

The computation time was 12.25 seconds on a Mac Mini. Here is a list of stops in the optimal order.

Team Houston has put together a huge map of Pokestops. When I picked up their data set on July 12, it contained 2,008 sites! I'm afraid the 2,121,499 meter (1,318 mile) walking tour is not going to attract many takers. But maybe some segments of the shortest tour will be useful in the big hunt.

Houston. Click for a full image. For an interactive version Click Here.

This instance was a challenge to solve with our iterative method of only calling for Google point-to-point distances when we really need them. The difficulty appears to be the very long walking paths to get down to Galveston from the center city. (Google rightly assuming that you don't want to stroll down I45.) Our method required 34 rounds of Google queries and over two hours of computation on a Mac Mini. Once the correct data set was found, the final TSP was solved in 484 seconds.

Here is a list of stops in the optimal order. Of course, the tour passes through Rice University.

Houston tour visits Rice University and Hermann Park.

Not to be left out, the Denver Post collected a list of Pokestops in Denver. Here is the shortest way to visit all 83 of them.

Denver. Click for a full image. For an interactive version Click Here.

This walk covers 13,153 meters. Here is a list of stops in the optimal order. The computation of the tour took 0.07 seconds on a Mac Mini, once point-to-point data was collected from Google Maps.

Here is a Pokemon Go tour of the University of Missouri. It covers 17,618 meters to pick up the 106 Pokestops reported in the Missourian

University of Missouri. Click for a full image. For an interactive version Click Here.

Here is a list of stops in the optimal order. The computation required 0.11 seconds on a Mac Mini.

A shortest-possible walking tour of 154 Pokestops on the campus of Kansas State University. The data for the problem was collected by The Collegian

Kansas State University. Click for a full image. For an interactive version Click Here.

The length of the tour is 22,453 meters. Here is a list of stops in the optimal order. The TSP took 0.16 seconds to solve on a Mac Mini.

Many thanks to Rahul Swamy for sending a link to his map of 55 Pokespots and Gyms in his home town of Champaign, Illinois. Here is the optimal walking tour.

Champaign, IL tour. Click for a full image. For an interactive version Click Here.

You should be able to walk this one in an hour or so: the total distance is 6,424 meters. Here is the list of stops in the optimal order. It took 0.05 seconds to compute on a Mac Mini.

WSLS10 put together a Pokemon Go map of Roanoke. The tour below is the shortest possible walk for the 230 stops.

Roanoke tour. Click for a full image. For an interactive version Click Here.

Here is the list of stops in the optimal order. The total length is 96,099 meters (about 59.7 miles). The computation time to solve this TSP example was 5.89 seconds on a Mac Mini.

Credits

• WCPO Cincinnati Pokestops/Gyms Google Map. The locations to visit in the Cincinnati tour were taken from this map in the morning of July 12, 2016. WCPO credits the map to Andrew Briz.
• Hey Siri, how can I solve the TSP? Video describing the method used to compute the optimal tour.
• In Pursuit of the Traveling Salesman Problem In this book you can pick up all you need to know to start your own attack on the TSP and maybe pick up a $1,000,000 prize from the Clay Math Foundation.