（模式识别与智能系统专业论文）基于fcd的城市交通动态诱导系统关键技术的研究.pdf

摘要 摘要 随着城市经济的发展和汽车数量的急剧增加，交通拥堵问题日益突出，缓解 道路交通压力已经成为个急需解决的重大问题。智能交通系统( i t s ) 是目前 公认的解决城市交通拥挤、改善行车安全、减少空气污染等问题的最佳途径。城 市交通动态诱导系统是智能交通系统的重要组成部分，它能够获得车辆在路网中 的位置以及实时道路交通状况，并提供最优路径诱导信息。该系统通过引导出行 者的出行行为来改善路网交通状况，减少交通拥堵，最终实现交通流在路网中的 合理分配。本文提出了一种基于f c d 和k d 5 0 的交通动态诱导系统框架，并重点 研究了交通动态诱导中的关键技术。论文的主要工作包括： 1 、以浮动车采集技术为实时交通数据采集手段，以k d 5 0 高性能并行机为计算 平台，提出了一种基于f c d 和k d 5 0 的城市交通动态诱导框架，并对应用在该 框架下的关键技术进行了描述。 2 、深入研究了f c d 在k d 5 0 平台下的并行处理流程。针对k d 5 0 的机群架构，设 计了f c d 任务分解和综合算法，实现了f c d 的多任务块分解、计算节点动态 调度和f c d 信息综合。 3 、详细分析了f c d 地图匹配中的关键步骤，如f c d 的预处理、候选路段集合的 生成、局部路径选择策略等；并在此基础上，设计了一种大规模路网下长间 隔的地图匹配算法。 4 、总结了动态路径搜索算法的三个重要条件和两种搜索策略；针对短行程情 况，设计了一种基于短时预测信息的动态路径诱导算法，在搜索过程中根据 短时预测数据动态调整全局最优路径。 5 、在对交通流动态诱导的关键技术研究的基础之上，设计并实现了基于f c d 的 北京市交通动态诱导系统；并对该系统的处理时间、路网覆盖率和路段平均 样本数进行了分析。 关键词：动态诱导，浮动车数据，并行处理，地图匹配，动态路径搜索 a b s t r a c l a b s t r a c t w i t ht h eu r b a ne c o n o m i cd e v e l o p m e n ta n dc a r si n c r e a s i n g ，t r a f f i cc o n g e s t i o nh a s b e c o m em o r e a n dm o r es e r i o u s h o wt oa l l e v i a t et r a f f i cc o n g e s t i o nh a sb e e na nu r g e n t p r o b l e m 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 st h eb e s ts o l u t i o nf o rr e l i e v i n g t r a f f i cj a m ，i m p r o v i n gt r a v e ls a f e t ya n dr e d u c i n ga i rp o l l u t i o n u r b a nd y n a m i ct r a f f i c g u i d a n c es y s t e m s ( u d t g s ) i sa l li m p o r t a n tp a r to fi t s u d t g sc a l lp r o v i d ea l l o p t i m a lp a t ha c c o r d i n gt ot h ep o s i t i o no fc a ra n dr o a dt r a f f i cc o n d i t i o n si nr e a l - t i m e ， a n dd i s t r i b u t et h et r a f f i cf l o wr e a s o n a b l yi nt h i sd i s s e r t a t i o n ，af r a m e w o r ko fu d t g s b a s e do nf c da n dk d 5 0i sp r o p o s e d ，a n ds o m ek e yt e c h n i q u e so fd y n a m i ct r a f f i c g u i d a n c ea r ed i s c u s s e d t h em a j o rc o n t r i b u t i o n sa n di n n o v a t i o n so ft h ed i s s e r t a t i o n a r ea sf o l l o w s ： 1 b a s e do nf l o a t i n gc a r ( f c ) c o l l e c t i o nt e c h n o l o g ya n dh i g h p e r f o r m a n c e c o m p u t e rk d 5 0 ，af r a m e w o r k o fu d t g si sp r o p o s e d ；a n dt h ek e yt e c h n i q u e so ft h i s f r a m e w o r ka r ed e s c r i b e d 2 t h ep a r a l l e lp r o c e s s i n gf l o wo ff c do nk d 5 0i ss t u d i e d t h ea l g o r i t h mo f f c d st a s kd e c o m p o s i t i o na n di n t e g r a t i n g i s d e v e l o p e d t h e m u l t i - t a s k d e c o m p o s i t i o n o ff c d ，d y n a m i cd i s p a t c ho ft h ec o m p u t i n gn o d e sa n df c d i n f o r m a t i o ns y n t h e s i sa r ei m p l e m e n t e d 3 s o m ei m p o r t a n tp r o c e s so ff c d sm a pm a t c h i n g ，s u c ha st h ep r e p r o c e s s i n g o ff c d ，t h eg e n e r a t i o no ft h ec a n d i d a t er o a d s ，l o c a lr o u t ec h o i c e ，a n dc a l c u l a t i o n m e t h o do fr o a da v e r a g es p e e da r ed i s c u s s e di nd e t a i l b yu s i n gt h e s ek e yp r o c e s s e s ，a m a pm a t c h i n ga l g o r i t h mo ff c d w i t hl o n gt i m ei n t e r v a l so nal a r g e 。s c a l en e t w o r ki s d e v e l o p e d 4 t h r e ep r e c o n d i t i o n sf o rd y n a m i cr o u t es e a r c ha l g o r i t h ma r es u m m a r i z e d i n t h ec a s eo fs h o r tt r a v e lt i m e ，ad y n a m i cr o u t es e a r c ha l g o r i t h mb a s e do nt h e s h o r t - t e r mt r a f f i cp r e d i c t i o n ( p d s p t ) i sd e s i g n e di no r d e rt oa d a p td y n a m i ct r a f f i c r o a dn e t w o r k 5 b a s e do nt h es t u d yo ft h ek e yt e c h n i q u e so fu d t g s ，b e i j i n gt r a f f i cd y n a m i c g u i d a n c es y s t e mi sd e s i g n e da n di m p l e m e n t e d t h es y s t e mp e r f o r m a n c e si n c l u d i n g p r o c e s s i n gt i m e ，c o v e r a g er a t eo fu p d a t e dr o a da n da v e r a g es a m p l en u m b e r sa r e a n a l y z e d n a b s t r a ( j r k e yw o r d s ：d y n a m i cg u i d a n c e ，f l o a t i n gc a rd a t a ( f c d ) ，p a r a l l e lp r o c e s s i n g ，m a p m a t c h i n g ，d y n a m i cr o u t es e a r c h m 中国科学技术大学学位论文原创性声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的 成果。除已特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或 撰写过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作 了明确的说明。 作者签名：谜 签字日期： 生! z ：吵 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学 拥有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构 送交论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入有 关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论 文。本人提交的电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 酪开口保密( 年) 作者签名：虚墨 签字日期：垒里哆：尘兰2 导师签名： 签字日期： 第1 章绪论 第1 章绪论 1 1相关背景 近年来，随着我国城市化和经济的快速发展，交通需求迅速增长所导致的交 通拥堵和交通事故等现象日益严重，已经成为制约城市建设与发展的重要因素。 目前，城市交通面临的问题主要表现在以下几个方面。 ( 1 ) 交通拥堵 2 0 世纪9 0 年代以后，中国的机动车数量大幅增加，而城市道路的增长速度 比机动车数量的增长速度要慢得多。以北京市为例，2 0 0 7 年北京的机动车保有 量已经超过2 2 9 万台，较之1 9 9 9 年的4 5 万台增加了5 倍以上；而城市道路的总 公里数比起9 0 年代初期只增长了2 0 ( 许彦等，2 0 0 7 ) 。城市交通严重的供需 不平衡，致使交通拥堵的现象日渐频繁，社会经济损失严重。 ( 2 ) 交通事故 在当今中国，交通事故发生频繁，已经成为了威胁公民生命财产安全的一个 主要原因。中国的交通事故数量每年都在递增，每1 万辆机动车的事故死亡率就 达到1 0 左右。根据公安部的资料，2 0 0 8 年1 月至9 月份，全国共发生道路交 通事故1 9 5 3 1 9 起，造成5 0 6 8 2 人死亡，2 2 9 4 8 4 人受伤，直接财产损失达7 7 亿 元。其中车辆的超速行驶、违法超车、疲劳驾驶和不遵守交通信号灯的指挥是导 致交通事故频发的主要原因( 公安部交管局，2 0 0 8 ) 。 ( 3 ) 交通污染 随着机动车数量的增长，交通造成的废气、噪声及振动等污染越来越严重， 特别是交通堵塞引发的机动车废气排放量增加显著。2 0 世纪8 0 年代末期，北京 三环路以内的机动车废气排放指标达3 0 ，现在已经超过6 0 ( 许彦等，2 0 0 7 ) 。 虽然近年来能源结构调整和“绿色汽车 投入使用，但是由于机动车的数量增长 速度惊人，环境污染状况难以得到改善。 ( 4 ) 出行效率 由于交通实时信息采集手段不足，同时缺乏相应的交通诱导方式，出行者很 难根据当前路况信息及时调整自己的出行路线，因而经常出现主干道发生交通拥 堵，而其他平行车道车辆稀少的现象。城市交通调配失衡，导致出行者滞留在路 面的时间变长，严重影响了出行者的出行效率，同时也容易诱发交通事故。 近年来，随着电子技术、通信技术、计算机技术等高新技术的发展，在城市 中实施智能交通系统( 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 ) 成为解决交通拥堵、 第1 章绪论 减少交通事故、防止交通污染、提高交通管理水平的最有效的途径。i t s 是将先 进的计算机处理技术、信息技术、数据通信传输技术、自动控制技术、人工智能 及电子技术等有效地综合运用于交通运输管理体系中，建立大范围、全方位发挥 作用的实时、准确、高效的交通运输管理体系。i t s 的出现为解决交通问题提供 了全新的方法，它是解决交通问题的根本途径，也是目前世界交通运输领域研究 的前沿课题。i t s 是在当代科学技术充分发展进步的背景下产生的，是目前国际 公认的解决城市交通拥挤、改善行车安全、提高路面运输效率、减少空气污染等 的最佳途径( 王兆娟，2 0 0 1 ) 。 目前发达国家实施的i t s 项目很多，其规模和功能都在不断发展壮大。其中 美国的i t s 研究开发体系最为完善，已受到国际i t s 研究领域的广泛认可。美国 相关部门将i t s 划分为七大系统( 杨兆升，2 0 0 4 ) ：先进的交通管理系统( a t m s ， a d v a n c e dt r a f f i cm a n a g e m e n ts y s t e m s ) 、先进的旅行者信息系统( a t i s ，a d v a n c e d t r a v e l e ri n f o r m a t i o ns y s t e m s ) 、先进的公共交通运输系统( a p t s ，a d v a n c e dp u b l i c t r a n s p o r t a t i o ns y s t e m s ) 、商用车辆运营系统( c v o s ，c o m m e r c i a lv e h i c l eo p e r a t i o n s y s t e m s ) 、先进的车辆控制系统( a v c s ，a d v a n c e dv e h i c l ec o n t r o ls y s t e m s ) 、自 动公路系统( a h s ，a u t o m a t e dh i g h w a ys y s t e m s ) 、先进的乡村运输系统( a r t s ， a d v a n c e dr u r a lt r a n s p o r t a t i o ns y s t e m s ) 。在i t s 的各组成部分中，a t m s 和a t i s 是核心部分，它们真正反映了一个城市的交通发展水平。 美、欧、日等发达国家在实施智能交通系统的过程中，始终把交通流动态诱 导系统的建设放在十分重要的位置( 王笑京，2 0 0 8 ) 。城市交通动态诱导系统通 过对实时交通信息的充分利用和主动诱导来达到提高路网通行能力的目的；它将 引导交通参与者由传统的凭经验和随机出行逐渐转变为在实时路网运行状态条 件下理性的自主选择，因此是道路交通实现“安全、畅通、有序”的关键技术和 基础。 1 2 交通动态诱导系统 交通流诱导系统( t f g s ，t r a f f i cf l o wg u i d a n c es y s t e m ) ，又称交通路径 诱导系统( t r g s ，t r a f f i cr o u t eg u i d a n c es y s t e m ) ，是a t i s 研究的一个子课 题，也是i t s 研究的一个重要方面。它基于电子、计算机、网络和通信等现代技 术，利用全球定位系统( g p s ，g l o b a lp o s i t i o n i n gs y s t e m ) 、电子地图、计算 机和无线通信技术，能够获得车辆位置和实时道路交通状况，并根据出行的起讫 点向用户提供最优路径诱导信息。该系统把人、车、路三者综合起来考虑，通过 引导用户的出行行为改善路网的交通状况，防止交通阻塞发生，减少车辆在道路 上的逗留时间，最终实现交通流在路网中各个路段上的合理分配( 杨兆升等， 2 第1 章绪论 2 0 0 0 ) 。 按照交通诱导所依据的信息的性质，交通流诱导系统可以分成静态诱导系统 和动态诱导系统两种( 崔水兵，2 0 0 5 ) 。静态诱导系统所依据的信息是静态的路 网信息，如路网拓扑图或是最短路径树，还可以是一个记录着过去交通状况的历 史数据库；而动态诱导系统所依据的信息主要是实时的动态路网信息和交通环境 信息，如当前和短期预测的路段旅行时间、交通管制信息以及道路天气情况等。 静态诱导系统采用的是路网静态数据，无需实时采集交通信息，因此减少了 通信代价，实现起来简单廉价。然而城市交通是一个复杂的巨系统，路段交通状 况变化很大，且受多种因素影响。通过静态数据来进行交通诱导误差较大，往往 只能找到局部最优路径而无法得到全局最优路径。动态诱导系统则考虑到城市路 网交通流的动态特性，根据实时交通状况对车辆进行引导。从整个路网来说，它 减少了车辆在路上的逗留时间，是一种有效地疏通和分配交通流的措施；从单个 车辆来说，它可以根据起讫点诱导出行者沿一条最佳路线行驶，从而达到节约时 间和金钱，同时安全舒适的目的( 王兆娟，2 0 0 1 ) 。 一般而言，交通流动态诱导系统由以下四个部分构成( l iq i n g q u a n ，2 0 0 6 ； 王兆娟，2 0 0 1 ) 。 ( 1 ) 交通信息采集子系统 采集子系统利用各种数据采集设备，采集路网中各个路段或区域内的交通信 息，并发送给交通信息中心进行处理。 ( 2 ) 交通信息中心 信息中心是动态路径诱导系统的主控中心，主要功能是从各种信息源获得实 时的交通信息，进一步处理产生要发布的交通数据。 ( 3 ) 通信系统 负责完成车辆和交通信息中心的数据交换。目前广泛使用的通信方式有射频 通信、红外通信、微波通信和蜂窝移动电话通信等。 ( 4 ) 车载诱导单元 车载诱导设备主要由计算机、通信设备和车辆定位设备组成。定位设备为g p s 接收机或信标信号接收机及速度、方向传感器等其它定位设备。主要功能是接收、 贮存和处理交通信息，为驾驶人员提供良好的人机界面，方便驾驶人员输入信息 和获得诱导指令。 第1 章绪论 1 3 国内外研究进展 1 3 1 国外研究现状 交通动态诱导系统能有效地解决城市交通拥挤、减少交通事故、降低空气污 染、提高运输效率，因此发达国家非常重视交通动态诱导系统的开发和应用，现 已形成了日、美、欧三足鼎立的局面。 ( 1 ) 日本的动态诱导系统 动态诱导系统的研究最早始于日本( 1 9 7 3 年) ，并在1 9 9 0 年建立了世界上第一 个道路车辆信息通信系统v i c s ( v e h i c l ei n f o r m a t i o na n dc o m m u n i c a t i o n s y s t e m s ) ( n a g a o k ak o j i ，1 9 9 9 ) 。v i c s 采用3 种通信方式：红外信标、短波信标 和调频副载波广播。它将警察部门和高速公路管理部门提供的交通堵塞、驾驶所 需时间、交通事故、道路施工、车速及路线限制，以及停车场空位等信息编辑处 理后及时传输给交通参与者，特别是在汽车导航车载机上以文字、图形显示。日 本目前正在部署一种与v i c s 兼容的加强的交通管理系统u t m s ( u r b a nt r a f f i c m a n a g e m e n ts y s t e m s ) ，它由五个子系统组成，其中的动态路径诱导系统 d r g s ( d y n a m i cr o u t eg u i d a n c es y s t e m s ) 是一种交互类型的中心决定式的路径诱 导系统，它使用来自于多个信息源的实时交通信息和行程时间数据进行中心决定 式的路径诱导。d r g s 将交通信息中心收集到的检测器数据转换为路段行程时间数 据，以此决定最优路径，所以即使在没有大量探测车辆的系统运行的早期阶段也 能够实现动态诱导( 杨兆升等，2 0 0 0 ) 。 ( 2 ) 美国的动态诱导系统 9 0 年代后，美国对交通动态诱导系统的研究开始介入和展开，并先后进行了 p a t h f i n d e r ，t r a v t e k ，a d v a n c e 等以动态路径诱导系统为主要内容的现场运营实 验( o hj u n - s e o k ，2 0 0 1 ) 。t r a v t e k 系统实现的路径诱导是基于拥挤和事故等实 时交通条件进行的，并具有为出行者服务的“黄页 信息，尤其适用于对该地区不 熟悉的旅行者使用；在美国芝加哥进行的a d v a n c e 项目的研究为动态路径诱导系 统建立了系统性的研究基础，该系统是一种基于实时交通条件( 当前路段行程时 间) 的分布式路径诱导系统，车辆定位主要采用差分g p s ，在g p s 处于盲区时辅以基 于车轮速度和方向传感器的航位推算法进行定位：t r a v i n f o 项目通过使用一系列 设备，如传呼机、出行者咨询电话系统、车载导航系统和i n t e r n e t 主页向出行者 提供及时而准确的多方式信息和动态路径建议。目前美国各地广泛布置了区域性 的多方式出行者信息系统( m u l t i m o d a lt r a v e l e ri n f o r m a t i o ns y s t e m s ) ，可以提 供实时的交通信息，而且i n t e r n e t 上的交通信息资源在美国已十分丰富( 杨兆升 4 第1 章绪论 等，2 0 0 0 ) 。 ( 3 ) 欧洲的动态诱导系统 欧洲的交通动态诱导研究开始是以红外信标通信为基础而展开的，英国于2 0 世纪8 0 年代就推出了世界上第一个商用车载路径诱导系统t r a f f i cm a s t e r 。进入 9 0 年代后，德国西门子公司开发的e u r o s c o u t 系统得到一定的应用，但是缺点 是需要大量投资用于安装路边的红外信标。后来，德国的s t o r m 项目致力于开发 双模式d r g s ，即在安装红外信标的区域开发基于红外信标的路径诱导，同时在广 域内开发基于r d s o t m c ( r a d i od a t as y s t e m - t r a f f i cm e s s a g ec h a n n e l ) 交通广播 的路径诱导，它能够向用户提供交通事故、拥挤、道路施工等信息；另外隶属于 p r o m e t h e u s 计划的d m r g ( d u a lm o d er o u t eg u i d a n c e ) 将静态的自主导航和基于 r d s o t m c 广播联合起来成为动态的分布式路径诱导系统，扩展的系统用g s m 代替 r d s o t m c 系统( 杨兆升等，2 0 0 0 ) 。2 0 0 1 年，德国宇航中心交通研究所在柏林交 通管理中心建立了世界上第一个实际运行的基于f c d 的交通信息系统，并于2 0 0 3 年已经开始商业运行。 综上所述，发达国家对交通流动态诱导系统的研究起步较早，取得了比较显 著的成果。其主要特点是( 杨兆升，2 0 0 4 ) ：( 1 ) 国家机关、民间企业( 特别是 汽车、电子企业) 、学术团体紧密配合，通过协作完成项目的研究、开发和实施 过程；( 2 ) 采用车辆与交通信息中心的双向通信手段进行信息的采集、传输与利 用，数据技术高度密集的项目；( 3 ) 车载设备较多，使用成本偏高。 1 3 2 国内研究现状 国内对城市交通动态诱导系统的研究起步较晚，主要由一些科研院所、学校 及少数公司进行探索性研究实验，有些城市已经开始了示范性使用，但尚未进行 大范围的推广。其中吉林大学在交通诱导系统方面做了许多工作，尤其在交通预 测、交通分配等方面开展了大量研究，取得了一些成果( 杨兆升，2 0 0 4 ) ：北京 工业大学交通研究中心在车辆定位与导航关键技术方面开展了多项研究，重点包 括：城市交通网络及其拓扑关系的表达，g p s d r 组合定位数据融合，基于g s m 进行数据通信等( 乔建刚等，2 0 0 4 ) ；同济大学结合了2 0 1 0 上海世博会的交通 需求和交通体系特点，构建了基于上海市综合交通信息平台的世博会综合交通诱 导系统的体系框架，并给出了诱导策略( 徐天东等，2 0 0 7 ) ；国内一些主要的 研究智能交通的公司如四维公司、安徽科力等公司通过与国外合作或引进或独立 研制，在城市交通信息处理与动态诱导方面做了大量的工作，取得了一定进展， 但均未达到实现产业化的阶段。 5 第1 章绪论 1 4 交通动态诱导中的关键技术 目前，城市交通动态诱导系统已经作为实现智能交通的关键一环，引起了各 国的强烈关注和用户的普遍欢迎。构建一个城市交通动态诱导系统，所涉及的关 键技术主要有以下几个方面： ( 1 ) 实时交通信息的获取 实时而准确的交通数据是进行动态诱导的基础。目前常用的交通数据采集方 法如地感线圈、红外、射频等技术虽然能够获得道路的车辆通行信息，但是存在 覆盖范围小，投资大，数据可靠性不高等缺点。因此，寻求一种廉价且实用的获 取路网实时交通信息的技术是实现城市交通动态诱导的前提。 ( 2 ) 交通源数据的处理 通过各种仪器设备和采集技术所采集到的交通源数据，由于存在误差和精度 限制等问题，不能直接作为诱导信息进行发布，必须要进行处理和转换。由于路 网交通数据庞大，数据处理的时间较长，为了满足实时诱导的要求，必须引进新 的技术和方法来提高交通数据处理的速度和精度。 ( 3 ) 动态最优路径搜索 动态诱导系统中的一个重要功能就是根据出行者提供的起讫点寻找到一条 全局最优路径。在传统的最优路径算法中，路段的权值不会发生变化，然而在实 际交通环境中，道路的权值会因道路的实时交通状况不同而发生变化。因此必须 采用一种动态环境下的最优路径搜索算法，以保证搜到的路径全局最优。 1 5 本文的研究内容与组织结构 本文以城市道路交通动态诱导系统为研究背景，对基于f c d 的交通动态诱导 系统所采用的关键技术进行研究：包括f c d 的并行处理策略、大规模路网下长间 隔的地图匹配、以及动态最优路径搜索算法等；并在此基础上，设计并实现了一 个基于f c d 的城市交通动态诱导系统。论文组织如下： 第一章绪论。本章首先阐明了研究的背景和意义，然后介绍了交通诱导系 统以及动态诱导的特点，并分析了交通动态诱导系统的国内外现状，最后简要阐 述了本文的研究工作和内容安排。 第二章基于f c d 与k d 5 0 的交通动态诱导系统框架设计。本章介绍了交通动 态诱导系统的基本框架，并结合浮动车采集技术的优点和k d 5 0 并行机作为后台 的强大计算能力，设计了一个基于f c d 与k d 5 0 的交通动态诱导系统框架，并对 其所采用的关键技术进行了描述。 第三章f c d 的并行处理策略。本章介绍了在k d 5 0 平台下的f c d 的并行处理 流程，详细分析了f c d 的任务分解、计算节点的动态调度以及f c d 的信息综合等 6 第1 章绪论 技术。 第四章大规模长采样间隔的地图匹配。本章介绍了f c d 的地图匹配技术， 包括了数据的预处理、路段候选集的生成以及局部路径选择策略等方面，并研究 了f c d 在大规模路网下长采样间隔的地图匹配算法。 第五章动态最优路径搜索算法。本章分析了动态寻优算法在路径诱导系统 中的作用和三个重要条件，然后针对短行程的情况，提出了一种基于短时预测信 息的动态路径搜索算法p d s p t 来寻找全局最优路径。 第六章系统实现与分析。本章实现了一个基于f c d 与k d 5 0 的北京市交通动 态诱导系统，并对其功能和性能做了具体介绍与分析。 论文的最后对全文内容进行总结并指出今后的研究方向。 7 第2 章基于f c d 和k d 5 0 的交通动态诱导系统框架 第2 章基于f c d 和k d 5 0 的交通动态诱导系统框架 城市交通动态诱导系统( u d t g s ，u r b a nd y n a m i ct r a f f i cg u i d a n c es y s t e m s ) 的主要目的是对路网中的车辆进行实时诱导，为出行者提供有效的出行信息，从 而实现一定区域范围内的最合理的交通流分配以及车辆的最优行驶路线规划。 ( 王川久等，2 0 0 3 ) 。本章在交通动态诱导系统基本框架的基础之上，介绍了浮 动车采集技术和k d 5 0 高性能计算机，并提出了一个基于f c d 和k d s 0 的交通动态 诱导系统框架。 2 1交通动态诱导系统框架 交通动态诱导系统主要包含了三个子系统：交通信息采集子系统、交通信息 处理子系统和诱导信息发布子系统( 崔水兵，2 0 0 5 ) 。其基本框架如图2 1 所示： 交通视频采集l 加入 h w 嗷布 历史 数据 信息 地感线圈检测 1 + 车载p d a 交 通 诱 数 导 据 信 浮动车采集l 预 诱导 处 处理 息 一 智能手机 及预 发 理 测布 处 红外、射频检测l 理 一i t s 中心 道路管理信息 - 交通数据库 采集子系统 处理子系统发布子系统 图2 1 交通动态诱导系统框架 2 1 1 交通信息采集子系统 得到准确、实时而又有效的城市交通信息是进行交通动态诱导的基础。城市 9 第2 章基于f c d 和i ( j 3 5 0 的交通动态诱导系统框架 交通信息按其变化频率可分为静态与动态两种。其中静态交通信息是在较长时间 不会发生变化的数据，主要是交通基础设施信息，如城市道路渠化图等；动态交 通信息主要是实时发生变化的交通数据，如道路的平均速度和通行流量等。 交通信息采集子系统主要功能就是采集和检测城市路网中动态的道路交通 信息。它通过道路交通流检测设备( 地感线圈、视频检测设备、超声波检测器、 红外检测设备等) 的检测数据、浮动车数据( f c d ，f l o a t i n gc a rd a t a ) 、以及 由交通管理部门提供的交通事件、阻塞、路段施工等交通信息来获得路网的实时 交通信息( 王川久等，2 0 0 3 ) 。这些交通信息为交通诱导处理和发布提供了真实 的源数据。 2 1 2 交通信息处理子系统 交通信息处理子系统是城市交通动态诱导系统的核心部分，也是连接交通信 息采集子系统和诱导信息发布子系统的纽带。由于路网覆盖率和采集精度等限 制，导致交通信息采集子系统所采集到的源数据存在噪声和误差，不能直接作为 诱导信息发布，因此需要使用交通信息处理子系统对这些源数据进行处理。 交通处理子系统的主要功能就是接收采集子系统传上来的交通信息源数据， 对各种格式的交通数据进行转化、融合与预处理，并结合交通历史数据进行诱导 处理和预测，从而生成诱导所需的实时准确的交通信息提供给诱导发布子系统。 2 1 。3 诱导信息发布子系统 交通信息处理子系统将原始的交通采集数据转换成实时交通信息后，需要通 过诱导信息发布子系统转化成合适的诱导信息，并以多种形式进行发布。由于发 布子系统需要与人进行实时交互，因此需要有良好的用户界面( g i s 电子地图) 和适用的操作手段。根据用户对实时交通数据的获取方式不同，诱导信息发布的 技术有多种形式，如w e b 网页显示、车载p d a 显示、电子指示牌等；根据用户对 实时交通数据的应用不同，诱导信息发布的对象也有多种类型，包括出行者、交 通管理者以及一些交通规划部门和研究部门等。 2 2 浮动车采集技术 2 2 1 交通信息固定采集技术 交通信息采集系统根据交通检测器的地理位置是否发生改变可以划分成固 定采集技术和移动采集技术。交通信息固定采集技术是运用安装在固定地点的采 集设备对移动车辆进行交通参数采集的方法，也是目前常用的交通信息采集方 i 0 第2 章基于f c d 和i r d 9 5 0 的交通动态诱导系统框架 式。根据其使用的设备不同，固定采集技术可分为磁频采集、波频采集和视频采 集三种类型( 崔水兵，2 0 0 5 ；郑芳芳，2 0 0 5 ) 。 磁频采集技术：通过埋设在路面下的地感线圈，车辆经过线圈调谐回路的频 率变化来检测车辆存在和采集交通参数。对车辆起直接作用的是环形线圈回路的 总电感量，其中包括线圈自感和线圈与车辆之间的互感。通过检测当车辆通过线 圈或停在线圈上时会引起线圈回路电感量的变化，来引起线圈调谐回路的频率变 化，从而达到检测目的。 波频检测技术：波频检测技术有两种工作方式。其一是交通检测器向检测域 发射具有一定波长的能量波束( c w 或者f c m w ) ，当有车辆穿过检测区域时，该波 束经过车辆反射后被检测器接收，处理后获得所需的交通参数。这种类型的设备 主要有微波交通检测器、超声波交通检测器和主动红外线检测器等。波频检测技 术的另一种工作方式是检测器对通过检测区域的机动车辆本身发射的具有一定 波长的能量波束进行接收，经过处理后获得所需的交通参数。这种类型的设备主 要有被动红外线检测器、被动声学检测器等。波频检测两种工作方式的差别主要 在于所依据的波束来源不同，前者由传感器发射并接收波束，而后者是由车辆发 出由传感器接收波束。 视频检测技术：这是一种将视频图像和模式识别技术相结合并应用于交通领 域的新兴检测技术。它通过视频摄像机和计算机模仿人眼的功能，将连续的模拟 图像转换成离散的数字图像后，在成熟的物理模型和数字模型的基础上编制软件 进行分析处理这种技术分非主动式检测( t r i p w i r es y s t e m s ) 和主动式检测 ( t r a c k i n gs y s t e m s ) 两种工作方式。前者是基于虚拟线圈的检测方式，可以提供 交通流量、平均速度、车头时距、车型分类和车道占有率等数据；后者除了提供 上述参数以外还可以提供车辆的跟踪功能。 2 2 2 固定采集技术的不足 传统的交通信息固定采集方式具有采集精度较高、稳定性较好和数据干扰小 等特点，但是同时也存在一些不足之处( 张永强，2 0 0 5 ) 。 1 ) 覆盖范围不足 由于经济和环境等条件的制约，固定交通信息采集仪器主要放置在城市的主 干道、主要交叉口以及部分断面，采集区域非常有限，采集点的数量和分布范围 都远远不能覆盖整个城市路网。 2 ) 采集信息参数有限 固定采集方法所采集的数据主要是交通流量、道路占有率和地点车速等断面 交通信息，对于能够反映道路交通运行状况的路段平均速度和平均行程时间等信 第2 章基于f c d 和k d s 0 的交通动态诱导系统框架 息非常少。因此目前固定采集技术主要面向于基于交叉口的交通信号控制，而很 少用于基于道路的交通信息诱导。 3 ) 安装和维护麻烦 由于固定采集技术安装在路面地下或道路两旁，每次安装和维护的过程中， 都需要破坏路面或影响正常的交通流，同时需要花费大量的人力和物力。 因为传统的固定采集方法不能满足城市交通动态诱导系统中海量、全面而且 实时的交通信息的需要，所以世界各国都在转向交通移动采集技术的研究，希望 借助移动采集技术的特点能够弥补固定采集技术的缺陷。在此背景下，一种基于 g p s 和浮动车( f c ，f l o a t i n gc a r ) 的移动采集技术应运而生，成为目前各国交 通信息采集技术研究的热点。 2 2 3 浮动车采集技术 浮动车系统是伴随着i t s 新技术应用而在近几年发展起来的新型交通流采 集技术。所谓浮动车就是指安装有定位和无线通信装置的普通车辆( 如出租车、 公交车、警车等) ( 张永强，2 0 0 8 ) 。浮动车在道路上行驶时，来自路网纵剖面的 交通流数据将被收集，这样可以方便的得到可靠的车辆行驶速度、路段行程时间 等参数。交通信息中心通过与交通流中一定比例的浮动车实时交换数据，从而实 现城市道路的交通诱导。 浮动车 图2 2 浮动车系统示意图 浮动车系统主要由车载g p s 定位设备、无线通信模块和交通信息中心三个 部分组成( 见图2 2 ) 。其中，g p s 定位模块接收由g p s 卫星传输过来的卫星定 第2 章基于f c d 和k d 5 0 的交通动态诱导系统框架 位信号，并计算出车辆的经纬度坐标以及瞬时行驶方向：无线通信模块负责将车 辆经纬度坐标、车辆行驶方向和瞬时速度等数据，通过通信运营商提供的通信基 站传送到交通信息中心，并接收交通信息中心发送过来的处理好的数据和指令； 交通信息中心对浮动车上传的数据进行存储、筛选和预处理，结合地图信息并利 用相应的计算模型对道路交通参数如路段平均速度、平均行程时间等进行估计和 预测，从而得到整个路网的实时动态交通信息( 张永强，2 0 0 8 ) 。 浮动车采集技术是一种移动采集技术，它与传统的固定采集技术相比，具有 以下几个优点( 温慧敏等，2 0 0 5 ) 。 ( 1 ) 覆盖面广 浮动车在城市路网中是流动的，几乎可以采集到城市道路网络各个区域的信 息，采集范围从交叉口和主干道扩大到整个路网，实现了点、线到面的突破。 ( 2 ) 采集数据多样且准确 浮动车所采集的路段平均车速、平均行程时间对于了解道路实时运行情况、 分析交通拥堵原因、提供交通动态诱导等服务提供了关键的参数。这些参数处理 所涉及的算法比传统的固定采集方法要更简单，结果也更精确。同时浮动车可以 直接产生基于o d 的数据，解决了部分交通规划和管理的数据来源。 ( 3 ) 安装方便且投资少 各种安装有定位和无线通信装置的车辆均可以作为浮动车使用。这些车通常 是出租车、公交车、警车，以及一些安装导航设备的私家车。这些车载设备安装 方便，且易于维护。 正因为浮动车采集系统具有传统采集技术所不能比拟的一些优点，国内外纷 纷对此展开研究，并在一些城市开始商业运行。2 0 0 1 年，德国宇航中心交通研 究所在柏林交通管理中心建立了世界上第一个实际运行的f c d 系统，并在2 0 0 3 年开始在柏林运行( k w e l l aba n dl e h m a n nh ，2 0 0 0 ) 。其他如慕尼黑、斯图加特、 纽伦堡、汉堡、阿姆斯特丹以及维也纳等二十多个欧洲城市也都开始使用f c d 系统。同时，日本和美国也都拥有自己的基于f c d 的交通信息采集及处理系统。 在国内，北京、上海、广州、杭州、宁波、厦门等城市目前已经拥有了一定规模 的浮动车( z h ul i y u n a l ，2 0 0 8 ； z h a n gc u n b a o a l ，2 0 0 7 ) ，一些大专院校、科研 机构和企事业单位先后开展了浮动车交通信息采集与处理技术的国际合作或自 主研发工作。但总的来说，国内对浮动车技术还缺乏系统性研究，相关工作和应 用也很有限，尤其在浮动车数据处理的实时性和准确性方面与国外相差较大。 2 3k d 5 0 i e 高性能并行计算机 k d - 5 0 - i 并行机是中国科学技术大学和国家高性能计算中心共同研制的我 1 3 第2 章基f f c d 和k d s o 的交通动态诱导系统框架 国首台采用国产高性能通用处理器芯片“龙芯2 f ”和其他国产器件、设备和技 术的万亿次高性能计算机( 张俊霞等，2 0 0 8 ) 。k d 一5 0 一i 整机采用单一机柜，集 成了3 3 6 个主频为7 5 0 m 的龙芯2 f 处理器，理论峰值计算能力达到l0 0 8 万亿次， 并且在板上机群、高密度计算节点、轻量操作系统和通信优化等关键技术方面取 得了突破，具有低占地( 占地05 1 平方米) 、低功耗( 整机功耗小于6 k w ) 、低 成本、高计算密度和全交换互联等特点。 k d 一5 0i e ( 后面简称k d 5 0 ) 是k d5 0i 的增强型，主要面向行业应用领域。 与k d5 0i 相比，k d 5 0 改进了计算节点的设计，提高了系统主频，采用了纠错 能力更强的存储芯片和速度更快的交换芯片，因而整机的性能大幅度提升，运行 更加稳定可靠。 k d 5 0 系统结构图如图23 所示。整个系统拥有7 台主控服务器和1 2 个计算 节点，一个计算节点包含两块交换地板，共享电源和散热风扇。每块交换地板上 集成了6 个处理单元( 简称p e ) ，采用内置的两个4 端口干兆以太网交换芯片( 也 称节点交换机) 连接每个交换芯片连接3 个处理单元，对外输出一个千兆网接 口。 图2 3k d 5 0 结构图 k d 5 0 的主控服务器采用o p t e r o n 八核处理器，主频为22 g h z 内存为8 g b 磁盘容量达8 7 8 g b 。其主要功能是为整套系统提供磁盘存储、系统引导、用户登 录和任务调度等功能。机柜交换机采用华为4 8 端口千兆以太网交换器设各，连 接节点交换机和主控服务器，机柜交换机间传输速率为万兆。处理单元采用主频 为7 5 0 i h z 的龙芯2 f 处理器，同时还包含i g bd d r 2 内存、r t l 8 l i o s c 千兆以太 网芯片、串口芯片、b i o sf l a s h 、实时时钟芯片以及各种电源变换电路等。 k d 5 0 的操作系统为d e b i a ng n u ( 主控服务器) l