What is the optimal route for visiting Pokéstops in Pokémon Go?

Question

Okay, I've got a fun problem for you, which was not suited for the gaming stackexchange:

Pokéstops are GPS locations with a certain radius. When you are in the radius, you can get certain ingame goodies like Pokéballs. Pokéstops have a refresh rate of ca. five minutes, which means that you can camp at a location and get new items every five minutes (1 per 5 min). Maybe there's a second Pokéstop nearby, so you can alternate between those two by walking and get double the items (2 per 5 min), but you still have to wait some minutes. So, now you are running or biking and could possibly reach more Pokéstops in time. But how do you plan your velocity-dependent route to maximize your Pokéstops hit per time ratio?

There's been a recent article (http://www.popularmechanics.com/culture/gaming/a21843/traveling-salesman-problem-pokemon-go/) in which mathematicians computed a solution to the traveling salesman problem with Pokéstops in the city. But this is not optimal in the sense of maximizing your Pokéstops hits per time.

How do you model and solve this problem? Bonus points if you incorporate a velocity parameter in your solution, so that you could find solutions for walking speed, running speed or sprinting.

Answer 1

The article you refer, is not getting the max per minute, he is calculating the most efficient route passing by all pokestops without repeating pokestop(euler paths or hamiltonian paths i cant remember)

For your question, i would select the part of the map with the most pokestops and draw a circle which circumference path is 5 min of walking or riding. so you have an enormous area covered. So you start and when arrive to the same point all the pokestops are reseted and start again

Answer 2

Let's say you have this graph as your set of nodes $PS_{i}$ of reachable Pokestops:

Every edge has a cost factor $\alpha_{j}$ in minutes or seconds. $\alpha_{j}$ is depending on your characters speed. For simplicity, the self-connecting edges of $PS_{i}$ have an $\alpha_{j}$ of 5. Because of 5 minutes waiting time and the other values are randomly chosen for demonstration purpose.

Create an adjacency matrix for the graph with the associated $\alpha_{j}$.

Afterwards you can model the problem (transportation problem) as a basic linear programming model and use the simplex algorithm to solve it. In this case, $x_{1}$ refers to the first entry in the table and $x_{9}$ to the last. It's also important that $x_{i}$ is an integer.

$$Minimize\ 5x_{1}+2x_{2}+x_{3}+2x_{4}+5x_{5}+3x_{6}+x_{7}+3x_{8}+5x_{9} $$ $$subject\ to\\ x_{1}+x_{2}+x_{3}=1$$ $$x_{4}+x_{5}+x_{6}=1$$ $$x_{7}+x_{8}+x_{9}=1$$ $$x_{1}+x_{4}+x_{7}=1$$ $$x_{2}+x_{5}+x_{8}=1$$ $$x_{3}+x_{6}+x_{9}=1$$

You can refine this model but this a basic approach to solve such problem. If you need alternatives like sprinting or walking, you can add such by extending the objective function and additional constraints.

In general, this approach is visiting all stores in a given period with the least cost/effort.