In a previous post, we discussed the problem of determining an efficient route to visit every county. Part of that post explicated the difficulty of even defining the problem. In this post, let’s take a look at using space filling curves (SFC) to address the problem. In other posts, we had discussed using SFC to address the traveling salesman problem (TSP). Let’s look at applying these to our current problem; in particular, they seem to let us skirt some of the definitional problems we encountered in our previous post.
Specifically, using SFC obviates the need to define where we enter and exit a county and where we head net when we are in a county. As in other SFC problems we discussed, we are just going to overlay a SFC over the state and then trace the curve as our route. As we trace, we’ll note when we are entering a previously unvisited county.
A new issue introduced with this method is we will most likely visit a given county more than once. Whether this matters at this point is unclear. For now, let’s keep our eyes on the prize: creating an efficient to visit each county in a state. We’ll start with one of my favorite biking states – Wisconsin. Our basic steps will be to 1) determine a bounding box for the state, 2) create a space filling curve within that box and 3) traverse the space filling curve from its start to its end, accounting for each county as it is first visited.
Determining a boundary box for Wisconsin
We could do this in any most GIS software (e.g. ArcGIS or QGIS), but for our purposes we will just use good old Google maps and sort of eyeball a bounding box by determining the extreme most north, south, east and west points (in lat and long coordinates). These are , respectively, 46.972535, 42.512362, -86.834162 and -92.898615. Note these may not be exact, but we don’t really need exacting precision here.
Create a space filling curve within the bounding box
We did something similar like this previously when we introduced this concept. Here’s an example of a fairly coarse curve overlaid on the county map of Wisconsin. We’ll likely use a finer curve, but this is better for illustrative purposes, as a finer curve doesn’t look as clear. We’ll traverse this curve from the southwest corner, ending up in the southeast corner.
Traversing the curve – Results
We can do this programatically as before and for now we’ll just show the results visually. The route highlighted below was derived from traversing a space filling curve that is a little finer than that shown above.
How does it look ? Well, it seems like a reasonable enough route, except for the NE corner portion. That portion , with Door County highlighted in green, actually requires a drive over water, which seems to be a weakness of this approach. Just using the naked eye, it would seem to be a reasonably efficient drive to come just around that bay, but the SFC can’t find it with the straight forward method we are using. So it seems this method will suffer a bit with odd shapes like that. Still, unusual shapes like that (or any sort of “isolated” destination) will likely cause problems for most solutions. Consider a baseball road trip to all the MLB stadiums; at some point, you’ll always have a drive out to Seattle and back that seems out of the way. But the SFC approach here is actually returning a route that is NOT driveable and it’s not clear given the nature of an SFC (essentially one continuous curve in an area) how once would work around this.
In any case, we should compare this method versus others for a more neatly shaped area that doesn’t have this sort of unusual shape.
