Star TSPs


Why 3D?

Astronomy has its own set of useful TSP applications, centered around the operation of telescopes. Such applications involve 2-dimensional movements of the big scopes from target to target, using motor-driven gears. It's hard to argue, from the direct applied side, that we should instead look at ploting geometric tours through 3-space to visit our neighbors, in ships that don't exist. Indeed, other fun projects, such as designing the optimal route for the world's longest pub crawl, have more of a whiff of an application. Just with 49,678 pints instead of the usual 4 or 5.

But the reason for studing 3D tours is same as our real motivation for the pub crawl: we want to push computational testing of TSP methods to new classes of large-scale instances. For several decades, all large tests consisted of a single type of problem. Namely, points drawn on a sheet of paper with travel measured by straight-line distances. The pub crawl used instead the actual (sometimes twisting or backtracking) shortest walking paths from pub to pub, provided by Google Maps. In the 3D examples, we use straight-line distances, but the extra dimension gives the star problems quite a different flavor. The hope is that with a wide range of TSP test data, we have a better chance to develop general-purpose methods applicable to new and varied classes of optimization models.