（模式识别与智能系统专业论文）智能交通系统动态网络流模型与优化算法研究.pdf

内容摘要 智能交通系统( i t s ) 将先进的信息技术综合应用于交通运输管理体 系，以实现道路利用效率的最大化以及车辆与行人的最佳流动现代交通 网络可以抽象为动态网络，与其相应的最优路径及流量分配等问题是目 前i t s 研究中的热点与难点，具有十分重要的理论与实际意义本文对 i t s 动态网络流的相关问题进行了研究，重点在出行决策建模、路况预测、 动态最优路径和动态流分配等方面展开了如下工作： 1出行决策建模，包括最短路程、最短时间、最小费用模型和公交 换乘方案 2 给出了全局最优的最短路径双向搜索算法 3 研究了变权网络最短路的稳定性问题：给出了最短路长度稳定和 最优解稳定的充要条件提出稳定分支的概念，在变权情形下应用 修正的d i j k s t r a 算法求解最短路 4 证明了动态网络最短路问题是n p 困难的，给出了基于稳定区问的 近似算法， 、 5 建立阻滞动态流问题的数学模型，定义拥挤度基于局部时间扩张 网络求出初始解，并以动态最小费用流和最速流为目标进行改进 6 数值仿真验证了本文所提出算法的有效性 关键词：智能交通，数学模型，动态网络，优化算法，最短路，稳定 性，拥挤度，时间扩张网络 a b s t r a c t 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 s ( i t s ) a r ea p p l i e dt ot r a f f i cm a n a g e m e n tf o r t h ep u r p o s eo fm a x i m i z i n gr o a du t i l i z a t i o nr a t i o t h es h o r t e s tp a t ha n df l o w d i s t r i b u t i o no fd y n a m i cd i r e c t e dn e t w o r k sa r es i g n i f i c a n tp r o b l e m si nt h e s t u d yo fi t s t h ec o n t r i b u t i o n si nt h i st h e s i sc a nb es u m m a r i z e da sf o l l o w s ： - m o d e l i n g t h et r a f f i cr o u t i n g s t r a t e g y - p r e s e n t i n gt h eg l o b a lo p t i m u mt w o w a ys e a r c ha l g o r i t h mo ft h es h o r t e s t p a t h - t h e c o n c e p ta n dt h es u f f i c i e n ta n dn e c e s s a r yc o n d i t i o nf o rt h es t a b i l i t yo f t h es h o r t e s tp a t h sa r eg i v e n b a s e do nt h i st h e o r y , an e ws t a b l eb r a n d - b a s e d v a r y i n gw e i g h ts h o r t e s tp a t ha l g o r i t h mi sp r o p o s e d 一p r o v i n gt h a tt h ed y n a m i cs i n g l es o u r c es h o r t e s tp a t hp r o b l e mi sn p - h a r d a na p p r o x i m a t e a l g o r i t h mb a s e do ns t a b l ei n t e r v a li sg i v e n - p r e s e n t i n gt h em a t h e m a t i cm o d e lo fb l o c k i n gd y n a m i cf l o w p r o p o s i n gt h e d e f i n i t i o no fs a t u r a t i o nl e v e l g i v i n gt h es c h e d u l i n gm e t h o d so ft h e m i n i m a lc o s tf l o wa n dt h eq u i c k e s tf l o w 一e x p e r i m e n t a ls i m u l a t i o n s s h o wt h e e f f i c i e n c y o ft h en e wa l g o r i t h m s s i g n i f i c a n t l y k e y w o r d s ：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 ，m a t h e m a t i cm o d e l ，d y n a m i c n e t w o r kf l o w , o p t i m i z a t i o na l g o r i t h m ，s h o r t e s tp a t h ，s t a b i l i t y , s a t u r a t i o n l e v e l ，t i m e e x p a n d e dn e t w o r k i i j _ 1 引言 1 1 智能交通系统概述 2 0 世纪8 0 年代以来，世界各发达国家已基本建成四通八达的现代化 道路网，但随着经济的发展，交通需求日益增加，路网通行能力已远远 满足不了交通量增长的需要，城市交通拥堵日趋严重等问题引起了普遍 关注目前，国际上先进的交通系统己从主要依靠修建更多的道路、扩 大路网规模，逐渐转移到用高新技术来改造现有的道路及其管理体系， 从而大幅提高路网的通行能力和服务质量，实现道路利用效率的最大化 以及车辆与行人的最佳流动因此，智能交通系统( i n t e l l i g e n t t r a n s p o r t a t i o ns y s t e m s ，简称i t s ) 的研发也应运而生 i t s 是指在较完善的道路设施基础上，将先进的信息技术、数据通信 技术、电子传感技术、自动控制技术、计算机技术、网络集成技术以及 系统工程等综合应用于整个交通运输管理体系，建立起一种全方位发挥 作用的实时、准确、高效的综合信息服务系统i t s 将服务对象的重点由 以往的管理者转向道路使用者，即通过先进的科技手段向道路用户提供 必要的信息和便捷的服务，以减少交通堵塞，从而达到提高道路通过能 力的目的杨2 0 0 0 ，郑2 0 0 1 ，张2 0 0 3 美国、欧洲、日本是目前世界i t s 研究的三大基地在国际上具代表 性的智能交通系统有：美国智能车辆道路系统( i v h s ) 、欧洲高效安全交 通计划( p r o m e t h e u s ) 、欧洲车辆安全道路结构计划( d r i v e ) 和日 本的车辆信息与通信系统( c s ) 1 2 理论研究热点 1 2 1 交通仿真 仿真是解决那些规模大、成本高、难于再现的问题的重要方法交通 仿真模型分为微仿真( m i c r o s c o p i c ) 、区域性仿真( m e s o s c o p i c ) 和宏仿 真( m a c r o s c o p i c ) 已有的微仿真模型主要有p a r a m i c s 、c o r s i m 、 v i s s i m 、a i m s u n 2 、t r a n s i m 和m i t s i m ，宏仿真模型主要有p r e f i d 、 a u t o s 、m e t a n e t 和v i s u m ，区域性仿真模型主要有d y n a s m a r t 、 d y n a m a t 和i n r e g m 0 n 等微仿真模型是基于连续或离散的计算 和预测单独的车辆状态，在仿真过程中测量每一个单独车辆的速度和位 置，它不依赖于交通流模型的理论，只是建立在车对车相互作用的基础 上宏仿真模型是将速度、流量和网络中每一条链路上的密度综合起来作 为对交通流的描述，只反映整个交通网络的特点区域仿真模型，则是将 以上两种模型结合起来这些模型都在特定的研究领域中取得了成功 目前较为成熟的是美国m i t 的交通仿真分析系统 1 2 2 并行计算 传统的i t s 主要基于单机上的串行处理技术，难以在全局范围上提 供有效服务，成为i t s 发展的瓶颈并行处理技术是解决这一问题的有效 t - 段 n i e d r i n g h a u s l 9 9 3 ，b e r t s e k a s l 9 9 6 并行处理的关键技术是交通域的 划分与分解一个好的网络分解方法应使子网的直径小、交界面少、边界 2 点总数少、每个交界面的边界节点数大合理、科学地划分并行交通域， 能够使城市交通并行计算系统负载平衡，处理机节点之间通信量小，达 到实时高效的应用目标 h e n d r i c k s o n l 9 9 3 应急服务在城市交通中具有特殊的地位，对系统实时性要求极高 并行处理技术为其提供了必要基础和有力支持：一方面，使立即反应成 为可能；另一方面，常规计算环境下许多难以处理的问题可以在并行计 算环境下得以简单解决 g e n d r e a u l 9 9 9 ，2 0 0 1 ，t r e m b l a y 2 0 0 1 基于并行计 算平台的急救车实时调遣已在美欧部分城市开始运行 1 2 3 交通路况预测 交通路况预测是出行决策的先导，而预测的直接依据是多源海量交 通信息城市交通是个复杂的大系统，影响交通路况的因素很多，除了路、 车、人之外，还有天气、季节、温度、时间段、突发事件等多源累积的 表征交通路况特征的数据巨大，包括交通流量、交通密度、时间平均速 度、空间平均速度、车头时距、车头空距等，并且异地分布存储，必须 利用交通流分析理论建立因素和参数的对应和关联，研究数据的融合与 集成、结构与联接、映射与重组、元服务等交通预测的关键技术有：全 局路况的递阶预测技术，基于历史信息的大样本的时间序列预测技术， 基于粗糙集的海量交通数据的约简技术目前，代表交通预测研究水平的 是美国加州大学戴维斯分校的交通数据管理、分析与挖掘利用系统，东 京大学京都大学的城市大规模交通网络动态预测与分析系统 1 2 4 动态网络流模型 交通网络是一种特殊的网络，其扰动因素多、可变性强静态的网 络流理论已较为成熟 f o r d l 9 6 2 ，b o n d y l 9 7 6 ，l a w l e r l 9 7 6 ，p a p a d i m i t r i o u 1 9 8 2 ，a h u j a l 9 9 3 ，e t c ，但对于i t s 服务来说，实时、动态的出行决策与 调度算法的研究显然更具意义但是，当各路段的车速( 或流量，交通 密度等) 均为时变函数时，基于静态网络系统的最优化原理不再成立， 静态最短路算法、最小费用流算法等也都不再适用因此许多科技工作 者致力于研究动态网络流模型，主要集中在动态最短路算法 c h e n l 9 9 8 ， 谭2 0 0 2 ，e t c 】和动态流分配算 法 b u r k a r d1 9 9 3 ，k l i n z1 9 9 8 ，e t c l 勺修正上 1 3 本文工作简介 1 3 1 本文研究内容 路径查询是i t s 最基本的功能之一，基于最短路算法的静态查询技 术已较为成熟研究中我们发现，对于静态的交通网络，通过存储预先计 算出的最优路径可以提高用户查询的效率，实现近似常数时间的查询( 只 依赖于数据库的查询时间) 当网络发生变化时，若以实时的弧权函数替 换原静态的弧权函数，再次调用最短路算法，效率会比较低既然已保存 了静态的最短路树，就应利用此刻未变的最优路径信息因此，本文研究 如何确定最短路树的不变部分( 稳定分支) ，以其作为初始的永久标号集， 提高了计算效率 对于弧权函数连续变化的动态网络，本文首先证明了动态最短路问 题是n p 困难的，进而给出了一种基于稳定性的近似算法：以分段的线性 函数形式逼近非线性的权函数，再将每个线性子区间划分为稳定区间， 各稳定区间的解联接起来得到整体的最优解 在这里对本文的两个概念作一下区分：“动态网络”是指弧的权重依 赖于时间不断变化，考查的是网络在一段时间内的特性；而“变权网络” 是指相对于静态而言，弧权发生了变化，考查的是网络此刻的瞬时特性 ( 如与静态相比较的稳定性) 可将“变权网络”视作“动态网络”的一 个时刻 另外，人工智能中的双向搜索思想很早就被引入最短路算法中，但 一直未能得到广泛应用，因为现有的最短路双向搜索算法是一种近似算 法，求得的路径不一定是最短的本文给出了基于“跨越弧准则”的全局 最优双向搜索算法，提高了最短路算法的运行效率 动态流的调度算法是本文研究工作的另个重点以往的动态流模 型有一个局限性：弧的运行时间是一个常数在实际的交通网络中，车辆 的运行速度往往与弧的拥挤度有关：流量越大就越拥挤，越拥挤车速就 越低，运行时间也就越长本文正是研究了这种带有阻滞作用的情形首 先建立此问题的数学模型，给出拥挤度定义，并提出基于局部时间扩张 网络的方法，依次求出多条单位流路作为初始解，然后分别以动态最小 费用流和动态最速流为目标进行改进，最终得到启发式调度方案 1 3 2 本文具体结构 本文的后续结构如下 第2 章：交通建模与路况预测2 1 节简述了静态方案( 最短路程模 型) 、动态方案( 最短时间模型和最小费用模型) 以及公交换乘方案( 最 短时间、最小费用、最少换乘和最短步行模型) 2 2 节综述了时间序列 预测技术，统计方法寻找数据的相关维及时延，进而用邻域法进行交通 路况预测 第3 章：动态网络最优路径算法3 1 节给出了全局最优的最短路径 双向搜索算法3 2 节研究了变权网络最短路的稳定性问题：给出了最短 路长度稳定和最优解稳定的充要条件；提出稳定分支的概念，在变权情 形下应用修i t i 拘d i j k s t r a 算法求解最短路3 3 节证明了动态网络最短路问 题是n p 困难的，给出了基于稳定区间的近似算法数值仿真验证了算法 的有效性 第4 章：动态阻滞交通流调度算法4 2 节建立阻滞动态流分配问题 的数学模型，定义拥挤度；4 3 节基于局部时间扩张网络依次求出多条单 位流路作为初始解；4 4 节分别以动态最小费用流和最速流为目标进行改 进4 5 节进行复杂性分析 第5 章：结语 2 交通建模与路况预测 2 1 最优出行决策 智能交通系统中，交通模型的建立是交通管理和信息服务系统的核 心与基础，在整个i t s 研究中具有极为重要的作用建模的目的是最大程 度地减小出行者路径选择的盲目性，最佳出行方案是服务的首选，并且 其计算时间占到整个系统运行时间的大半部分如由m a h m a s s a n i 建立的 动态交通分配模型中用于最短路计算的c p u 时间占总c p u 时间的7 0 以上可见，最优出行方案模型和算法的选择对整个交通管理系统的性能 有着很大的影响 根据需求可以建立不同的最优出行模型：按出行条件可分为静态模 型和动态模型；按出行方式可分为步行模型，出租车模型和公交模型； 按出行目的可分为路程最短、时间最短、费用最少或是个性化目的等等； 一般情况下都可以抽象为在特定道路网中寻找具有最小代价的路径问 题，但往往不能直接应用图论中的最短路( 最小权路) 算法，因为赋权 的不仅仅为弧( 比如公交模型中节点也可以赋权) ，权函数有时是可变的 我们可以把城市交通网络看作一个有向图g 。，一) ，各交叉路口构成 节点集v 一 l 2 ，n ，各路段构成弧集a 一 ( f ，nf ，一1 ，2 ，一 ，弧( f ，) 爿的 权( 弧长) 为c l ，z 0 ，在交通网络中一般称为路( 段) 阻( 抗) 函数，它 可由多种因素复合而成，例如路段长度，宽度，拥塞情况( 可由平均车 速表示) ，路面等级等，路长和车速是其中之关键并设s ，“y 为指定的 起点和终点一条s 一“路是指一组首尾相接的弧的序列，其中s 是首项的 起点，“是末项的终点一条s 一“路p 的长度定义为 妒) | 。o 。7 ，e p 最短路问题是：求一条s 一“路p 使其长度f ( p ) 为最小 2 1 1 静态方案一最短路程模型 所谓静态，也称零流，是指不考虑车流和拥塞的情况那么，在此 前提下无论何种目标的最优都可归结为路程最短，当然，路程最短也是 行人和自行车出行的一般目标这时，路阻函数就可以近似地由路段长 度s 。来表示， c ；一， 借助经典的最短路算法，如d i j k s t r a 算法，我们可以得到从指定起点到其 余各点的最短路径 2 1 2 动态方案一最短时间模型 更为有意义的是考虑实时动态的乘车出行方案，那么这时交通路况 便是一个不能忽略的因素反映路况好坏有三大参数：交通流量、车行密 度以及平均车速，其中车速可由车载的g p s 数据直接提供，是最为方便 的，因此我们一般就以路段o ，) 的平均车速来表示该路段的拥堵情况 不同的用户往往关注的对象不同，时间因素经常是用户首先要考虑的， 若目标函数为到达终点的最短时间m m t ( p ) ，我们可以把行驶路段( f j ) 的时间定义为路阻函数 那么求解出的最小权路径所对应的便是最短时间决策 2 1 3 动态方案一最小费用模型 时间并不是评价所选路径优劣的唯一指标，有时行车距离、油耗或 尾气排放也在用户的考虑之列，往往需要定义一个广义费用来表征综合 的路阻这里采取一种简化的方式，即参考出租车的计价方式，给出与 所选路径相关的费用：设定一个低速阈值v 。，当车速高于此阈值时，费 用仅和路程有关，每公里单价设为d ，；当车速低于此阈值时，需要双重 计费，即不仅计算路程，还要计算时间，每分钟单价设为d t ，那么总费 用就应该是 粥卅，。+ d r 0 善詈 若目标函数为到达目的地的最小费用m i n d ( p ) ，我们可以把行驶在各路段 上的费用作为路阻函数，即 o v o ； i d ，+ d ，号，t 那么求解出的最小权路径所对应的便是最小费用决策 2 1 4 公交模型 在原始的城市交通网络g 上构造一个有向的公交线路辅助网络g ， 图的节点为各公交站点与出行者的起讫点如果在某个节点有七个公交 站，那么就把此节点分拆为k + 1 个子节点：后路公交站对应k 个公交子节 点，步行弧对应一个步行子节点；地理位置相同的一组k + 1 个子节点构成 一个有向完全图( 因此可称为团) ，其中连接公交子节点的边的权都相同， 记为，( 换线时的等待) ；从步行子节点到公交子节点的弧的权也为i g ， 从公交子节点到步行子节点的弧的权为0 ( 下车后不用等待直接转为步 行) 两组节点之间有弧相连，弧可分为两类，一类为公交直通弧( 相邻 站点i ，j 之间如果有相同的公交线路经过才定义此类弧) ，弧长为两站之问 的行驶时间( 或费用) ，记为。芋，k 一1 ，2 ，为公交线路编号；另一类为步 行弧，弧长记为。：，设定一个距离l ，长度超过的步行弧删去 根据出行者的目的不同，我们提出以下四种方案： ( 一) 公交最短时间模型 当出行者的目标为时间最短，就可以应用此模型这时把在某段弧 ( 直通弧和步行弧) 上的走行时间定义为弧长，应用修订的d i j k s t r a 算法 来求解最短路：一旦某一组中某个子节点获得标号( 称为“首标点”) ， 其余子节点自动获得标号：如果是从公交到公交或步行转公交，其余子 节点的标号等于首标点的标号加上等待时间，如果是从公交到步行，其 余子节点的标号与首标点的标号相同出行者每走到一个站点都面临三 个选择：第一，继续原线路，这时公交线路编号k 保持不变；第二，继 续乘车，但改变线路，这时k 发生变化，并且要计及等车时间w ；第三， 由乘车改为步行 ( 二) 公交最小费用模型 往往有些出行者的目标是费用最少，这时需修改上述最短路算法： 首先，运行时问换成车费，那么，步行费用= 0 ；其次，换线的等车费用 = 0 ；最后，还需加一个约束：总步行 见h ) ， 即以化) + 见化卜见k ) + 几k ) 2 f ( p 1 ) ，所v a v ：肯定不在最短路上，这与假 设矛盾，所以最短路上的所有节点都已经搜索到口 双向搜索区域大约是经典算法的一半，如图3 1 1 所示如果暂不考 虑高架路，实际的交通网络都是平面图，且各节点的度一般在3 5 之间， 那么跨越弧就不是很多因此双向搜索提高了最短路算法的执行效率 图3 1 1 双向搜索与经典算法搜索范围示意图 由于双向搜索具有互不干扰性，即从起点出发的搜索和从终点出发 的搜索没有数据相关性，我们可以考虑将双向搜索的任务划分为两个互 不相干的子任务，将这两个子任务分配到并行机的两个节点上分别执行， 可以将响应时间再缩短近1 2 有些交通网络中会存在一些关节点，即从起点到终点所必须经过的 点例如，在上海要从浦西到浦东，必须经过跨越黄浦江的桥梁或者隧 l o 道这些桥梁和隧道就构成了整个路径的关节点在这种情况下，当处 理机数量较大并且有空闲时，我们可以考虑在起点、终点和每个关节点 处配置一个处理机进行搜索，进一步缩短计算时间 3 2 变权网络最短路的稳定性研究 ， 在经典最短路问题中，诸弧的权( 长度或费用) 是事先给定且固定 不变的但是，在实际交通问题中，这些弧长可能发生变化例如在交通 出现拥堵时，线路的运行时间会变长近年来，由于分布式计算及任务调 度、网络通信，尤其是智能交通系统的迅速发展，变权网络上的最短路 算法的研究受到了越来越多的关注 针对i t s 中所面临的问题，本文提出了一种基于稳定分支的变权网 络最优路径算法模拟实验显示本文方法在计算效率上明显优于传统的 d i j k s t r a 算法我们的工作受到如下一些观察、分析的启发： 1 对于静态的交通网络，通过存储预先计算出的最优路径可以提高 查询的效率，实现近似常数时间的查询( 只依赖于数据库的查询时间) 而 对于动态网络的某个时刻，最短路树通常只发生了部分的改变( 与静态 树相比) ，当用户的查询只涉及最短路树的不变部分( 稳定分支) 时，系 统则不必调用最短路算法，从而在整体上提高系统的效率 2 当网络发生变化时，若以实时的权函数替换原静态的权函数，再 次调用最短路算法，效率会比较低既然已保存了静态的最短路树，就应 利用此刻未变的最优路径信息来优化初值，以提高计算效率 根据上述分析，找出最短路树的不变部分是问题的关键 3 2 1 预备知识 最短路问题可表为如下的线性规划( p ) 【p a p a d i m i t r i o u l 9 8 2 】： 嘶n 。譬” 豇弘泓。忙 无之0 ，v ( i ，) 彳 ( 3 2 1 ) ( 3 2 2 ) ( 3 2 3 ) 此问题( 特殊的最小费用流问题) 总存在整值最优解，记为 ) ，f h m l 的弧组成的s 一“路p 一定是一条最短路；反之，一条最短路p 一定对应于 这样的最优解 其次来看上述问题的对偶问题设以为节点i 的位势，约定发点s 的位 势以- 0 原设问题( p ) 的对偶问题( d ) 如下： 0 q ，胙一 筠 对于每一个弧( f ，i ) e a ，石，一一称为它的势差，势差不超过弧长 由线性规划的对偶定理可得如下互补松弛性条件：原设问题( p ) 的 可行解饥，是最优解的充要条件是存在对偶问题( d ) 的可行解协) 使得 fq ) 0 a i a l - c q 这将成为最短路的判定准则：最短路中的每一条弧都有势差等于弧长 d i j k s t r a 标号算法求出的最短路长度 p ) 就是对偶问题的最优解， 即其永久标号p 0 ) 就是最优解中的位势曩【p a p a d i m i t r i o u l 9 8 2 】算法求出 的所有最短路构成以s 为根的支撑树，称为最短路树借助d i j k s t r a 算法 可求出初始状态( 或称静态) 的最短路树r ，并将其存储下来例如在下 图表示的网络中，弧旁的数字为弧长c l j ，节点旁的数字为标号p 0 ) ，粗线 表示最短路树 ( 1 )仰( i6 ) 3 2 2 最短路的稳定性 图3 2 1 最短路树r 初始状态时交通网络中诸弧的长度设为最小值，当状态发生变化( 例 如路段出现拥挤现象) 时，一部分弧的长度就会增加，所以本节约定只 讨论权值增大的情形假定己求出了一条静态最短的s 一“路p 首先来 研究最优值的稳定性，即当一部分弧长增加时，是否仍然存在同样长度 的最短路? 由约束条件( 3 2 5 ) ，位势满足丌，一以c 。，v ( i ，j ) e a ，且当弧( f ，j ) p 时，等号成立反之，我们定义 4 一 ( f ，j ) g a i 一一i c 。 ， 称为等式子集它在图g 中的导出子图g o - g 【a 】称为等式子图例如图 3 2 1 的网络g 的等式子图g 0 如图3 2 2 所示如下的命题是最优值不变的 判定准则 图3 2 2 等式子图g o 命题3 2 1当网络g 中一部分弧长增大时，最短路长度不变的充要 条件是：在等式子图g o 中，删去长度增大的弧后，从s 到h 是连通的 证首先，运用线性规划对偶定理的互补松弛性，得到如下论断： 一条s h 路p 是最短路的充要条件是p 含于等式子图g 0 之中因此，当一 部分弧长增大时，虽然等式子图g 0 会发生变化( 它不包含弧长增大的弧) ， 但只要从s 到“是连通的，便存在s h 路p 由上述论断可知它是原网络 的最短s 一“路，从而最短路长度不变反之，若最短路长度不变，则必 存在另外的最短路p 而由前述论断，它含于等式子图瓯之中，从而从s 到“是连通的证毕口 例如在图3 2 2 中，若s 一1 “- 8 ，而弧长c 。和c 鹌增大了，等式子图g o 不再包含弧( 3 ，4 ) 及( 4 ，8 ) ，但从s 到“还是连通的，因为存在另外的最短路 q 3 ，6 ，8 ) 在等式子图g o 中判定s 一“连通性并寻找新的最短路可以直接运用常 用的图搜索算法，如d e p t f i r s ts e a r c h 或b r e a d t h f i r s ts e a r c h 其次，讨论最优解的稳定性，这里的最优解是指静态最短路树r 现 设弧长c 。增大为 c q ，u ，) 爿我们仍用r 表示树r 的弧集，则可用如 下递推算法求出相对于树r 的新的位势“) ： ( 1 ) 彰- o ( 2 ) 若一已求出，而弧( f ，j ) e t ，则令石：- 彰+ c ； 命题3 2 2 当弧长从c i j 变为后，树r 仍为最短路树的充要条件是 新的位势“) 满足 石：一一j c ：，v ( ，) 爿 ( 3 2 6 ) 证若新的位势满足条件( 3 2 6 ) ，由对偶问题( d ) 的约束条件得到， 彻就是( d ) 的可行解而当o ，j ) e t 时，由新位势递推算法可知，条件 ( 3 2 6 ) 的等号成立作为原设问题可行解的r 与对偶可行解w ) 满足对偶 定理的互补松弛性条件，故当弧长变化为c ：后，r 仍然为最优解( 最短 路树) 反之，若弧长变化后的r 仍为原设问题( p ) 的最优解( 最短路 树) ，则由上述新位势递推算法确定的一必定是从s 到f 的最短路长度用 反证法，假设条件( 3 2 6 ) 不成立，必有某一个弧o ，) 使得形一一，即 石一+ ，则存在这样一条从s 到，的路，它先沿r 从s 走到f ，然后通 过弧o ，j ) 到达，而其长度小于石：，这便与r + 的最优性矛盾因此，假设 错误，新的位势必满足条件( 3 2 6 ) 证毕口 注命题3 2 2 对于弧长减小的情形同样适用口 弧长变化时整个最短路树r 都不变的情况是罕见的一般情况下， 只有一部分最短路不变这就引出如下“稳定分支”的概念当弧长 c 。 变为e 时，若从发点s 到节点x 的最短路不变，则z 称为稳定节点如下 是它的判定条件，其中饥 及“) 为分别由h 及“ 确定的位势 命题3 2 3 若节点辜满足如下奈件，则一定是稳定节点： ( a ) 在树t + 中从s 到z 之前的节点都是稳定的； ( b ) 对任意节点f ，若已知它是稳定的，则 一+ c ：， 否则 主+ t 这里，若弧o ，工) 不存在，则认为t 一+ * ，从而上述不等式自然成立 证在原设问题( p ) 及对偶问题( d ) 中，认为z 就是终点“欲证 在树r 中从s 到x 的路p 相对于弧长“ 仍然是最优解为此，构造对偶 问题的可行解 柏使得路p 处于相应的等式子图之中，从而p 是最优的 首先，令- 其次，对任意节点i x ，令矿为从s 到f 的最短路长度( 相 对于弧长碱 ) 由条件( a ) 知，对路p 的任意节点f 均有吖一彰同时， 对任意稳定节点f 也有吖t 一但对其它节点i 贝1 j 有吖2 一( 由于所有弧长 只增不减，从s 到f 的最短路长度不可能减小) 由条件( b ) 知，对任意 稳定节点i 有 嚣：l 珏：珏：+ c ：- 露：+ c 2 ， 对其它节点i 有 石：i 玎：s 石+ c ：s 石j + c 二， 综上得到 珏：一耳：s c ： 另一方面，对任意节点i 及，一x ，由最短路的性质知 石：一石? c ：，( f ，j ) s a 因此，的确是对偶问题的可行解而对路p 中的弧o ，) ，上述不等式 2 5 的等号成立，即p 处于由确定的等式子图中所以p 是最短路，石为 稳定节点证毕口 根据此命题的条件，从发点s ( 它总是稳定的) 出发，沿着树r 的方 向按广探法( b r e a d t h f i r s ts e a r c h ) 顺序，逐步找到稳定节点这样找到 的稳定节点构成的子集记为，由它导出的r 的子树称作稳定分支例 如，在图3 2 1 所示的网络中，弧长勺发生了变化，变化后的c ；如图3 2 3 弧旁的数字在图3 2 3 中粗线仍表示原来的最短路树r ，节点旁括号内 的标号为e h r 确定的新位势“ 稳定分支的节点集为w o 一仉2 ，3 ，4 , 5 ，6 ，8 ) 13)06) ( 2 5 ) 图3 2 3 稳定分支 3 2 3 基于稳定分支的变权最短路算法 这时进行最短路计算就不必从头开始了，因为我们已经掌握了部分 信息r + 的稳定分支，因此，可以为初始的永久标号节点集，继续 执行d i j k s t r a 算法算法步骤如下： ( 1 ) 对已有的静态最短路树t 求出稳定分支的节点集对每一个 节点f ，设其新位势为一，其前导节点为坼) ( 2 ) 4 - w 。w o 并对，令p ( f ) 。一而对y x v w o ，定义i 临时标号 p o ) 。卿 p ( f ) + c ： 当上式中p ) - p q ) + c 0 时，- x 的前导为6 0 ) 一 ( 3 ) 调用d i j k s t r a 算法 以图3 2 3 所示稳定分支为例，接下去求出的最优解如图3 2 4 所示 o ( 1 6 j 口” 图3 2 4 变权后的最短路树 综上，对于变权网络，寻找最优路径的步骤如下： s t e p0 计算初始状态( 静态) 以任意节点为根的最短路树( 或等式 子图) ，并将其存储下来，这一步骤的计算复杂性为d 0 3 ) ，一为总节点数 当然，此步骤只在模型建立之初执行一次即可 s t e p1 在等式子图中，删去权重增大的弧后，判断从起点到终点是 否连通( 命题3 2 1 ) 如果连通，就已找到最优路径；若不连通，转下 一步这一步骤的计算复杂性为d ) s t e p2 判断原静态最短路树是否依然是最优解( 命题3 2 2 ) ? 若是， 就已找到最优路径；若不是，转下一步这一步骤的计算复杂性为d ) ， m 为总弧段数 s t e p3 寻找稳定节点( 命题3 2 3 ) ，进而确定稳定分支判断终点是 否在稳定分支内? 若在，就已找到最优路径；若不在，转下一步这一步 骤的计算复杂性为o ( m ) s t e p4 以稳定分支为初始的永久标号组，执行d i j k s t r a 算法，求解最 优路径这一步骤的计算复杂性为o ( n 2 ) 口 可以看出，依照本文提出的算法，在最好的情况下可以把求解变权 网络最优路径的时间复杂度降至d 0 ) 或d 伽) ；当然最差的情形是稳定分 支只有一个节点( 起点) ，这时须从头执行d i j k s t r a 算法对于查询用户 来说，算法的整体时间复杂度依旧为o ( n ：) ，但一般情况下根据稳定分支 的大小可不同程度地减少搜索步骤，提高运算效率 3 2 4 稳定分支结合双向搜索提高算法效率 我们可以将稳定分支与上节讨论的双向搜索方法相结合，进一步提 高变权网络最短路算法的执行效率首先确定以起点s 和终点u 为根的稳 定分支节点集秽和”，以它们为初始的永久标号集分别开始执行 d i j k s t r a 算法( 不论时和睇是否有交集) ，当一个新的公共节点进入永久 标号集矿和睨时停止搜索，寻找跨越弧) ，) ，继而得到最优路径 3 2 5 仿真实验 为了验证本文算法的性能，我们进行了模拟实验对随机生成的有向 网络分别采用经典的d i j k s t r a 算法与基于稳定分支的改进算法( 单向搜索 与双向搜索) 进行最优路径计算，考察各自的计算开销，并定义加速t t - - 经典算法计算时间改进算法计算时间 实验按总节点数为9 0 0 、2 5 0 0 、6 4 0 0 分成3 组，每组按权重的最大 变化倍率为1 2 ，1 5 ，1 8 ，2 0 ，2 5 又分成5 小组，每小组包含4 个网络，一 共对4 x 5 x 3 。6 0 个网络进行了实验，其中初始权重是随机生成的，权重的 变化在控制的倍率内也是随机分布的单向搜索时稳定节点数占总节点 数的百分比如图3 2 5 所示，单向稳定分支改进算法的平均加速比如图 3 2 6 所示；双向稳定分支改进算法平均加速比如图3 2 7 实验结果显示： 1 改进算法相对于经典算法的加速比均高于1 ，也就是说改进算法降 低了计算开销 2 随着权重变化倍率的增大，稳定节点数的比例降低，稳定分支改 进算法的加速比也相应呈下降趋势，与理论预期相符 3 双向搜索可进一步提高算法效率 0 8 0 7 0 6 _ 琏0 5 铲0 4 删0 3 h e 0 2 0 1 0 、 1 2 01 5 01 8 02 0 02 5 0 权重变化范围( 倍) 图3 2 5 单向稳定节点占总节点数的比例 3 5 3 4 3 3 逛3 u 3 瑙 - r2 2 8 2 7 、 、 、 一 1 1 2 01 5 01 8 02 0 02 5 0 权重变化范围( 倍) 图3 2 6 单向稳定分支改进算法的加速比 ， 7 、 一二 一 、- 1 21 522 5 权重变化范围( 倍) 图3 2 7 双向稳定分支改进算法的加速比 5 4 5 3 5 2 5 1 5 0 4 3 2 1 o 一逛一丑硝曩 3 j 全动态网络最短路问题 上节讨论的是弧长由气变为时最短路的稳定性实际应用中，每条 弧的权往往随时间的变化而变化，是时间f 的函数c 。( f ) 计算网络中某节 点到目标节点的最小代价路径( 最短时间或最小费用) 的决策过程 当网络中各弧的权重随着时间演进而发生变化时就变成动态的，称 为单源动态最短路( d y n a m i cs i n g l es o u r c es h o r t e s tp a t h ，简称d s s s p ) 问题 d e m e t e r s c u 2 0 0 1 ，e t c ，此动态网络( d y n a m i cn e t w o r k ，简称d n ) 有时也称作时间依赖网络( t i m ed e p e n d e n tn e t w o r k ，简称t d n ) 【k a u f m a n 1 9 9 3 ，z i l i a s k o p o u l o s 2 0 0 1 ，e t c 动态网络一般是指网络中的弧是动态变化的，具有四种可能形式： 弧的添加与删除，弧之权重的增大与减小若这四种形式都被允许，则称 此网络为全动态络 f r i g i o n i 2 0 0 0 ；若只允许弧权的增大与弧的删除( 或 只允许弧权的减小与弧的添加) ，则称此网络为半动态网络 f r a n c i o s a 1 9 9 7 事实上，弧的添加是弧权减小的一种特例( 弧权由0 0 减小为有限 值) ，弧的删除是弧权增大的一种特例( 弧权增大至* ) 因此只须研究 弧权变化的情形 本节研究弧权函数非线性变化的全动态网络，基于网络状态已知( 或 可预测) 的假定 3 3 1 数学模型 在动态网络情形，权函数c f ( f ) 可定义为从节点f 到j 的运行时问，其 中f 为进入弧( f ，) 的时刻这里路径( 时间) 长度是依赖于时间过程的若 3 1 有一条路p 一 ( f l ，i ：) ，( f ：，3 ) ，( i t ，i t 。) ，开始时亥i j # j t , ，则其长度为 l ( p ) c i l 2 ( f 1 ) + q p ，( f ：) + + c l 。瓴) 其中 f 2 一 + 气l ：( f 1 ) 岛l f 2 + c i 一，( f 2 ) t k - t k l + c l 。 以一1 ) ， 而d s s s p 问题仍然是求一条s u 路p ，使这种新定义的长度f ( p ) 为最小 这种动态问题不能沿用已有的动态规划类型的s p 算法首先来看如 下的例子，其中除q ( f ) 之外，各弧的长度均为常数 图3 3 1 动态网络实例 阻 0 f l ( f ) t 4 ， 1 s f c 2 5 1 2 ，2 5 f 5 从节点1 到4 的最短路为( 1 ，2 ，3 ，4 ) ，长度为5 其他两条路( 1 ，3 ，4 ) 及( 1 ，4 ) 的长度均为6 但在最短路( 1 ，2 ，3 ，4 ) 中，子路( 1 ，2 ，3 ) 不是最短的这说明 “最优化原理”不成立，即不能用动态规划来求解一般来说，此类问题 具有十分复杂的组合结构，求解比较困难 3 3 2 相关工作 因为传统的静态s p 算法( 如d i j k s t r a 算法) 不能直接移植到动态网 络中，众多研究者致力于寻找有效的近似算法 一般认为，s p i r a p a n s p i r a l 9 7 5 和m c q u i l l a n e ta l 【m c q u i l l a n l 9 8 0 】 最早开始研究d s s s p 问题；d e m e t e r s c ue ta l 【d e m e t e r s c i l 2 0 0 1 】证明了经 典的s p 算法可以求解一类严格限制的d s s s p 问题；f r i g i o n i 【f r i g i o n i 2 0 0 0 】 和f r a n c i o s a f r a n c i o s a l 9 9 7 系列工作分别研究了半动态和全动态最短 路问题，给出了一种动态修正的d i j k s t r a 算法，将动态弧分为权重增加和 权重减小的两组分别进行处理；n a r v a e ze ta l n a r v a e z 2 0 0 0 给出了动态修 正的d i j k s t r a 、b e l l m a n - f o r d 和d e s o p o - p a p e 算法；l i nf e n g - t s e l i n 2 0 0 1 】 讨论了模糊环境下的s p 问题 o r d a & r o m o r d a l 9 9 0 ，1 9 9 6 1 和c a i e ta l 【c a i l 9 9 7 提出允许在节点匕 有一个等待时间m ，这相当于任务到达时不一定立刻执行，对这样的模 型可以建立动态规划算法定义最优值函数p ( ，) = 从起点s 到节点_ 的最 短路长度( 运行时间) ，由最优化原理得到递推方程： p ( ，) i m ：l p o )