A TSP Variant – An efficient route for visiting all counties in a state ?

i was reading a bicycle tourist’s idea of visiting every county in his home state. He had diligently chipped away at the goal for a number of years, visiting a few at a time.

The question occurred to me as to how we would route that if you wanted to do it in one fell swoop (assuming one had the physical ability to do so). It’s sort of the variant of the famous traveling salesman problem (TSP), but with a couple of differences.

If we decided we wanted to visit a consistent location in each county (say the county seat, or maybe the centroid of the county), then it would be exactly the traveling salesman problem. But I’m thinking of a slightly different formulation. Visiting a county in this formulation is merely setting foot in said county (equivalent to saying I’ve been to Wisconsin if I’ve been anywhere at all in Wisconsin, rather than having to had visit the capital of Madison in order to count it as having visited the state)

So how does this effect our attempted solution to the problem ?

1. The most significant, it would seem, is in construction of the distance matrix. In a standard TSP problem, we usually use some agreed upon distance matrix between locations. So when we try to solve the problem of visiting all county seats in a state, for instance, we know all the points we might visit in advance. So we might use Google driving distance as our distance metric and we can calculate all the distances in advance. And while we may have multiple routes possible to get from one stadium to another, we might agree to take Google’s shortest suggestion as our distance. In our new formulation in this problem, we need to determine what the distance from one county to another is. How do we do this.? Is it the smallest distance between any two points in the two counties ?

2. The entrance point to a county (stepping into the county) is not necessarily (and almost certainly not) the same point where we leave the county to enter the next county. So we need to account for this, as well as any distance traveled within a county to get from the entrance point to the exit point of a given point.

So I don’t know if this is a well known variant of the TSP, but it’s something I will look into over some upcoming posts.