旅行商问题概述

２００６年第８期　（总第９４期）　大众科技　ＤＡ　ＺＨＯＮＧ　ＫＥ　Ｊ　Ｎｏ．８，２００６　（Ｃｕｍｕｌａｔｉｖｅｌｙ　Ｎｏ．９４）　旅行商问题概述　郭靖扬　（电子科技大学光电信息学院，四川成都６１００５４）　【摘要】旅行商问题是组合优化的经典问题，应用广泛，而且长期以来被作为ＮＰ—ｃｏｍｐｌｅｔｅ问题的理想研究平台。文章介绍　了旅行商问题的基础知识、应用，以及常用的求解方法。　【关键词】旅行商问题；组合优化；ＮＰ—ｃｏｍｐｌｅ￣；ｋ～ｏｐｔ；智能算法　【中图分类号１　ＦＰ１８２　【文献标识码】Ａ　【文意编号】１００８—１１５１（２００６）０８—０２２９—０２　旅行商问题（Ｔｒａｖｅｌｉｎｇ　ＳＭｅｓｍａｎ　Ｐｒｏｂｌｅｍ，简称ＴｓＰ１是一个　２４９７８个城镇。　著名的组合优化问题：给定ｎ个城市，有一个旅行商从某一城　一、应用　市出发，访问每个城市各一次后再同到原出发城市，要求找出　旅行商问题具有蘑要的实际意义和工程背景。它一开始　的巡回路径最短。如果用图论来描述，那就是已知带权图Ｇ＝　是为交通运输而提出的，比如飞机航线安排、送邮件、快递服　（Ｃ，Ｌ），寻出总权值最小的Ｈａｍｉｌｔｏｎ圈。其中Ｃ＝｛ｃ　，Ｃ！，…，ｃ　｝表　务、设计校车行进路线等等。实际上其应用范围扩展到了许多　示ｎ个城市的集合，Ｌ＝　ｃ，，ｃｉ∈Ｃｊ是集合Ｃ中元素（城市）两　其他领域．下面举几个实例。　两连接的集合，每一条边ｌｉｉ’都存在与之对应的权值ｄ　实际应　印制电路板转孔是１＇ｓＰ应用的经典例子，在一块电路板　用中　可以表示距离、费用、时间、油量等。　上打成百上千个孔，转头在这些孔之间移动，相当于对所有的　ＴＳＰ的描述虽然简　．解决起来却很困难。最简单思路是　孔进行一次巡游。把这个问题转化为ＴＳＰ，孔相当于城市．子Ｌ　用穷举法把所有可能的巡回路径全部列出来．最短的一个就　到孔之问的移动时间就是距离。　是最优解，但这样只能处理很小规模的问题。旅行商　题属于　为了避免大气干扰，使光学系统达到其衍射极限分辨率．　ＮＰ—ｃｏｍｐｌｅｔｅ问题．是ＮＰ￣ｏｎ—ｄｅｔｅｒｍｉｎｉｓｔｉｃ　ｐｏｌｙ—ｎｏｍｉｎａｌ１『口Ｊ题　欧美发达国家提出发展空间光十涉仪和综合孔径望远镜的计　中最难的一类，不能住多项式时间内求解。如果有１３座城市，　划。美国航空航天局有一个卫星群组成空间天文台ｆＳｐａｃｅ—　那么巡游路径共有（ｎ一１）！／２条，计算的时间和（ｎ一１）！成　Ｆ比。　ｂａｓｅｄ　Ｏｂｓｅｒｖａｔｏｒｉｅｓ１的计划，用来探测宇宙起源和外星智慧生　城市数ｎ＝２０，巡同路径有１．２ｘ１０　种，ｎ＝１００，巡回路径就有多　命。欧洲空间局也有类似的Ｄａｒｗｉｎ计划。对天体成像的时候，　达４．６ｘ１０髓种。而据估计宇宙中基本粒子数“仅仅只有”ｌＯ　需要对两颗卫星的位置进行调整，如何控制卫星，使消耗的燃　个。　尽管如此，随着算法研究的逐步深入和计算机技术飞速　料最少，可以用ＴＳＰ来求解。这里把天体看作城市，距离就是　卫星移动消耗的燃料　提高．对ＴＳＰ问题的研究不断取得进展。７Ｏ年来，被ｉ【Ｅ服的　美国国家卫生协会在人类基因排序工作中用ＴＳＰ方法绘　ＴｓＰ规模从几十个城市增加到上万个城市。目前的最高汜录　制放射性杂交图。把ＤＮＡ片断作为城市．它们之间的相似程　是侄２００４年５月。找到的巡游瑞典２４９７８个城镇的最优路径　度作为城市问的距离。法国科学家已经用这种办法作出了老　ｆｓｗ２４９７８），花费了８４．８个ＣＰＵ年。图１展示了ＴＳＰ的研究进　展，最近的二一十年时间里．被攻克的ＴＳＰ规模高速增长，差　鼠的放射性杂交图。　不多是每十年增加一个数量级。照这样发展下去的话，再过２０　此外，旅行商问题还有电缆和光缆布线、晶体结构分析、　年就能解决上　万个城市的ＴＳＰ．有专家甚至已经为此准备　数据串聚类等多种用途。更重要的是．它提供了一个研究组合　好了数据：全球１９０，４７ｌ１个城市的坐标。当然。能不能达到这　优化问题的理想平台。很多组合优化问题，比如背包问题、分　个目标，有赖于未来计算技术的发展。　配问题、车间调度问题．和ＴＳＰ同属ＮＰ—ｃｏｍｐｌｅｔｅ类，它们都　Ｂｗ２４９７８　是同等难度的．如果其中一个能用多项式确定性算法解决，那　么其他所有的ＮＰ　ｃｏｍｐｌｅｔｅ类问题也能用多项式确定性算法　解决。很多方法本来是从ＴＳＰ发展起来的．后来推广到其他　ＮＰ—ｃｏｍｐｌｅｔｅ类问题上去　二、ＴＳＰ求解方法　求解旅行商　题的方法町以分为两大类．一类足精确算　法，目的是要找到理论最优解：另一类是近似算法，不强求最　”　”“　ｖ　优解，只要找到“足够好”的满意解就可以了。　图ｌ　ＴＳＰ的发展　（一）精确算法　字母后面的数字表示城市数．“ｓｗ２４９７８”就是瑞典的　如前面所述．穷举法和全局搜索算法属于精确算法　但　【收稿Ｅｌ期】２００６—０３—１８　【作者简介】郭靖扬（１９８０一），四川宜宾人，电子科技大学光电信息学院硕士研究生。　—－２２９——　维普资讯 http://www.cqvip.com

