（交通运输工程专业论文）基于交叉口延误的动态与随机交通网络行车诱导路线算法研究.pdf

liii【10llllo-i r e s e a r c ho ns h o r t e s tp a t ha l g o r i t h m si nd y n a m i ca n ds t o c h a s t i c t r a f f i cn e t w o r k s b y z h o uh u i b e ( h u n a nu n i v e r s i t y ) 2 0 0 8 at h e s i ss u b m i t t e di np a r t i a ls a t i s f a c t i o no ft h e r e q u i r e m e n t sf o rt h ed e g r e eo f m a s t e ro fe n g i n e e r i n g l n t r a n s p o r t a t i o ne n g i n e e r i n g i nt h e g r a d u a t es c h o o l o f h u n a nu n i v e r s i t y s u p e r v i s o r p r o f e s s o rl is h u o m a y ，2 0 1 1 m 95洲5肌7， 09iiiii-m y 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 作者签名： f 飘娄 日期：文。f 年多月2 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇 编本学位论文。 本学位论文属于 l 、保密i i ，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“”) 作者签名： 导师签名： 同髦 毒仉乏 日期： 口年6 月上日 ， 日期：二bij 年月2 日 基于交叉u 延误的动态j 随机交通网络行车诱导路线算法研究 摘要 随着信息与通讯技术的不断进步，智能交通系统( i n t e l l i g e n tt r a n s p o r t a t i o n s y s t e m s ，i t s ) 的发展也日渐进步，其中先进的出行者信息系统( a d v a n c e dt r a v e l e r i n f o r m a t i o ns y s t e m s ，a t i s ) 和先进的行车路线诱导系统( a d v a n c e dd r i v e r sr o u t e g u i d a n c es y s t e m ，a d r g s ) ，可向出行者和车辆驾驶员提供交通信息和行车路线 信息服务。这些信息可以方便选择出发时间、行进路径等。在i t s 提供路径诱导 信息时，一个最重要的问题就是如何产生有效与可靠的路径信息。 动态随机最短路径问题定义为在路段行程时间被模拟为连续的时变随机过程 的交通网络中寻找期望的最短路径。本研究的目的在于考虑具有时间变化性 ( t i m e d e p e n d e n t ，以下简称“时变 ) 的道路网路段成本情况下，探讨在不同 的交通量时空分布条件下对于车辆的到达时间、行程时间、以及行车路径的影响， 以作为出行者出行路线规划的参考依据。在道路网络动态与随机交通信息的设计 上，本研究加入不同时段对于出行时间影响的概念，并且以时间范围和相对应概 率方式表示，即加入了某种程度的道路网交通分布的随机性。 本文提出了两个算法架构来求解动态随时路网下的可能旅行路径。首先修正 了m i l l e r h o o k sa n dm a h m a s s a n i ( 1 9 9 8 ) 提出的算法，计算出道路网络的时变行车最 短路径。 当车辆在道路网中行驶时，其所遭遇到的行车成本简单分为两种：其一为路 段行程时间成本；其二为通过道路交叉口时的延误时间成本。现有算法在计算最 短路径时大多未将交叉口的延误问题列入考虑，但实际上城市道路网影响整体车 辆行程时间最大的应属于通过交叉口时所产生的延误成本。所以本文研究的第二 个算法在考虑交叉口延误的情况下，发展时变的最短行车路径( t i m e d e p e n d e n t s h o r t e s tp a t h ) 算法，并探讨其合理性。本研究在分析与交叉口延误相关的行车成 本的计算模型后，采用以信号控制为主的控制延误成本( c o n t r o ld e l a y ) 。并将考虑 车辆在交叉口的转向选择，以此配合交叉口的延误时间的算法，可更进一步反应 交通网络的动态特性，并可应用于未来i t s 的环境。 关键词：时变；随机；最短路径算法；路段行程时间；交叉口延误 h 硕上学位论文 a b s t r a c t a d v a n c e dt r a v e l e ri n f o r m a t i o ns y s t e m s ( a t i s ) a n da d v a n c e dd r i v e r sr o u t e g u i d a n c es y s t e m ( a d r g s ) a r et h es u b s y s t e m so fi 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 ) w h i c ha r ed e s i g n e dt od e l i v e rt h et r a f f i ca n dr o u t ei n f o r m a t i o nd i r e c t l yt o t r a v e l e r s b a s e do ns u c hi n f o r m a t i o n ，t r a v e l e r sc a nm a k eb e t t e rd e c i s i o n sa b o u tr o u t e a n dd e p a r t u r et i m e o n eo ft h ek e yi s s u e so fp r o v i d i n gr o u t eg u i d a n c ei n f o r m a t i o ni s h o wt oe f f e c t i v e l yg e n e r a t er e l i a b l er o u t ei n f o r m a t i o n t h ed y n a m i ca n ds t o c h a s t i cs h o r t e s tp a t hp r o b l e m ( d s s p p ) i sd e f i n e da sf i n d i n g t h ee x p e c t e ds h o r t e s tp a t hi nat r a f f i cn e t w o r kw h e r et h el i n kt r a v e lt i m e sa r em o d e l e d a sa - c o n t i n u o u s t i m es t o c h a s t i cp r o c e s s t h eo b j e c t i v eo ft h i sp a p e ri st ot oe x a m i n e t h ep r o p e r t i e so ft h ep r o b l e ma n di d e n t i f i e sw h a te f f e c t sd i f f e r e n ts p a t i a la n dt e m p o r a l d i s t r i b u t i o no ft r a f f i ch a v et o w a r d sv e h i c l ea r r i v a lt i m e ，l i n kt r a v e lt i m ea n dt r a v e l p a t h so nt h e s et i m e - d e p e n d e n tn e t w o r k s ，a n dt ou s ei ta sac o n s u l t a t i o nf o rt r a v e l e r s r o u t ep l a n n i n g w h e ni tc o m e st ot h ed e s i g no fd y n a m i ca n ds t o c h a s t i ct r a f f i c i n f o r m a t i o n ，t i m er a n g ea n dt h ec o r r e s p o n d i n gp r o b a b i l i t ya r ep r o p o s e dt op r e s e n t d y n a m i ca n ds t o c h a s t i cn e t w o r k t h i sp a p e rp r o p o s e st w op r o c e d u r e st od e t e r m i n ep o s s i b l et r a v e lr o u t e sa n dt h e i r a s s o c i a t e dp r o b a b i l i t i e si nat i m e d e p e n d e n ta n ds t o c h a s t i cr o a dn e t w o r k t h ef i r s t a l g o r i t h mg e n e r a t e st h er a n g eo fp o s s i b l et r a v e lt i m eo ft h es u g g e s t e dp a t hb a s e do n t h ea l g o r i t h mp r o p o s e db ym i l l e r h o o k sa n dm a h m a s s a n i ( 19 9 8 ) w h e nv e h i c l e sa r et r a v e l i n gi nad y n a m i ca n ds t o c h a s t i cr o a dn e t w o r k ，t h et r a v e l c o s tc o u l db ed i v i d e di n t ot w op a r t s ，l i n kt r a v e lt i m ea n di n t e r s e c t i o nd e l a y m o s to f t h es h o r t e s tp a t ha l g o r i t h m sa s s u m et h a tt h e r ei sn oc o s t so rp r o h i b i t i o n sa s s o c i a t e d w i t hi n t e r s e c t i o nd e l a y s ，b u tt h ei n t e r s e c t i o nd e l a y sm i g h tb et h ed o m i n a n tf a c t o r w h e nc a l c u l a t i n gt h es h o r t e s tp a t h si nac o n g e s t e du r b a nr o a dn e t w o r k t h es e c o n d a l g o r i t h m a i m sa t d e v e l o p i n gt i m e d e p e n d e n t s h o r t e s t p a t ha l g o r i t h m s w i t h i n t e r s e c t i o nd e l a y s t h em e t h o do fc a l c u l a t i n gi n t e r s e c t i o nd e l a y sa r ea v e r a g ed e l a y s c o n s i d e r i n gd r i v e r s t u r ns e l e c t i o nu n d e rs i g n a lc o n t r 0 1 t h ed e l a yu n d e rs i g n a l c o n t r o lc o u l dr e f l e c tt h ei m p a c to fs i g n a la n dv a r i a t i o n so ff l o w t h i sa l g o r i t h m sc o u l d r e f l e c tt h ed y n a m i cc h a r a c t e r i s t i c so ft r a f f i ca n da p p l i c a t i o nt ot h ee n v i r o n m e n to fi t s i nt h ef u t u r e 1 l l 基于交叉u 延误的动态与随机交通网络行车诱导路线算法研究 k e yw o r d s ：t i m e d e p e n d e n t ；s t o c h a s t i c ；s h o r t e s tp a t ha l g o r i t h m s ；l i n kt r a v e lt i m e ； i n t e r s e c t i o nd e l a y t v 硕1 ：学位论文 目录 学位论文原创性声明和学位论文版权使用授权书i 摘要i i a b s t r a c t i i i 插图索引一v i i 附表索引v i i i 第1 章绪论1 1 1 论文研究背景与目的l 1 2 国内外相关研究综述一2 1 3 研究流程及内容一5 第2 章城市道路交通网络模型研究8 2 1 概述8 2 2 基本术语介绍8 2 2 1 节点8 2 2 2 路段9 2 2 3 道路网的连通性9 2 2 4 图和有向图一9 2 2 5 赋权图9 2 2 6 节点的邻接边9 2 2 7 节点的出度和入度9 2 2 8 路径和路径长度9 2 2 9 节点的上游节点和下游节点一1 0 2 3 道路网连通性表达一lo 2 3 1 基于转向限制的道路网数学模型1 0 2 3 2 道路网的复杂性分析1 1 2 4 道路网中交叉口延误分析一1 2 2 4 1 各种交叉口延误的定义1 2 2 4 2 车辆延误的影响因素14 2 5 本章小结l5 第3 章最短路径算法研究1 6 3 1 概j 苤16 3 2 最短路径算法1 7 v 基于交叉口延误的动态j 随机交通网络行车诱导路线算法研究 3 2 1 问题定义17 3 2 2 最短路径算法分类一1 7 3 3 时变的最短行车路径问题1 8 3 3 1 问题定义1 8 3 4 求解算法1 8 3 4 1 标号设定法( l a b e ls e t t i n ga l g o r i t h m ) 1 9 3 4 2 标号修正法( l a b e lc o r r e c t i n ga l g o r i t h m ) 19 3 4 - 3 算法比较及选用2 0 3 5 本章小结2 0 第4 章新算法的架构及实例2 2 4 1 新算法道路网络架构及相关变量2 2 4 2 新算法的架构2 4 4 3 可准时抵达目的地的最迟出发时间分析2 5 4 3 1 求解问题的定义2 5 4 3 2 求解问题的方法2 5 4 3 3 求解步骤2 6 4 3 4 算法理论分析2 7 4 3 5 算法应用实例2 9 4 4 考虑道路交叉口延误的最短行车路径问题3 2 4 4 1 道路交叉口模型3 2 4 4 2 道路交叉口延误时间计算公式一3 2 4 5 本章小结4 5 结论与展望4 6 参考文献4 8 致谤 5l 附录a 攻读学位期间所发表的学术论文目录5 2 v l 硕上学位论文 图2 1 图2 2 图4 1 图4 2 图4 3 插图索引 交通网络基本建模要素l1 节点构造法1 2 动态与随机道路网络范例3 0 按照各个交通流向设计的道路交叉口i 计算模型3 2 实例有向道路网络3 5 v u 基于交叉口延误的动态j 随机交通网络行车诱导路线算法研究 表2 1 表4 1 表4 2 表4 3 表4 4 表4 5 表4 6 表4 7 表4 8 附表索引 节点转向表一l2 动态与随机道路网表达方式( 以路段( i ，j ) 为例) 一2 3 动态与随机道路网络的变量表示( 以路段( “i ) 为例) 2 4 动态与随机道路网络范例的已知数据3 0 最早到达的最短出行路径算法的动态与随机道路网范例计算结果3 l 实例有向道路网络动态与随机路段行程时间资料( s e c v e h ) 一3 6 实例有向道路网络节点( 道路交叉口) 交通控制信号参数资料3 7 计算得出的道路网节点( 交叉口) 平均车辆延误时间( s e e d v e h ) 3 7 最短出行路径算法的动态与随机道路网实例计算结果4 4 v i i i 硕 ：学位论文 1 1 论文研究背景与目的 第1 章绪论 由于我国社会经济的快速增长，各大中城市的道路交通问题愈来愈严重，尤 其是与f 1 激增的机动车辆保有量，对各大中城市的道路交通环境造成严重的冲击， 整体道路交通运输系统因缺乏有效的管理与运作而无法满足现有的道路交通需 求。因此，各国均开始着手进行智能交通系统( 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 ) 的研究与发展。i t s 的主要发展目标是希望结合先进的电子、控制、计算机 网络、通讯、以及导航等新兴科学技术，来解决各种道路交通问题，并加强道路 交通系统的效率与安全【1 , 2 , 3 l 。近年来，随着信息科技和通讯系统发展迅速，智能 交通系统( i t s ) 逐渐受到重视，其中先进出行者信息系统( a t i s ) 和先进的动态行 车路线诱导系统( a d r g s ) ( 含动态停车诱导系统) 的目标在于提供道路出行者必 要的路况和交通信息，使其顺利和快速地达到目的地。因此如何提供对道路出行 者有用而且准确率高的道路交通信息是本研究领域关心的课题。 目前世界各国已有不少发展a t i s 和a d r g s 来应用于私人汽车和公共交通系 统。例如私人汽车所安装的定位导航系统，可提供驾驶员查询从起点至讫点的行 车路线诱导功能【4 】。此外，在现有的道路诱导系统部分，为使驾驶员最快到达目 的地，多半以最短行车时间路径方式呈现结果。 尽管道路交通诱导系统的目的在于提供最快到达的道路路线信息，然而受限 于道路交通数据量大、动态和随机性( 实时性) 、数据采集不易、相关技术的发展 等因素，使得过去系统多采用静态交通数据，即道路网络的路段成本以确定型的 距离或行程时间等方式表示，并未考虑时变的道路网络路段阻抗【5 l 的问题。实际 应用中，时变的行车阻抗却是影响行程时间的最大因素，因此为提供出行者更有 效的行前信息，时变的最短行程时间路径才更符合实际的道路交通需求。 所谓的时变最短行程时间路径问题，是指道路路段上的车辆行程时间阻抗会 随着出发时间的不同而有所不同，且道路路段行车阻抗除了与出发时间有关之外， 也会随着出发后到达道路路段的时刻的不同而不同。正因为道路路段时变行车阻 抗更加复杂，因此就必须寻找一个可有效处理不同时间点的算法，以进行求解。 此外，当车辆在道路网中行驶时，其阻抗可简单分为两种，其一为车辆在道路路 段上的行程时间阻抗；其二为车辆通过道路交叉口时所发生的延误阻抗。 在城市道路网中，无疑影响整个车辆行程时间最大的因素应属于通过道路交 叉口时所产生的延误阻抗。所以若在计算最短行程时间路径时未将道路交叉口的 基于交叉1 2 1 延误的动态i 随机交通网络行车诱导路线算法研究 延误问题列入考虑，其所得到的结果无法反应真正的道路交通阻抗和状况。所以 在时变最短行程时间路径计算中若能加入道路交叉口延误阻抗的因素，应可- 以为 道路出行者提供更加确实可靠的行车路径信息。对于道路路段行车阻抗方面，在 基本的最短行程时间路径计算开始时，便固定所使用的道路路段行程时间阻抗以 及道路交叉口延误阻抗，使其不会随时间变动而改变；而在时变最短行程时间路 径的求解过程中，道路路段的行程时间阻抗和道路交叉口的延误阻抗都将会随着 时间的变化而发生变化。 为了要解决行车路线的诱导问题就必须解决动态和随机的道路交通流量在道 路网络中的道路路段和交叉口的交通量分配问题，即所谓的“实时动态交通分配 ( r e a lt i m e - - d y n a m i ct r a f f i ca s s i g n m e n t ) ”问题。解决这一问题的主要目的是： 预测道路交通系统运行状况，提供道路交通诱导信息，实时引导车辆在最佳路线 上行驶，为道路出行者提供最优出发时间和选择最佳出行方式，提供实时行车路 线诱导信息与道路交通控制系统的运作相互关联，为先进的道路交通管理系统和 道路交通信息系统提供重要的理论基础。 本研究是以标号修正最短路径算法( l a b e lc o r r e c t i n ga l g o r i t h m ) 为基础，模 拟离散型动态与随机型道路路段行程时间数据，考虑车辆在道路交叉口的转向延 误阻抗，构建离散型动态与随机状态下的后推式最快( 短) 行车路径算法，应用于 道路出行者出发前的行车路径决策；为道路出行者提供最佳行驶路径建议和最晚 可行的出发时间：使得道路出行者可视实时路况、实时交通状况、或根据自我需 求改变其出行决策。因而免除因为不确定性所造成不必要的行程时间延误和等候 时间的浪费，从而提高动态与随机道路交通网络的运行效率。 本研究的目的概述如下： ( 1 ) 分别探讨动态与随机的最短行车路径算法，考虑离散型动态与随机道路 路段行程时间算法，并在其中加入道路交叉口延误阻抗。 ( 2 ) 根据动态与随机道路网中不同的出行起讫点、预定到达时间等条件，计 算出各种不同的动态与随机最短行程时间的行车路径结果，主要是最短行程时间 的行车路径和最晚出发时间，使得车辆驾驶员能在预定的时间内准时到达目的地。 ( 3 ) 分析道路交叉口的车辆延误阻抗构成，根据左转、右转、直行延误模型， 考虑出现车辆在信号交叉口的的车辆延误，使算法得出的结论更加符合实际情况。 1 2 国内外相关研究综述 先进的出行者信息系统( a t i s ) 和动态与随机行车路线诱导系统( a d r g s ，又 称道路交通诱导系统) 是智能交通系统( i t s ) i 拘重要组成部分。a t i s 在提高城市道 路交通网络的利用效率方面确实可以发挥重要作用：t s u j i e t a l l 6 1 通过模拟发现：驾 车者在交通信息系统引导下可获得9 0 1 4 的效益，在突发性道路交通拥挤中甚 硕士学位论文 至会更高。k a n a f a n ia n da i d e e k l 7 l 的研究发现，道路交通诱导信息可使道路网进 入最佳运行状态，产生4 的净效益。a d r g s 以实时动态与随机交通分配理论为 核心，综合运用车辆检测、交通通信、计算机网络、交通控制、全球定位系统( g p s ) 、 以及交通地理信息系统( t g i s ) 等高新技术，动态地向驾驶员提供最佳行车路径 诱导指令和实时的动态交通信息，通过对每个车辆个体行车路线进行诱导，改善 道路交通拥挤状况，防止和减轻交通阻塞，减少车辆在道路上的逗留时间，并最 终实现交通流在道路网中各个路段上的合理和均匀分配。动态与随机行车路线诱 导技术是正确引导道路使用者顺利到达目的地、实现道路交通流优化分布、避免 道路交通阻塞、更有效地管理现代道路交通的新技术。动态与随机行车路线诱导 系统将成为2 l 世纪地面交通运输管理体系的模式和发展方向，并成为使得道路交 通运输系统进人信息化技术时代的重要标志。杨兆升和初连禹总结1 8 】了动态路径 诱导系统问题研究的一些进展。黄海军1 9 ，1 0 ，分析了动态交通网络中交通流的特 征、分类，较全面地回顾了交通模型、算法研究的进展。 在动态与随机最短行车路径的计算中，主要的阻抗考虑可分为道路路段距离 与道路路段行程时间，大多数文献都是假设出行者的择路行为是选择最短( 旅行费 用、旅行时间或旅行距离最小) 路径。因此，有许多文献是对最短路径选择的模型 和算法进行研究【1 2 之3 1 。当以行程时间作为最短路径行车成本时，所面对的交通阻 抗主要是道路路段行程时间、道路路段及交叉口延误时间。而在动态与随机最短 行车路径中所讨论的道路路段行程时间阻抗中，主要的计算方式是采用道路路段 的长度除以平均行车速度求得；但对于延误时间阻抗而言，却有着许多不同的影 响因素，因此在计算和使用上也较为复杂及多样化，其中较常见也是影响最大的 莫过于车辆通过道路交叉口时所产生的延误时间阻抗。所以，本研究主要针对车 辆在道路交叉口所产生的相关延误阻抗进行讨论与计算。 关于动态( 或时变) 最短行车路径问题( t i m e d e p e n d e n ts h o r t e s t p a t h p r o b l e m ) ，主要在于每一道路路段上的行程时间阻抗在不同时段存在不同的值。 一般最短路径问题的路段行程时间阻抗为固定常数，但在动态最短行车路径问题 中，路段行程时间阻抗会随着时间的不同而有所变化。 z i l i a s k o p o u l o s 和m a h m a s s a n i l 2 4 l 主要求解道路网络中任一节点到一特定终点 ( 多对一) 的定性且时变的最小可能行程路径问题，且适用于非先进先出 ( n o n f i f o ，n o nf i r s t i n f i r s t o u t ) 情况。此研究将所考虑的时间范围分割成m 个 时间段( t i m ei n t e r v a l ) ，且每个节点及时间段均有一个相对应的道路路段行程时间 成本。他们提出从所有节点到终点的最短行程时间成本算法，修正为一对多的标 记修正法，采用反推算的方式( b a c k w a r d ) ，即将特定终点视为开始计算起，道 路网络中的其它节点视为后面的节点加以计算。故算法首先由终点出发，求得终 点的所有上游节点到达终点的最短行程时间成本，将最短行程时间值发生更新的 基于交叉口延误的动态与随机交通网络行车诱导路线算法研究 上游节点加入到备选节点集合s c a ne l i g i b l en o d el i s t ( s el i s t ) 当中；再由s el i s t 当中挑选第一个节点出发，求得该节点的上游节点当中的最短行程时间值有变化 者，加入到s el i s t 当中，直到s el i s t 为空集合时为止。此算法所需要的计算时 间复杂度为d f 3 m 3 l ，其中n 为节点总数。 m i l l e r h o o k 和m a h m a s s a n i t 2 5j 采用与z i l i a s k o p o u l o s 和m a h m a s s a n i l 2 6 1 相类似 的架构，不同之处在于前者的研究将定性且时变的道路网络改为动态且随时间变 化的道路网络，计算高峰时段不同起点出发( 多对一) 的时变的最短行车路径。 假设随机道路网络路段阻抗函数相互独立，且可适用于非先进先出的道路网络。 第一个算法针对每个出发的时间段，求出从道路网络中的任一节点到迄点的最小 可能时间行车路径、最小可能行程时间、以及与其相对应的概率下限值；第二个 算法则改进为找出k 条最小可能行车时间路径和与其相对应的概率下限值。此两 种方法均能有效地找出最短行车路径，且s el i s t 架构能够提供更多信息时，计 算的时问复杂度仍不会增加太多。 f ua n dr i l e t t l 2 7 , 2 8 】的目的在于估计每天固定发生的道路网状态下的动态起讫 点的旅行时间。首先将道路网按照城市布局分为三个区域，假设区域中的每个路 段行程时间曲线一致，并将一天的时问按照高峰离峰分为三个时段，以离峰时段 的行程时间为基础，高峰时段行程时间设定为正态分布函数。此研究提出一两阶 的f e e df o r w a r d 人工神经网络将不同时段的行程时间行为模式化，结果表明人工 神经网络可以预测在动态路网下两地间的行车时间。 d a v i e sa n dl i n g r a s ! ”l 放松区别所有节点的限制，求解动态路网最短路径问 题。类似于f ua n dr i l e t t 的算法，并假设路段权重( w e i g h t ) 为己知的时间函数。 主要采用遗传算法( g e n e t i ca l g o r i t h m s ) ，延伸到重新规划最短路径问题，并以 降低结果的准确率来取得更加迅速的计算时间。但是，此方法仅适用于较简单的 路网，在高度动态，路段成本呈非线性的路网中，所得效果较修正后的d i j k a s t r a 算法差。 f ua n dr i l e t t l 3 0 】主要求解在给定路网的出发时间下，求解从起点到讫点的最小 路径。首先将道路网路段的行程时间设定为连续的随机变量，且概率分布和一条 的时间是相依的，并假设可获得不同时间点的平均值和方差。此研究根据k 条最 短路径算法，在道路网上没有交通事故发生的前提下，提出一套启发式算法，其 测试结果是找出较佳解，且小幅增加k 值和计算时间，但是其路段行程时间资料 为虚拟值，所以无法得知是否适用时间路网。 f ua n dr i l e t t 2 3 1 探讨可从智能交通系统获得信息的情况下，求解动态与随机最 短路径问题。此研道路网中的路径行车时间为连续时间型的随机过程，且假设在 不同时间点，每个路段的行程时间相互独立。首先利用统计方法了解动态与随机 网络中的路段行程时间平均值与方差的关系，证明随机动态最短路径问题在计算 硕l ：学位论文 上相当复杂，因此研究根据k 条最短路径算法概念，将时间相依的最短路径求解 从旅行时间的问题，转换为求解到达时间的问题，并利用泰勒展开式将旅行时刻 期望值展开，并有取其二阶近似值的方式，求解到达时间的期望值。其测试结果 发现k 值越大效果越好，且增加的计算时间均在可容忍范围，但是路段行程时间 资料为虚拟值，所以无法得知是否适用实际路网。 w a l l e ra n dz i l i a s k o p o u l o s t mj 主要探讨在考虑时间和空间相依的旅行成本下的 随机最短路径问题，适用于当使用者以进入路网后，仍可依据时间状况随时间调 整其路径规划。空间相依的最短路径问题即假设路段的成本相依性只受临近路段 的影响，此研究设定每个路段只与其一上游点相依，且道路网路段成本必须大于 零，也不允许在节点上等待。时间相依最短路径问题假设在到达任一节点时，可 得出连接此节点的路段成本，且未来短期的路段成本可根据目前的观察值产生。 时空相依的最短路径问题有两项假设前提，一是必须有实时监控系统采集下游节 点的信息，二是经过一路段所需的行程时间很小，不至于在经过期间其行程时间 成本会有所改变。此两种问题均修正多对一的标号修正法，求解定性且随时间变 化的最短路径，即使增加路网复杂度，计算时间不会改变太大。 另外，根据行程时间采集方法的不同，可分为两种情形：其一是以统计分布 方式获得每个时间段的道路路段行程时间，属于连续型( c o n t i n u o u s ) ；另一种则是 通过资料搜集或其他方式，将时间以时段来区分，依据每个时间所属的区段来获 得所需的行程时间，属于离散型( d i s c r e t e ) 。 综上所述，过去文献对于依时性最短路径问题的路段行程时间的表示，多数 采用定性、离散型分配的历史统计资料；其主要原因在于现实生活中，行车时间 资料的取得困难，相关的行程时间函数的建立也相当复杂，所以为了方便求解， 而忽略了行程时间成本随时间变化的特性。对于依时性最短路径问题的求解方法， 除了少数利用人工神经网络和遗传演算法以外，大多算法的发展仍采用标号修正 法的概念作为研究基础，再根据不同的研究范围和目的加以修j 下。过去文献在解 决时间相依最短路径问题上，仍未完整表示时间相依的路段行程时间特性，且极 少探讨相关的随机问题。唯有m i l l e r h o o ka n dm a h m a s s a n i 的算法所提出的概率 表示较为相近，所以本研究将针对此算法配合本研究的目的加以修正。 1 3 研究流程及内容 在本研究领域文献中，有关动态与随机最短行车路径问题的研究多属于前推 式最短路径算法，很少研究涉及后推式最短路径问题及其算法。以下依序介绍依 时变性前推式最短行车路径算法、离散型时变性后推式最短行车路径算法。 前推式最短路径问题是道路出行者确定其出发起点d 、讫点d 和预计出发时 基于交叉口延误的动态与随机交通网络行车诱导路线算法研究 间( ) 之后，通过离散型或连续型时变性前推式( 即从起点计算起，直至终点的计 算方法) 最短行车路径算法。计算结果为建议的最短行车路径( d ，f ，j ，d ) 和可能的到达时间也) 。道路路段行程时f qf j ，o ，) 则由车辆进入道路路段的时间点来 决定，并限制 ，= f f + ，。“) 。以连续型时变性前推式最短行车路径算法为例，路 径行程时间由道路路段行程时间r 。累加求得。假设从起点出发时间的时间是“， 道路路段( o ，f ) 的行程时间假设为a l ，因此离开道路交叉1 2 1f 的时间为f o + q ；道 路路段( f ，) 的行程时间假设为呸，因此离开交叉口j 的时间点为，o + 口i + a 2 ，以此 类推，直到搜寻计算至讫点d 为止。 后推式最短行车路径问题是道路出行者确定其出发起点d 、讫点d 和预计抵 达时间r 。) 后，通过离散型或连续型时变性后推式最短行车路径算法，计算结果为 建议的最短行车路径( o ，f ，j ，d ) 和可行的出发时间( ，口) 。离散型后推式最 短行车路径算法的道路路段行程时间是从离开下游交叉口，的时间点f ，往后推 得进入上游交叉口f 的时间点，必须要满足+ ，。( t i s ) t j ，t a 为某一时间段s ( t i m e i n t e r v a l ) 内节点f 的出发时间，且f 西f ，进而求得进入上游交叉口f 的时间点 f ，= ，一t ，k ) ，再依此时f q 点往起点反向推算出建议的最短行车路径和可行的出发 时间。注意，最开始的计算节点是终点d 。 本文的研究流程各个步骤及内容详细说明如下： l 、描述与界定问题 依据目前实际道路网的交通状况，提出适用的动态与随机最短行车路径问题， 并根据研究动机与目的将问题作一个完整的描述与界定。 2 、搜集资料与文献综述 搜集国内外探讨时变的最短行车路径问题的相关文献，并综述文献的解决方 法、模型、及其算法；比较分析不同算法的限制条件、优缺点与适用性；从中挑 选出一个较符合本研究的算法；针对其不合理性，修正为较符合现实道路网交通 况的算法。 3 、构建时变与随机型的道路交通网络模型 根据目前实际道路网可提供的相关交通数据形式，构建一个时变型的道路交 通网络模型，用以描述求解动态与随机最短行车路径问题的特性和与之相关的限 制条件。 4 、构建考虑道路交叉口延误的时变的道路交通网络模型 在研究流程( 3 ) 的基础上，利用文献【3 2 】提出的道路网交叉口延误模型计算 各道路交叉口的交通延误时间，并加入到本文的动态与随机交通网络模型中。 5 、设计求解算法 利用所设计的算法求解道路交通流不同时空分布状况下的最短行车路径和道 路网中各个起讫点对( o ，d ) 之间从起点o 最晚时间出发可以到达讫点d 的时 硕- f ：学位论文 间。 6 、结论与展望 对本研究的过程与结果进行全面的总结和提出建议。 7 基于交叉口延误的动态j 随机交通网络行车诱导路线算法研究 2 1 概述 第2 章城市道路交通网络模型研究 城市道路交通网络是由节点之间通过许多有限长度的道路路段连接而成的， 它是一个复杂、开放、自适应和具有突变特征的系统【3 3 1 。首先，由于多行为主体 的参与，不同道路出行者对时间、费用的敏感程度不同，对道路阻抗的预测能力、 理解能力和信息获得能力也不同( 安装了a t i s 装置的和没有安装的) ，因而会做出 不同的出行路径选择行为。系统中多行为主体构成的道路交通流分布本身就具有 不确定性，而且系统存在突变，这就决定了城市道路交通网络的高复杂性。其次， 即使是同一个出行者，由于具体的出行目标、约束时间、道路熟悉程度和行程时 间波动程度等，在不同出行情景中也会做出不同的出行路径选择。这种选择的结 果就反映到道路网中的交通流分配上，就形成了自适应、动态、随机、反馈、多 行为主体和非线性的道路交通流，系统突变时在线的信息以及系统的开放性决定 了城市道路交通流的高复杂性和不确定性。积累效应、吸引性、开放性进一步加 深了道路交通网络的复杂程度。 这种复杂道路交通环境中的不确定性分为两类：一是道路网络自身在客观上 存在的随机性，如天气的随机变化，交通流的随机分布，交通事故的随机发生； 二是道路出行者对道路网络主观认识上存在着模糊性，对道路阻抗理解的模糊性。 如他们的预测能力、理解能力、风险承担能力、信息获得能力、出行经验和道路 熟悉程度等都会影响其出行路径的选择行为。 通常，简化道路网复杂性有两个方法：第一个方法是从路径算法着手，修正 经