（地图制图学与地理信息工程专业论文）基于fcd的网络模型与动态最佳路径规划算法研究.pdf

摘要 摘要 动态路径诱导系统是智能交通系统中出行者信息子系统的一个重要组成部分，其主要功能是辅 助驾驶员选择到达目的地的路径并沿既定路线行驶，必要时可帮助驾驶员重新选择路径。在出行之 前，出行者所感兴趣的是如何找到一条从起点到终点的最佳路径( 针对不同的需求，最佳路径可以 是两点之间的距离最短路径、时间最短路径、路况最佳路径) 。但是最短路径不仅仅是简单的物理意 义上的路径最短或静态时间最短。因为道路通行能力受到多种因素综合限制，如交叉口信号灯控制 状况、天气状况、拥挤状况等。必须综合考虑影响通行能力的多种因素，才能比较真实地反映现实 的路况。为此，本论文对基于f c d ( f l o a t i n gc a rd a t a ，f c d ) 的道路网模型和动态路径规划技术进 行了全面的研究，并且提出了具体的道路网络建模方式和动态路径规划算法。 首先，论文概述了基于f c d 的道路网络模型和动态路径规划算法的研究背景、研究意义、国内 外研究现状、研究目的以及研究内容；详细阐述了路网模型的建立方法、动态路网的特点和最短路 径算法选择。 其次，论文论述了动态路径规划的相关技术领域，详细分析了当前动态路径规划面临的难题， 简述了如何在浮动车数据处理技术的基础上，利用g i s - t 空间数据库、路网拓扑关系表达和最短路 径算法等相关技术解决动态路径规划的问题。 再次，论文通过分析实际路网的特殊性以及动态路径优化算法对路网信息的适用条件，阐述了 研究路网简化、连通性表达以及信息存储方法的必要性，最终选择了g e o d a t a b a s e 数据模型来存储路 网数据，并设计了详细的路网数据结构，为高效的算法实现奠定了基础。 最后，在比较和分析了d i j k s t r a 和a 吐薹两种经典的静态路径优化算法之后，以前文设计的路网 数据模型为基础，提出一种基于交通限制且面向时态数据的动态路径规划算法。最后编程实现了设 计的算法。测试结果表明，该算法计算结果的合理性和运算效率可以满足动态路径规划的实际需要， 具有进行动态路径规划的能力。 关键词：动态最佳路径；路网模型；a 幸算法；f c d 东南大学硕士学位论文 a b s t r a c t d y n a m i cr o u t eg u i d a n c es y s t e mi sa ni m p o r t a n tp a r to ft h et r a v e l e ri n f o r m a t i o ns y s t e m ，w h i c hi sa s u b s y s t e mo ft h ei 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 sm a i nf u n c t i o ni st oa s s i s td r i v e r sc h o o s i n gt h ep a t h s a n dd r i v i n ga l o n gt h ee s t a b l i s h e dr o u t e st og e tt h ed e s t i n a t i o n sa n dt oh e l pt h ed r i v e r sr e s e l e c tt h ep a t h s w h e nn e c e s s a r y t h et r a v e l e r sa r ei n t e r e s t e di nf i n d i n gt h eb e s tp a t hb e t w e e nt h eo r i g i na n dt h ed e s t i n a t i o n b e f o r et h e i rt r i ps t a r t e d t h eb e s tp a t hi sc o n s i d e r e da st h es h o r t e s to n eb e t w e e nt w op o i n t s t h eo n el e a s t t i m en e e d e d , o rt h eo n ew i t ht h eb e s tm a dc o n d i t i o n , a c c o r d i n gt od i f f e r e n td e m a n d s h o w e v e r , t h e s o c a l l e ds h o r t e s tp a t hi sn e i t h e rt h es h o r t e s tp a t hi ns i m p l ep h y s i c a ls e n s en o rt h es t a t i cs h o r t e s tt i m ep a t h , f o rt h er o a dc a p a c i t ym a yb el i m i t e db yo t h e rf a c t o r s ，s u c ha st h ei n t e r s e c t i o ns i g n a lc o n t r o lc o n d i t i o n s ， w e a t h e rc o n d i t i o n s ，c o n g e s t i o ns i t u a t i o n sa n ds oo n t a k i n ga l lt h ef a c t o r sw h i c ha f f e c tt h er o a dc a p a c i t y i n t oa c c o u n ti sn e c e s s a r yt or e f l e c tt h er e a lr o a dc o n d i t i o n t h e r e f o r e t h i sp a p e rm a k e sc o m p r e h e n s i v e s t u d yo nt h er o a dn e t w o r km o d e l sb a s e do nf c d ( f l o a t i n gc a rd a t a , f c d ) a n dt h ed y n a m i cp a t hp l a n n i n g t e c h n o l o g y , a n dp u tf o r w a r dap r a c t i c a lr o a dn e t w o r km o d e l i n gm e t h o da n dd y n a m i cp a t hp l a n n i n g a l g o r i t h m f i r s t ，t h i sp a p e rs u m m a r i z e dt h er o a dn e t w o r km o d e lb a s e do nf c d ，t h er e s e a r c hb a c k g r o u n d ，m e a n i n g ， d o m e s t i ca n do v e r s e a sr e s e a r c hs t a t u s ，p u r p o s ea n dc o n t e n t so nd y n a m i cp a t hp l a n n i n ga l g o r i t h m ，a n d e x p a n d e di nd e t a i l t h ee s t a b l i s h m e n to fn e t w o r km o d e l ，t h ec h a r a c t e r i s t i c so fd y n a m i cn e t w o r k , a n dt h e c h o o s i n go fs h o r t e s tp a t ha l g o r i t h m s e c o n d ，t h i sp a p e rd i s c u s s e dt h er e l a t e dt e c h n o l o g i e s ，a n da n a l y z e dt h ep r o b l e m si nn o w a d a y sd y n a m i c p a t hp l a n n i n g a na p p r o a c ht os o l v et h ed y n a m i cp a t hp l a n n i n go nt h eb a s i so ff l o a t i n gc a rd a t ap r o c e s s t e c h n o l o g y , g i s ts p a t i a ld a t a b a s e ，e x p r e s s i o no fn e t w o r kt o p o l o g i c a lr e l a t i o na n ds h o r t e s tp a t ha l g o r i t h m w a sb r i e f l yd i s c u s s e d s u b s e q u e n t l y , b ya n a l y z i n gt h ep a r t i c u l a r i t yo fr o a dn e t w o r ki nr e a l i t ya n dt h ed e m a n d sf o rr o a dn e t w o r k i n f o r m a t i o n ，t h ep a p e rd e s c r i b e dt h en e c e s s i t yo ft h er e s e a r c ho nt h es i m p l i f i c a t i o no fr o a dn e t w o r k , t h e e x p r e s s i o no fc o n n e c t i v i t ya n dt h es t o r a g eo fi n f o r m a t i o n f i n a l l y , t h ep e r s o n a lg e o d a t a b a s eo fe s r iw a s a d o p t e dt os t o r et h er o a dn e t w o r kd a t a , a n dad e t a i l e dr o a dn e t w o r kd a t as t r u c t u r ew a sd e s i g n e d ，w h i c hl a i d af o u n d a t i o nf o rt h ee f f i c i e n ti m p l e m e n t a t i o no fa l g o r i t h m f i n a l l yt w ot r a d i t i o n a ls t a t i cr o u t i n ga l g o r i t h m sd i j k s t r aa n da 事a r ec o m p a r e da n da n a l y z e d t h e na d y n a m i cp a t hp l a n n i n ga l g o r i t h mw i t ht h er o a dn e t w o r km o d e ld e s i g n e db e f o r ei sp u tf o r w a r dw h i c hh a s p u tt r a f f i cr e s t r i c t i o na n dr e a l - t i m ed a t ai n t oc o n s i d e r a t i o n t h ea l g o r i t h mi sr e a l i z e dv i ap r o g r a m m i n gw i t h t e s tr e s u l t ss h o w i n gt h a tt h en e wa l g o r i t h mc a ns a t i s f yt h ep r a c t i c a ln e e do fd y n a m i cp a t hp l a n n i n gd u et o i t ss o u n dt e s tr e s u l ta n dh i g hc o m p u t a t i o n a le f f i c i e n c yt h u si ti sc a p a b l eo fd y n a m i cp a t hp l a n n i n g k e yw o r d s ：d y n a m i co p t i m a lr o u t e ；r o a dn e t w o r km o d e l ；a 幸a l g o r i t h m ；f l o a t i n gc a rd a t a l i 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。 尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过 的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书而使用过的材料。与我 一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 研究生签名： 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的复印 件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内容和纸质 论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布( 包括 刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权东南大学研究生院办理。 日期： 第一章绪论 1 1 研究背景及意义 第一章绪论 近年来一个有目共睹的事实是公路交通系统的复杂性和拥挤度与日俱增，特别是车辆增长的速 度已经远远的高于道路和其它交通设施的增长速度。最近一项研究发现，仅美国的主要城市每年由 于交通拥挤浪费了多达1 4 3 5 亿升的燃料和2 7 亿工作小时【1 | 。2 0 世纪9 0 年代以来，这些数字以每 年5 1 0 的速度继续递增。虽然运输需求增长的需要可以靠提供更多的交通设施来满足，但在资源 和环境矛盾越来越突出的今天，交通设施的增长将受到限制。为了大幅提高公路交通的通行能力和 安全度，研究采用新技术以改变现有公路交通技术面貌是国际公路交通科学的发展方向，先进的智 能交通系统有潜力缓解这一通行能力与需求的矛盾。交通管理部门越来越多的借助于当今科学发展 的新技术来保障交通畅通、改善道路安全，减少交通拥挤和空气污染对生态环境造成的恶劣影响。 这一新兴的领域被称为智能交通系统( 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 ) 。它为解决交通问题 带来了新的思路，而且越来越受到人们的关注。目前智能交通系统的范畴已经扩大到了水运、铁路、 航空等其它交通方式l l 】。在本文的研究中，所指的智能交通系统仅仅指的是城市公路交通系统。 城市交通网络在城市发展中占有至关重要的地位。它不仅是城市的一个重要组成部分，同时也 决定了城市中居民的生活方式。城市交通从本质上说，是一种人文活动在空间上的体现。这种活动 的主体和客体时刻都处在不断的发展变化中，传输着大量的能流、物流，具有极强的空间性与时序 性。由于交通本身所具有的动态性、复杂性，使得g i s 技术在交通领域的应用与其他领域相比具有 很大的差异。这也使得交通地理信息系统( g i sf o rt r a n s p o r t a t i o n ，g i s t ) 被强化为一个专有名词。 一般认为，g i s t 是在传统g i s 基础上，加入几何空间网络概念及线的叠置和动态分段等技术，并 配以专门的交通建模手段而组成的专业信息系统。在i t s 所包含的6 个高级交通系统中，有4 个与 g i s t 支持下的交通网络分析直接相关【2 j 。由此可以看出g i s t 在i t s 中占有举足轻重的地位。 然而，随着g i s t 的迅速发展，也暴露出g i s 应用于交通领域所存在的许多问题，主要可以归 结为以下两个方面。一是现有的g i s 数据结构及数据管理方式难以适应交通网络分析的需求，二是 绝大部分传统的g i s 应用软件不具备交通网络分析能力。虽然目前一些g i s 工具软件例如a r c g i s 也具有网络分析模块，但受制于原有数据结构，交通网络建模与分析的效率难以令人满意，所以需 要从根本的数据模型入手解决问题，创建合适的交通网络模型以便于进行更高效的网络分析。路网 分析中基本问题之一是动态路径优化问题。所谓动态最佳路径，不仅仅指一般地理意义上的距离最 短，还可以应用到其他的参数，如时间、费用、流量等。相应的，动态路径问题就成为最快路径问 题、最低费用问题等。图论的理论发展与不断完善的计算机数据结构以及算法的有效结合，使得新 的动态路径算法不断涌现。实际上，无论是距离最短、时间最快还是费用最低，他们的核心算法都 是最短路径算法。 现在最短路径分析基本上基于静态交通信息，他们首先用历史统计信息确定道路网中路段交通 信息，然后按照实际需求用最短路径算法计算出车辆当前位置到目的地的完整路径，使得其预期旅 行时间最短或者费用最少等。这些算法最基本模型是假设整个道路网络的交通信息是固定不变的， 也就是两点之间的路径是确定的并且与时间无关，而且没有考虑到堵车、事故、道路施工修路等因 素。这些算法在用于动态路网求解最佳路径时，只能在每次数据更新后重新计算，计算量大且效率 不高。 在现实交通网络中，由于交通拥挤程度随着时间的变化而变化，因此，每条道路上的实际旅行 时间都是随时间变化而变化的量，并且带有不确定性。这种不确定性是由司机和车辆特性的变化以 东南大学硕士学位论文 及其他不可预测事件( 如恶劣天气或塞车等) 的可能发生所导致的。现在，概念上已经接受，实验上已 经证明了交通网络中的随机性和时间依赖性。这种网络特征( 如路段权值、转向延时等) 既具有随机性 又具有时间依赖性的网络称之为随机时间依赖( s t o c h a s t i ca n dt i m e d e p e n d e n t ) 网络，简记为s t d 网络。 现实交通网络是典型s t d 网络，其中每条道路的实际旅行时间都是具有时间依赖概率分布的随机变 量。 在实践中，交通网络特征( 如路段权值、转向延时等) 会时刻发生变化，要求最佳路径算法必须实 时地自动更新重算，其中路段权值、转向延时等均为时间的函数，既可以是离散函数，也可以是连 续函数。上述实时交通信息通过浮动车数据采集并处理后，利用适宜的道路网络模型和高效的动态 路径算法向用户推荐最佳的行驶路线，避开前方拥挤路段，从而使得交通流在路网中得到重新分配， 不仅能够缩短单个用户的出行时间，降低出行费用，而且整个路网的道路利用率也能够得到优化， 整个路网的效率也得到了很大提高。可见，对动态路径规划所涉及的关键技术进行研究是解决目前 大部分大城市中日益严重的交通拥挤问题的有效手段之一1 2 j 。 1 2 国内外研究现状 1 2 1 国外研究概况 从t o m l i n s o n 第一次提出“地理信息系统”这一概念时起，交通地理信息系统的发展可以追溯 到上世纪六十年代年代。计算机技术的发展，给人们很大的帮助，它使得信息存储和数字计算变得 容易。学者们建立起许多不同的数学模型来用计算机表达客观世界。同样，地理学者们也试图用尽 量少的数据种类和数据量来表达地理事物，并进行复杂的操作和计算拉j 。 在上世纪六十年代，美国人口统计局建立的d i m e 以及后来的t i g e r 数据模型中，研究者们就 开始采用基于点和线的一维线性网络来表达道路系统。在同那些点线相连的属性表中，记录了点线 的各种属性信息。这一模式成为一直以来道路交通系统表达模型的一个主流。这种表达方式也适于 进行道路交通系统的路径分析。随着城市的发展，城市道路交通系统变得复杂起来，诸如多车道、 单行线、转弯限制、立交桥等的出现。初时，学者们可以通过向属性表中增加新的字段来解决这些 新现象。如加入字段一一车道数来表示该路段的车道属性，加入字段一一通行方向来注明该路段是 否单行线。在向大众提供即时路况信息方面，一些系统采用传输由闭路电视系统记录的即时交通画 面的方式来发布信息。这是一个相对独立的系统，与交通信息系统是不相连的，公众只知道道路交 通的大致情形，而无法充分利用所给予的信息。随著情形变得越来越复杂，仅仅对属性表修改已不 能满足现代城市交通地理信息系统发展的要求。g o v e r n 、g o o d c h i l d 和c h u r c h 首先提出了基于车 道的交通网络数据模型。f o h l 等人提出了一种多车道表达的交通网络概念模型，将建模的基本单位 定义为现实中的车道。车道表存储一条路段的车道信息，在动态分段的数据模式中，每个车道是一 个单独的路径元素。用一个与道路中心线的偏移值来表达车道，存储一个路径对应于每个车道。或 者，存储弧段的车道数，即将一个路段分为几个车道，在路径中以属性存储弧段的车道数，这样， 存储空间节省了，但没有存储车道之间的语义。 在城市交通网络中，路网交通量具有明显的时态特征。时态g i s ( t e m p o r a lg i s ，t g i s ) 一直是g i s 中的一个研究热点。人们期望在数据库中记录空间数据与属性数据在时态上的变化。t g i s 的基本功 能包括动态信息存贮、分析、更新、质量控制、计划预定、显示等。对于空间目标在时态上的变化， 现已提出6 种模型，即快照模型、更新模型、时空组合模型、3 d 4 d 模型、一体化模型、三域模型。 众多的研究者就路网模型开展了大量的深入的研究，其最终目的是为了实现高效、准确地路径 分析。在路径规划方面，荷兰数学家e w d i j k s t r a 提出的标号设定法( l a b e ls e t t i n g a l g o r i t h m s ) ，是目 前理论最完善，迄今为止应用最广泛的非负权值网络最短路径算法。标号设定法是一种基于贪心策 2 第一章绪论 略的最短路径算法，它要求在路径选择中的每一步所选择的路径都是目前为止最好的。在局部最优 而导致最优的假设下，寻求最佳路径不同的实现方法，构成d i j l ( s t m 算法的庞大家族，如a r c i n f o 采用的二叉堆优先级队列来实现d j j k s t r a 算法：g e o s t a r 采用的快速排序的f i f o 队列来实现d i j k s t r a 算法；动态段数据模式的双向比较追索法的d i j k s t r a 算法；最大邻接节点树构造节点矩阵的d i j k s t r a 算法；改进型o p e n c l o s e 表的d i j k s t r a 算法等。 路径优化经典算法有d i j k s t m 算法、f l o y d 算法、a 奉算法等。在经典算法的基础上，还形成了一 些改进算法。针对路径优化的非线性和不确定性，研究人员引入人工智能技术，开发了基于遗传算 法( g e n e t i c a l g o r i t h m ) 、神经网络( n e u r a ln e t w o r k ) 、蚁群优化算法( a n tc o l o n yo p t i m i z a t i o n a l g o r i t h m ) 等技术的方法。 1 2 2 国内研究概况 1 9 9 9 年陆锋等人提出了基于特征的城市交通网络非平面数据模型。该模型是基于车道的非平面 导航数据模型的进一步扩展。该数据模型引入了对象的概念，把道路等作为有特征的对象；引入了 车道的概念，以车道作为道路组成的基本单位；引入高程z ，突破c o r b e t t 二维平面单元理论，使对 道路的描述不再是平面的。该模型相当于2 5 d 的数据模型，在一定程度上解决了立体交通的问题。 通过面向对象的方法，动态分段技术和关系表指针操作，结合实例描述了基于完整交通特征的非平 面数据库的实现方法。基于特征的城市交通网络非平面数据模型是目前最成熟的非平面数据模型解 决方案，它从理论到实际应用都是相当完善的。 文献【3 ，4 】从逻辑描述方案的角度探讨道路数据的空间逻辑描述、属性描述和整体逻辑关系，建立 了道路空间数据库。文献p j 从数据组织和数据缓冲角度，提出用分级数据组织、分级预取策略和基 于启发信息的预取策略，有效的实现了车辆导航系统的地图显示问题。文献【6 1 针对嵌入式系统的特 点，对路网的数据结构进行了简化，并采用重整实体i d 的方法，进一步提高了检索数据的处理效率。 文献1 7 j 提出一种针对移动导航系统的名为h o t 的层次化路网模型。 龚健雅在1 9 9 7 年提出版本信息法用于解决属性字段的时态变化： 1 ) 将版本信息记录在关系表上，当目标属性发生变化时，重新产生另一个关系表。这种方法是 最简单的，可以从指定的时间段抽出完整的数据关系表，但可能会产生大量的数据冗余； 2 ) 将版本信息记录在元组上，当目标发生变化时，重新增加一条记录。这种方法比第一种方法 的冗余度大为减少，但查询效率有所降低： 3 ) 将版本信息记录在属性上，通过增加属性值来记录目标属性在时态上的变化，这种方法无数 据冗余但操作也最复杂。 最优路径查询是g i s 网络分析中的一个基本问题，国内许多学者都在这个方向做了大量的研究 工作。他们的研究大多集中于对最短路径算法的改进和优化，比如张连蓬，刘国林等人提出了方向 优先的快速搜索算法，该算法在路径搜索过程中，首先搜索与前进方向更加接近的方向，可以在搜 索的早期找到最短路径，从而在以后的搜索中剪去更多的节点和分支。另外，有不少研究是提出了 新的算法，如赵建宏等人定义了有向图的代价邻接矩阵和最短路径矩阵，给出称为“乘位加比小” 的种代价邻接矩阵间的新运算，基于该矩阵运算，证明了一种称为“代价邻接矩阵乘位加比小算 法”的新的最短路径算法；严寒冰等人从城市道路网络的特点出发，分析了分段车道间的连通关系， 得出一种求城市道路网络两节点间的最短路径的算法嘲。 1 3 研究目的 路径规划子系统在车辆导航系统中处于核心地位，可帮助驾驶员在出行前或出行中确定行驶路 3 东南大学硕士学位论文 线，是实现导航功能的前提条件，如图1 1 所示。按照规划目的的不同，路径规划可分为多车路线 选择与优化和单车选择与路线优化1 9 埘。车辆导航系统的路径规划属于单车辆路径规划的范畴，它要 解决的主要问题是在给定道路网中寻找从出发点到目的地之间的最优路径，要求路径规划数据存储 空间足够小，并且规划时间尽可能短，这就对路径规划算法设计在时间和空间上提出了新的要求。 图1 - 1 路径规划模块在整个导航系统中的位置 本文拟在研究动态交通网络模型的基础上，对实时最佳路径算法进行深入的研究，以期能在一 定程度上对动态交通诱导问题提供有效的解决方法。针对传统路径诱导系统中路网模型效率低、最 优路径算法时间复杂度较高，在准确表达道路拓扑关系的基础上提出一种高效的道路网络模型和与 之对应的动态最佳路径算法，从而使动态交通诱导系统在实时性和智能性方面有所改善。 1 4 研究内容 通过对路网模型和最佳路径算法的国内外研究现状进行总结与分析，可以发现以往的各种研究 以数据模型为基础，不同的数据模型决定不同的分析模型和研究思路。本文是面向f c d 设计道路网 络模型和动态最佳路径算法，确定以下研究内容： ( 1 ) 面向f c d 的道路网络模型 研究针对f c d 处理技术的道路网络模型，使f c d 处理得到路网数据的过程更简便，在能够准 确的表达路网的拓扑关系的基础上建立更加完整、高效的数据结构，从而对以后的路径分析工作提 供辅助。具体分析实际道路网络的复杂性以及动态路径优化算法对路网信息的要求，研究路网的简 化、连通性的表达以及信息存储方法。采用g e o d a t a b a s e 数据模型来存放路网数据，设计路段动态信 息表储存路段实时信息，设计节点路段属性表储存静态信息。为了提高算法的检索效率，设计了路 段和节点的邻接关系表。 ( 2 ) 设计动态最佳路径算法 分析两种经典的路径规划算法，t ! p d i j k s t r a 算法和a 事算法。相比之下，a 事算法的效率相对较高， 4 第章绪论 于是采用a 幸算法作为本文路径规划算法的基础。 动态路网中求解最佳路径的难点在于路段权重实时刷新，先前的求解结果会随着路段权值的实 时刷新而作废。如果在离散的时间段内重复调用静态路网的算法，理论上是可以求解动态最佳路径 的，但是即使采用相对效率较高的a 幸算法，每次更新权值后把整个路网重新计算，效率也是非常低 下。 在先前设计的路网数据模型和a 事算法基础上，提出一种基于交通限制路径规划算法，这种算法 考虑了交叉口的转向限制，更加符合城市路网的实际情况。通过分析历史交通流数据的变化规律， 针对时态数据对a 幸算法的代价函数做适当修改，按照时序变更统计路段权重。 1 5 本章小结 概述了基于f c d 的道路网络模型和动态路径规划算法的研究背景、研究意义、国内外研究现状、 研究目的以及研究内容；详细阐述了路网模型的建立、动态路网的特点和最短路径算法选择。 5 东南大学硕士学位论文 第二章动态路径规划技术分析 2 1 动态路径规划相关技术 2 1 1 浮动车数据处理技术 浮动车通常是指具有定位和无线通信装置的车辆。浮动车所采集的数据一般包括时间戳、位置 坐标、瞬时速度、行驶方向、运行状态及其他内容。浮动车系统主要由车载设备、无线通信网络和 交通信息中心等组成。车载设备主要包括g p s 模块、无线通信模块等，g p s 模块接收卫星定位信号 并运算出车辆的坐标和瞬时速度，无线通信模块负责将车辆坐标、速度等数据传送到交通信息中心， 并接收交通信息中心发送的指令和数据。无线通信网络主要是指通信运营商提供的通信基站和数据 传输服务。交通信息中心主要包括无线通信设备、基于g i s 的交通信息处理系统及计算机设备等。 对浮动车数据处理后可以有效的用于分析动态路网交通状况和动态路径规划。 f c d 处理技术通常是指对采集的f c d 进行分析处理生成交通信息的技术。f c d 处理中的数据 处理过程中又涉及数据预处理、数据组织存储、坐标转换、地图匹配、交通路径计算等流程；而交 通信息分析则主要是将上一步处理后的数据转化成交通管理者和出行者所能利用的交通信息。在这 些处理过程中，需要设计高效的处理算法，这也是f c d 处理技术的研究重点。具体来说，在对海量 的f c d 进行处理时，数据存储组织的设计宣接决定了查询运算的效率；地图匹配是数据处理中的基 础环节，需要保证较高的准确度和匹配效率：而在交通信息分析方面，路段交通参数的估计和预测， 交通事件检测等都是处理的重点，这些技术的应用将会给交通出行者和管理者带来极大的便利。因 此，f c d 处理技术是f c d 能得以广泛应用的重要基础，也是智能交通领域的重要研究方向。车载设 备向交通信息中心传输的数据主要包括：车载终端i d 号、经纬度坐标、瞬时速度、方向、回传时间、 有效性标识等字段。交通信息中心对车载设备上传的数据进行存储、预处理，结合地图利用相应的 计算模型对交通参数如速度、行程时间等进行估计和预测，从而得到整个道路网的实时动态交通信 息【l i 】。 浮动车系统的硬件设备包括由通讯服务器、数据服务器、应用服务器、大屏幕显示设备以及通 讯网络等构成的计算中心。 浮动车系统的软件平台分为两种：p c 端平台和车载端平台。p c 端软件平台一般包括很多复杂 的功能，比如浮动车动态交通数据的采集、传输、融合；构建路网动态交通数据库；基于出租车动 态交通数据的出租车乘客o d 分析；路段车辆行驶速度监测、行驶时间估算、路段交通异常事件探 查；根据g p s 采集的速度数据判断路段车辆的行驶状态以及路段的交通状况；检测交通故障、事故， 提示报警，安排警员排查事件等。而车载端软件平台相对简单些，除了一般的g i s 地图控制、显示、 查询功能外，主要是接收交通中心发布的动态路径诱导信息【1 2 】。 2 1 2g i s t 空间数据库 交通地理信息系统是收集、存储、管理、综合分析和处理空间信息和交通信息的计算机软、硬 件系统，是g 1 s 技术在交通领域的延伸，是g 1 s 与多种交通信息分析和处理技术的集成。 g i s t 数据库是交通管理的基础信息数据库，它由静态的道路网、道路宽度、等级、路名、地 形地貌、重要场所等信息和动态的交通组织方案、等时图、交通拥堵、交通事故多时段、路段、警 6 第二章动态路径规划技术分析 力配置等信息共同组成。它可以利用多媒体技术把一张地图分层展开，并按需要配上相应的数据、 图形、图像、声音信息，使我们最大限度地对有关内容得到了解。g i s - t 数据库的特点是规模庞大、 结构复杂、功能综合、因素众多 1 3 , 1 4 】。在本文中主要研究的是面向道路交通网络的空间数据库。 道路交通空间网络数据主要包括：现状道路网络、规划中的道路、建设中的道路。对于g i s 来 说，道路交通网络实际上是一种地理网络，具有地理网络的一般特性。道路交通网是一种典型的具 有空间网络特征的空间实体，可以使用空间网络数据模型来描述。但是道路网络又不同于一般的空 间网络。有其自己的特点。具体来讲，道路网络具有以下几个特殊情况： 道路的方向性。道路是有方向的，大部分城市道路都是双向的，但有些单向限制的道路只具有 一个方向，另一个方向是不畅通的。 转向限制。有些城市道路的交叉口会禁止左转，甚至禁止右转，这样会导致有些相邻的道路却 并不连通，需要特殊处理。 立体交叉。立体交叉的两条道路，根据匝道设置的不同，会有不同的连通情况，这一点也需要 在数据模型中表现出来。 道路阻抗的动态性。道路阻抗一般是指道路的长度、行驶时间、收费等等，其中行驶时间、收 费会随时间变化的，这也是在存储道路网络时需要注意的问题。 2 1 3 路网拓扑关系表达 拓扑一词来源于希腊文，意思是“形状的研究”。拓扑学( t o p o l o g y ) 是几何学的一个分支，它研 究在拓扑变换下能够保持不变的集合属性拓扑属性。作为近代数学的一门基础理论科学，拓扑 学己经渗透到数学的许多分支及物理、化学、生物学之中，而且在工程技术中也有广泛的应用。由 于拓扑学是研究图形在拓扑变化下不变的性质，拓扑学己成为地理信息系统空间关系的理论基础， 为空间点、线、面之间的包含、覆盖、相离和相接等空间关系的描述提供直接的理论基础i l 引。 只有正确地建立了路网的拓扑结构之后，才可能在其基础上进行最短路线的计算。拓扑结构就 是指在数据结构上借助拓扑几何学的概念来定义空间实体的相互关系。 在g i s 拓扑数据结构中，通常具有如下三种重要的拓扑形式： ( 1 ) 说明线串如何相连的连通性( c o n n e c t i v i t y ) ，即线串( l i n es t r i n g ) 是在节点( n o d e ) & 相互连接的。 ( 2 ) 多边形是由一系列相连通的线串组成的。 ( 3 ) 记录多边形的相邻信息以表示拓扑结构的连续性( c o n t i g u i t y ) 是指根据线串的走向，可以决定 谁是左多边形，谁是右多边形。同时，两多边形之所以相邻是因为二者具有共同的边界。 拓扑关系是指图形保持连续状态下变形，但图形关系不变的性质，描述了图形实体之间的邻接， 关联和包含关系。对于矢量图形的拓扑关系的描述，主要有基于网络的拓扑模型和基于点集拓扑理 论的拓扑模型。基于网络的拓扑模型具有直观，结构清晰，互导性强，便于组织存储等优点。路网 拓扑关系主要讨论线与线之间的连通性关系，即将其按节点和边的关系抽象为图的结构，这称为构 建网络的拓扑关系。 利用g i s 技术基于道路网络的路径分析与优化，是实现高效交通管理和交通出行的关键技术之 一。道路网络路径分析的基础是路网拓扑结构的建立。路网数据模型是构建道路拓扑、路径分析的 基础。路径分析系统可采用a i c - n o d e ( 弧段一节点) 模型，该模型表示为： n r = ( y ，e ) 矿= l r ， v n s e = r s l 凡= 加，矿7i ，1 ，叼 式中：n r 为道路网络；n s 为道路的节点集，对应图的顶点集；尽为道路的有向路段集，对应图 的弧段集，可以用道路网络中两个节点的拓扑关系表示；、v 为道路的起点和终点；为路段的属 7 东南大学硕士学位论文 性集，可表示长度、平均时速、行程时间掣埘。 2 2 路径规划技术 最短路径算法广泛应用在地理信息系统、机器人探路、计算机网络等领域。随着计算机和地理 信息科学的发展，地理信息系统的应用领域越来越广，最短路径问题无论是在交通运输，还是在城 市规划、物流管理等方面，它都发挥了重要的作用。近几十年，对静态路网的最短路径算法得到了 很大成就，常用的算法有d i j k s t r a - 算法、a 幸算法、f l o y d 算法等，针对实际需求还出现了大量的改进 算法，大多以d i j k s t r a 算法和a 幸算法为基础。 2 2 1 基于d i j k s t r a 算法的改进算法 基于d i j k s t r a 算法的改进算法很多，改进的切入点主要有两个，即网络存储结构和空间分布特 性。针对这两个切入点，下面分别介绍和分析两种常用的改进算法。 2 2 1 1 基于二叉堆优先级队列的d i j k s t r a 算法 在d i j k s t r a 算法中，涉及两个点集合的检索操作耗时巨大。在算法的具体计算过程中，通过设置 优先级队歹；i j q 的操作，将集合s 中的节点加入到集合t 中，一般的d i j k s t r a 算法是采用线性数组来实现 优先级队列q ，而这里采用二叉堆这种数据结构来实现优先级队列q 的一系列操作。 w i l l i o m s 在1 9 6 4 年提出了堆排序方法，该方法引入了堆这种特定的数据结构。这里二叉堆结构可 以被视为一棵完全二叉树，而且其含义表明，完全二叉树中所有非终端节点的值均不大于( 或不小于) 其左、右子节点的值。除了用于堆排序之外，二叉堆最常见的应用是作为高效的优先级队列。该优 先级队列是一种用来维护由一组元素构成集合s 的数据结构，而且这一组元素中的每一个都有一个关 键字。在分时计算机上，进行作业调度和进行事件驱动的仿真器都要用到优先级队列，而且通常采 用二叉堆结构来实现优先级队列。一般作用于优先级队列上的二叉堆的相应操作有： h e a p i f y ( s ) ：即首先将集合s 调整成二叉堆，并设定其根节点具有最小关键字；然后该操作从堆 的根节点开始，通过对当前节点的左右子树关键字的比较，来调整相应节点在堆中的正确位置，即 通常所谓的“筛选”过程，而且此操作为维持堆性质的关键。 h e a p i n s e r t ( x ，s ) ：即将元素x 插入集合s ，并调用h e a p i f y 将其调整成- - - x 堆。该操作是首先将 堆加以扩展，即在树的最后一层加一片叶子，然后遍历由新加的节点叶子到根的路径，以找到放新 元素的合适位置。 h e a p e x t r a c t - m i n ( s ) ：即抽取具有最小关键字的元素，并调用h e a p i f y 将其调整成二叉堆。该操 作可通过对堆的h e a p i f y 操作来实现。其运行时间主要花费在调整成二叉堆的操作上。 该算法的具体实现步骤： ( 1 ) 初始化操作。首先搜索与源节点s t a r t p o i n t 关联的节点a d j s t a r t p o i n t ，然后初始化节点列表 n o d e l i s t q b 所有节点的权值c o s t n o d e i 】，i 周用h e a p i n s e r t 方法实现初始化i n i t i a l i z e 操作，来初始化优先 级队列h e a p ，同时创建堆h e a p 中节点与节点列表n o d e l i s t 中节点相互关联的索弓ll n d e x 。 ( 2 ) 抽取最短距离节点操作。即对优先级队g u h e a p 的操作，通过调用h e a p e x t r a c t m i n ，选择节点 n o d e j ，使得c o s t i - - m i n c o s t i 】n o d e i 】e n o d e l i s t 。其中，n o d e j 为当前求得的从s t a r t p o i m 出发 的最短路径终点。 ( 3 ) 松弛操作。对从n o d e j 出发的节点n o d e k 进行松弛操作，松弛操作是通过d e c r e a s e - k e y 方法 来实现，即若c o s t l j + c o s t j ，k 】 m d ， n 的临界点构成了以s 、g 为焦点，以m d 为长轴的椭圆，如图2 1 所示。其直观意义为，即使在s 与n 、 n 与g 之间存在直线路径，由于二者之和已经大于所估计的s 至g 的最短路径的极大值m d ，在算法运 行过程中对此节点不予考虑。算法中椭圆限制的关键是求解合适的椭圆长轴m d ，以结合起终点坐标 构造限制椭圆。可以采用统计分析方法完成这一工作。在交通网络节点集合中系统抽取具有代表性 的一定数目的节点，构造两个节点集合a 与b 。则其笛卡尔乘积为 c = 彳x b = ，亿功l 向e a ) af 2 je b ) j c 中的每