是计算量太大不可能实现。常用的精确求解方法主要有两种。　１９５４年，Ｇｅｏ￣ｅ　Ｄａｎｚｉｇ等人用线性规划的方法取得了历　史性的突破——解决了美国４９个城市的巡回问题。这就是割　平面法，在整数规划问题上也广泛应用。还有分枝限界法，所　模拟退火算法随机接受一些劣解。这样就有希望从局部最优　解中跳出，找到全局最优解。　遗传算法ｆＧＡ）是根据自然界的“物竞天择，适者生存”现象　提出的一种随机搜索算法。把一定数量的解作为一个群体，通　过选择、交配和变异把适应性强的染色体（ＴＳＰ中较好的一些　谓限界，就是求出问题解的上、下界．通过当前得到的限界值　排除一些次优解，为最终获得最优解提示方向。每次搜索下界　最小的分枝，可以减小计算盛。总的来说，精确算法比较复杂。　要写很长的代码，而且计算量仍然很大。　边）遗传下来，使解进化（优化）。人工神经网络（ＡＮ　是对人脑　神经系统的仿真．具有并行性、容错性、学习能力、知识存储等　优点。用Ｈｏ口ｄ丘ｅｌｄ神经网络求解ＴＳＰ问题取得了很好的成果。　（二）近似算法　大多数情况下只要能求得满意解就可以满足要求了。用　蚁群算法ｆＡＣＡ）是模拟蚁群行为的一种仿生算法。蚂蚁个　体能力很低，却可以协同工作，集中食物，建筑蚁穴，依靠群体　智能发挥出超出个体的智能。与前面几种智能算法不同的是．　蚁群算法更接近巡回路径构造算法而不是巡回路径优化算　近似算法得到的满意解和最优解往往只差几个百分点。和精　确算法相比，近似算法比较简单，计算量小很多。大致可分为　三类：　１．巡回路径构造算法。这种算法是把城市一个一个地加入　到路径中去，全部加进去以后就得到了一条巡回路径。最简单　的巡回路径构造算法是贪婪算法，每次选择最小的一条边。但　是最后要把起点和终点连起来，最后这条边往往会很长，所以　找到的是一个很“粗糙”的解。此外，还有插入法、双最小生成　树法、Ｃｌａｒｋ＆Ｗ￣ｇｈｔ法等。　２．巡回路径优化算法。也就是局部搜索算法。搜索一个解　空间邻域里的最优值。先产生一条初始巡回路径，再改变其中　某些城市的顺序，使路径优化，逐渐接近最优解。　ｋ－ｏｐｔ算法的思路是，从巡回路径中找出ｋ条边，把它们换　成另外ｋ条边（换过以后仍然是一条巡回路径，没被断开），使　路径得到优化。ｋ是一开始就设定的常数。从巡回路径中找出　ｋ条边，共有Ｃ．ｋ种选择方法，必须全部考虑到。如果无论选出　哪ｋ条边来替换都不能进一步优化，则称这条巡回路径是ｋ一　最优。显然，ｋ越大，优化后的效果越好，可是随着ｋ的增大，计　算量也快速增大。一般用２一ｏｐｔ和３一ｏｐｔ。Ｌｉｎ和Ｋｅｍｉｇｈａｎ提出　了Ｌｉｎ—Ｋｅｍｉｇｈａｎ算法，和ｋ－ｏｐｔ相比，多了一系列替换规则，　大大减小了计算量，是目前处理ＴＳＰ最好的局部搜索算法。　３．智能算法。所谓智能算法，是指２０世纪以来借助自然界　的规律，根据其原理设计的算法，如模拟退火、遗传算法、神经　网络、蚁群算法等。本文把它们都归入近似算法。　模拟退火算法ｆＳＡ），它是局部搜索算法的一种扩展，根据　复杂组合优化问题与固体退火过程之间的相似之处．在它们　之间建立联系。退火过程中。固体最终达到能量最小的状态　对应于模拟退火算法找到最优解。与局部搜索算法不同的是。　－２３０－　法，每只蚂蚁单独完成巡游，并通过信息索交流，最终都聚集　到一条局部最优路径上来。　三、结语　旅行商问题是离散最优化的＿二－个基本问题，由于提法简　单，求解的思路和方法非常自由。多年来对以ＴＳＰ为代表的　ＮＰ—ｃｏｍｐｌｅｔｅ问题的研究取得了许多丰硕的成果，许多算法因　此而产生并发展起来，其影响遍及现代科学技术很多领域．如　计算机科学、人工智能、管理科学、通信工程、电力电子、机械　工程和生命科学等。对ＴＳＰ的各种研究方法正面临越来越广　阔的发展前景，ＴＳＰ本身的应用范围也在不断扩展。不论从理　论还是实际来讲，研究旅行商问题取得的每一步进展都有重　大意义。　【参考文献】　【１】段海滨．蚁群算法原理厦其应用［Ｍ】．北京：科学出版社，　２００５．　［２】文建国．光综合孔径望远镜子孔径阵列的优化和计算机　仿真［Ｄ］．２００３．（２）．　［３］李随成，刘广．一种改进的　Ｐ问题启发式算法［Ｊ］．管理　工程学报，２ｏ０５，（２）．　【４］马少平，朱小燕．人工智能［Ｍ】北京：清华大学出版社。　２ｏ０５．　［５】陈斌，徐华中．一种改进遗传算法及其在ＴＳＰ中的应用　［Ｊ］．计算机工程，２００２，（９）．　【６］程明，刘琴．神经网络ＴＳＰ问题仿真分析【Ｊ】．郑州走学学　报，２０ｏ４，（３）．