TY - RPRT
A1 - Fischer, Thomas
A1 - Merz, Peter
T1 - Embedding a Chained Lin-Kernighan
Algorithm into a Distributed Algorithm
N2 - The Chained Lin-Kernighan algorithm (CLK) is one of the best heuristics to solve Traveling Salesman Problems (TSP). In this paper a distributed algorithm is proposed, were nodes in a network locally optimize TSP instances by using the CLK algorithm. Within an Evolutionary Algorithm (EA) network-based framework the resulting tours are modified and exchanged with neighboring nodes. We show that the distributed variant finds better tours compared to the original CLK given the same amount of computation time. For instance fl3795, the original CLK got stuck in local optima in each of 10 runs, whereas the distributed algorithm found optimal tours in each run requiring less than 10 CPU minutes per node on average in an 8 node setup. For instance sw24978, the distributed algorithm had an average solution quality of 0.050% above the optimum, compared to CLK's average solution of 0.119% above the optimum given the same total CPU time (104 seconds). Considering the best tours of both variants for this instance, the distributed algorithm is 0.033% above the optimum and the CLK algorithm 0.099%.
T3 - Interner Bericht des Fachbereich Informatik - 331
Y1 - 2004
UR - https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2081
UR - https://nbn-resolving.org/urn:nbn:de:hbz:386-kluedo-15959
ER -