旅行商问题的几种求解方法

《旅行商问题的几种求解方法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第23卷第O8期计算机仿真2006年08月文章编号：1006—9348(2006)08—0153—05旅行商问题(TSP)的几种求解方法田贵超，黎明，韦雪洁(南昌航空工业学院测试技术与控制工程系，江西南昌330034)摘要：旅行商问题(TSP)是组合优化领域里的一个典型的、易于描述却难以处理的NP完全难题，其可能的路径数目与城市数目是呈指数型增长的，求解非常困难。而快速、有效地解决TSP有着重要的理论价值和极高的实际应用价值。该文首先介绍了什么是TSP，接着论述了六种目前针对rsP比较有效的解决方法(模拟退火算法、禁

2、忌搜索算法、Hopfield神经网络优化算法、蚁群算法、遗传算法和混合优化策略)的基本思想，并且简单阐述了它们的求解过程，最后分别指出了各自的优缺点并对解决TSP的前景提出了展望。关键词：旅行商问题；组合优化；路径；展望中图分类号：TP301．6文献标识码：ASeveralMethodsforSolvingTravelingSalesmanProblemTIANGui—chao，LIMing，WEIXue—jie(DepartmentofTest&ControlEngineering，NanchangInstitut

3、eofAeronauticalTechnology，NanchangJiangxi330034，China)ABSTRACT：TheTravelingSalesmanProblem(TsP)isoneofthetypicalNP—Completehardproblemsincombinatorialoptimization，whichiseasytobedescribedbuthardtobesolved．Itspossibleamountsofpathincreaseexponentiallywiththeamou

4、ntsofcity，SOitisverydificulttosolve．ButtosolveTSPquicklyandeffectivelyhasimportanttheoreticalvaluesandhighpracticalapplicationvalues．TSPisfirstintroducedinthispaper．Thenthebasicthoughtsofsixeffectivemethods(simulatedannealingalgorithm，taboosearchalgorithm，Hopfi

5、eldneuralnetworksoptimizationalgorithm，antcolonyalgorithm，geneticalgorithmsandhybridoptimizationstrategy)forsolvingTSPandtheirprocessesarediscussed．Atlast，theadvantagesanddisadvantagesofthesixmainsolvingmethodsarerespectivelyindicated，andtheprospectforthefuture

6、ofsolvingTSPisprovided．KEYWORDS：Travelingsalesmanproblem(TSP)；Combinatorialoptimization；Path；Prospect2)非对称旅行商问题(d≠，了i，』=1，2，3，⋯，rg)。l引言非对称旅行商问题较难求解，我们一般是探讨对称旅行旅行商问题(TravelingSalesmanProblem，简称TSP)即商问题的求解。给定n个城市和两两城市之间的距离，要求确定一条经过各若对于城市V=，：，，⋯，}的一个访问顺序为r城市当且仅当一次

7、的最短路线。其图论描述为：给定图G=={tl，t2，t3，⋯，t一，t}，其中t．∈V(i=1，2，3，⋯，n)，且(，A)，其中为顶点集，A为各顶点相互连接组成的边集，记t=t。，则旅行商问题的数学模型为⋯：minL=设D=(出)是由顶点和顶点'『之间的距离所组成的距离矩∑阵，要求确定一条长度最短的Hamilton回路，即遍历所有顶f：1点当且仅当一次的最短距离。TSP是一个典型的组合优化问题，并且是一个NP完全旅行商问题可分为如下两类：难题，是诸多领域内出现的多种复杂问题的集中概括和简化1)对称旅行商问题(d=，

8、V，J=1，2，3，⋯，rg)；形式，并且已成为各种启发式的搜索、优化算法的间接比较标准。因此，快速、有效地解决TSP有着重要的理论价值和极基金项目：国家自然基金(60475002)高的实际应用价值。收稿日期：2005～06—30一153—形成一套完整算法。它是对局部邻域搜索的一种扩展，是2主要求解方法一种全局逐步寻优算法，是对人类智力过程的一