A slight change on the question may give you a better perspective. Instead of "how do I pass over the most given a specified location", instead figure out "given X moves, what is the best starting position & path". This gives you a one time problem, which you may be able to apply more resources to. Once you do that, you have a single sub-optimal day where you move to your new starting location, and then you just cycle through the pattern and it's reverse on alternate days.
in reply to Graph Traversal
...you might be eaten by a grue...