（管理科学与工程专业论文）求解旅行商问题的新方法研究.pdf

中文摘要 本文对旅行商问题以及一些传统算法进行了介绍，并做出了评价。在此基础 上提出了一种分割处理旅行商问题的合成算法。 首先，本文描述了旅行商问题的定义和数学模型，并对旅行商问题的不同的 分类与分类方法进行了介绍，还提供了一些旅行商问题应用的实际例子。 其次，本文阐述了一些基本的旅行商问题的算法，其中着重研究了基于交换 边来改进当前解的l k 算法和目前最有潜力的神经网络和遗传算法。接着，本文 利用实际数据检验了部分算法的优劣。 再次，本文研究了目前最新且最有效的l k 算法的变种l k h 算法，介绍了 它的主要特点，利用实验数据分析了它的优点和缺点，提出了改进的思路。 再次，本文提出了一种新的分割求解的方法。实证结果表明，这种方法有一 定的作用，而且这种方法对其它算法的改进具有一定的参考价值。 最后，本文将l k h 算法和分割求解的方法相结合，提出了一种合成算法。 实证结果表明，这种合成算法有一定的作用，特别是针对一些分布较有规律的旅 行商问题。 关键词：旅行商i u nl k 算法l k h 算法r o p t 算法分割求解 a bs t r a c t b a s e do nt h e1 n s t r o d u c t i o nt ot h et s pa s s o c i a t e dw i t hl t st r a d i t i o n a la l g o r i t h m 。 a ne v a l u a t i o ni sg i v e na n dan e wa l g o r i t h mi sd e v e l o p e dt os o l v et h et s r f i r s t ，t h i st h e s i si n t r o d u c e st h ed e f i n i t i o na n dm a t h e m a t i c a lm o d e lo ft s p , a n d s u m m a r i z e sd i f f e r e n tc l a s s i f i c a t i o n sw i t hs o m ec a s es t u d i e si nm a n yf i e l d s s e c o n d l y ，i nt h i st h e s i ss o m et r a d i t i o n a la l g o r i t h m sa r er e v i e w e d ，a n dl k a l g o r i t h m ，w h i c hu s e st h ee d g e - e x c h a n g i n gt oi m p r o v ei t sp e r f o r m a n c e ，i sp r e s e n t e d i nd e t a i l t h ea n na n dg aa l g o r i t h m ，w h i c ha r et h em o s tp o t e n t i a l ，a r ed e s c r i b e da s w e l l a n dt h e ns o m ev a r i e n t so fl ka l g o r i t h m sa r ec o m p a r e db ye x p e r i m e n t s ，a n dt h e d i f f e r e n c e sb e t w e e nt h e mc a nb ee a s i l yr e c o g n i z e d t h i r d l y ，t h i st h e s i sh a sm a d eac l o s el o o ki n t ol k ha l g o r i t h m ，t h em o s te f f i c i e n t v a r i a n to ft h el ka l g o r i t h m s t w om a j o rf e a t u r e so fl k i ta l g o r i t h m sa r ea n a l y z e d a n da ne x p e r i m e n ti sm a d et o a n a l y s et h ee x c e l l e n c ea n ds h o r t c o m i n go fl k h a l g o r i t h m t h e r e f o r e ，ac o n c e p t i o nt oi m p r o v eo nt h ea l g o r i t l m ai sp r o p o s e d f i n a l l y ，an e wa l g o r i t h mw h i c hi sb a s e do nt h em e t h o do f d i v i d e a n d c o n q u e ri s p r o p o s e d t h er e s u l tf r o mac a s es t u d ys h o w st h a tt h ep r o p o s e dm e t h o di su s e f u la n d e f f e c t i v ea n dc a nb ef lr e f e r e n c ef o ri m p r o v e m e n ti na l g o r i t h m sr e l a t e d 。 k e yw o r d s ：t s pl k a l g o r i t h m l k h a l g o r i t h m r - o p ta l g o r i t h md i v i d e - a n d - - c o n q u e r 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得墨鲞盘堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名z 7 v签字日期：? “年v 月y 诮 学位论文版权使用授权书 本学位论文作者完全了解叁鲞盘堂有关保留、使用学位论文的规定。 特授权基鲞盘鲎可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者虢兽咖 签字日期0 西年y 月协同 翩躲幻产 签字日期：( 广年_月同 第一章绪论 1 1 研究背景 第一章绪论 组合数学，又称为离散数学。但有时人们也把组合数学和图论加在一起算成 是离散数学。组合数学是计算机出现以后迅速发展起来的一门数学分支。计算机 科学就是算法的科学，而计算机所处理的对象是离散的数据，所以离散对象的 处理就成了计算机科学的核心，而研究离散对象的科学恰恰就是组合数学。组合 数学的发展改变了传统数学中分析和代数占统治地位的局面。组合数学不仅在基 础数学研究中具有极其重要的地位，在其他的学科中也有重要的应用，如在计算 机科学、编码和密码学、物理、化学、生物等学科中均有重要应用。组合数学的 发展则是奠定了本世纪的计算机革命的基础。计算机之所以可以被称为电脑，就 是因为计算机被人编写了程序，而程序就是算法，在绝大多数情况下，计算机的 算法是针对离散的对象，而不是在作数值计算。正是因为有了组合算法才使人感 到，计算机好像是有思维的。 旅行商问题是经典的组合数学的问题，生活中随处可见这类组合数学问题。 例如，计算下列赛制下的总的比赛次数：n 个球队比赛，每队只和其他队比赛一 次。在纸上画一个网络，用铅笔沿着网络的线路走，在笔不离开纸面且不重复线 路的条件下，一笔画出网络图。一个邮递员从邮局出发，要走完他所管辖的街道， 他应该选择什么样的路径，这就是著名的“中国邮递员问题”。一个通调网络怎 样布局最节省? 美国的贝尔实验室和i b m 公司都有世界一流的组合数学家在研 究这个问题，这个问题直接关系到巨大的经济利益。库房和运输的管理也是典型 的组合数学问题。怎样安排运输使得库房充分发挥作用，进一步来说，货物放在 什么地方最便于存取。以上的这些例子中，有一部分例子就和旅行商问题有联系。 组合数学涉及到将一个集合的物体排列成满足一些指定规则的格式。有以下 问题反复出现： 1 排列的存在性。如果有人想要排列一个集合的成员使得某些条件得以满 足，那么这样一种排列是否可行根本就不是显而易见的。这是最根本的 问题，如果这种排列不总是可能的，那么我们要问，这种排列在什么样 的( 必要和充分) 条件下能够实现。 2 排列的计数和分类。如果一种排列是可能的，那么就会存在多种方法去 实现。此时，人们就可以计数并将它们分类。 第一章绪论 3 研究一个已知的分类。当人们建立起满足某些指定条件的一个排列( 可 能不容易) 以后，可能要考察这个排列的性质和结构。这样的结构可能 会涉及分类问题。 4 构造- 个最优的排列。如果有可能存在多于一个的排列，人们也许想要 确定满足某些优化准则的一个排列，即找出某种规定意义下的“最好的” 或最优的排列。 1 9 世纪，哈密尔顿爵士发明了一个智力游戏，其目标是在一个十二面体的边 上找出一条路线，该路线起始于某个顶角，当它到达其他每个顶角恰好一次后， 又回到起始的那个顶角。 哈密尔顿游戏适用于任意一个简单图： 设g 是一个简单图，能否确定一条路线，使它从g 的某一个顶点出发、沿g 的边到达其他的每个顶点恰好一次后，又返回到起始顶点。 今天，我们把图g 中一个哈密尔顿游戏的解叫做一个哈密尔顿圈。更确切地 说，n 阶图g 的一个哈密尔顿圈是g 中一个长度为n 的圈： x l x 2 一x 3 一一x 月一i x ”一x i 其中，x 1 , x 2 ，x 3 ，x n - 1 , h 是g 中以某种顺序排列的n 个顶点。 旅行商问题实际上就是所谓的最小哈密尔顿圈问题。它的描述如下： 一个推销商要去若干个城市推销商品，从城市1 出发，经其余城市一次，然 后回到城市1 ，问如何选择行走路线，使总里程最短。 旅行商问题已被证明为n p 一完备问题。这个概念意味着： 1 任何n p 一完备问题都不能用任何已知的多项式算法求解。这类问题随着 规模的扩大，会遇到组合爆炸的问题。 2 若任何一个n p 一完备问题有多项式算法，则一切的n p 一完备问题都有多 项式算法。 旅行商问题是经典的组合优化问题，在v l s i 芯片设计、机器人控制、车辆 选路，甚至在基因测序方面都有广泛的应用。图1 一l 和图1 2 分别是两个应用的 实例。 第一章绪论 图卜1美国1 3 5 0 9 个城市的旅行商问题的最优解 图l 一2 一个有1 3 1 个钻孔的v l s i 芯片的最优路线 第一章绪论 由此可见对旅行商问题的研究已经成为一个很有价值的研究课题，这也是本 论文选题的主要依据。 1 2 研究现状及存在的问题 目前，对于该类问题的研究有两个方向：完全算法能保证得到最优解，但是 运行时间是呈指数复杂度的，因而难以适应大规模计算的要求；近似算法则只要 求近似解，可在多项式时间内结束。 在旅行商问题上的近似算法分为两类：构造算法和环路改进算法。前者从某 个非法解开始，通过某种增广策略逐步改变该解，直到得到一个合法解为止。这 类算法包括最近邻算法、贪心算法、c l a r k e w r i g h t 算法、c h r i s t o f i d e s 算法 等。环路改进算法则在给定初始的合法解之后，使用某种策略来改进初始解，这 些镜略包括局部搜索、模拟退火、遗传算法等，其中最为简单和有效的方法为局 部搜索，如2 - o p t 、3 - o p t 、l k ( l i n k e r n i g h a n ) 、l k h ( l i n k e r n i g h a n h e s l g a u n ) 等。通常这两类算法结合起来使用，用环路构造算法来构造初始解，而用环路改 进算法改进这个初始解。a r o r a 对欧氏空间的旅行商问题提出了多项式时间的 近似策略，这也是近年来在近似算法的研究中所取得的一项重要进展。h e l s g u n 则提出了目前精度最高的近似算法l k h 算法。 目前存在的问题主要是随着生产的发展，实际问题的规模越来越大，规模往 往在百万以上。现有的算法在规模超过十万时表现都不是很好，要么耗时太长， 要么精确度太差。 1 3 本文工作 本论文在已有研究的基础上，系统阐述了旅行商问题和相关的传统算法，重 点介绍了l k h 算法，在此基础上提出了一种分割求解旅行商问题的方法。实验 结果表明这种基于l k h 算法的混合算法有一定的作用。 本论文第一章绪论部分简要介绍了旅行商问题的研究背景和研究现状及本 文的主要工作；第二章旅行商问题概述部分阐述了旅行商问题的模型、定义、问 题的种类及扩展形式，用于对旅行商问题有详细的了解；第三章旅行商问题算法 部分阐述了目前常用的求解算法，重点研究了l k 算法和目前最有潜力的神经网 络和遗传算法，并对各种算法的优劣做了简单的评价；第四章专门介绍了目前精 度最高的l k h 算法，对算法的主要特点进行了详细的介绍，并通过对比实验描 第一章绪论 述了l k h 算法的优点和缺点；第五章提出了一种分割求解( d i v i d e a n d c o n q u e r ) 方法，并通过算例表明了方法的有效性。第六章将分割求解方法和l k h 算法相 结合，形成一种合成算法，通过算例，表明，这种合成算法有一定的作用。本论 文在最后回顾和总结了基于l k h 算法的分割求解方法的优点以及存在的问题， 探讨了今后尚需研究的方向。 1 4 本章小结 本章介绍了旅行商问题研究的背景和现状，指出由于旅行商问题的时间复杂 性，现有的算法不可避免地不适用于大规模的旅行商问题。在总结前人经验教训 的基础上，本章最后概括了本文所研究工作的主要内容。 第一章绪论 述了l k h 算法的优点和缺点；第五章提出了一种分割求解( d i v i d e - m i d c o n q u e r ) 方法，并通过算例表明了! j 法的有效性。第六章将分割求解方法和i , k h 算法相 结合，形成一种合成算法，通过算例，表明，这种合成算法有一定的作用。本论 文在最后回顾和总结了基于l k i t 算法的分割求解方法的优点以及存在的问题， 探讨了今后尚需研究的方向。 1 4 本章小结 本章介绍了旅行商蒯题研究的背景和现状，指出由于旅行商问题的时削复杂 性，现有的算法不可避免地不适用于大规模的旅行商问题。在总结前人经验教训 的基础上，本章最后概括了本文所研究工作的主要内容。 的基础上，本章最后概括了本文所研究工作的主要内容。 第二章旅行商问题概述 第二章旅行商问题概述 2 1 旅行商问题的定义和数学模型 1 定义 旅行商问题( t r a v e l l i n gs a l e s m a np r o b l e m ，简记t s p ) 是组合数学中一个古老 而又困难的问题，它易于描述但至今尚未彻底解决，现已归入所谓的n p 完备问 题类问题，经典提法为： 有一货物推销员要去若干个城市推销货物，从城市l 出发，经其余各城市至 少一次，然后回到城市l ，问选择怎样的行走路线，才能使总行程最短( 各城市间 距离为已知) 。 该问题在图论的意义下就是所谓的最小h a m i l t o n 圈问题，由于在许多领域 中都有着广泛的应用，因而寻找其实际而有效的算法就显得颇为重要了。遗憾的 是，计算复杂性理论给予我们的结论却是，这种可能性尚属未知。 例如，对于一个仅有1 6 个城市的旅行商问题，如果用穷举法来求问题的最 优解，需比较的可行解有：1 51 2 = 6 5 3 ，8 3 7 ，1 8 4 ，0 0 0 个。在1 9 9 3 年，使用当时 的工作站用穷举法求解此问题需时9 2 小时。 尽管现在计算机的计算速度大大提高，而且已有一些指数缴的算法可精确地 求解旅行商问题，但随着它们在大规模问题上的失效( 组合爆炸) ，人们退而求其 次，转向寻找近似算法或启发式算法，经过几十年的努力，取得了一定的进展。 目前，一般来说，一万个城市以下的旅行商问题基本可用近似算法在合理的时问 内求得可接受的误差小于1 近似解或最优解。 2 数学模型 记g ：( 矿，e ) 为赋权图，矿= 1 , 2 ，h ) 为顶点集，e 为边集，各项点间距离 白。已知( c f f 0 ，白= + o 。，i ，j ) ，并设 f 1 ，边( i ，) 在最优路线上 勺2 1 0 ，其它 则旅行商问题的数学模型可写成如下的线性规划形式 第二章旅行商问题概述 m i n z = 。f 峋 h = 1 ， 。膀矿1 i k i , j e s x 。e 0 , q ， f v j v 1 kc v i ，e 矿 这里，k 为v 的所有非空子集，i k l 为集合kq u n n n g 的顶点个数。前 两个约束意味着对每个顶点而言，仅有一条边进和一条边出，后一约束则保证了 没有任何予回路解的产生。于是，满足上述约束的解构成了一条h a m i l t o n 回路。 除此之外，模型还有其它一些等价的书写形式。 2 2 旅行商问题的分类 旅行商问题按不同的分类方法可以分成为不同的种类。 1 据距离矩阵划分 当c f ，= c 驴( f ，j 矿) 时，问题被称为对称型旅行商问题。反之，称为非对 称型旅行商问题。非对称型旅行商问题可以化为对称型旅行商问题，用对称型的 方法求解。 当对所有f ，j ，k 【1 ，肝 ，有不等式+ c j k c i k 成立时，问题被称为是满 足三角形不等式的，简写成三角型旅行商问题。三角形不等式在很多情况下是自 动满足的，如：只要距离矩阵是由一度量矩阵导出的即可。另一类自动满足的是 闭包矩阵，i 是 勺 的闭包，是指在 1 , 2 ，力拍完全图中，勺为边( i ，j ) 距 离，c 。则是f 争，之最短路长。一般而言，现实生活中的大多数问题都满足三 角形不等式，它是旅行商问题中的一种主要类型。个别不满足的，也可转换成其 闭包问题，它们的旅行商问题解是等价的。 当c 。是欧氏距离时，则称为欧氏距离的旅行商问题。显然此类问题既是对称 型旅行商问题也是三角型旅行商问题。 2 根据顶点的分布形态划分 有均匀分布的( u n i f o r mp o i n t s ) 、聚集分布( c l u s t e r e dp o i n t s ) 、随机距 离矩阵( r a n d o m i l i a t f j c e s ) ，此外还有旅行商问题库( t s p l i b ) 中的实际范例。前 三种都是人工模拟产生的旅行商问题，主要用于测试算法对不同分布形态的旅行 第二章旅行商问题概述 商问题的表现，并计算算法的时间函数。后一种实际范例彳是人们关注的重点。 3 根据距离矩阵在数据文件中的存储方式划分和来源划分 m a t r i x 型：距离矩阵直接给出。e u c 一2 d 或c e i l 一2 d ：给出顶点坐标，距离矩 阵需计算才能得到。g e o ：给出顶点坐标，距离矩阵需计算才能得到，坐标来源 于地理坐标。 2 3 旅行商问题的扩展 旅行商问题的研究经过几十年发展， 商问题外，目前已引申出许多扩展形式， 】最小哈密尔顿链的问题 这是起点和终点不同的旅行商问题， 于求解该类问题。 取得了一系列的成果。除了经典的旅行 常见的有： 前面提到的许多算法都可略作修改，用 2 瓶颈问题( b o t t l e n e c kt s p ) 目标函数为m a x ，c i i x 加) ，且i ，i ，j g 的旅行商问题。 3 非对称旅行商问题( a s y m m e t r i ct s p ) 距离矩阵非对称的旅行商问题。 4 多人旅行商问题( m u l t i p e r s o nt s p ) 由多人完成环游的旅行商问题。该问题可转换成等价的单人问题，只需将点 l 改为m 个虚拟点( 1 ，2 ，m ) 其间用边连接，距离为充分大m 卜， 各虚拟点i 到j 的距离c “= c lf ，对新问题求解其旅行商问题后，从虚拟点i 7 进入原网络再回到虚拟点i7 的那段路线即是m 人中某一个的环游路线。 5 多目标旅行商问题( m u l t i o b j e c t i v e t s p ) 若各边弧上有m 个权值，则使得哈密尔顿圈上相应的1 1 1 个目标值都尽可能 小的解就称为多目标旅行商问题的( p a r e t o ) 有效解。如实际问题中常常需要考虑： 路程最短、时间最少、费用最省、风险最小等等多方面的因素。由于多目标意义 下的所谓最优解是一种“折衷解”、“非劣解”，因此，多目标旅行商问题解的含 义为：假定有一哈密尔顿圈的解h ，若不存在任何其它回路解q ，使得 z t ( q ) z 女( h ) ，k = 1 , 2 ，m ，其中至少有一个不等式严格成立( 乙为相应 的目标函数值) ，则h 为p a r e t o 解。 6 依次排序问题( s e q u e n t i a lo r d e r i n gp r o b l e m ( s o p ) ) 这类问题是非对称旅行商问题，在给定的一系列顶点和距离矩阵下，寻我最 短从顶点l 到顶点n 哈密尔顿链，同时满足限制：某些顶点要在另一些顶点之前 被连接。 第二章旅行商问题概述 7 载货量受限制的选径问题( c a p a c i t a t e d v e h i c l er o u t i n g p r o b l e m ( c v r p ) ) 给定n 一1 个顶点和一个仓库，已知顶点和顶点、顶点和仓库的距离。卡车的 载货量受限制，卡车每次在部分顶点和仓库之间往返，寻求一条经过所有顶点的 最短路线。 一般来说，这些扩展问题都有特殊的不同于对称型旅行商问题的求解方法， 但也可将它们转化成对称型旅行商问题求解。在本篇沦文中，除非特别说明，所 提到的旅行商问题都是对称型问题。 2 4 研究旅行商问题的意义 旅行商问题是一个n p 一完备问题，它抵御了两代数学家们的顽强攻击。这 个概念意味着：任何n p 一完备问题都不能用任何已知的多项式算法求解：若任 何一个n p 一完备问胚有多项式算法，则一切n p 一完备问题都有多项式算法。 由此，不少人猜测任何n p 一完备问题都没有多项式算法，但至今无人证明。 事实上，人们普遍认为，不发展全新的数学技术就证明不了这个猜想。这样一种 认识的实际意义就在于许多人相信，难计算是这样一类问题的固有性质，因此它 们不可能用有效算法求解，而所有能精确求解n p 一完备问题的算法，在最坏情 况下都需要指数级的时问。 另外，旅行商问题是一个理想化的问题，大多数对于此问题的研究都不是为 了直接的实际应用，但这些研究可以经转化后用于许多现实的组合优化问题。很 自然地可以想到，旅行商问题的成果可以应用于运输和物流问题。旅行商问题最 早的应用是在上个世纪的四十年代，应用于校车路线的优化。现在，旅行商问题 在越来越多的方面得到应用。 1 电路板钻孔进度的安排。在这个应用当中，电路板上的孔代表旅行商问 题中的城市，钻头从一个钻孔移动到另一个钻孔。寻找最短路径变成了 寻找最省时的钻头移动时间。尽管目前钻机的工艺技术发展很块，但钻 头的移动时间仍然是一个令人头疼的问题。 2 基因测序。c o n c o r d e 是一种求解旅行商问题的程序。美国国家卫生机构 的研究人员利用这一程序来进行基因测序。在这一应用中，局部的基因 图谱作为城市，城市与城市的距离代表某张图谱与其它图谱相连的可能 性。研究人员试图寻找一种可能性最高的连接方式把这些局部的图谱合 成为整张基因图谱。 3 半导体的线路设计。一家半导体生产厂家应用c o n c o r d e 程序来优化半导 第一二章旅行商问题概述 体的线路设计，这样可以节省n , n 半导体的时间，也能减少半导体电路 消耗的能量。 4 光缆的线路设计。贝尔电话公司利用c o n c o r d e 程序来设计光缆的铺设线 路，同样的方法也应用于电话和电力线路的铺设当中。 5 在机器人控制等其它方面，旅行商问题也有应用。 2 5 本章小结 旅行商问题是经典的组合问题，在现实生活生产实践中有着广泛的应用。本 章通过介绍了旅行商问题的定义、分类、扩展的形式、研究的难点和应用领域等， 为以下章节算法的介绍和研究提供了理论的支持。 1 0 第三章旅行商问题的求解算法 第三章旅行商问题的求解算法 1 9 5 4 年，第一个4 2 个城市的旅行商问题用线性规划的方法得到了求解。那 时起，陆续诞生了许多种算法用来求解旅行商问题。目前，最大的已成功求解的 旅行商问题有2 4 7 9 8 个城市。各个时期旅行商问题求解的里程碑如图3 一l 所示。 石 - o e z 3 1 精确算法 图3 一l 各个时期旅行商问题求解的罩程碑 1 可解特殊旅行商问题的精确算法 对于旅行商问题的一些特殊情况，业已研究出一系列非常完美的结果，如： 机器排序问题( g i l m o r e 等，1 9 6 4 ) 、二分图情形( l a w l e r ，1 9 7 1 ) 、平面旅行商问题 中的一些特例( b u r k a r d ，1 9 8 9 ) ，等等。出于可解情形的结果都是成熟的定理，因 此严格来说已不属算法研究的范畴。 2 线性规划算法 这是求解旅行商问题的最早的一种算法，主要是采用整数规划中的割平面 法，即先求解模型中由前二个约束构成的松驰线性规划问题，然后通过增加不等 式约束产生割平面，逐渐收敛到最优解。 d a n t z i g 等人早在1 9 5 4 年就求解过n = 4 2 的旅行商问题最优解。7 0 年代中 期对于t s 多面体理论的研究，产生了一些比较有效的不等式约束，如：子回路 消去不等式( s u b t o u r e l i m i n 砒i o n ) 、梳子不等式( c o m bi n e q u a l i t i e s ) 、团树不等式 第二章旅行商问题的求解算法 ( c l i q u et r e ei n e q u a l i t i e s ) ，等等。曾经报导过用割平面法在中小型机上求解n _ 3 1 8 规模的例子。 目前，常用的方法是先用近似算法来求得近似解，再将此近似解作为下限， 用线形规划方法来精确求解或证明此下限为最优解。 对于目前最大的已成功求解的例子s w e d e n 2 4 9 7 8 ( 城市数为2 4 7 9 8 ) ，它的求 解过程如下： s t e p1 用l k h 算法求得近似解8 5 5 ，5 9 7 。 s t e p2 用线性规划的方法求得解的下限为8 5 5 ，3 9 1 1 7 。 s t e p3 证明在8 5 5 ，3 9 1 1 7 和8 5 5 ，5 9 7 之问不存在解。 整个线性规划求解( 不包括用近似算法求解) 的过程是在工作站上完成的， 折算成个人计算机( i n t e lx e o n2 8g h zp r o c e s s o r ) 所耗费的时间为8 4 8 年。 图3 - 2 为s w e d e n 2 4 9 7 8 用线性规划方法求解的分枝修剪树图。 图3 2s w e d e n 2 4 9 7 8 的分枝修剪树图 3 动态规划算法 由于动态规划算法的时间复杂度为0 ( n2 2 n ) ，空间复杂度为0 ( n 2 “) ，故一般 除了很小规模的问题外，几乎不予采用。 4 分支定界算法 分支定界法是一种应用范围很广的搜索算法，它通过有效的约束界限来控制 搜索进程，使之能向着状态空间树上有最优解的分支推进，以便尽快找出一个最 优解。该方法的关键在于约束界限的选取，不同的约束界限，可形成不同的分支 定界法。 ( 1 ) 以分派问题为界 通过求解相应的分派问题，得到旅行商问题的一个下界，以此进行分支定界 搜索。这是一种使用较多的分支定界算法 第三章旅行商问题的求解算法 ( 2 ) 以匹配问题为界 通过求解相应的匹配问题，得到旅行商问题的一个下界，以此进行分支定界 搜索。该方法适用于对称型旅行商问题。 ( 3 ) 以最小权l 生成树问题为界 通过求解相应的最小权l 生成树问题，得到旅行商问题的一个下界，以此进 行分支定界搜索。在此基础上，h e l d 和k a r p ( 1 9 7 0 ) 曾将问题加以转换，得到更紧 的下界，有时甚至能将搜索树整个显示出来。 虽况分支定界法对于较大规模的问题并不十分有效，可有时却被用来求解近 似解。而且，将分支定界法与一些启发式算法相结合，常常能获得一些意外的成 功。 3 2 近似算法 由于精确式算法所能求解的问题规模非常有限，实际中使用的往往都是多项 式阶数的近似算法或启发式算法( h e u r i s t i c s ) 。算法的好坏用c c + e 来衡量，c 为近似算法所得到的总行程，c + 为最优总行程，e 为最坏情况( w o r s tc a s e ) 下，近 似解与最优解的总行程之比所不超过的上界值 1 插入型肩发式算法( i n s e r t i o nh e u r i s t i c s ) 插入型算法可按插入规则的不同而分为若干类，其一般思想为： s t e pl 通过某种插入方式选择插入边( j ，j ) 和插入点k ，将k 插入i 和j 之 i b j ，形成 ，f ，k ，j ， ； s t e p2 依次进行直至形成回路解。 适用范围：对称的三角型旅行商问题。 具体实施中，可以将出发点取遍v 中各点而得到多个解，从中选择最好的 一个，但此时的时间复杂度增加了n 倍。常见的插入型算法有： ( 1 1 最近插入( n e a r e s ti n s e r t i o n ) 法 最坏情况：e = 2 ：时间复杂度：0 m 2 1 。 ( 2 ) 最小插入( c h e a p e s ti n s e r t i o n ) 法 最坏情况：e = 2 ；时间复杂度：o ( n 2i n n ) 。 ( 3 ) 任意插入( a r b i t r a r yi n s e r t i o n ) 法 最坏情况：e = 2 l g h 十0 1 6 ；时间复杂度：o ( n 2 1 。 ( 4 ) 最远插入( f a r t h e s ti n s e r t i o n ) 法 最坏情况：e = 2 l g f t + 0 1 6 ；时问复杂度：o ( n 2 1 。 ( 5 ) 凸核插k ( c o n v e xh u l li n s e r t i o n ) 法 第三章旅行商问题的求解算法 最坏情况：e = 未知；时间复杂度：o ( n 2i n n ) 。 2 最邻近算法( n e a r e s tn e i g h b o rh e u r i s t i c s ) s t e p1 任取一出发点； s t e p2 依次取最近的点加入当前解中直至形成回路解。 适用范围：对称的三角型旅行商问题。 具体实施中，可以将出发点取遍v 中各点而得到多个解，从中选择最好的 一个，时间复杂度增加了n 倍。 但此时最坏情况：e = ( 1 9 n + 1 ) 1 2 ；时问复杂度：o ( n 2 、。 3 c l a r k & w r i g h t 算法 s t e p1 任取一出发点p ，计算吩= d + d 珂一略； s t e p2 将各j ，由大n 4 , 排9 0 ； s t e p3 将排好后的各配对顶点 f ，j ) 依次适当连接，形成回路解。 适用范围：对称的三角型旅行商问题。 具体实施中，可将出发点p 取遍v 中各点而得到多个解，从中选择最好的 一个，但此时的时间复杂度增加了n 倍。 最坏情况：e = 2 l g n 7 + 5 2 l ；时间复杂度：o m 2 1 。 4 双生成树启发式算法( d o u b l es p a n n i n gt r e eh e u r i s t i c s ) s t e pl 首先求出最小生成树： s t e p2 将树中各边都添一重复边并求出其e u l e r 回路； s t e p3 在e u l e r 回路点序列中去除重复点，形成回路解。 适用范围：对称的三角型旅行商问题。 最坏情况：e = 2 ：时间复杂度：0 m 2 1 。 5 c h r i s t o f i d e s 算法 s t e pl 首先求出最小生成树； s t e p2 对树中所有奇顶点解最小权匹配问题； s t e p3 将匹配边添入生成树并求出其e u l e r 回路； s t e p4 在e u l e r 回路点序列中去除重复点，形成回路解。 适用范围：对称的三角型旅行商问题。 最坏情况：e = 3 2 ；时问复杂度：o ( n 3 1 。 6 r - o p t 算法 该方法是一种局部改进搜索算法，由l i n 等人( 1 9 6 5 ) 提出。 适用范围：对称型旅行商问题。 s t e p1根据一定的规则求出每个项点的候选顶点集，人为地规定该顶点只 能和候选集中的顶点相连接： 第三章旅行商问题的求解算法 s t e p2 产生初始路线； s t e p3 对每一个顶点轮流进行r - o p t 交换，直到无法改进当前解为止； s t e p4 输出当前的解作为结果。 最坏情况： e = 2 ( n 8 ，r 4 ) ； 时间复杂度： o ( n 7 1 。 l k 算法是一种典型的改进算法，也称为ro p t ( f o3 ，4 ) 算法。这种 算法从一条初始可行解出发，每一次从路径中选择r 条边，如果能通过交换边来 减少路径的长度，则交换，否则再选择另外的，条边进行同样的操作。如果在当 前路径中，任意，条边都不能通过交换来获得更短路径，则当前路径就是算法最 终的解。r 条边合计可能有的交换形式共有( 2 r 一3 ) ! 个，实际中往往只尝试几种 典型的交换形式，所以实践中采用的r o p t 都是受限制的r o p t 交换。 一个典型的2 - o p t 交换如图3 - 3 所示。右边的图为交换后的结果，显然，这 条路径中任意2 条边都不可能再通过交换来减少路径的长度，所以这条路径也是 一次2 - o p t 算法最终的解，在此例子中也是最优解。一个典型的3 - o p t 交换如图 3 - 4 所示 显而易见，3 - o p t 得到的结果理所当然是2 - o p t ，类似的有，r - o p t 的结果也肯 定是r - o p t ( 2 i i ) 。也就是浣，r - o p t 要优于r - o p t ( ，i i ) 。当r = n 时，r - o p t 的结果就是最优解。但遗憾的是，这种算法的时问函数是o j ，太大时。所 需时间会变得不经济。大量计算发现，3 o pt 法比2 o pt 法好，而4 - o p t 、5 - o p t 等却并不比3 - o p t 来得优越，况且r 越大，运算时间越长。目前常用的是3 - o p t 和2 - o p t 算法。对于3 - o p t 算法，有一经验公式，求得最优解的概率p = 2 “。r o p t 算法对于初始可行解的质量要求不高，不管初始可行解是随机的还是已经优化过 的，都能得到相近的结果。 图3 - 3一次2 - o p t 交换 第三章旅行商问题的求解算法 图3 - 4 一次3 - o p t 交换 对于一个5 0 个城市的旅行商问题，只须随机地将城市与城市相连，形成一 条可行路径，再以此为初始可行解，代入到3 - o p t 算法中求解，即可求得一个近 似解。分别独立地产生随机初始路径并求解1 5 0 次，在得到的1 5 0 个近似解当中， 其中至少有一个为最优解的概率大约为p j 一“一丁删7 0 ) 1 5 0 = 0 9 9 1 4 5 。 根据初始路线、候选集( c a n d i d a t es e t s ) 、数据结构、边的搜索交换方式 的不同，l k 算法有很多的变种，其中精度最高的是l k h 算法。l k 算法及其变 种是目前实际使用最多的算法，在很多实践中都得到应用。 7 合成算法( c o m p o s i t ea l g o r i t h m ) 用某个近似算法求得初始解，然后借助一个或若干个r o p t 算法对解加以改 进。这种合成型的算法往往能获得较好的解，但也很耗时，一般仅在对解有较高 要求时采用。 8 概率算法( p r o b a b i l i s t i ca l g o r i t l u n ) 该算法能对任意给定的e 0 ，在1 + e 之内几乎处处解决对称型旅行商问 题。假定g 位于单位正方形内，函数f ( 门) 映射到诈有理数，满足： f l 0 9 2 ( 1 0 9 2 肝) ；对所有n ， f 是完全平方。则有： s t e p l以k 0 ) 玎j “为尺寸构成网格，将单位f 方形分成丹f ( 厅) 个正方 形，将g 也分成n f ( ”) 个子图； s t e p2 用动态规划方法求解每个子图的最优回路； s t e p3 将n f ( 以1 个子图各自收缩为一点，其问距离定义为原子图的最优 子回路间最短距离，并对新构成的图求最小生成树t ； s t e p4 将t uf 各子图的最优子回路 视为一可能有点、边重复的闭回路， 根据三角形不等式条件，归约重复点或边，得旅行商问题回路。 适用范围：对称型旅行商问题。 最坏情况：e = 1 + f 任意给定正数) ；时间复杂度：o ( n l n n l 。 9 神经网络算法( n e u r a ln e t w o r ka l g o r i t h m1 八。卜年代中后期，美、日等国家出现了一股神经网络热潮，许多从事脑科学、 第二章旅行商问题的求解算法 心理学、计算机科学以及电子学等方面的专家都在积极合作，开展这一领域的研 究。其早期思想源于四十年代，由于受v o nn e u m m m 串行处理体系的限制，一 直进展不大，直到八十年代，美国生物物理学家h o p f i e l d 提出人工神经网络 ( a n n ) 模型，才被认为是一个重大突破。 人工神经网络( a r t i f i c i a ln e u r a ln e t w o r k ，a n n ) ，也称为神经网络( n e u r a l n e t w o r k s ，n n ) ，是山大量处理单元即神经元( n e u r o n s ) 互相连接而成的网络， 通过反映人脑的基本特性，对人脑进行抽象、简化和模拟的一种工程系统。人工 神经网络算法成为近年来的热点研究领域，涉及到电子科学与技术、电气工程、 控制科学与技术等诸多学科，其应用领域包括了建模、对| 、日j 序列分析、模式识别 和控制等，并且仍然在不断扩展。 作为神经网络的基本单元，神经元模型具备三个基本要素。其一是具有一组 突触或连接，常用w ，表示神经元i 和神经元，之间的联接强度，或称之为权值， 取值可在负值和正值之间；其二是具有反映生物神经元时空整合功能的输入信号 累加器；其三是具有一个激励函数用于限制神经元的输出。典型的人工神经元模 型如图3 - 5 所示。 一0 ， 图3 - 5人工神经元模型 在图3 - 5 中，j ，( ，= l ，2 ，n ) 为神经元f 的输入信号，w ，为联接权，i ： 表示输入信号线性组合后通过激励函数f ，o ，表示神经元的输出，0 ，表示神经元 的阈值。 根据信息流向和网络的拓扑结构，可以将神经网络模型分成以下几大类。 ( 1 ) 前馈神经网络。 ( 2 ) 反馈神经网络。 ( 3 ) 随机神经网络。 ( 4 ) 竞争神经网络。 而h o p f i e l d 和t a n k ( 1 9 8 5 ) 用a n n 方法求解旅行商问题获得成功以来，更 是引起了极大的关注，国内也报导了求解数百个结点旅行商问题的有关结果。该 _ 巧 第三章旅行商问题的求解算法 方法的思想是通过对神经网络引入适当的能量函数，使之与旅行商问题的目标函 数相一致来确定神经元之间的连接权，随着网络状态的变化，其能量不断减少， 最后达到平衡时，即收敛到一个局部最优解。w i l s o n 和p a w l e y ( 1 9 8 8 ) 曾研究了 算法的稳定性，当n 很大时，他们得出了相当悲观的结合，即，求解中很有可能 陷入在解空间中作无目标的周游或者落到许多局部最小点中的某一点上。但是， t a k e f u j i ( 1 9 8 8 ) 等发现，只要适当修正l i a p u n o v 函数，就可消除许多困难，他们 的结论因此而显得比较乐观。 目前，前述的几种神经网络都有在旅行商问题商的应用实例，且取得了一定 的成功，但还存在着严重缺点，而且就一般实际问题而言，无法与其它近似算法 相比。因此，该算法的适用范围很可能在于非欧空间或不可度量的旅行商问题方 面。 1 0 模拟退火算法( s i m u l a t e da n n e a l i n ga l g o r i t l u n ) 这是一种源于五十年代、基于m o n t ec a r l o 迭代求解思想的随机搜索算法， 八十年代才丌始应用于组合优化领域，其出发点是将组合优化问题与统计力学的 热平衡作类比，把优化的目标函数视作能量函数，模仿物理学中固体物质的退火 处理，先加温使之具有足够高的能量，然后再逐渐降温，其内部能量也相应下降， 在热平衡条件下，物体内部处于不同状态的概率服从b o l t z m a n n 分布，若退火步 骤恰当，则最终会形成最低能量的基态。这种算法思想在求解优化问题时，不但 接受对目标函数( 能量函数) 有改进的状态，还以某种概率接受使目标函数恶化