求解大规模TSP问题的混合算法

A New Hybrid Algorithm for Solving Large Scale TSP

遗传算法求解大规模TSP时呈现出求解时间长、后期效率明显降低等缺陷。通过结合分块方法、局部搜索算法以及禁忌算法,本文提出一个求解TSP的混合算法,以提高初始解质量,减少计算量。利用遗传算法和混合算法对几个TSP进行数值实验,表明无论在结果的质量上还是在运行效率上,混合算法都明显优于遗传算法,而且,规模越大效果越明显。

Genetic algorithm （GA） is an effective method for solving traveling salesman problem （TSP）. However, GA becomes inefficient for large-scale TSP due to its shortcomings, such as long time expense and appearent efficiency decline during the final stage. By means of divided and conquer method, searching algorithm and Tabu algorithm, a new hybrid algorithm for TSP is formulated, which leads to better initial solutions and less computation load. Experiments demonstrate that the hybrid algorithm outperforms GA in both the quality of results and efficiency. Furthermore, the proposed hybrid algorithm is even more efficient in solving much large scale TSP.