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 ESA data make up the bulk of the popular HYG Database, combining the Hipparcos, Yale Bright Star and Gliese catalogues.
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.
Full View
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.
Research team
• David Applegate, Google Research
• Robert Bixby, Gurobi Optimization and Rice University
• Vašek 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
Notes
For a guide to navigating the moving image, click the ⓘ button in the top right corner of the page.
Links to lots of information on the mathematical techniques we have employed can be found on the TSP home page and on the LKH web site.
Details on the point set for the star TSP instance are given on the Data page; further images can be found on the Tour page.
The computations were carried out on systems located at Roskilde and Waterloo. We thank our universities for their support.
The tour is rendered with the three.js JavaScript 3D library.
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.