| 1. |
- Dong, Changxing, et al.
(författare)
-
Effective Heuristics for Large Euclidean TSP Instances Based on Pseudo Backbones
- 2009
-
Ingår i: Proceedings of 8th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2009). ; , s. 3-6
-
Konferensbidrag (refereegranskat)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 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.
|
|
| 2. |
- Dong, Changxing, et al.
(författare)
-
Effective Tour Searching for TSP by Contraction of Pseudo Backbone Edges
- 2009
-
Ingår i: Proceedings of 5th International Conference on Algorithmic Aspects in Information and Management (AAIM 2009). - Berlin-Heidelberg : Springer. ; , s. 175-187
-
Konferensbidrag (refereegranskat)abstract
- We introduce a reduction technique for the well-known TSP. The basic idea of the approach consists of transforming a TSP instance to another one with smaller size by contracting pseudo backbone edges computed in a preprocessing step, where pseudo backbone edges are edges which are likely to be in an optimal tour. A tour of the small instance can be re-transformed to a tour of the original instance. We experimentally investigated TSP benchmark instances by our reduction technique combined with the currently leading TSP heuristic of Helsgaun. The results strongly demonstrate the effectivity of this reduction technique: for the six VLSI instances xvb13584, pjh17845, fnc19402, ido21215, boa28924, and fht47608 we could set world records, i.e., find better tours than the effective reduction of the problem size so that we can search the more important tour subspace more intensively.
|
|
| 3. |
- Ernst, Christian, et al.
(författare)
-
Finding Good Tours for Huge Euclidean TSP Instances by Iterative Backbone Contraction
- 2010
-
Ingår i: Proceedings of 6th International Conference on Algorithmic Aspects in Information and Management (AAIM 2010). - Berlin-Heidelberg : Springer. - 9783642143540 - 9783642143557 ; , s. 119-130
-
Konferensbidrag (refereegranskat)abstract
- This paper presents an iterative, highly parallelizable approach to find good tours for very large instances of the Euclidian version of the well-known Traveling Salesman Problem (TSP). The basic idea of the approach consists of iteratively transforming the TSP instance to another one with smaller size by contracting pseudo backbone edges. The iteration is stopped, if the new TSP instance is small enough for directly applying an exact algorithm or an efficient TSP heuristic. The pseudo backbone edges of each iteration are computed by a window based technique in which the TSP instance is tiled in non-disjoint sub-instances. For each of these sub-instances a good tour is computed, independently of the other sub-instances. An edge which is contained in the computed tour of every sub-instance (of the current iteration) containing this edge is denoted to be a pseudo backbone edge. Paths of pseudo-backbone edges are contracted to single edges which are fixed during the subsequent process.
|
|
| 4. |
- Richter, Dirk, et al.
(författare)
-
Improving the Efficiency of Helsgaun’s Lin-Kernighan Heuristic for the Symmetric TSP
- 2007
-
Ingår i: Proceedings of the 4th conference on Combinatorial and Algorithmic Aspects of Networking (CAAN 2007). - Berlin-Heidelberg : Springer Berlin/Heidelberg. - 3540772936 - 9783540772934 ; , s. 99-111
-
Konferensbidrag (refereegranskat)abstract
- Helsgaun has introduced and implemented the lower tolerances (-values) for an approximation of Held-Karp’s 1-tree with the purpose to improve the Lin-Kernighan Heuristic (LKH) for the Symmetric TSP (STSP). The LKH appears to exceed the performance of all STSP heuristic algorithms proposed to date. In this paper we improve Helsgaun’s LKH based on an approximation of Zhang and Looks’ backbones and an extension of double bridges further combined with implementation details by all of which we guide the search process instead of Helsgaun’s -values. Our computational results are competitive and lead to improved solutions for some of the VLSI instances announced at the TSP homepage.
|
|
