求解TSP问题的多级归约算法

被引：57

作者：

邹鹏

周智

陈国良

顾钧

机构：

[1] 中国科学技术大学计算机科学技术系

来源：

软件学报 | 2003年 / 01期

关键词：

TSP(travelingsalesmanproblem); NP-hard; 部分解; 归约; 多级归约算法;

D O I：

10.13328/j.cnki.jos.2003.01.006

中图分类号：

TP301.6 [算法理论];

学科分类号：

摘要：

TSP(traveling salesman problem)问题是最经典的NP-hard组合优化问题之一.长期以来,人们一直在寻求快速、高效的近似算法,以便在合理的计算时间内解决大规模问题.由于对较大规模的问题,目前的近似算法尚不能在较短的时间内给出高质量的解,因此提出了多重归约算法.该算法的基本原理是通过对TSP问题的局部最优解与全局最优解之间关系的分析,发现对局部最优解的简单的相交操作能以很高的概率得到全局最优解的部分解.利用这些部分解可以大大缩小原问题的搜索空间,同时也不会降低搜索的性能.这就是所谓的归约原理.再通过多次归约使问题的规模降到足够小,然后对这个较小规模的实例直接用已有的算法求解,最后通过相反的次序拼接部分解,最终得到一个合法的解.在TSPLIB(traveling salesman problem library)中,典型实例上的实验结果表明,此算法在求解质量和求解速度上与目前已知的算法相比有较大的改进.

引用

页码：35 / 42

页数：8

共 9 条

[1] Computer solutions to the traveling salesman problem. LinS. The Bell System Technical Journal . 1965
[2] Cost versus distance in the traveling salesman problem. BoeseK. . 1995
[3] An effective heuristic algorithm for the traveling salesman problem. LinS,KernighanBW. Operations Research . 1973
[4] Optimization by simulated annealing. KirkpatrickS,GelattCD,VecchiMP. Science . 1983
[5] Well-Solvable special cases of the traveling salesman problem: a survey. BurkardRE,DeinekoVG,DalRV,et al. SIAM Review . 1998
[6] TSPLIB—a traveling salesman problem library. ReineltG. ORSA Journal on Computing . 1991
[7] A method for solving traveling salesman problems. CroesGA. Operations Research . 1958
[8] Computers andIntractability: aGuide to theTheory ofNP-Completeness. GareyMR,JohnsonDS. . 1979
[9] Scheduling of vehicles from a central depot to a number of delivery points. ClarkeG,WrightJW. Operations Research . 1964

← 1 →