Proc. of the 8th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, Ecole Polytechnique and CNAM, Paris, France June 2-4, 2009

Abstract: We present two approaches for the Euclidean TSP which compute high quality tours for large instances. Both approaches are based on pseudo backbones consisting of all common edges of good tours. The first approach starts with some precomputed good tours. Using this approach we found record tours for seven VLSI nstances. The second approach is window based and constructs from scratch very ood tours of huge TSP instances, e. g., the World TSP.

Download:  ctw09.pdf