Effective Heuristics for Large Euclidean TSP Instances Based on Pseudo Backbones
2009 (English)In: Proceedings of 8th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2009) / [ed] Sonia Cafieri, Antonio Mucherino, Giacomo Nannicini, Fabien Tarissan and Leo Liberti, 2009, 3-6 p.Conference paper (Refereed)
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 pre-computed good tours. Using this approach we found record tours for seven VLSI instances. The second approach is window based and constructs from scratch very good tours of huge TSPinstances, e. g., the World TSP.
Place, publisher, year, edition, pages
2009. 3-6 p.
IdentifiersURN: urn:nbn:se:umu:diva-84459OAI: oai:DiVA.org:umu-84459DiVA: diva2:684256
8th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2009).