[精品]TSP问题综述及相应求解算法研究.doc

《[精品]TSP问题综述及相应求解算法研究.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、TSP问题综述及相应求解算法研究摘要:TSP问题是组合优化中的经典问题。其解决方法有局部优化方法和一些启发式算法。关键词：TSP；2-交叉法算法；Lin-Kernighan算法旅行商问题，即TSP问题(TravelingSalesmanProblem)是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路经的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。它被证明是NP难(NP——hard)问题并与VLS制造，输油管道铺设，电路布线等问题有关，学术界对该问题的认识日益深入。由于求其确定

2、解的时间是指数型的，不易掌握，因而对其近似算法的研究一直是算法设计中的一个重要课题。目前已经有很多关于求解TSP近似最优解的算法。主要包括：些局部优化算法，如:近邻法(nearest-neighbor)最近插入(nearestinsertion)>最远插入法(farthestinsertion)、贪心法(greedy)>分枝定界法(branchandbound填空曲线法(space-fillingcurve)、Karp法、2・交叉法(2-opt)、k交叉法及Lin・Kernighan法等；一些启发式算法如模拟退火算法［3］、遗传算法［4］、蚁群算法［5］、免疫算法［6］、神经网络等

3、。F面就来分析一下TSP问题的各种算法。(1)2-它从城市的一个随机排列(称为路径T)开始并试图去改善它。T的邻域定义为交换T中不相邻的两条边得到的所有路径的集合。这种移动称为2-交叉法(2-opt),如图1、图2所示。如果cost(0,2)+cost⑸6)>cost(0,5)+cost(2,6)，即城市0和2之间的距离与5和6之间的距离和大于0和5与2和6之间的距离和，那么路径T(0—2—4—1—8—7—3—5—6—9_0)就替换(0—5—3—7—8—1—4—2—6—9—0),如图2所示。如果在邻域中找不到比T更好的结果，则T为2・交换的最优结果且算法结束，在彻底放弃之前一定要尝

4、试多个随机排列o752图2(2)Lin-Kernighan算法求解TSP问题的目前最好的局部搜索过程是Lin・Kernighan算法。C=J基本的Lin・Kernighan算法有多种版本，它们在细节上稍有差别。现在来简单地描述其中的一种，该方法所采用的表示方式并不是哈密顿路径而是所谓的5-路径。下面是它的原理。5-路径结点的个数比边数多1,并且在路径中所有的结点除了最后一个结点可以在前面出现过以外，其它结点都仅出现一次。如图3所示，它也许可以加深我们的理解，它图示了一条&•路径：a—b—c—d—e—f—g—h—i―j—e。这就是一条5-路径，因为它有10条边和11个结点，并且除了最

5、后一个结点e外，别的结点都只出现了一次。任何一条6•路径都可以通过替换最后一条边而成为合法路径。例如，用边（j,a）替换边（j，e）就产生了一条合法路径;并且，用任何一条从j起始的边来代替边（j,e）都会产生一条新的6-路径，如果用边（j,f）来替换边（j,e）。用switch（e,f）来表示这样一条路径的替换疋和f表示切换的结点。其中结点的顺序非常重要:第一个结点（e）被删除并被第二个结点（f）替换。如果交换的结点本身并不重要，就用switch来表示次替换。新的6•路径的费用增加了cost（j,f）-cost（j,e）,当然这个增量可能为负。还要注意的是一条6-路径有两条“最后边

6、”。在图3中，在建立合法路径或者产生一条新的§・路径时既可以替换边（j，e）,也可以替换边（f，e）。F面来描述Lin-Kernighan算法的基本步骤。它从一条随机路径T开始并产生一系列的6・路径。第一条路径由T产生，后面的6•路径则总是通过切换移动由前一条6•路径产生。Step1产生一条路径T,Best_cost=cost(T)XT中每个结点k和T每条边edge(ik)做以下操作。Step2如果存在jHk使得cost(i,j)Wcost(i,k)则移去边(i,k)并增加边(i,j)来建立一条路p,否则转向Step4oStep3由p中构造一条路径T，如果cost(T)

7、cost则Best_cost*-costT保存T;如果存在p的一个切换使产生了一条费用不大于cost(T)的6•路则进行切换得到一条新的6•路P，转向Step3oStep4如果cost(T)vBest_cost则Best_cost=cost(T),保存T,如果还有未测试的结点或者边的组合则转向Step2oKernighan算法是最著名的局部搜索算法，它具有非常快的执行速度，能得到100万个城市的最优解，与最优路径仅相差2%，在一台现代工作站上只需不到一个小时的时间。