（交通运输规划与管理专业论文）随机交通流网络行程时间可靠度近似算法研究.pdf

摘要随着城市的快速发展，交通网络可靠性己受到各方的高度关注。目前，在路网可靠性的研究中，主要有两大类计算方法：一类为精确算法，另一类为近似算法。由于交通网络是开放性的巨系统，且交通供需具有随机性变动的特点，因此精确计算交通网络可靠度是不切实际的，需要对交通网络可靠度进行近似计算。在列举网络状态的近似算法中，主要有两类：一类是列举网络的最可能状态，这类算法的研究比较多，计算概率性指标时比较有效，但用于计算重要性指标时，计算精度较低；另一类是列举网络的最重要状态，这类算法的研究比较少，计算重要性指标时比较有效，但用于计算概率性指标时计算精度较低。本文在m i 算法( 可列举网络的最重要状态) 、m p 算法( 可列举网络的最可能状态) 的基础上，建立了m i m p 算法( 可同时列举网络的最重要状态和最可能状态) 。该算法可以将生成的网络状态划分为四种类型：第一类是对网络重要性指标可靠性影响较大且发生可能性较大的状态；第二类是对网络重要性指标可靠性影响较小但发生可能性较大的状态；第三类是对网络重要性指标可靠性无影响但发生可能性较大的状态；第四类是对网络重要性指标可靠性影响较大但发生可能性较小的状态。依据这四种类型的网络状态，m i m p 算法可以近似计算路网的可靠性指标。最后，本文将三种算法分别应用于具体算例，并进行了对比分析，得到了令人满意的结果。关键词：交通网络可靠度；近似算法；行程时间；交通延误；m i 算法；m p 算法；m i m p 算法a b s t r a c ta l o n gw i t ht h ec i t y sf a s t d e v e l o p m e n t ，t h et r a n s p o n a t i o nn e t w o r kr e l i a b i i i t yh a sr e c e i v e dt h eh i g ha t t e n t i o n a tp r e s e n t ，t h e r ca r em a i n l yt w o “n d s0 fc o m p u t a t i o n a lm e t h o d si nt h er o a dn e t w o r kr e l i a b i l i t yr e s e a r c h ：o n ei st h ep r c c i s ea l g o r i t h m ，t h eo t h e ri sc h ea p p r o x i m a t ea l g o r i t h m a st h et r a n s p o r t a t i o nn e t w o r ki st h e0 p e ng r e a ts y s t e ma n dt h et r a n s p o n a t i o ns u p p l y d e m a n dh a st h ec h a r a c t e r i s t i co fr a n d o mc h a n g e ，s oi ti si m p r a c t i c a li np r e c i s ec a l c u l a t i n gt h et r a n s p o r 【a t i o nn e t w o r kr e l i a b i l i l ya n dn e e d st o 印p r o x i m a t e l yc a l c u l a t et h er e l i a b i l i t yo ft h et r a n s p o n a t i o nn e t w o r k i nt h ea p p r o x i m a t ea l g o r i t h m so fe n u m e r a t i n gt h en e t w o r ks t a t e s ，t h e r ea r em a i n l yt w ok i n d s ：o n ei st oe n u m e r a t et h em o s tp o s s i b l es t a t e so ft h en e t w o r kw h i c hh a sm o r er e s e a r c h e s ，a m o n gt h e m ，t h ea l g o r i t h mi sq u i t ee f f c c t i v ei nc a l c u i a t i n gt h ep r o b a b i l i t yi n d e x h o w e v e r t h ec o m p u t a t i o np r e c i s i o ni sc o m p a r a t i v el o w e ri nc a l c u l a t i n gt h ei m p o n a n c ei n d e x c o m p a r e dw i t hi t ，a n o t h e re n u m e r a t i n gt h em o s ti m p o r t a n ts t a t e so ft h en e t w o f kh a saf e wr e s e a r c h e s ，a m o n gt h e m ，t h ea l g o r i t h mi sq u i t ee f 如c l i v ei nc a l c u l a t i n gt h ei m p o r t a n c ei n d e x h o w e v e r ，t h ec o m p u t a l i o np r e c i s i o ni sc o m p a r a t i v el o w e ri nc a l c u l a t i n gt h ep r o b a b i l i t yi n d e x i nt h i st h e s i s ，o nt h eb a s i so fm ia l g o r i t h m ( w h i c hc a ne n u m e 豫t et h em o s ti m p o r t a n ts t a t e so ft h en e t w o r k ) a n dm pa l g o r i t h m ( w h i c hc a ne n u m e r a t et h em o s tp o s s i b l es t a t e so ft h en e t w o r k ) ，t h ea u t h o rb u i l d st h em i m pa l g o r i t h m ( w h i c hc a ns i m u l t a n e o u s l ye n u m e r a t et h em o s ti m p o r t a n ts t a t e sa n dt h em o s tp o s s i b l es t a t e so ft h en e t w o r k ) t h ea l g o r i t h mc a nd i v i d et h ep r o d u c e dn e t w o r ks t a t e si n t of b u rt y p e s ：t h ef i r s ti st h eb i g g e rp o s s i b i l i t ys l a t e sw h i c hh a sb i g g e ri n n u e n c eo nt h er e l i a b i l i t yo ft h en e t w o r ki m p o r t a n ti n d e x ；t h es e c o n di st h eb i g g e fp o s s i b i l i t ys t a t e sw h i c hh a ss m a l l e ri n f l u e n c eo nt h er e l i a b i l i t yo ft h en e t w o r ki m p o r t a n ti n d e x ；t h et h i r di st h eb i g g e rp o s s i b i l i t ys t a t e sw h i c hh a sn 0i n f l u e n c eo nt h er e l i a b i i i t yo ft h en e t w o r ki m p o r t a n ti n d e x ；t h ef b u r t hi st h es m a i i e rp o s s i b i l i t ys t a t e sw h i c hh a sb i g g e ri n n u e n c eo nt h er e l i a i b i l i t yo ft h en e t w o r ki m p o r t a n c ei n d e x s or e i y i n go nt h e s ef b u rt y p e so fn e t w o r ks t a t e s ，t h em i m pa 1 9 0 r i t h mc a na p p r o x i m a t e l yc a l c u i a t et h er o a dn e t w o r kf e l i a b i l i t yi n d e x f i n a l l y ，t h r e ea 1 9 0 r i t h m sw i i ib ea p p l i e dr e s p e c t i v e l yi nc a i c u l a t i n gt h es p e c i f i ce x a m p i e t h r o u g hc o m p a r a t i v ea n a l y s i s ，i to b t a i n st h es a t i s f y i n gr e s u l t k e yw o r d s ：t r a n s p o r t a t i o nn e t w o r kr e l i a b i l i t y ；a p p r o x i m a t ea i g o r i t h m ；n a v e lt i m e ； r r a n s p o r t a t i o nd e i a y ；m ia i g o r i t h m ；m pa l g o r i t h m ；m l m pa l g o r i t h m长沙理工大学学位论文原创性声明本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。作者签名：澎磐彰笋日期：，秒年，月叫日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权长沙理工大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。本学位论文属于1 、保密口，在年解密后适用本授权书。2 、不保密团。( 请在以上相应方框内打“”)日期：砷年，月纠日日期：弦叮年r 月刁日1 1 选题来源第一章绪论论文的研究内容来源于交通部应用基础研究项目一一道路网络可靠性研究及在交通规划中的应用，项目编号；2 0 0 5 3 1 9 8 2 5 0 5 0 。1 2 研究背景与意义可靠性作为一门新兴的工程学科，主要用于研究系统所提供服务水平的稳定程度。在电力系统、供水系统以及通讯系统等网络中，可靠性分析作为规划、设计及运行的重要部分，已经得到比较广泛的应用，并取得了丰硕的成果。但是，可靠性分析在交通网络中的应用还比较少。以下几方面问题的出现引起了人们对交通网络可靠性的高度重视。第一，近年来，日本、北京等地出现的自然灾害造成了严重后果：1 9 9 5 年1月1 5 日凌晨，日本神户的大地震造成了交通瘫痪的被动局面：在我国，2 0 0 1 年1 2 月7 日北京的场大雪几乎使交通瘫痪。第二，随着城市规模的不断扩大、生活节奏的不断加快，人们都希望自己的出行能够在预定的、可接受的时间范围内到达目的地；而作为交通网络的管理者也都希望网络一直处于畅通状态。因此，即使在日常的交通状况下，出行者和管理者也都迫切需要一种更为稳定可靠的交通运输网络服务水平。第三，由于在目前的路网规划中很少考虑可靠性，以致路网在短时间内即暴露出各种问题( 拥挤、阻塞现象日益严重) ，给社会造成了巨大的损失。在路网可靠性的研究中，主要有两大类计算方法：一类为精确算法，另一类为近似算法。但由于实际路网的复杂性，精确计算是不切实际的，因此，对路网可靠性指标的近似算法进行研究将是一个发展趋势。对路网可靠性的高精度近似计算可以使人们对路网的性能、状态有一个清晰的认识，从而做出最优的决策：对于出行者而言，可以选择更为可靠的出行线路；对于管理者而言，可以发现路网的薄弱环节，为路网性能的改善提供依据。依据路网可靠性改进后的路网可以更好的发挥交通运输系统在国民经济中的基础作用。对于新建路网，在规划阶段就应考虑规划路网的可靠性，以增加规划后路网的可靠性、环境适应性，节约短时间内再次改造路网的费用。有意识的将可靠性引入规划中，将使规划后的交通网络更能承受各种突发事件的影响，使其发挥更大的作用和效益。1 3 国内外研究现状路网可靠性的研究起步较晚，其可靠性概念提出至今只有2 0 多年，研究内容随社会经济的变迁、交通技术的变革、交通模式的发展而发生变化。目前对路网可靠性的研究主要集中在连通可靠性、行程时间可靠性和容量可靠性三方面。1 3 1 路网可靠性国外研究现状( 1 ) 连通可靠性连通可靠性( c o n n e c t i v er e l i a b i l i t y ) 是指网络中的节点保持连通的概率。连通可靠性反映了网络中各节点的连通状况，是从网络的拓扑结构来描述网络可靠性的。路网连通可靠度的概念最早由日本的m i n e 和k a w a i 在1 9 8 2 年提出“1 。具体含义是：对于给定时段内的任一节点对，至少存在一条能够将它们连接起来的完好路径的概率。它关注的是实际存在的0 d 对间的路径的连通程度。对每一节点对，如果其中至少有一条路径是连通的，那么认为这一o d 对间的路网就是畅通的。1 9 8 9 年，日本的i i d a 和w a k a b a y a s h i 提出路网终端可靠性的最小路集和割集算法，以进行特殊o d 对间连通可靠性研究”1 。1 9 9 7 年，b e n 等建议将路段的二元状态进行扩展，即管理者可以主观定义路段的连通与否”1 。由于连通可靠性仅考虑路段最大通行能力或者通行能力为零的两种运行状态，在应用上有很大局限，只适用于道路交通网络处于极端状态下。研究连通可靠性的主要方法是图论、布尔代数和整数规划。由于连通可靠性问题本质上是一个n p 难问题，对于大规模网络的连通可靠性计算一般采用近似算法，如w a k a b a y a s h i 等利用布尔代数，通过e s a r y p r o s c h a n 上下边晃法来计算连通可靠性“，。( 2 ) 行程时问可靠性行程时间可靠性( t f a v e l t i m er e l i a b i l i t y ) 是指对于给定的起终点之间，出行者能够在规定时间内顺利完成出行的概率1 。行程时间可靠性也可定义为在给定概率下到达目的地的最大时间。根据研究侧重点的不同，行程时间可靠性又可分为路径行程时间可靠性、0 d 对行程时问可靠性以及系统行程时间可靠性。路径行程时间可靠性是指给定路径的行程时间在可接受阀值内的概率；o d 对行程时间可靠性是综合给定o d 对之问所有被用户使用的路径的行程时间以得到一个关于o d 对服务水平的测度；系统行程时间可靠性则是考虑所有0 d 对得到的一个关于整个系统服务水平的指标。路径行程时间可靠性有助于出行者对路径的选择，而0 d 对及系统行程时间可靠性则有助于管理者估计路网的性能。1 9 9 1 年，a s a k u r a 和k a s h i w a d a n i 提出以行程时间波动性来反映路网可靠性，即行程时间可靠度，讨论o d 对问交通在一定的路网交通需求水平下在特定时间间隔内能够成功到达的概率。该方法定义行程时间可靠度函数为阻塞状态运行时2间与畅通状态运行时间之比”1 。1 9 9 6 年a s a k u r a 验证了道路通行能力下降情况下的行程时间可靠度1 。1 9 9 8 年b e l l 等人研究行程时间可靠性的日交通需求变动灵敏性分析法，证实了行程时问可靠度可有效分析路网维持日常运营状态时其运营服务质量的稳定性盯1 。但这种基于交通分配模型的行程时间可靠度估计存在假设条件苛刻、多种可靠性影响因素无法量化的不足。( 3 ) 容量可靠性路网容量可靠性( c a p a c i t yr e l i a b i l i t y ) 是美国犹他州州立大学a n t h o n yc h e n等在1 9 9 9 年提出的，其含义是：在一定服务水平下，路网能够容纳一定交通量的概率抽1 。这个定义是建立在路网备用容量( n e t w o r kr c s e r v ec a p a c i t y ) 基础上的。路网备用容量系数，是指一个o d 矩阵扩大若干倍以后，将其分配到路网上时既不会大于路段的容量。也不会超过预先规定的流量与容量之比，这个最大的倍数就被称为路网备用容量系数”。1 ”，此系数可采用解析方法求得，该方法与w a r d r o p路径选择行为相结合，可用双层规划模型表示如下3 ：m a x s t v 。( 腑) 巴v 4 a( 1 1 )( 1 2 )式中心) 为路段a 上的均衡流，e 为路段a 的容量，为路网备用容量系数，辱为现状o d 需求矩阵。对于所有o d 对的需求，在0 d 需求矩阵牙的基础上统一乘以，通过解下面的交通分配问题( t a ) 获得：m i nz = n ( x ，e ) 出( 卜3 )4 e os ，t = 靠，v w e 矽( 1 4 )匕= 贬，v a( 卜5 )蟮r0 ，v r r( 卜6 )其中，a 是网络中的路段的集合；w 是网络中o d 对的集合；r 是网络中的路径的集合；肌是o d 对，之间的路径的集合，w ；为整个网络的o d 矩阵乘子；q 是路段4 上的随机容量，4 e a ；v 。是路段n 上的交通量，口a ；f a 也，c d )是路段口上的走行时间，口a ；钆是o d 对w 之间的现有需求，w 形；露是矢量形式的现有o d 需求矩阵；是路径r 上的流量，r r ；。f 1 如果路径，使用了路段口屯2 1 0 ，其他3上层规划( 式( 卜1 ) ( 卜2 ) ) 用于确定约束于容量限制的最大o d 矩阵乘子，下层规划( 式( 卜3 ) ( 卜6 ) ) 通过解一个标准的交通分配问题以确定路段流量，下层规划明确考虑了路径选择行为和拥挤效果。从双层模型可看出，在确定路网备用容量系数时考虑了用户的路线选择行为。路网备用容量系数表明了现在的路网状态，如果p l ，说明路网还有l o o ( p 1 ) 的储备容量；若1 ，则说明路网上的流量超出了现状需求的1 0 0 ( 1 ) 。同时，备用容量系数还被用来评价现有路网对预期交通需求水平d 的满足程度，用来计算路网的容量可靠性，即r ( d ) = p 0 d )( 1 7 )r ( d ) 表示路网在需求水平为d 时的可靠度，路网容量可靠性的上下界是由预期交通需求水平决定的，当| d ；o 时，r ( d ) = l ，而当d z 一时，r ( d ) = o ，即在没有交通需求时，路网1 0 0 可靠；当需求水平无限大时，路网的可靠度是o 。如果路段状态以布尔代数值表示，则上式即为连通可靠度。传统的路网容量概念是指在路段通行能力的制约并满足路网系统最优的情况下，路网所能承担的最大交通流量。与传统的路网容量概念比较，c h e n 明确考虑了路网中存在的随机因素。它既考虑了路段容量限制问题，又考虑了出行者的路径选择行为，弥补了连通可靠度的一些缺陷。容量可靠度能用来评价交通条件恶化情况下，路网容量满足一定需求水平的概率，可用于说明现在的路网对于预期的需求是否足够。至此，路网可靠性研究由此前基于个体出行者局部利益，拓展至基于交通系统管理者全局性利益的规划设计。( 4 ) 其它可靠性指标除上述可靠性指标外，也有学者基于其它系统目标研究了路网可靠性问题。d u 和n i c h o l s o n 提出了分析降级网络的一般理论框架，并将路网可靠性定义为在路网能力下降的情况下，系统交通流量的变化小于某一阈值的概率“”1 。从出行者角度出发，b e n 等“”定义了“遭遇可靠性( e n c o u n t e r e dr e l i a b i l i t y ) ”。“遭遇可靠性”是指在传统的用户均衡条件下。出行者在所选路径上行走时不会遇到路段能力下降的概率。b e r d i c a 引入路网的“脆弱性( v u l n e r a b i l i t y ) ”测度以确定路网存在的弱点以及它们的影响“”。t a y l o r 使用稠密路网交通模型用于路网的可靠性研究，使用透过性、可达性和曲折性三个指标来评价路网布局和交通管理计划，t a y l o r 的研究着重于交通网络的局部区域“6 。1 “。1 3 2 路网可靠性国内研究现状国内对交通网络可靠度的研究比国外稍晚，到目前为止在这一领域的研究比4较零散，不够系统。毛林繁将可靠性指标引入公交网络的设计中其基本思想是采用图论的方法将公交网络用重图表示，并将城市公交网络的可靠性定义为其相应重图的弧连通度“”。虽然建立的双层规划模型中包含了出行者路径选择模型，但本质上考虑的仍然是连通可靠性。上海交通大学的侯立文在分析路网可靠性与服务水平关系的基础上对城市道路网进行了可靠性研究，提出了路径可靠度、路段可靠度、节点可靠度及路网可靠度的计算公式“”2 ”。东南大学朱顺应等对连通可靠性进行了扩展，使用饱和度确定法来研究路段的可靠度，以此为基础建立整个交通网络的可靠性指标”“。北京工业大学的陈艳艳、梁颖等提出了路段( 或交叉口) 的畅通可靠度指标。”矧，用于评价路网的运营状态。畅通可靠性( u n b l o c k e d r e l i a b i l i t y ) 是指高峰期内，在正常使用条件下，道路交通运营状态能满足畅通状态的概率。根据不同畅通标准，道路畅通度可定义为：高峰期内，正常使用条件下，车辆能在畅通的服务水平下行驶的概率，或车辆在路段( 交叉口) 以畅行速度( 畅通状态下容许的延误范围) 行驶的概率。西南交通大学金键从系统工程学角度出发，对道路交通网络不可靠因素进行分析，提出应根据不同的交通信息需求进行综合交通信息分析，对城市道路交通网络进行可靠性管理，实施交通运营可靠性优化，才能达到道路网络可靠性增长”。研究还指出权衡公共交通系统和个体交通系统可靠性是道路网络可靠性设计，管理的重点，应针对不同城市交通发展阶段实施分级可靠性管理体系，将可靠性管理思想引入城市道路交通管理。范海雁、杨晓光、严凌、夏晓梅”运用蒙特卡罗随机模拟方法，建立了公交线路运行时间可靠性的数学模型，计算了公交线路的运行时间可靠性。刘海旭、蒲云心们基于净经济效益概念，提出一种新的可靠性指标以描述弹性需求随机路网的性能。新的可靠性指标定义为路网的净经济效益满足给定水平的概率，是一种能够反映路网综合性能的指标。黄中祥、况爱武曙7 1 定义服务水平可靠性为：路段容量的随机变化使路段或路网服务水平维持在某一等级的概率。服务水平可靠性将路网的随机动态性结合到路网服务水平之中，能综合反映路网的性能，是系统管理者和用户衡量随机路网性能的有力指标。1 3 3 可靠性算法研究现状文献 2 8 3 0 一直致力于通信网络或计算机网络的运行可靠度方面的研究，并作出了不少成就。在其方法中，需列举出网络的所有可能状态，由于状态空间巨大，在实践中，这种评价方法只能局限于很小的网络。实际上，文献 3 1 、5 3 2 已经证明这些可靠性量度的精确计算是p 难的。为了避免状态空间指数分布的缺陷，l i 和s i i v e s t e r m l 提出了一种通过计算网络最可能状态来得到全局运行可靠度近似值的方法。因为网络在大多数时间都是以这些状态运行着，并且当所考虑的状态概率之和达到了状态空间的大部分时，就能得到该网络可靠度的一个较好的近似值。在文献 3 4 中，c h i o u 和l i 推广了文献 3 3 中的算法，并提出了一个用于近似计算具有多状态组件的通信网络可靠度的算法，称作o r d e r m 算法。在文献 3 5 中，从优化时间复杂度角度出发，发展并形成o r d e r m 1 i 算法。( 1 ) o r d e r m 算法本算法是c h i o u 和l i ( 1 9 8 6 年) 对文献 3 3 中的0 r d e r 算法( 两状态网络) 的改进，使其能够适用于多状态网络。其基本思路为：1 ) 通过一个两阶段的程序来依概率递减的次序产生m 个最可能状态s 使其概率和( p r ( s ；) ) 达到状态空间一定的覆盖率；百、。2 ) 计算可靠度f ：f = p f ( 网络平均信息延误2 0 0 m s ) = p r ( 墨mt( 1 8 )其中：f ：1 如果在s 中的网络信息延误蔓2 0 0 吣( 卜9 )“1 0 否则使用该算法，人们能够用一个很有效的方式来计算网络平均信息延误的概率分布函数，并达到一定的精度。( 2 ) o r d e r m i i 算法y 柚g 和k u b a t ( 1 9 8 9 年) 提出了一个新的有效算法一一0 r d e r m i i 算法，该算法主要从最可能状态的产生方式方面对o r d e r m 算法进行了改进，使得该算法的时间复杂度大为降低。该算法把确定q ，( 即( 1 一s ) 的最小覆盖空间集合) 的问题转化为树形网络搜索问题。给定m ( 路段i 的状态数) 和风，( 路段i 处于j 状态的概率) ，f = l ，2 ，n ，j = l ，f ，就定义了一个有序树形网络。树形网络g 中的树叶地址与状态空间q中的状态是一一对应的。这样，寻找最小覆盖空间集合q 。问题就等价于在g 中识别最重要树叶的地址，使它们的权重和大于等于1 一。其基本策略是：首先在g 中识别权重最大的树叶，然后识别权重第二大的树叶，如此反复进行，直到目前所有已识别树叶的权重和大于等于l 一占。也就是说，g 中的第m 位重要的树叶的地址将在算法的第m 次迭代中得以识别。因为g 是由表中的f 和n ；完全定义的，所以能够构思整个图g 的结构而不必创建真正的树形结构来再现它。6该算法的时间复杂性为d ( 1 q 。j n + l q 。；i ) = d ( ；q 。；m ) s d ( ；q 。；州)( 卜l o )i ；l注l这里= m a 】【( i ，2 ，m ) 。( 3 ) 其他算法设g = ( ，a ，m ) 是从起点s 到终点f 的一个随机流量网络，其中为节点集合，a = q l f n 为路段集，m = m 1 ，j l f 2 ，m ” ，j l f 为路段q 的最大容量，f = 1 ，2 ，厅。记x = ( ，而，) 为系统的容量向量，其中玉为路段j 的容量。记y ( x ) 为容量向量为x 时的最大流。给定d ，系统的可靠度兄定义为最大流不小于d 的概率，即毛= p r x l 矿( 神2 d l 。x u e 的算法、最小路径法、最小割法三种方法用来寻找系统的水平为d 的最小上界与最大下界。最小上界与最大下界是研究系统的可靠度时常常用到的两个概念，分j j 对应于图论中的最小路径( m i n i m a lp a t h s ) 和最小割( m i n i m a lc u t s ) 两个概念。1 ) x u e 的算法1将系统g = ( n ，a ) 进行模块分解，例如分解成m p s ：墨，如，e ，结构函数取y ( x ) = d ( s m ( ) ，( z ，五，) ) = j = l其中d ( ) 表示系统的分解，s h m ( ) 为通过m p s 的所有流，( z ，正，厶) 为x 下的可行流。记帆( i ) = ( 劬l ，劬2 ，) ； 织。( f ) = ( z ，厶，肼) i 乃= f 以 o l ，2 ，与 ，= l 2 ，m ；= lp 枷( ) = ( 劬。，劬：，) i ( ，劬：，) 脚( 乃) ，j = l ，2 ，m ) ；扣lj = l；l其中。一帆嘞= 骺：zm m 乒吼弓其求系统的水平为d 的最小上界的算法为：s t e p l ；对系统进行模块分解，( 分解成m p s 或m c s ) 列出恤o ) ；s t e p 2 ：求柳。( d ) ；s t e p 3 ：求p f f ( d ) ；s t e p 4 ：从p 枷( d ) 中去掉不是最小上界的向量。7对不能直接分解成模块的系统，需要额外的工作扩展系统，使其能够分解成模块，然后再使用上面的算法。2 ) 最小路径法毛= p r x i y ( x ) d = p r x ；x x ，x i 为水平为d 的最小上界( 1 1 1 )只要找到系统的所有水平为d 的最小上界就可以计算出系统的可靠度。3 ) 最小割法= p r x i y ( x ) d = 1 一p r x i y ( x ) d 一1 = l p r x x j i x i 为水平为d l 的最大下界( 卜1 2 )只要找到系统的所有水平为d l 的最大下界就可以计算出系统的可靠度。文献 3 7 ，3 8 等用最大流最小割定理设计算法来寻求系统的所有水平为d 的最大下晃。m p s 和m c s 是解决这类问题的简单而有效的方法，但也有其局限性：已知系统所有的m p s 、m c s ，并不是很容易的事情。1 4 本文研究内容本文主要针对随机交通流网络行程时间可靠度的近似算法进行研究。目前在列举网络状态的这些近似算法中，主要存在如下问题：计算精度偏低，仅单独考虑网络的最可能状态或最重要状态而未能将两类状态结合在一起考虑。根据上述问题，本文的章节安排如下：第二章是网络可靠性基本理论，重点介绍了网络可靠性的基本知识和典型模型，为进行网络可靠性分析做了铺垫。第三章是城市交通网络可靠性分析，重点对交通网络特性( 随机性) 进行了分析，并介绍了对网络可靠性进行计算的精确算法和近似算法。由于交通网络的随机性和复杂性，对交通网络可靠性进行精确计算是n p 难的，因此本文采用近似算法来计算交通网络可靠性。第四章是随机交通流网络可靠性近似算法，详细介绍了两种适用于交通网络的可靠度近似算法一一m p 算法、m i 算法，从而建立了精度更高的m i m p 算法，最后用m a t l a b 将这些算法程序化。第五章是算例分析，将上述算法分别应用于一个具体算例中，并进行了对比分析，得出结论：m i m p 算法是比m i 、m p 算法更为有效的算法。第六章是总结与展望，主要是对论文所做的工作进行简单的总结，并展望了今后的研究工作和本领域的未来发展方向。第二章网络可靠性基本理论2 1 可靠性基本概念2 1 1 可靠性可靠性b 们是指产品在规定的条件下和规定的时间内完成规定功能的能力，可靠性的概率度量称为可靠度。( 1 ) 规定的条件规定的条件是指产品在其寿命周期内所处的预先规定的全部外部条件。外部条件包括环境、使用、维修等条件。( 2 ) 规定的时间规定的时间是指产品完成规定功能的时间，可用时间单位表示，也可用相当于时间单位的公里数、周期数表示。( 3 ) 规定的功能规定的功能是指产品的性能技术指标，一个产品往往具有若干项功能。这里所说的“完成规定功能的能力”，是指产品若干功能的全体，而不是其中的一部分。对功能的描述有些场合能用定量的，有些场合只能用模糊的方式。2 1 2 维修- 牲维修性是指可修产品在规定的条件和规定的时间内，按照规定的程序和方法维修时，保持或恢复其规定状态的能力。维修性的概率度量称为维修度。2 1 3 可用性可用性是指产品在规定的条件下，在任意随机时需要和开始执行任务时，处于可工作或可使用状态的程度，其概率度量称为可用度。它反映了产品的可靠性和维修性，也称为广义可靠性。狭义可靠性不包含维修性的概念。2 1 4 故障故障是指在规定的条件下，产品丧失规定的功能的现象。一般对可维修产品使用“故障”，对不可维修产品称“失效”。故障可分为五类：一是间歇故障：产品在某时闻出现故障，但能自动恢复其功能：二是独立故障：组件发生故障，只是由自身原因引起；三是从属故障：组件由于其它部分失效的原因引起的故障：四是人为故障：是由人的误用、违反操作程序、误判所导致的故障；五是灾害性故障：是由自然和人为灾难引起的故障。92 2 典型系统可靠性模型2 2 1 串联系统可靠性模型若系统由，1 个子系统组成，当且仅当n 个子系统全部正常工作时，系统才正常工作，或只要一个子系统故障时，则系统故障，这时称系统是由n 个子系统构成的可靠性串联系统，其可靠性框图如图2 1 所示。图2 1 串联系统可靠性框图令第i 个子系统的寿命为x ；，其工作时闻为的可靠度为墨= p x ， f ； ，x 。，x 。，x 。相互独立，系统寿命为x ，工作时间为，则系统可靠度为：e o ) = p ( x l f ，x 2 f ，x 。 f ) = 兀p ( x ： f ) = 兀r ( f )( 2 1 )i ；】，；l串联系统的可靠度等于子系统可靠度的乘积，可见串联系统的子系统越多，系统可靠性越低。2 2 2 并联系统可靠性模型若系统由n 个子系统组成，只要有一个子系统正常工作时，则系统正常工作，当系统故障时，必定是，1 个子系统全部故障，这时称系统是由n 个子系统构成的可靠性并联系统，其可靠性框图如图2 2 所示。毒图2 2 并联系统可靠性框图令第f 个子系统的寿命为x 。，其工作时间为的可靠度为尽= p x ， ，x 。，x ：，x 。相互独立，系统寿命为x ，工作时间为，则系统可靠度为：x ，= i m x ( x l ，x 2 ，x 。)e ( f ) = p ( x ， f ) = p ( 眦x ( x l ，x 2 ，x 。) f )= 1 一p ( m a x ( x l ，x 2 ，x 。) f )= 卜兀p ( x r ) = l 一兀( 1 一号( f ) )( 2 2 )扫ll = l由上式可看出并联产生的效果，并联子系统越多，系统可靠性越高。1 02 2 3 混联系统可靠- 眭模型混联系统可分为系统冗余和部件冗余两种，其可靠性框图如图2 3 所示。设部件的可靠度分别为墨，是，民，不可靠度分别为q i ，幺，q ，即有q = 1 一墨( 扣l ，2 ，n ) ，则：蠕：导册一目l ( = ) 互 一剧础剖倒a ) 系统冗余可靠性框图b ) 部件冗余可靠性框图图2 3 混联系统可靠性框图( 1 ) 系统冗余情况，系统可靠度为= l 一【l n r 】2 = 【兀墨1 【2 一兀足】扛ij 1扭l= 【兀( 1 一q ) 】【2 一兀( 1 一q ) 】( 2 3 )i - li l l( 2 ) 部件冗余情况，系统可靠度为酝= 丌( 1 一g 2 ) ；兀( 1 一q ) ( 1 + q ) = 叽( 1 一q ) 】【兀( 1 + q ) 】( 2 4 )b ij - li - li = 1可以证明，一 o ，即在任何情况下部件冗余可靠度总是大于系统冗余可靠度。2 2 4n 中取r 系统可靠- 陛模型这种系统也称为表决系统，系统的n 个部件中只要有r 个部件正常工作，则系统就正常工作，其可靠性模型如图2 4 所示。卜仁口斗仝l ( 五r 图2 4n 中取r 系统可靠性模型图设部件可靠度为民，不可靠度为姥，且有像= 1 一民，则系统的可靠度为玛= c 瞄姘。( 2 5 )t = 2 2 5 冷贮备系统可靠性模型( 1 ) 弗+ 1 个部件组成的系统，其中1 个部件工作，n 个部件不工作作为冷贮备，当工作部件故障时，贮备的部件逐个去顶替它，直到n + 1 个部件全部故障，系统才故障( 假设部件贮备期间不发生故障) 。n + 1 个部件组成的冷贮备冗余系统如图2 5 所示。图2 5 冷贮备冗余系统图设，l + 1 个部件的寿命分别为x ，x ：，x 。，且相互独立，则系统寿命为x ，= x 1 + x 2 + + x ，系统的可靠度为墨o ) = p ( x ， f ) = 1 一p ( x ，f ) = l 一尸( x l + x 2 + + x 。“s f )( 2 6 )( 2 ) 有冷贮备的串联系统，系统由n + z 个部件组成，工作部件是f 个部件组成的串联系统，贮备仍为n 。事实上，可将该系统等效成一个故障率为该串联系统故障率的部件，另外，1 个部件在等待的冷贮备系统来分析。除了以上模型之外，在工程系统可靠性分析中还存在竞争模型、混合模型、复合型等典型的系统可靠性模型。2 3 网络系统可靠性模型除前面介绍的串联、并联和冷贮备等典型模型之外，还有一种一般网络模型，如通信网络、交通网络、给排水网络和电路网络等，如图2 6 所示。根据节点失效和不失效的情况，网络系统又可分为节点失效和节点不失效网络系统模型。图2 6 网络系统可靠性框图2 3 1 节点不失效网络系统可靠性模型网络系统由节点和节点间的连线( 弧或单元) 连接而成。节点不失效的情况1 2下，一般讨论网络的终端问题。这类问题可以描述为：设g 是一个给定的网络，一、y ，是指定的两个节点，求从h 到达v ，的概率即r = p v i 可以到达v ， ，称为终端可靠性阅题。节点不失效网络可靠性问题的基本假定有：( 1 ) 弧( 或单元) 和系统只有两种可能状态，即正常或失效；( 2 ) 节点的可靠度为l ，即节点不失效：( 3 ) 弧( 或单元) 之间相互独立。节点不失效网络可靠性有以下几种求解方法：( 1 ) 真值表法。真值表法也称穷举法，根据假设，1 个部件构成的系统具有z 种微观状态，又可归纳为正常或失效两种状态。系统正常的概率即为所有正常的微观状态之和，因为这些微观状态是互斥的，当厅较小时此方法比较实用。( 2 ) 全概率分解法。应用全概率公式，选择分解元，对复杂网络进行分解，化简为一般的串并联系统，从而计算系统正常的概率。如，设g 为系统正常事件，毒为被选分解单元正常事件。i 表示被分解单元失效事件，由全概率公式可知：r ( g ) = p ( 曲p ( g i d + p ( 习p ( g 胁( 2 7 )式中，p ( g f 工) 表示在单元工正常工作的条件下系统正常工作的概率；p ( g 向表示在单元工失效条件下系统正常工作的概率。( 3 ) 最小路集法。由于真值表法只适用于小型网络，全概率法难以程序化，所以网络可靠性的一般算法目前多用最小路集法。路集是由网络中的部分单元组成的集合，当路集中的单元全部正常时，则网络系统正常。当路集中去掉一个单元时，不成为路集，则称此路集为最小路集。最小路集的求解方法一般有邻接矩阵法和节点遍历法。若己知网络系统的节点l 到歹有掰个不同的最小路集s ；，霹，s 孑，那么节点i 到节点j 的可靠度为：加*i岛= p u ) = ( _ 1 ) “1 p ( n 砖)t = ll t lk 局( 不交和算法不交积之和算法的原理是概率公式( 3 5 ) 。设只( 江1 ，2 ，f ) 表示网络的所有极小道路( k 一树、生成树或割集) ，4 表示只( i = 1 ，2 ，z ) 中所有边都正常运行的事件，则网络的两终端可靠度不交积之和( 简称不交和：s u mo f d i s j o i n t p r o d u c t s ，简记为s d p ) 算法就是将式( 3 5 ) 中的项化为彼此不相交项的和，然后再求这些不相交项的概率。不交项与可靠度表达式中的项一一对应。p r ( g ) = p r u u u 如) = p ， ) + p r 矾 + + p r 硒矾 ( 3 5 )该算法由内外两个循环组成。外循环是指从计算p ， 4 到脚 砸矾的循环；内循环是指具体处理某一项p ， 4 如屯一。a 而形成的循环。此外，不难看出在不交积之和算法中得到的不交积和的项数越少，计算时间和所占空问就越少，产生的计算误差也就越小，人们一般用不交积和的项数来衡量算法的有效性。s d p 方法是由l f r a t t a 和u g m o r t a n a r i 在1 9 7 3 年首先提出来的“，随后很多学者作了大量的研究，使s d p 算法得到不断的改进。算法的改进主要集中在道路 如如j 的排序问题上以及在内循环中如何应用布尔代数知识来巧妙的化简内循环上。1 9 7 9 年j a a b r a h a m 在文献 5 1 中给出了一个定理，该定理为s d p 算法奠定了基础。p b e i c h e l t 算法“、m 0 l o c k s 的a l r 算法”引等都是在j a a b r a h a m 算法的基础上提出来的，并且当时认为a l r 算法可能使不交积和项数达到了最小或几乎最小。1 9 8 9 年k d h e i d t m a m r “”在求不交和时运用了一个新的技巧：用几个变量的积同时取逆来代替单个变量分别取逆，得出了一个使计算时间及不交积和项数都显著减少的算法，使s d p 方法向前推进了一大步。m v e e r a r a 曲a v a n 等1 和l c z h a o 、j c x u m l 又在文献m 1 的基础上分别得到了两个更有效的不交积和算法。总体看来，根据将式( 3 6 ) 中的项化为不交积和时取逆方法的不同，这些算法可分为两大类：一类是单变量取逆；一类是多变量取逆。一般认为多变量取逆比单变量取逆有效。另外，不交积和的项数还与输入的极小道路集合( 置一树，生成树) 或割集的排列顺序有关”“。因此在求事件并的概率之前，都将对输入的事件集合排序，排序方式有：字典序、按道路( 置一树、生成树) 或割集中含边数增加的顺序或二者结合排序等“”。1 9 9 8 年，t l u o 和k s t r i v e d i 在m v