The tour of Gaia DR1 stars begins and ends at our sun, moving in straight lines through 3-dimensional space, from star to star to star, visiting each of the 2,079,471 locations. The itinerary is given in the following three gzipped files.
• gaia2079471_tour.txt.gz, a list of integers from 1 up to 2,079,471, giving the order the stars appear in the tour,
• gaia2079471_order.txt.gz, the points for gaia2079471 permuted in the tour order,
• gaia2079471.288843524.tour.gz, the tour in TSPLIB format.
The tour's total length is 28,884,352.4 parsecs, measured as described on the data page. It might not be an absolute shortest-possible solution, but we have proven, using linear programming and lots of computing power, that no tour for gaia2079471 can have length less than 28,884,139.0 parsecs. So we are at most 213.4 parsecs longer than an optimal tour.
The remaining gap, between our tour length and the linear-programming bound, is still a good step, as they say in The Culture. But, compared to the total length of the route, it's barely measurable. Less than a factor of 0.0000074. That's a close approximation.
Nonetheless, it would be great to see progress in TSP methods to produce an even better tour. So, to push this along, I'm offering a reward of $50 for each parsec you can save by rearranging the 2,079,471-star tour. Check out the Challenge page for details on how to pick up your cash.
The Tour -- Zoom, pan, and rotate the point set to see the 3D structure. Stars are represented by twinkling points, using color to represent each star's position in the tour. The tour is traced by colored lines.
Animation -- See the tour grow segment by segment.
Light version -- Stars are represented by colored particles, resulting in an image that is easier to render (in case you have trouble with the main version).
Particles -- An even lighter rendering, where no edges are drawn. The tour is represented by the colors of the particles.
