Using a three-opt algorithm, we found the following proposed shortest tour of all the MN state parks and recreation areas. The route is about 2850 miles long.
Constructing a tour like this turns out to be a hard problem known as the "Travelling Salesman" problem. While there are algorithms that can find the guaranteed shortest route, they get complicated, and complicated is no fun to program. Here, we'll try out the three-opt algorithm.
In short, the three-opt algorithm starts with a random tour of the parks and at each step considers three pairs of connected parks. If a rearrangement of the connections gives a shorter tour, the algorithm picks the shortest such rearrangement. This continues until no better rearrangement is found. It is important to run the algorithm many times to ensure that it picks the best route instead of just a good one. Nevertheless, three-opt remains a heuristic, so the route presented here still may not be the best. All we do is propose that it's pretty good.
For reference, here are the parks in order of the route (also in a CSV):
Tettegouche State Park
Temperance River State Park
Grand Portage State Park
Judge C.R. Magney State Park
Cascade River State Park
George H. Crosby-Manitou State Park
Bear Head Lake State Park
Lake Vermilion-Soudan Underground Mine State Park
Iron Range Off-Highway Vehicle State Recreation Area
