New strategy for improving performance of chained Lin-Kernighan algorithm
Dongmei Lin · Journal of Computer Applications · 2012
Through analyzing the characteristics of the edge sets of the optimal solutions from Traveling Salesmen Problem(TSP),a kind of new model was proposed to produce the referring optimization edge sets for Lin-Kernighan algorithm on the basis of authors' previous research(WANG DONG,WU XIANG-BIN.Strategy for improving the performance of chained Lin-Kernighan algorithm.Journal of Computer Applications,2007,27(11): 2826-2829).The number in the edge sets produced by the new model is less than those produced by normal algorithms or previous research.Meanwhile,the new edge sets include more edges that belong to the global optimal solution than them.Applying the new model to Lin-Kernighan algorithm,the execution time of the algorithm is further reduced,without losing the algorithm accuracy for a single call.Furthermore,the solution performance of Lin-Kernighan algorithm is improved also.With previous research achievement,the performance of all hybrid algorithms using Lin-Kernighan algorithm as the local search algorithm could be improved too.