The European Space Agency has a long history of mapping the skys. Going back to a 1989 launch, its Hipparcos mission generated an important early catalogue of 118,218 stars, during three and half years of observations.
The 109,399-star tour, shown in the moving image, is the shortest possible route through the core stars of the HYG collection, where point-to-point travel is measured by straight-line 3D Euclidean distance, rounded to the nearest 1/10th parsec.
The computation took 10 days on a network of processors, for a combined 127.7 days of compute time. The result has a claim as the largest test instance of the TSP to be solved to exact optimality, but it comes with an asterix. First, the full 119,614-star HYG instance was also solved optimally, but it would be cheating to count that as a single example, given the outer rim of 10,215 points. Second, although this star instance has more points, the shortest crawl to 49,687 pubs in the UK was actually much more difficult to solve.
Click "Full View of Tour" in the top bar to fill the window with the tour drawing; the full view includes a piano piece Corona, composed by Dan Naiman.
• David Applegate, Google Research
• Robert Bixby, Gurobi Optimization and Rice University
• Vaek Chvátal, Charles University
• William Cook, University of Waterloo and Johns Hopkins University
• Daniel Espinoza, Google Inc.
• Marcos Goycoolea, Universidad Adolfo Ibanez
• Keld Helsgaun, Roskilde University
For a guide to navigating the moving image, click the ⓘ button in the top right corner of the page.
The computations were carried out on systems located at Roskilde and Waterloo. We thank our universities for their support.
We thank Bob Vanderbei for pointing us to the HYG database and Michael Boyle for suggesting the use of color hue to indicate the order stars appear in our solution.