李博 颜靖艺

1 桂林航天工业学院 计算机科学与工程学院，桂林 广西 541004;2 桂林电子科技大学信息科技学院 管理系, 桂林 广西 541004

如果一个人要依次前往多个城市旅游，他就需要进行相应的路程规划。当仅仅以各个城市之间距离作为衡量标准，不考虑其他因素时，这就转换为寻找最短路径的问题——旅行商问题。旅行商问题，即TSP问题(Traveling Salesman Problem，TSP)，指的是：有个旅行商人需要独自依次前往数个城市经商环游，在整个旅程中他对于每个城市去且仅能去一次，不能多次经过同一座城市，并且在整个旅行的最后他需要回到起点，基于这些条件他需要计划出一条最短的路径。

TSP问题在我们生活中有很广泛的应用，比如路径规划等[1-3]。同时，TSP问题是NP-Complete问题，因此在求解过程中不能选用一些传统的优化算法。基于TSP问题的普遍性和趣味性，国内外科学工作者对这个数学问题进行了各种角度的研究，很多知名的算法被选用处理该问题，比如：贪心算法(Greedy algorithm)、蚁群算法(Ant colony algorithm)、模拟退火算法(Simulated annealing algorithm)、遗传算法(Genetic algorithm)等[4]。对于TSP问题，研究人员设计解决该问题的算法都希望尽可能快的求出路径规划方案，并且其路径规划长度更短，即又好又快。但是由于TSP问题的复杂性，这些算法目前都有些不足：贪心算法在计算离散的优化问题时，由于其运算规则的设计，在求解过程中会出现局部最优问题[5]；遗传算法是一种比较常见和通用的算法，在很多问题上都有很好的表现。但是遗传算法作为一种通用算法，在处理TSP问题时也有些局限性，比如当城市的数量增加时，其计算精度会下降，而运行时间会增加；……