（计算机应用技术专业论文）时间依赖网络中国邮路问题研究.pdf

大连理工大学硕士学位论文 摘要 与传统中国邮路问题相比，对动态网络中国邮路问题的研究具有更为重要的现实 应用意义，成为了智能交通系统、计算机网络通信等复杂应用领域迫切需要解决的问 题。解决传统中国邮路问题虽然已经有高效的算法，由于交通事故，天气变化等偶发 因素，使得当网络为时间依赖网络时，应用传统算法得到的解将不符合实际情况的要 求。所以需要提出时间依赖网络中国邮路问题的模型，并借鉴时问依赖网络车路由问 题算法思想给出高效的算法。 本文总结了中国邮路问题各个分支的研究成果，详细介绍了时间依赖网络在最短 路径，货郎担问题，车路由问题中的研究情况；然后介绍了时间依赖网络的基本概 念、线性规划模型和f i f o 特性，并给出了求解时日j 依赖网络中最短路径算法的理论基 础，对动态的中国邮路问题进行了分类和综述，定义了时间依赖网络中的中国邮路问 题，总结了问题的特性，对动态网络和静态网络中的中国邮路问题进行了比较，证明 了该问题为n p 完全问题，并对静态算法在时间依赖网络中的病念实例作了分析；建立 了问题的线性规划模型，给出了时间依赖网络中的中国邮路问题第一种情况即时间依 赖欧拉问题的动态规划算法，并提出最近邻居启发式算法和随机最近邻居启发式算 法。 文章随后提出时间依赖中国邮路问题的分支割平面的精确求解算法和基于时间依 赖信息素空间的蚁群启发式求解算法，在随机产生的时i 日j 依赖网络中的实验结果表 明，此算法在解决时间依赖网络中的中国邮路问题上是有效的。 理论证明及实验测试都表明，时间依赖网络中国邮路问题算法为动态中国邮路问 题的研究提供了新的思路。时间依赖网络中国邮路问题算法的优点不仅在于模型更符 合实际情况，能够应用于各种实际问题，而且算法的效率较高，这对于某些领域的应 用是很重要的。 关键词：时间依赖网络；中国邮路问题；线性规划；分支割平面算法；蚁群优化方法 大连理工大学硕士学位论文 r e s e a r c ho nc h i n e s ep o s t m a np r o b l e mi nt i m e d e p e n d e n tn e t w o r k s a b s t r a c t c o m p a r e dw i t ht h es t a t i cn e t w o r k , c h i n e s ep o s t m a np r o b l e m ( c p p ) r e s e a r c hi nd y n a m i c n e t w o r ki sm o r ea p p l i c a b l e ，e s p e c i a l l yf o r m a n yc o m p l i c a t e da p p l i c a t i o n si n c l u d i n g i n t e l l i g e n tt r a n s p o r t a t i o ns y s t e m ( i t s ) ，c o m p u t e rn e t w o r ka n dc o m m u n i c a t i o n , e t c t h o u g h t r a d i t i o n a ln e t w o r km o d e la n da s s o c i a t e dc h i n e s ep o s t m a np r o b l e ma l g o r i t h m sa l r e a d yh a v e e f f i c i e n ta l g o r i t h m s ，t h et r a d i t i o n a la l g o r i t h mi si m p r a c t i c a lw h e nt h en e t w o r ki st i m e d e p e n d e n t d u et ot h ee f f i c i e n ta l g o r i t h mf o rt h et i m e d e p e n d e n tv r pp r o b l e m w ec a nb r i n g i nt h et h e o r yt 0s o l v et h ep r o b l e m t h e r e f o r e t h er e s e a r c ho fn e wn e t w o r km o d e la n d a s s o c i a t e dh i g he f f i c i e n ta l g o r i t h mf o rc h i n e s ep o s t m a np r o b l e mi nt i m e d e p e n d e n tn e t w o r k s b e c o m ea ni m p o r t a n tp r o b l e mt ob es o l v e du r g e n t l y ，w h i c hi sa l s ot h eg o a lo f t h i sp a p e r t h i sp a p e rs u m m a r i z e ss o m er e s u l t so fb r a n c h e so fc h i n e s ep o s t m a np r o b l e m t l l i s p a p e r a l s oi n t r o d u c e ss t a t i cc h i n e s ep o s t m a np r o b l e ma sw e l la si t ss o l u t i o n si nd e t a i l t h e n ， t h i sp a p e ri n t r o d u c e sb a s i cc o n c e p t ，t h el i n e a rp r o g r a m m i n gm o d e l ，t h ef i f oc h a r a c t e r i s t i co f t i m e d e p e n d e n tn e t w o r k ，a l s on ph a r do ft h ep r o b l e mi sp r o v e d ，a n dh a sg i v e nt h e o r y f o u n d a t i o nf o rt h es h o r t e s t p a t ha l g o r i t h mo ft i m ed e p e n d e n tn e t w o r k t h i sp a p e ra l s o c o m p a r e st i m e d e p e n d e n tc h i n e s ep o s t m a np r o b l e mw i t hs t a t i cc h i n e s ep o s t m a np r o b l e m ， a n da n a l y z e ss i c ki n s t a n c e sw h i c ht h es t a t i ca l g o r i t h m si nd y n a m i cn e t w o r k s f i n a l l y ，t h i s p a p e rp r o d u c e sd y n a m i cp r o g r a m m i n ga l g o r i t h ma n dn e a r e s t n e i g h b o rh e u r i s t i ca l g o r i t h m f o rt i m e d e p e n d e n tn e t w o r ke u l e r i a np r o b l e m t h e nt l l i sp a p e r p r e s e n tab r a n c h - c u t - p l a n ea l g o r i t h ma n da na l g o r i t h mb a s e do na na n t c o l o n ys y g e mu s i n gat i m e d e p e n d e n tp h e r o m o n e ss p a c e f i n a l l yr a n d o m l yg e n e r a t e d p r o b l e m sa r et e s t e dt oi l l u s t r a t eh o w t h ea l g o r i t h mc a nb ea p p l i e d n et i m e d e p e n d e n tn e t w o r km o d e la n dt h ec h i n e s ep o s t m a np r o b l e mp r o v i d eaw h o l l y n e wm e t h o dt oe f f e c t i v e l yi m p l e m e n tt h ec h i n e s ep o s t m a np r o b l e mf o rd y n a m i cn e t w o r k t h ea d v a n t a g e so fc h i n e s ep o s t m a np r o b l e mi nt i m e d e p e n d e n tn e t w o r ka l g o r i t h me x p r e s s n o to n l yo nt h ew i d eu i nm a n y p r a c t i c a la r e a s b u ta l s oo nt h eg r e a te f f i c i e n c yt os o l v et h e p r o b l e m , w h i c hi sv e r yi m p o r t a n tf o rm a n ya p p l i c a t i o n s k e yw o r d s ：t i m e - d e p e n d e n tn e t w o r k s ；c h i n e s ep o s t m a np r o b l e m ；l i n e a r p r o g r a m m i n g ；b r a n c h - c u t - p l a n ea l g o r i t h m ；a n tc o l o n yo p t i m i z a t i o n 独创性说明 作者郑重声明；本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 作者签 大连理工大学硕士学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位论文版权使 用规定”，同意大连理工大学保留并向国家有关部门或机构送交学位论文的复印件和 电子版，允许论文被查阅和借阅。本人授权大连理工大学可以将本学位论文的全部或 部分内容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇 编学位论文。 作者签名： 导师签名： 仓童画 量复丝 岬年牟月日 大连理工大学硕士学位论文 1 绪论 1 1 研究背景及意义 中国邮路问题是管梅谷教授【l 】在1 9 6 0 年第一次提出来的。基于此，a l a ng o l d m a n 推荐j a c ke d m o n d s 使用“中国邮路问题”这个题目，当时j a c ke d m o n d s 在g o l d m a n 的u s n a t i o n a lb u r e a uo fs t a n d a r d s ( 现在的n i s t ) 的运筹学组工作。e d m o n d s 很喜欢这 个题目并采纳了它。所以以后国际上就沿用这个题目了。e d m o n d s 和j o h n s o n 提出二 部匹配算法，这一算法可以同时用于解决无向图和有向图，但是对于同时含有有向边 和无向边的混合图却是n p 完全问题【l j 。 问题描述为：一个邮递员从邮局出发投递信件，他必须在所管辖范围内的所有街 道至少走一次，最后回到邮局，并希望选择一条最短的路线完成投递任务。如果把邮 递员管辖范围内的区域看作一个网络，邮局对应于网络中的结点，邮局间道路对应于 网络中的边，中国邮路问题转化为在网络中找到一条回路，使得回路包含所有结点， 且走过的边长最短。 中国邮路问题为图论中经典问题，有很多应用实例。例如，对不同层次上的计算 机系统拓扑结构进行测试这一实际问题可以转化为中国邮路问题。这些系统可以 被描述为图。处理器，开关或者寄存器对应于图中结点，结点日j 的数据流或者数据线 对应于图中的边。走遍一个欧拉回路被用来描述为发送一个测试包在最小时间内走遍 所有边和结点的过程。同时，邮路问题在车辆路径问题，清扫街道，机器人开发，交互 式系统分析，网站可用性上也有广泛应用。因此，这一问题一直受到国内外学者的广 泛关注。 但是，传统的中国邮路问题算法解决的都是静态网络中的问题，即网络中边权是确 定不变的情况。近年来，随着计算机网络与通信、分布式处理和智能交通系统的兴 起，向传统问题提出了新的挑战：时间依赖，即网络中边的走行时间是时间的函数。 因为在现实交通网络中，道路的交通状况是不断变化的，由于不可预测事件( 如恶劣天 气或修路、交通事故等) 的可能发生，邮递员管辖范围内的网络为动态网络，邮递员送 信所要经过的街道上的旅行时间是变化的。在车辆配送和运输过程中，经常会出现由 于交通事故，天气变化等偶发因素引起交通密度的改变和车辆行驶速度的变更，进而 导致旅行时间的变化。研究时问依赖网络中国邮路问题在很多领域具有现实意义，该 问题已成为亟待解决的新问题。 这在最短路径 2 - 4 1 ，货郎担问题，车路由问题等领域已经得到了深入的研究和应 时间依赖网络中国邮路问题研究 用。同样，我们注意到时间依赖网络中的中国邮路问题也有着重要的实际应用价值。 目前国内外这方面的研究很少，本文正是从这个角度出发，将中国邮路问题与时间依 赖网络相结合，做了有益的尝试。 时间依赖网络中国邮路问题算法的研究，相对于传统中国邮路问题算法提出了更 高的要求：( 1 ) 如何定义更贴近于实际情况的时间依赖网络模型；( 2 ) 如何借鉴传统 中国邮路问题算法思想及已有的时| 1 日j 依赖网络问题的研究成果，构建时间依赖网络中 国邮路问题算法的理论基础：( 3 ) 如何得到效率较高的时间依赖网络中国邮路问题算 法；本文的研究工作正是针对以上提出的要求而展开的。 时间依赖网络中国邮路问题算法的研究，能够为智能交通系统、计算机网络与通 信、分布式处理等应用领域提供坚实的理论基础；同时对构造新的动态网络模型，研 究新的中国邮路问题算法，扩大算法的应用领域，都具有非常重要的意义。 1 2 研究现状 中国邮路问题引起了国内外学者的广泛关注和深入研究。一方面，从提高算法的 计算效率的角度，给出了解决无向图和有向图中的中国邮路问题的多项式时间算法： 另一方面从解决实际应用的角度，引申出了许多中国邮路问题的推广问题，如乡村邮 路问题以及水灾邮路问题【l 引。国内外学者对图论中另一经典问题旅行商问题( t s p ) 及车路由问题( v r p ) 进行了深入的研究，并把时间依赖性假设引入到网络中，提出了很 多值得借鉴的研究思路。另外，很多学者也从各自从事的研究领域、不同的侧面对时 间依赖网络最短路径问题进行了研究。从问题定义到具体算法设计，国内外众多学者 都给出了很多成熟的思路和经验。 1 2 1 中国邮路问题研究现状 国内外目前对于中国邮路问题的研究主要有以下几个方面：在提高算法的计算效 率方面，管梅谷教授给出奇偶点图上作业法，但是算法不是多项式界的i ”。随后国内外 许多学者对中国邮路问题进行了广泛研究，j e d m o n d s ，e l j o h n s o n 提出了解决无向图 和有向图中的中国邮路问题的多项式时b j 算法【2 刀。混合图中的中国邮路问题，属于n p 困难问题【”，不可能找到一个多项式时间的算法。与混合图相近的是风向邮递员问题 ( w i n d yp o s t m a np r o b l e m ) u j ，该问题被证明是n p 困难问题。但是，如果图是欧拉图， 则问题可以用多项式时间求解。另外，在层次的中国邮路问题( h i e r a r c h i c a lc p p ) 中，图 中的边被分成群集，并且在群集上定义一个优先关系，要求群集上的服务顺序必须满 足这个关系。m d r o r ，h s t e m ，p t r u d e a u t l 6 】指出这个问题是n p 困难问题，但如果每 个群集是连通的并且优先关系是线性的时候，问题可以在多项式时日j 解决。对于n p 困 大连理工大学硕士学位论文 难问题，众多学者给出了启发式算法。另一个研究方向为中国邮路问题推广问题， n c h r i s t o f i d e s 和v c a m p o s ，a c o r b e r a n b 】首次提出乡村邮递员问题( r u r a lp o s t m a n p r o b l e m ) 。此问题假设邮递员需要到几个乡村的街道送信，而乡村日j 的道路只用来往 返，不需要进行服务的情况。类似地，关于e n 的s t e i n e r 邮路问题【2 甜，考虑图中包含两 个连通分支的情况，其中磊为边的子集。h s i a o f hw a n g ! 硎首次将时l 日j 窗口的概念加 入到了中国邮路问题中，即要求邮递员必须在投递的最后一定的时间范围内回到出发 点。 1 2 2 时间依赖旅行商问题研究现状 t d v r p 扩展了车路由问题( v r p ) ，它是货郎担问题( t s p ) 的一个延伸。v r p 把两点 日j 的开销或旅行时间看作已知和固定的。v r p 通常假定两点间的开销或旅行时间为距 离标量的转换。而现实生活中可能使用一些综合的可改变的计算开销的方法。假设开 销是固定的和实际近似的情况。在拥挤的城市中，两点日j 的开销或旅行时间不只是距 离的函数因为速度是变化的。交通密集度的波动会引起速度的波动从而导致旅行时间 的差异。这种差异一方面由于事故、天气状况或其他随机事件。另一方面由于每小时、每 天、每周或每季度的交通状况的循环。 如果旅行时间的主要差异由于时刻的差异，那么两点间的旅行时i 日j 就是确定的两 点间距离和到达某点的时刻的函数。如果忽略旅行时间的时刻依赖，我们也许得到一种 最适度的解答，得到一个另外路线结构和另外的需要的车数量而不是时间依赖最佳方 案。还有，我们也许获得各条路线都违犯时间窗口或最大可允许时间的解答。 作为t s p 的扩展，t d v r p 属于n p 完全问题( l e n s t r aa n dr 1 n n o o y k a n l 4 卅) ，多项时间确切的算法不太可能被开发。 许多学者对t s p 问题( d a n t z l g ，f u l k e r s o na n dj o h n s o n t 4 ”) 、多t s p 问题 ( g a v i s ha n ds 对瓦a n l h 【4 卅) 和v r p 问题1 4 3 1 做了大量研究。 p i c a r da n dq u e y r a t , r n e 研究t s p 问题认为相关各个结点的费用不仅取决于在 它之前的结还取决它在序列的位置，f o x ，g a v i s ha n dg r v e s t 4 9 】提出了先| ；i f 时间依 赖t s p 问题的一种新公式。他们假设城市i 和城市j 的时间消耗取决与时问段并且任何 二个城市之间的旅行时间是一时间段。在这些论文中讨论的时间依赖t s p 问题在概念 上与本文讨论的t d c p p 问题接近。在我们的模型中，对于t d t s p 和t d v r p 假定任 何二个城市之间的旅行时间是一时间段并且旅行时间取决于时刻而不是结点访问序 列，b a k e r t 4 4 1 ，m m s o l e m o n 和j d e s r o s i e r s l 5 0 1 研究了带时间窗口的t s p 和v r p 问 题。 时间依赖网络中国邮路问题研究 论文余下部分组织如下。在下章建立t d v r p 的数学模型并以t d t s p 作为特例。 第二部分讨论时间依赖函数的特性和问题的属性。第三部分阐述无时间窗口的t d t s p 和t d v r p 的最近邻居启发式算法。第四部分阐述无时间窗口的t d t s p 数学规划算 法。第五部分给出随机产生问题算法的结果。第六部分总结论文、阐述结论和将来工 作方向。 1 2 3 时间依赖最短路径问题研究现状 动态网络中的最短路径问题比传统的最短路径问题更具有现实意义，吸引了许多 研究者的兴趣。许多研究者认识到动态网络与静态网络的差异性，从各自从事的研究 领域、不同的侧面研究这一问题。 d r e y f u s 6 7 】认为传统的最短路径算法可以应用到动态网络，给出了改进d i j k s t r a 算 法求解动态网络最小时间路径问题的方法，并断言该方法会像静态最短路径问题一样 有效。显然这个结论是不正确的。k a u f m a n 和s m i t h 6 8 l 给出的d r e y f u s 算法在动态网络 中是不正确的反例，说明传统的最短路径算法的局限性，建立了严格的一致性条件来 限制“病态”实例的出现，即f i f o 网络，但是对于非f i f o 网络并没有进行研究。 o r d a 和r o m 6 9 , 7 0 】给出了三种类型的网络模型：提出了不受限制的等待模型、禁止 等待模型和源等待模型。当访问的结点允许等待时，这种方法可以确定最优等待时闭 或者如果在其它结点不允许等待而在源结点的最优等待时间。如果每一结点都不允许 等待，o r d a 和r o m 方法不能找到最优路径。o r d a 的方法在计算机通信网络中是有效 的，但是，在交通网络中是无效的，因为交通网络结点处等待是没有意义的，交叉路 口是不允许等待的。 文献 2 从理论上证明了传统最短路径算法，如d i j k s t r a 算法，在时间依赖网络上 不能有效地求解最短路径问题；同时，在没有任何限制性条件下，建立了一套完整的 理论和算法解决各种情况的问题，给出了时间依赖的网络模型、理论基础、求解最短 路径的优化条件和算法。 另外，随机网络最短路径算法研究的代表性论文有 3 1 , 3 8 1 。 1 2 4 动态网络车路由问题研究现状 由于动态网络v r p 受时间影响较大，且问题非常复杂，算法需要适应网络时间依 赖和随机变化的性质，因此传统v r p 研究中的各种算法己不能直接用来解决动态网络 v r p ，构造新算法与改进己有算法显得尤为重要( d y n a m i cv e h i c l er o u t i n gp r o b l e m ， d v r p ) 。 一4 - 大连理工大学硕士学位论文 目前对动态网络v r p 的研究主要是对时间依赖车路由问题( t d v r p ) 的研究。 t d v r p 的研究主要是从上世纪9 0 年代开始的，己被成功用来解决t d v r p 的模型主 要集中在混合整数规划模型方面，解决问题的算法主要是( 亚) 启发式算法，包括贪婪算 法、禁忌搜索算法、遗传算法和蚂蚁算法等。在时间依赖性质处理上，虽然用连续函 数表示行程时间比较接近实际，但为了便于计算，现有的研究大多都是用分段函数来 表示行程时间，或用分段函数表示行驶速度从而得到行程时问。m a l a n d r a k i 等( 1 9 9 2 ) 建 立了静态需求不带时间窗的t d v r p 的混合整数规划模型，其将网络路段运行时问函数 表示为分段函数，并且为了避免超车现象。其假定车辆可在结点处等待。 s l l 针对 t d v r p 和t d t s p 设计了贪婪算法，同时又针对t d t s p 提出了c u t t i n gp l a n e s 启发式 算法，并在实例计算中对两种算法做了比较。结果表明两种算法均能处理2 3 个时段 函数下的1 0 2 5 个结点问题，前者需要的计算时间更少，但不能保证得到最优解。 m a l a n d r a k i 等( 1 9 9 6 ) 隅l 在动态规划基础上结合贪婪算法提出限定的动态规划启发式算法 用来解决t d t s p ，其可以解决的结点数达到了5 5 个。b y o n g h u n ( 1 9 9 1 ) ，首次将时间 窗问题与t d v r p 结合，为降低问题复杂性，将时变函数设为单调函数，保证了节约、 插入和边交换等传统启发式算法的合法应用。 进入二十一世纪，t d v r p 研究获得了较大的发展，一些较成熟高效的算法被改进 用于解决t d v r p s o u m i a 等( 2 0 0 3 ) 硌】，提出了f i f o 准则，即从一点出发到相同的下一 点且在同一条路径上行驶，先出发的车辆要先到达。该准则比较符合实际情况，然而 早期研究在假设时变函数时并来充分考虑该准则。他们用时变函数表示行驶速度，再 由速度和距离间接得到行驶时间，从而避免使时间产生跳跃。在此基础上，s o u m i a 等 ( 2 0 0 3 ) 改进了并行禁忌搜索算法，将其应用于有时间窗的t d v r p ，并用基于三时段函 数1 0 0 个客户的实例比较了时间依赖策略和静态策略。结果表明，时间依赖程度越 商，前者比后者平均节约的成本越多。 在2 0 0 3 年，a l b e r t ov 等人发表了三篇关于t d v r p 的文章，提出应用蚂蚁算法解 决t d v r p 。他们通过将传统蚂蚁算法中的人工蚁释放的静态信息素改为具有时间依赖 型的动态信息素来适应t d v r p 时间依赖特性的需要，目标函数则是派车成本与行驶成 本最小化，应用两个蚁穴来进行优化，一个用来优化派车成本，另一个用来优化行驶 成本。取得了一定的效果。遗传算法在v r p 中应用比较纯熟且广泛，但由于t d v i 心 中时间特性突出，使得复制交叉变异算子的应用比较困难，需做较大的改进。s o u m i a 等( 2 0 0 3 ) t 7 3 l ，提出了f i f o 准则，即从一点出发到相同的下一点且在同一条路径上行 驶，先出发的车辆要先到达。该准则比较符合实际情况，然而早期研究在假设时变函 数时并未充分考虑该准则。他们用时变函数表示行驶速度，再由速度和距离间接得到 时间依赖网络中国邮路问题研究 行驶时间，从而避免使时间产生跳跃。在此基础上，s o u m i a 等( 2 0 0 3 ) 改进了并行禁忌 搜索算法，将其应用于有时间窗的t d v r p ，并用基于三时段函数1 0 0 个客户的实例比 较了时间依赖策略和静态策略。结果表明，时间依赖程度越高，前者比后者平均节约 的成本越多。 为了适应随机需求的情况，他提出在每个时段某一时刻保存原有路线己行驶部分 同时以当时位置做起点重新安排路线的策略，并在此基础上建立了混合整数规划模 型，讨论了适合的种群数量、运行代数、终止条件以及交叉复制概率等参数，针对固 定发车费用、等待成本、延迟成本、路径成本及车容量等参数进行了灵敏度分析。除 了上述主要成果外，在m a l a n d r a k i ( 1 9 9 2 ) 基础上建立了一种新的混合整数规划模型，对 l - k 启发式算法进行扩展并将其用于t d t s p ，对应用b e n d e r s d e c o m p o s i t i o n - b a s e d 上 下界启发式算法解决该问题也进行了尝试。实验表明，l k 扩展方法能在较短时间内 解决1 0 0 个结点的问题，并能保证得到较好的解。h i l l 和b e n t o n ( 1 9 9 2 ) t 7 5 1 提出了 p a r s i m o n i o u s 模型用来估计时间依赖型的旅行速度，并进行了实例的验正。y a n g b y t m g ( 2 0 0 0 ) 1 7 6 1 同样针对路径成本与客户满意度两个目标建立了混合整数规划模型，在 c - w 节约式算法基础上，提出了适合该模型的b c 节约式算法f b i c r i t e r i a s a v i n g a l g o r i t h m ) ，取得了一定的效果。 综上所述，当前，在国内外对中国邮路问题的研究中，具有广泛应用前景的动态 中国邮路算法，至今还没有人提出解决的算法。把完善的时间依赖网络问题的理论和 思想与传统的中国邮路问题求解思路相结合，研究时间依赖网络模型下的中国邮路算 法，将成为解决这一难题的有效途径之一，这也正是本文的研究重点。 1 3 本文的研究方法及主要工作 针对时间依赖网络中国邮路问题的研究要求，基于已有的时间依赖网络的研究成 果，本文主要做了以下几个方面的工作： 第一，首次提出了时间依赖网络无向中国邮路问题，即网络中边上的权值不是固 定不变的，而是随着到达边尾处的时间而变化，是一个时间依赖的变量。 第二，说明传统的静态中国邮路问题求解算法在时间依赖网络中不能正确求解问 题的病态实例，并给出了t d c p p 的问题特性和分析。 第三，提出了该问题的线性规划模型并在边点转换算法的基础上用动态规划方法 求解了该问题的欧拉问题。给出算法正确性的理论证明，以及算法时i 日j 复杂度，并给 出算法实例。 大连理工大学硕士学位论文 第四，设计实现了分支割平面的精确求解算法和高效的启发式求解算法。给出了基 于时间依赖信息素空间的蚁群求解算法及两个启发式最近邻居求解算法。 第五，构建用于实验测试的时间依赖网络，通过进行不同网络规模和网络特性下 的数据测试，给出了算法的求解效果及分析。 最后，总体评价本文研究方法的优缺点，对下一步的工作进行了展望。 1 4 本文的组织结构 本文余下部分组织如下： 第二部分介绍传统的中国邮路问题算法。主要介绍传统中国邮路问题模型的基本 定义、传统中国邮路问题算法。 第三部分介绍时间依赖网络算法。主要介绍时间依赖网络模型的基本定义、时间 依赖网络最短路径算法以及算法的优缺点评价。 第四部分时间依赖网络无向中国邮路问题模型和算法。首先给出了时问依赖网络 中国邮路问题的模型和定义。基于时间依赖网络理论基础，给出了时间依赖网络中国 邮路问题的特性和分析。说明传统的静态中国邮路问题求解算法在时i b j 依赖网络中不 能正确求解问题的病态实例并证明了时间依赖网络的中国邮路问题为n p 困难问题。 第五部分时间依赖网络有向中国邮路问题模型和算法。给出了时间依赖网络中国 邮路问题的边点转换算法。用动态规划方法求解了该问题的欧拉问题。给出算法正确 性的理论证明，以及算法时间复杂度，并给出算法实例，以及两个启发式最近邻居求 解启发式求解算法并给出了试验结果分析。 第六部分给出了分支割平面的精确求解算法。 第七部分设计实现了t d c p p 高效的求解算法，给出了基于时间依赖信息素空i 日j 的 蚁群求解算法。 第八部分实验测试。首先构建用于测试的时间依赖网络，然后通过对本文算法实 验测试，给出与算法的计算性能相关的因素：最后对实验结果做了理论分析。 最后，给出本文的结论和不足之处，并对下一步的工作进行了展望。 时间依赖网络中国邮路问题研究 2 传统中国邮路问题 2 1 邮路问题基本定义 定义2 1 图g 是指由非空有限集合v ( g ) ，矿( g ) 中某些元素的无序对的集合e ( g ) 构成的二元组( y ( g ) ，e ( g ”。v ( g ) 称为g 的顶点集。e ( g ) 称为e ( g ) 的边集。每一条边 都是无向边的图称为无向图。每一条边都是有向边的图称为有向图。 定义2 2 如果有两条边的端点是同一对顶点，则称这两条边为重复边。给定图 g = ( v ，e ) ，设v o ，v l ，v ，q ，e 2 ，e n e ，其中e t 是关联于结点- l ，l 的边，交 替序列称为联结v o 到的路。当v o = 时，这条路称作回路。 定义2 3 若图g 只有一个连通分支，则称g 是连通图。设无向图g = 0 。在g 中求一条闭迹c ，使它经过g 中每条边至少一次，并且c 包含 的边权总和最小。 问题的数学描述为：在赋权连通图中，求出添加重复边的集合e 1 e 满足：( 1 ) 把 互中的所有边作为添加边加入g 中，使得原图不包含奇数度结点，得到欧拉图；( 2 ) 在满足( 1 ) 的前提下，使脚( 置) = c o ( e ) 达到最小。 艇e 如果原图为欧拉图，则可以找出欧拉回路；如果图中存在奇数度结点，就要添加 重复边，使得新图中每个节点都为偶数度节点，并且耗费最小。 大连理工大学硕士学位论文 2 2 欧拉图的寻迹算法 2 2 1 弗罗莱算法 算法步骤如下圈： s t e p l ：任取起始点v 0 ，v o 寸r ； s t e p 2 ：设路r = 编( v o ，v ) ， p 2 ( v j i ，一：) 9 j 9 p ，( v 一v 。) ) 已选出，则从e 乜，p 2 ，e ，) 中选出边p ，+ ，使p 。与k 相连，除非没有其它选择，g ， e 。 仍应为连通的。 s t e p 3 ：重复步骤( 2 ) ，直至不能进行下去为止。 尽管这个方法显得很简单，但是它的时间复杂度却很高，因为要在每一步都要确 定即将删除的边是不是桥，而这是很苦难的。正因为如此，e d m o n d s 和j o h n s o n 给出 了另一个时间复杂度为o ( 1 v 1 ) 的算法，这就是e n d p a i r i n g 算法。 2 2 2e n d - p a i r i n g 算法 e n d p a i r i n g 算法描述如下： s t e p l ：给出一个简单的回路，它可能不包含图中所有的顶点，如果所有的边都包 含在该回路中，则算法结束。 s t e p 2 ：给出任意一个在回路中的顶点v 且该点连接一条部在回路中的边。从v 点 开始构造另外一条回路并且不与第一条回路重叠。 s t e p 3 ：假设e i 和p 2 是第一条回路上连接顶点v 两条边，e ，和气是第二条回路中连 接点v 的两条边，把这两条回路合并成一条简单的回路：从顶点v 出发经过边已遍历回 路2 直到经过边气回到点，再从边岛开始遍历回路1 直到经边q 回到点n 这样两条回 路就被连成了条回路。如果所以的边都遍历了则算法结束，否则回到第二步。 2 3 无向中国邮路问题 2 3 1u c p p 的整数线性规划定义 定义吻为何，巧) 上的重复边的个数， 的奇数度结点。公式表示如下： 一 m i n i m i z e乙c hx ( v ，叶) e 万o ) 为从形出发的边的数目。丁v 为y 中 ( 2 1 ) 时间依赖网络中国邮路问题研究 f l ( m o c l 2 ) 如果u t 满足：( 。，二( 啪砌2 1 0 ( m o d 动如果v f 叭r 2 3 2 传统中国邮路问题求解算法 解决静态中国邮路问题的算法 2 7 1 有管梅谷教授提出的奇偶点图上作业法， e d m o n d s & j o h n s o n 方法，f l o y d - h u n g a r y 算法。其中，e d m o n d s & j o h n s o n 方法为多项 式时间算法。 ( 1 ) 奇偶点图上作业法 定理2 2 设g 是包含了连通加权无向图g 的所有边的一个回路，则g 具有最小长 度的充要条件是： g 的每条边在g 中最多重复一次； g 的每个回路上，在g 中重复边的长度和不超过回路长度的一半。 算法主要过程 s t e p l ：任给一个初始方案，按照初始方案添加重复边，使网络各结点的度数均为 偶数，网络成为欧拉图。 s t e p 2 ：检查每一回路重复边的长度和是否不超过回路长度的一半，如是，则现行 方案即为最优解，否则进行下一步。 s t e p 3 ：调整重复边，即将回路中重复边改为不重复，不重复的边改为重复，返回 s t e p 2 a ( 2 ) e d m o n d s & j o h n s o n 方法 当网络规模较大的时候，圈的数目比较多，圈的检查易于遗漏，并且重复边的调 整亦无规律可言。 e d m o n d s 和j o h n s o n 利用二部匹配法给出了解中国邮递员问题的有效方法。 定理2 1 3 设g = ( 矿，e ，m ) 为赋正权的连通图，e 为g 的最优集，h ：6 e + 】，矿 为g 中所有奇点的集合，l v l = 2 k ，则日+ 可以表示为分别连接v 中k 对不同顶点的g 中七条最短链的总和。 定理2 4 说明：要找出g 的最优集，只要求出g 中以2 个奇点为起点和终点的七 条最短链，并使这k 条最短链的权之和最小。这样七条最短链的所有边的集合就是g 的 最优集。由此启发我们构造一个以y 为顶点集的赋权完全图。令图中每条边 上的 权等于g 中最短m ，n ) 链的权。因此求g 中满足上述要求的t 条最短链就等价于求图 的最小权完美匹配，即最小权最大匹配。 大连理工大学硕士学位论文 算法步骤： s t e p l ：应用任意顶点对之间的最短路径算法，计算原网络各奇点之间的最短路 径。 s t e p 2 ：从网络中取出所有的奇点，构成一个导出子图，予图中顶点数必为偶数。 取足够大常数减去相应顶点对之间的最短路长来定义各个边的权值。 s t e p 3 ：在导出子图中求解最大权匹配，则所得到的必为饱和各奇点的最小权匹 配。 s t e p 4 ：为了恢复到原图，明确与原网络对应的重复边，需要按最短路径列出所有 的重复边。构成最短路径的重复边与奇点关联的边数为1 ，与偶次顶点关联的边数为 2 。 ( 3 ) f l o y d - h u n g a r y 算法 算法步骤： s t e p i ：找出奇点及奇点数。 设中国邮路问题对应的无向图为g = ( 矿，d ，且m = j l ，i e l - 历设图中有v 个奇 点，分别记作圪，由图论知识可知，v 为偶数。 s t e p 2 ；求出各个奇点的最短距离。 利用f l o y d 方法，求出顶点v f 与v j 之间的最短距离，当然也找出了，碥：，中 每两点之间的最短距离，记f = ( ) 。，显然，f 是对称矩阵。 s t e p 3 ；找出各个奇点的两两配对的最优方案。 设矩阵c = ( 气) 。，其中白= i f l j , ，i l * ：j ，为最小指派问题的系数矩阵，利用 h u n g a r y 算法求出最小指派对称解，不妨设c l b ，a i ，c 如，c b b ，c 0 帆瓯札为最小对称 指派解。即c l h + c 岛l + c + c + + g 驰+ c “铀为矩阵c 中，个独立元素和的最小 值。则血+ 矗+ 五：b + 硒4 - 4 - 麻西+ 矗“为f 中r 个独立元素的最小值，则 h + 1 + 厶, 1 3 + 矗t ：+ + 矗埔+ 尼。为奇点，两两配对的最小距离总和。 s t e p 4 ：为各个配对奇点的最小距离加边。 在图g 中，血+ 矗i + 皿+ 硒+ + 丘南+ 五b 。为奇点，配对，再按 照f l o y d 方法找出配对奇点之间的路径，为该路径的每一条边增加一条重复边，则图 g 没有奇点，任意一条欧拉回路即为中国邮路问题的最优解。 时间依赖网络中国邮路问题研究 2 4 有向中国邮路问题 2 4 1 整数线性规划定义 定义集合，的任意结点砩中，满足入度大于出度的结点的集合为研。集合，的任意 结点”中，满足出度大于入度的结点的集合为西。有向中国邮路问题定义如下： n f i n c o x v ( 2 2 ) v l e l e j 满足：艺，x u2 鼬( v ，) v f e 勖= d j( n ，) 叶e j x o 0m ，v j ，) 2 4 2 问题描述 在中国邮递员问题中，如果邮递员负责投递的街区的每条街道都是单行道，则邮 递员的投递区可以用赋正权的连通有向图表示，其中每条街道对应一条边，街道的交 汇点对应一个顶点，街道的长看作边的权，因此这类邮递员问题称为赋权有向图上的 邮递员问题。 各条边的有向性使邮递员回路不能在各条边上任意前进，在某些网络中其有向回 路可能不存在，当某个定点仅有入边而没有出边时，回路将终止于该顶点。有向图中 欧拉回路存在的条件是仅当图中各个顶点的度都为对称平衡的，即进入顶点的入度等 于该顶点离开的出度。 2 4 3 静态算法 有向网络中的中国邮路问题可以转化为最小费用流问题。为此，只需在原网络中 增加虚原点v s 和虚汇点耽，各个入度大于出度的发点均收到一条来自于虚原点的入边， 各个出度大于入度的收点均发出一条出边指向虚汇点。令每一条虚原点至发点的边容 量等于该发点的供量，每一条收点至虚汇点的边容量等于该收点的收量，并令原网络 中每一条边的容量为无限大，各条边的权值为费用率，与虚原点，虚汇点相关联的边 的费用率为0 ，据此，可以求得满足所有收发量的最小费用流，也就是是重复边的权值 总和最小的有向邮递员回路。 大连理工大学硕士学位论文 2 5 混合中国邮路问题 给定一个强连通图g ( v ，e 彳) ，其中