关键词: 链式Lin-kernighan算法, 旅行商问题, 边集, 随机算法, 混合算法

Abstract: Lin-Kernighan algorithm is a kind of high effective optimization algorithm for combinatorial optimization problems. Traveling Salesmen Problem (TSP) is one of the typical NPhard problems in the field of combinatorial optimization. Through the discussion on the simplification of the problems, probability simplifying model was established, the prior probability was produced via experimental analysis, and stochastic algorithm for simplifying initial edge set of traveling salesman problem was constituted. The solving performance of chained Lin-Kernighan algorithm was improved obviously by utilizing the edge set produced by the stochastic algorithm as reference optimizing edge set of chained LinKernighan algorithm. Better convergence effect was achieved while combining the stochastic algorithm with different intelligence algorithms.

Key words: chained Lin-Kernighan algorithm, Traveling Salesmen Problem (TSP), edge se, stochastic algorithm, hybrid algorithm