（计算机应用技术专业论文）关于全局最优交通寻路算法的研究.pdf

上海大学硕士学位论文 摘要 随着交通运输业的发展，车辆导航系统被越来越多的人们所接受，用来在行 驶过程中，快速准确地确定车辆的位置，为司机指出到达指定目的地的合理路径。 在车辆导航系统中，如何引导车辆是一个至关重要的问题，因为如果采用不合适 的引导策略，导航系统的应用可能反而会对交通系统的效率产生负面影响。事实 上，传统的贪婪引导法，也就是将所有车辆都引导到最优路径上，可能会因为最 优路径上聚集了超过其交通容量的车流，而造成堵车等现象，从而降低交通系统 的效率。从这个角度来讲，适当分流，让一部分车辆选择其他路径行驶，反而会 提高交通系统的整体效率。而如何分流才能使得交通系统中所有车辆的总行驶时 间最短，是一个值得探讨的问题。 本文提出了一种新型的启发式算法一b o l t z m a n n 全局最优寻路算法，该算法 为交通系统中从不同起点出发开往不同终点的所有车辆，寻找近似全局最优的交 通流分配方案。该算法的主要思想是反复迭代地根据在当前的交通状况下，车辆 通过各路段所要花费的行驶时间，结合基于q 值的动态规划算法和b o l t z r n a n n 分布 为交通系统寻找拟最优路径，根据该拟最优路径分配交通流，然后再根据分配后 的交通流，启发式地更新路段行驶时间，再次寻找新的拟最优方案，直到交通系 统中所有的路段行驶时间收敛，我们找到近似全局最优交通流分配方案为止。 该算法分别在静态交通系统和动态交通系统中与g r e e d y 算法，即将所有车辆 都引导到最优路径上的车辆引导算法进行了比较。这里，在静态交通系统中，我 们假设流入交通系统的车流量是静态不变的；而在动态交通系统中，从不同起点 出发到达不同终点的车流量，都将随机不断生成。实验结果显示，应用b o l t z m a n n 全局最优寻路算法能够合理地分配交通流，为交通系统带来更高的整体效率。 本文所做的主要贡献有：( 1 ) 结合基于q 值的动态规划算法，提出了b o l t z m a n n 全局最优寻路算法( 2 ) 分别在静态和动态模拟交通系统中对其加以了验证( 3 ) 对实验结果进行分析和评估，并提出了改进建议。 关键词：q 值；动态规划：b o l t z r n a t m 分布；贪婪算法；全局最优 v 上海大学硕士学位论文 a bs t r a c t n o w a d a y s ，g i l l n a v i g a t i o ns y s t e m sa r ec o m m o n l ya d o p t e di nt h et r a n s p o r t a t i o n s y s t e m st oh e l pc a rd r i v e r sa c c u r a t e l ya n dd y n a m i c a l l yl o c a t et h e i rp o s i t i o n so nt h e m a pa n dt h e nf i n dd e s i r a b l er o u t e sf o rm e i rd e s t i n a t i o n s i n d e e d ，t h es c h e d u l i n g m e t h o d s ，i e ，h o wt r a f f i ci sg u i d e di nv e h i c l en a v i g a t i o ns y s t e m sm o r es p e c i f i c a l l y , h a v ea ni m p o r t a n ti m p a c to nt h es y s t e me f f i c i e n c y , s i n c ea d o p t i n gu n s u i t a b l eg u i d i n g s t r a t e g i e sw o u l dp r o b a b l yr e s u l ti nt e r r i b l ec o n d i t i o n s a c t u a l l y , t h et r a d i t i o n a l m e t h o d st e l l i n ge v e r yd r i v e rt h es h o r t e s tp a t hh a v eah i g hp r o b a b i l i t yt oc a u s et r a f f i c c o n g e s t i o n , b e c a u s es h o r t e rr o m es e c t i o n sm a ya t t r a c tm o r ev e h i c l e s ，w h i c hw o u l d p o s s i b l ye x c e e d st h er o a dd e s i g nc a p a c i t i e s i nt h i ss e n s e ，i n t r o d u c i n ga l t e r n a t er o u t e s m a yp r e s e n tg r e a t e ra d v a n t a g ei ng i o b a lp e r s p e c t i v e ，a n dh o wt om a k et h er o u t e sf o r a l lt h ev e h i c l e si nt h ew h o l et r a f f i cs y s t e mw i t haf e a s i b l ea n dr e a s o n a b l ew a ya r i s e s a sac h a l l e n g i n gt a s kf o r t h ec e n t r a l i z e dt r a f f i cs c h e d u l e r t h e r e f o r e ，i nt h i sp a p e r , w ep r o p o s eah e u r i s t i cm e t h o d b o l t z r n a n no p t i m a l r o u t em e t h o dt r y i n gt of i n dag o o da p p r o x i m a t i o nt ot h eg l o b a lo p t i m u mr o u t ef o r o r i g i n d e s t i n a t i o np a i r st h r o u g hi t e r a t i o n su n t i lt h et o t a lt r a v e l i n gt i m ec o n v e r g e s 1 1 1 eo v e r a l li d e ao fo u rm e t h o di st oi t e r a t i v e l yu p d a t et h et r a v e l i n gt i m eo fe a c hr o u t e s e c t i o na c c o r d i n gt oi t sc o r r e s p o n d i n gt r a f f i cv o l u m e ，a n dc o n t i n u o u s l yg e n e r a t ea n e wg l o b a lr o m eb yqv a l u e - b a s e dd y n a m i cp r o g r a m m i n gc o m b i n e dw i t hb o l t z m a n n d i s t r i b u t i o n f i n a l l y , w ec a ng e tt h eg l o b a lo p t i m u mr o m ec o n s i d e r i n gt h et r a f f i c v o l u m e so ft h er o a ds e c t i o n s t h en e wp r o p o s e dm e t h o di sc o m p a r e dw i t ht h ec o n v e n t i o n a ls h o r t e s t - p a t h m e t h o d g r e e d ya l g o r i t h mi nb o t hs t a t i ct r a f f i cs y s t e mw h e r et h ev o l u m e so fa l lt h e g i v e no r i g i n - d e s t i n a t i o np a i r so fr o a dn e t w o r k sa r es t a t i ca n dd y n a m i ct r a f f i cs y s t e m i nw h i c hd y n a m i ct r a f f i cv o l u m e sa r ec o n s t a n t l yp r o v i d e d t h er e s u l td e m o n s t r a t e s t h a tt h ep r o p o s e dm e t h o dp e r f o r m sb e t t e rt h a nt h ec o n v e n t i o n a lm e t h o di ng l o b a l p e r s p e c t i v e t h ek e yc o n t r i b u t i o n so fo u rr e s e a r c ha r ed e s c r i b e da sf o l l o w ：f i r s t ，w ep r o p o s e aqv a l u e b a s e dd y n a m i cp r o g r a m m i n ga l g o r i t h mw i t hb o l t z r n a n nd i s t r i b u t i o nf o r o p t i m i z i n gt h eg l o b a lt r a f f i cr o u t i n gs t r a t e g y s e c o n d ，t h ep r o p o s e dm e t h o dh a sb e e n s i m u l a t e db o t hi ns t a t i ct r a f f i cs y s t e ma n dd y n a m i ct r a f f i cs y s t e m t h i r d ，b a s e do n e x p e r i m e n t s ，s o m em e t h o d st oe v a l u a t et h ea l g o r i t h mp e r f o r m a n c eh a v eb e e nu s e d a n ds o m es u g g e s t i o nt oi m p r o v et h ep e r f o r m a n c eh a sb e e n p u tf o r w a r d k e y w o r d s ：qv a l u e ；d y n a m i cp r o g r a m m i n g ；b o l t z r n a n nd i s t r i b u t i o n ；g r e e d y a l g o r i t h m ；g l o b a lo p t i m u m v i 上海大学硕士学位论文 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作。 除了文中特另i ；d h 以标注和致谢的地方外，论文中不包含其他人己发 表或撰写过的研究成果。参与同一工作的其他同志对本研究所做的 任何贡献均己在论文中作了明确的说明并表示了谢意。 签名：盆阻日期： 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即： 学校有权保留论文及送交论文复印件，允许论文被查阅和借阅；学 校可以公布论文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) 签名：金些蛰 翩躲扯 上海大学硕士学位论文 第一章绪论 1 1 课题研究的目的和意义 交通运输业的发展水平是国家兴旺发达的重要标志之一。交通运输业的高 速发展，一方面促进了物资交流和人们的往来，大大地缩短了出行时间，提高 了工作效率；另一方面也带来了许多弊病，特别是地面汽车交通运输，不论是 在发达国家还是在发展中国家，都存在着不同程度问题。近半个世纪以来，交 通拥挤、道路阻塞和交通事故的频繁发生正越来越严重地困扰着世界各国的大 城市。为了提高运输网络使用效率，解决交通拥挤和交通安全问题，从六十年 代以来，许多发达国家都进行了城市交通规划研究和交通控制研究【l 】。智能运 输系统就是其成果之一。智能运输系统的研究在发达国家起步较早，并取得了 一些比较有影响的成果 2 1 1 3 1 1 4 5 】。特别是美国、德国和日本已经开发出了各 具特点的智能运输系统的雏形。虽然与大面积应用尚有一定的差距，但初步试 验表明，该系统在加强交通控制与管理功能方面的作用是不可低估的【6 】。 我国是一个经济持续发展的发展中国家，改革开放以来，城市化与汽车化 发展十分迅猛。改革开放前，城市化水平不足1 9 ，目前已经发展到超过3 0 ， 预测2 0 1 0 年将接近5 0 ；机动车拥有量目前已达6 0 0 0 万辆，并以每年1 0 以 上的速度增长，预计2 0 1 0 年达到1 3 亿多辆。我国城市的大气质量恶化，已逐 步由无烟煤污染转变为机动车尾气污染，其主要原因是交通拥堵、车速下降以 及车况差、车辆技术性能低等，致使在世界十大空气污染最严重的城市中，我 国就占了7 个。同时，车辆状况差也直接影响到城市交通，并己成为制约我国 城市交通的重要因素。以车况较好的北京市为例，平均日故障次数达5 0 0 次以 上，给城市交通带来巨大压力 7 】。在此背景下，如何充分发挥交通设施的效能， 解决交通拥挤的问题已成为摆在我们面前的重要课题。从交通运输的未来发展 趋势看，为我国的大中城市建立智能交通系统是必要的。 上海大学硕士学位论文 1 2 智能运输系统简介 1 2 1 智能运输系统 智能运输系统 8 】( 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 ) i t s 的实施技术研究，主要把电子控制技术、通信技术、计算机处理技 术、g p s 定位导航技术等有效地运用到i t s 的各项研究中。目前，在实施技术 方面的研究进展较大，已经取得了较为理想的成果。 ( 2 ) i t s 的基础理论研究，也是交通流诱导系统理论研究。i t s 基础理论通 常称“实时动态交通分配( r e a lt i m ed y n a m i ct r a f f i ca s s i g n m e n t ) 。该理论模型 是美国i t s 研究的“出行和运输管理系统 、“出行需求管理系统”、“公共交通 运输管理系统”、“商业车辆的运营系统”、“应急情况的管理系统 、“先进的交 通控制和安全系统和欧洲的“d r i v e 、“p r o m e t h e u s ”以及日本的“r a c s ”、 “a m t i c s 、“v i c s 、“s s v s 等领域研究的核心内容。 1 2 2 交通流诱导系统 交通流诱导系统 1 】( t f g s ) ，也有人称之为交通路线引导系统( t r g s ， t r a 伍cr o m eg u i d a n c es y s t e m ) 或车辆导航系统( v n s ，v e h i c l en a v i g a t i o n s y s t e m ) 。它利用全球定位系统( g p s ，g l o b a lp o s i t i o n i n gs y s t e m ) 、电子交通图 ( e l e c t r o n i cm a po f t r a f f i cn e t w o r k ) 、计算机和先进的通信技术，使得车载计算 机能够自动显示车辆位置、交通网络图和道路交通状况，为驾驶员找到从当前 位置到目的地的最优行驶路线，并协助出行者方便地进入原先没有去过的地方。 2 上海大学硕士学位论文 使用这种系统，能够有效地防止交通阻塞的发生，减少车辆在道路上的逗留时 间，并最终实现交通流量在网络中各路段上的最优分配。根据诱导信息作用的 范围，t f g s 可以分为车内诱导系统和车外诱导系统两大类。在车内诱导系统 中，实时交通信息传输于个别车辆和信息中心之间，车辆上安装有定位装置、 信息接收装置和路径优化装置。由于诱导对象是单个车辆，因而也称为个别车 辆诱导系统。这类系统的诱导机理比较明确，容易达到诱导目的。目前各发达 国家研究的大部分是这种系统。但其对车内设施和信息传输技术要求较高，造 价相对昂贵。相比之下，车外诱导系统的交通信息是在车流检测器、信息中心 和可变标牌之间传输，诱导对象是车流群，因而也称为群体车辆诱导系统。这 种系统般适用于高速公路或路段较长的城市交通流的诱导。 发达国家的t f g s 一般由三部分构成：车辆定位模块、通信模块和驾驶员 决策支持模块。车辆定位模块的功能是跟踪车辆在路网中的位置。其输出既包 括车辆当前的绝对位置( 经度、纬度和高度) ，也包括车辆在电子地图上的相对 位置。定位过程主要依靠航位测定、地图匹配和全球定位系统( g p s ) 完成。 通信模块负责完成车辆和交通信息中心的数据交换。车辆利用接收器可以获得 从交通信息中心发射来的实时交通信息( 当前路段的行程时间、堵塞或事故发 生地点等) 。同时，车辆作为流动的交通信息探测设备，把当前的交通信息通过 发射装置反馈给交通信息中心。目前广泛使用的通信方式有射频通信( 无线电 广播通信) 、红外通信、微波通信和蜂窝移动电话通信等。驾驶员决策支持模块 的功能是进行最优路径的计算和路径引导信息及其他信息的显示。最佳路径的 计算是t f g s 的关键部分。在进行计算之前，首先由用户输入目的地，然后该 模块根据定位模块提供的定位信息和通信模块提供的当前交通状态信息计算出 从当前位置到达目的地的最优路径。所得到的最优路径随驾驶员的需求不同而 不同，可以是路程最短的路径，也可以是运行时最短的路径。路径优化采用较 多的是图论中的最短路算法和人工智能中的启发式搜索算法。最优路径的显示 可以有三种方式：文本方式、声音方式和图形方式。其中文本方式用文字在显 示器上显示诱导信息，如“在前面路口向右拐”等；声音方式通过文语转换和 语音合成单元将文本信息以声音的形式输出，这是一种最直接、最有效的方式； 3 上海大学硕士学位论文 图形方式是在电子地图上用特殊颜色的连线表示出最优路径信息，这是一种常 见的比较直观的屏幕输出形式。 交通诱导系统自诞生以来，就受到了人们的普遍关注。许多发达国家如美 国、德国、日本等均将其列入国家研究计划，投入了大量的人力、物力和财力 对其进行研究、试验和开发。目前，研究开发比较成功的有美国的t r a v t e k 系 统、德国的趾i s c o u t 系统和日本的导航系统等。 1 3 国内外研究现状 1 3 1 国外研究概况 在国外，智能交通系统的发展以美日欧为代表，通过传播实时信息和主动 管理使道路交通更加顺畅、舒适；通过智能汽车和自动驾驶技术的开发，使得 安全性得以飞速提高；通过对商业用车提供信息和引进电子通关功能，使运输 效率得以大幅度提高；通过消除道路堵塞，大大减轻了交通对环境的负荷。总 结文献 9 1 0 1 1 】，各国研究发展概况如下。 美国对智能运输系统的研究始于1 9 6 7 年，当时称其为“智能车一高速公路 系统( i n t e l l i g e n tv e h i c l e h i g h w a ys y s t e m s ，简称i v h s ) 。其发展特点是国家统一 规划、投资充足、发展迅速。1 9 9 4 年美国根据i v h s 的实际研究项目，认为i v h s 的名称已不能覆盖其全部内容，因而把i v h s 改为i t s ，并于同年9 月，经国会 批准成立了美国智能交通协会( r r s a ) 。i t s a 的成员包括联邦政府、州政府、 地方政府和外国政府机构，与智能运输系统开发有关的国家和国际公司，大学、 独立研究机构、对智能运输系统感兴趣的公共团体及其他从事智能运输系统活 动的团体。它的主要活动为：帮助政府制定政策；组织技术论坛；帮助发展标 准、处理横向问题：促进国际合作；管理和交换智能运输系统信息；展示智能 运输系统新技术；支持地方和州范围的智能运输系统计划；提高公众对智能运 输系统的认识。 美国实施的智能运输系统取得显著经济效益和社会效益。如在密西根州， a t m 使高峰小时车速提高3 5 ；a t m s 使行驶时间缩短1 9 ；a v c s 使公共汽 车交通事故率降低2 0 ；自动车辆定位节约4 0 万美元年；电子收费和交通管 4 上海大学硕士学位论文 理使收费车道上事故降低为0 ；运营费用降低1 6 万美元年。根据i t s a 2 0 0 2 年 初公布的预测，到2 0 1 1 年左右，美国智能运输系统将达到如下一些社会效益： 降低交通事故，每年减少死亡5 0 0 0 7 0 0 0 人；缓解交通拥堵，因此每年节省2 0 0 亿美元支出、1 0 亿加仑的汽油消耗和1 3 的出行时间；提供充分的实时交通信 息，以利于出行者做出恰当的出行选择等。 在欧洲，德、英、法等国于2 0 世纪8 0 年代初期先后各自研究路径诱导系 统。但各国的诱导系统互不相容的问题对过境车辆和道路交通管理带来了不便。 欧洲的智能运输系统推进组织是成立于1 9 9 1 年的欧洲道路运输通信技术实用 化促进组织e r t i c o ，它的目的是协调和支持全欧洲的i t s 活动。在该组织的 积极参与下，欧盟自1 9 8 8 年以来在智能运输系统领域相继实施了五个骨干计 划，具体计划中包括许多项目，其中主要的项目分成两条战线。一是由欧盟组 织的为完善道路设施、提高运输服务水平的d r i v e 计划和t - t a p 计划，二是 由民间企业为主导的为提高欧洲汽车竞争力的p r o m e h e u s 计划和改善欧洲 运输机动性的p r o m o t e 计划。这些计划的共同特点是它们都是跨国合作的大 项目，其中的子项目有全欧联合的、局部地区联合的和单个国家或城市的，大 多数子项目由下自上通过公开征集确定。从欧盟2 0 世纪9 0 年代中期以来先后 实施的两个i t s 骨干计划来看，均是包括道路交通运输、航空运输、铁路和水 路运输及多式联合运输的综合性研究开发计划，表现出比日、美更重视综合运 输的i t s 项目。由此可见，强调国际( 主要是洲际) 合作和标准化、强调综合 运输系统智能化是欧洲i t s 发展的主要特点。 日本的i t s 发展几乎与欧洲同时起步。1 9 7 3 年，日本进行其第一个i t s 项 目c a c s ，这是世界上第一个动态路径诱导系统。2 0 世纪8 0 年代中期开始，由 运输省等政府部门组织上百家企业，会同大学和研究机构进行大规模联合开发， 形成了官、民、学协调体制，极大地推动了智能运输系统的发展。2 0 世纪9 0 年代中期，日本相继完成了路车间通信系统、交通信息通信系统、广域旅行信 息系统、超智能车辆系统、安全车辆系统以及新交通管理系统等方面的研究。 在此基础上，1 9 9 4 年1 月，由日本警视厅、通产省、运输省、邮政省和建设省 等五个部门联合成立了日本道路、交通、车辆领域智能化促进协会，其使命是 5 上海大学硕士学位论文 推进i t s 的研究、开发和利用。在新阶段，四省一厅于1 9 9 5 年8 月公布了“公 路、交通、车辆领域的信息化实施方针”，提出了i t s 研究的九大领域；四省一 厅于1 9 9 6 年7 月提出“推进i t s 总体构想”，开始了面向i t s 采取综合的、有 体系发展的对策，并投入巨资进行i t s 的研究、开发与利用，形成以众多政府 部门参与，重视技术、产品开发和场地试验为特点的全面推进日本i t s 建设的 发展态势。 1 3 2 国内研究概况 据文献 1 1 6 】显示，我国从2 0 世纪8 0 年代初就开始从治理城市交通管理 入手，运用高科技来发展交通运输系统。8 0 年代中期，在广泛开展城市调查、 规划、治理的同时，着手对城市交通控制技术进行研究。9 0 年代初，一些高校 和交通研究机构开始了城市交通诱导系统技术的研究和尝试，并在北京、上海、 南京等城市做了试点。同时，北京、上海、沈阳等城市先后从英国、澳大利亚 等国引进了s c o ot 或s c a t s 控制系统。这些研究和实践，开拓了我国交通 研究新领域，也在一定程度上缓和了当地的交通紧张矛盾。9 0 年代中期至上世 纪末，中国许多地方陆续开始智能交通系统的研究，内容涉及先进的交通控制 和管理、信息系统、通信系统、电子收费、环保和规划、运输管理等领域。目 前，我国的智能运输系统还处于发展的初级阶段，需要借鉴国外的先进经验， 同时更要从我国的国情、路情出发尽早解决交通拥挤堵塞问题。 1 4i t s 对城市交通系统的影响 智能运输系统的应用会给城市交通系统带来各种各样的影响，其中包括对 系统效率有益的影响，当然也免不了伴随着一些无益的负面效应。许多研究者 【1 2 都针对智能运输系统对城市交通系统的影响进行了研究。在本节中，我们 总结文献来讨论这些智能运输系统给城市交通系统带来的正面促进和负面影 响。 6 上海大学硕士学位论文 1 4 1i t s 的正效应 有许多文献表b 韭 1 2 1 1 3 1 智能运输系统会给城市交通系统带来好的影响，对 城市交通系统的效率起到促进的作用。这些正面效应可归纳如下。 1 为交通出行者提供便利： 各国提出i t s 计划受到广泛拥护的主要原因就在于i t s 为出行者提供先进 服务的诱惑。受到i t s 服务的出行者可以减少出行时耗，缩短不必要的行驶里 程，从而省时、省油，并提高行车安全。具体来说，智能运输系统为驾驶员( 包 括小汽车出行、商务用车出行、货运车辆出行) 提供的服务包括： 出行前各类信息服务：出行前查询路径拥堵情况和诱导路径。 在途驾驶服务信息系统 先进的车辆控制系统 车辆导行系统 其为公共交通出行者提供公交车辆的运行状况信息，减少其等车时间和出 行中由于不知公交车辆运行信息所面临的不确定性( u n c 脚a i n t y ) 。 2 为交通管理者提供有力的支持： 交通管理者需要在充分了解现有道路交通运行状况的基础上，做出相应的 管理决策。i t s 的实时信息采集与处理能力使管理者能够全面地了解交通运行 状况，能裕如地处理各种道路交通异常情况。其发布信息能力又使管理者及时 将决策传达给交通行为者，从而实现高效、安全的目标。而且i t s 强大的信息 发布能力能够使得交通管理者根据管理目的，在一定范围内实现对交通需求的 积极、主动引导，有助于改变其被动地适应交通需求的局面。具体来说，交通 管理者的得益体现在： 。 应急救援 缓解拥挤 为决策和检验决策效果提供依据 改善公交服务和经营 对交通设施的智能化管理：提高交通设施的运行效率，有效地维修设 7 上海大学硕士学位论文 施。如智能交通设施( i t i ：i n t e l l i g e n tt r a n s p o r t a t i o ni n f r a s t r u c t u r e ) ； 为企业的物流运输提供更经济有效、安全的服务。 当然，对于智能运输系统能否减缓拥挤也存在一些有争议的观点。如 k a n n i n e n 认为 5 】，人们在拥挤时段的出行决策显然是基于以往交通信息的优化 后作出的，那么现有的交通拥挤也是由于这种已经优化了的出行决策经过长时 间均衡后而出现的。因此，路网交通信息的发布不会改变已有的交通拥挤状况。 但一些小型路网的模拟研究表明，智能运输系统会改善拥挤状况。 3 社会的得益： 充分利用道路资源，使路网负荷均匀化，能够避免出行者因交通信息 不全而致的路网负荷不均匀情形。但对于因路网结构不合理所致的负 荷不均匀问题无明显效果。 如果不考虑智能运输系统本身建设的成本，具有同样结构的交通系统 将以一种更低成本( 用户费用、环境成本) 的方式满足同样的出行需求， 较原有交通系统交通量减少、车速提高、污染减轻。同时智能运输系 统通过提供各种有选择的信息服务，能够使得出行者的路径选择向网 络均衡的系统最优方向接近。 使得交通流运行平稳，提高交通安全，减少交通事故。 智能运输系统的运行需要大量的电子信息产品，智能运输系统的技术 发展与市场需求会推动与其相关的产业发展，增加就业岗位，促进经 济发展。 1 4 2i t s 的负效应 在i t s 的应用得到一片掌声的同时，也有研究者提出了反面的意见。b e n - a l d v a 等 1 4 】认为i t s 会对车辆的出行行为带来不良影响，这些不良影响可能会 使交通系统产生以下三种不良现象： ( 1 ) 信息过剩现象( o v e rs a t u r a t i o n ) ： 信息过剩现象是指出行者由于面对大量的可用信息，不知所措，不能正确 处理路径选择所需的信息。该现象是一个人机交互作用问题。 8 上海大学硕士学位论文 ( 2 ) 过激反应现象( o v e rr e a c t i o n ) ： 过激反应现象即大量的出行者接受信息诱导，并遵循诱导建议时，可能会 使一条路段的拥挤转移至另一条路段，甚至使道路的使用产生一种振荡现象。 只有出行者进行出行决策时，正确预计了其他出行者对诱导信息做出的反应之 后，过激反应现象才会消失，而这在现实中是十分困难的。 ( 3 ) 集聚现象( c o n c e n t r a t i o n ) ： 大量的出行者根据真实的路网交通信息选择其最优出行路径时，其中具有 相似偏好的人在相同的出行时刻会集聚到同一路径上。由此，越多的交通信息 会导致更加严重的交通拥挤。这说明仅仅向出行者提供出行信息并不一定就能 解决交通拥挤问题，还必须研究出行者在知晓信息时的出行行为。在此基础上， 依靠向出行者发布不同的、分层次的信息可能会减轻负作用。 另外，a m o t t 等甚至在他们的研究中表明 1 5 】，道路交通信息提供的对象越 少，个体服务对象从中得益也越大。而当交通信息服务的对象很多时，个体服务 对象的得益也越少。 1 5 本文研究的主要内容 传统智能运输系统中的车辆诱导系统往往只考虑为某一单一出行者选择最 佳出行路径，这也是造成交通系统陷入过激反应现象和集聚现象等负面效应的原 因之一。事实上，在越来越多的出行者开始利用智能交通系统所提供的交通信息 选择出行路径的情况下，单单只考虑个体最优是不够的，提供全局最优的车辆诱 导方案才是提高整个交通系统的运行效率，避免交通拥挤，并使个人出行者也同 时获利的最佳方案。因此，本文的第三章中提出了一种新型的启发式算法 - - b o l t z m a n n 全局最优寻路算法，该算法利用基于q 值的动态规划算法【1 6 】，结 合b o l t z m a n n 分布 2 3 】，为交通系统寻找近似全局最优的配流方案。该算法分别在 静态流量的交通系统和动态交通分配模型中与g r e e d y 篑：法进行了比较。实验结果 显示，应用b o l t z r n a n n 全局最优寻路算法能够有效地减轻导航系统对车辆行为造 成的负面影响，为交通系统带来更高的整体效率。 1 6 论文结构安排 本文分为以下几个部分： 9 上海大学硕士学位论文 第一章：介绍了课题研究的意义，关于智能交通系统的一些知识背景，国 内外的发展状况以及本文的研究内容。 第二章：首先解释了动态规划的基本原理，介绍了基于q 值的动态规划 算法的具体流程，然后通过与其他传统最优路径寻路算法的对比，说明了为什 么在本文提出的全局最优寻路算法中要采用基于q 值的动态规划算法计算各个 路段到终点的最优路径。 第三章：在本章中重点描述了本文提出的b o l t z m a n n 全局最优寻路算法的 基本结构和各部分的具体内容。 第四章：展示了b o l t z m a n n 全局最优寻路算法在静态交通系统中的模拟结 果。 第五章：介绍了动态交通分配的背景知识，描述了本文的动态交通系统采 用的动态交通分配模型。 第六章：展示了b o l t z m a n n 全局最优寻路算法在动态交通系统中的模拟结 果。 第七章：论文的总结以及对未来研究工作的展望。 1 0 上海大学硕士学位论文 第二章基于q 值的动态规划最优路径算法 2 1 动态规划简介 基于q 值的动态规划最优路径算法 1 6 ，是利用动态规划的思想，计算最 优路径的算法。那么什么是动态规划呢? 在本节中，我们首先对动态规划作一 个简单的介绍。 2 1 1 动态规划的来源 在数学上和计算科学领域，动态规划是一种将问题实例分解为更小的、相 似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题 的算法策略。 动态规划这一词起源于1 9 4 0 年r i c h a r db e l l m a n 对解决多阶段决策过程的 优化问题的表述。1 9 5 3 年，他又将其赋予了模型意义【1 7 】，被i e e e 归类于系统 分析和工程的课题。1 9 5 7 年r i c h a r db e l l m a n 出版了他的名著d y n a m i c p r o g r a m m i n g ) ) ，这是该领域的第一本著作。为了纪念b e l l m a n 的贡献，用来解 决动态规划问题的核心思想的公式被命名为b e l l m a n 公式。 动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面 得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、 装载等问题，用动态规划方法比用其它方法求解更为方便。虽然动态规划主要 用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态 规划( 如线性规划、非线性规划) ，只要人为地引进时间因素，把它视为多阶段 决策过程，也可以用动态规划方法方便地求解。 2 1 2 动态规划的基本思想 动态规划的实质是分治思想和解决冗余，适用动态规划的问题必须满足最 优化原理和无后效性。 上海大学硕上学位论文 ( 1 ) 最优化原理( 最优子结构性质) 最优化原理可这样阐述：一个最优化策略具有这样的性质，不论过去状态 和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策 略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原 理又称其具有最优子结构性质。 最优化原理是动态规划的基础，任何问题，如果失去了最优化原理的支持， 就不可能用动态规划方法计算。根据最优化原理导出的动态规划基本方程是解 决一切动态规划问题的基本工具。 ( 2 ) 无后向性 将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前 各阶段的状态无法直接影响它未来的决策，而只能通过对当前的这个状态的影 响来间接影响未来的决策。换句话说，每个状态都是过去历史的一个完整总结。 这就是无后向性，又称为无后效性。 ( 3 ) 子问题的重叠性 动态规划算法的关键在于解决冗余，这是动态规划算法的根本目的。动态 规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生 过程中的各种状态，所以它的空间复杂度要大于其它的算法。选择动态规划算 法是因为动态规划算法在空间上可以承受，而搜索算法在时间上却无法承受， 所以我们舍空间而取时间。 所以，能够用动态规划解决的问题还有一个显著特征：子问题的重叠性。 这个性质并不是动态规划适用的必要条件，但是如果该性质无法满足，动态规 划算法同其他算法相比就不具备优势。 举个例子，在f i b o n a c c i 数列中，有f 3 = f 1 + f 2 和f 4 = f 2 + f 3 ，这就使 得f 4 和f 3 的计算都要f 2 ，而f 4 和f 3 又是计算f 5 的必要条件。简单的解决 办法是用f 2 计算两次或者两次以上来得到f 5 ，但是这样做非常浪费时间。为 了避免这样的冗余，我们可以先把f 4 和f 3 计算完毕后，保存起来，用来计算 f 5 。也就是说，我们每次都把已经解决的问题保存起来，然后在解决后续问题 时，采用已经得到的结果。如果我们确定某一子结果在将来不再会用到，我们 1 2 上海大学硕士学位论文 就可以将其抛弃掉了。 一个标准的动态规划算法，通常可按以下几个步骤进行： 1 ) 划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。注意 这若干个阶段一定要是有序的或者是可排序的( 即无后向性) ，否则问题就无法 用动态规划求解。 2 ) 选择状态：将问题发展到各个阶段时将所处于的各种客观情况用不同的 状态表示出来。当然，状态的选择要满足无后效性。 3 ) 确定决策并写出状态转移方程：之所以把这两步放在一起，是因为决策 和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出 本阶段的状态。所以，如果我们确定了决策，状态转移方程也就写出来了。但 事实上，我们常常是反过来做，根据相邻两段的各状态之间的关系来确定决 策。 4 ) 写出规划方程( 包括边界条件) ：动态规划的基本方程是规划方程的通 用形式化表达式。 一般说来，只要阶段、状态、决策和状态转移确定了，4 ) 这一步还是比较 简单的。动态规划的主要难点在于理论上的设计，一旦设计完成，实现部分就 会非常简单。根据动态规划的基本方程可以直接递归计算最优值。 2 2 传统最短路径寻路算法分析 不论是传统智能交通系统中的交通诱导系统，还是本文提出的寻找全局最 优路径方案的新方法，都要先利用智能系统提供的交通信息为每个出行者寻找 一条通往目的地花费最小的路径。单纯寻找一条这样的路径并不难，有许多著 名的算法比如d i j k s t r a 算法 1 8 】，a 幸算法【1 9 】 2 0 】等都可以解决这一问题。 2 2 1 d i j k s t r a 算法 d i j k s t r a 算法是1 9 5 9 年由荷兰计算机科学家艾兹格迪科斯彻发现的。该 算法解决的是有向图中最短路径问题。 给出一个指定起点的有向图，该算法可以找到从该点起，到图中任意一点 的最短路径，当然，如果目的地明确，该算法也可以为单一的起点终点寻找最 1 3 上海大学硕士学位论文 短路径。举例来说，如果图中的顶点表示城市，而边上的权重表示著城市间开 车行经的距离。d i j k s t r a 算法可以用来找到两个城市之间的最短路径。 d i j k s t r a 算法在其计算的每一步都为每对起点和终点寻找最优路径。其基本 原理是：每次新扩展一个距离最短的点，更新与其相邻的点的距离。当所有边 的权都为正时，由于不会存在一个距离更短的没扩展过的点，所以这个点的距 离永远不会再被改变，因而保证了算法的正确性。 该算法在其每一步都进行全局搜索，当网络中的节点数为乃边的数量为层 时，其时间复杂度可以写成旧和i 明的大0 函数。 d i j k s t r a 算法最简单的应用，是将其所有节点的权值都存贮在有序的链中， 这样对最优值得搜索为线性的，其时间复杂度为o ( 1 v 1 2 + l e l ) = o ( 1 v 1 2 ) 。 在稀疏图中，边的数量小- 于l v l 2 ，d i j k s t r a 算法可以通过将图存在领接表 中，另外用二叉堆，对堆或者f i b o n a c c i 堆等排序法寻找最小权值节点，来提 高算法的效率。当应用二叉堆时，该算法需要的时间复杂度为 o ( ( 1 v l + l e i ) , o g l v i ) ；如应用f i b o n a c e i 堆，则时间复杂度为o ( i e i + i v i l o g i v i ) = d ( 吲) = o ( i v l 2 ) 。d i j k s t r a 算法能得出最短路径的最优解，但由于它遍历计算 的节点很多，所以效率低。 2 2 2a 算法 在计算科学中，a 幸算法是用来寻找从单一起点到单一终点的最短路径搜索 算法。该算法与d i j k s t r a 算法很类似，但在计算边的权值时其引入了一个启发 式函数。在该算法中，从起点经过某一节点刀到终点的最小权值为 f ( n ) = g ( ，z ) + j l l ( 咒) ；其中，g ( n ) 是从起点到节点n 的最小权，h ( n ) 为从万到终 点的评估权。由于h ( n ) 是一个启发式函数，它的估计值不能超过从r l 到终点的 真实距离，以保证算法的正确性。所以在将该算法应用在如寻找交通最短路径 等问题时，一般会让其等于两点之间的直线距离，因为从物理上来说，该距离 是两点间的最短距离，它总是小于或等于两点间的实际行驶距离。 1 4 上海大学硕士学位论文 1 9 6 8 年，p a e rh a r t ，n i l sn i l s s o n 和b e r t r a mr a p h a e l 第一次在他们的论文 中描述了该