（计算机软件与理论专业论文）道路网上连续最近邻查询方法研究.pdf

摘要 在智能交通系统( i n t e l l i g e n tt r a i l s p o r 怃l t i o ns y s t e m s ，r r s ) 中，最近邻( n e a r e s t n e i g h b o r n n ) 查询是研究的重点问题之一，它用来找出交通路网中离查询对象 最近的目标对象，尤其是查询对象在路网上连续移动的情况，即称为道路网连续 最近邻查询。 目前，国内外的大多数研究都是建立在基于静态信息的路网模型上，即把路 段的长度作为该路段的行驶代价，而没有考虑动态交通信息( 如交通控制，信号 灯等待，交通堵塞等) 。由于交通路网状况复杂，交通信息实时发生变化，静态 路网模型下的最近邻查询不能反映交通路网的真实情况。本文将最近邻查询建立 在动态信息的路网模型上，将路段上的行程时间定义为路段权值，并且该权值随 着交通网络信息的改变而随时发生变化。另外由于交通信息中心进行数据转换并 发布信息也需要一定的时间，想要准确地给出最近邻查询结果，这就需要对路段 上未来行程时间进行预测。本文采用了基于r b f 神经网络的行程时间预测模型， 根据已有的历史数据对未来时段的行程时间进行预测，从而改变路段的权值，使 它能较准确地反映该路段的行驶代价。 同时，随着交通状况的变化，当路段的权值改变，服务器就需要更新。传统 的路网连续最近邻查询方法是采用的快照方式，相当于做了一系列的静态最近邻 查询，每次更新都要重新查找所有的最近邻，存在重复计算的问题。本文对传统 的路网连续最近邻查询进行改进，考虑到两次连续的查询结果之间存在一定的联 系，充分利用前次查询结果的有效部分，减少数据库的更新。改进算法在处理更 新时考虑了各种更新情况，并合理地安排处理各种更新的顺序，以提高查询效率。 最后本文分别就传统路网移动对象连续最近邻算法和改进的连续最近邻算 法运用真实数据做实验比较，实验表明，改进算法准确率和查询效率都要优于传 统算法。 关键词：智能交通系统，交通路网，连续最近邻查询，i 啦f ，神经网络 a bs t r a c t t h en e 鲫喊n e i 曲b o rq u e 哆q n q ) h 鹤b e 既v e 巧i i n p o 舳ti n 心h l t e l l i g e n t t r 趾s p o r t a t i o ns y s t e m ( i t s ) ，c s p e c i a l l yw h 髓n l eq u e 巧o b j e c tm o v i n go nt l l er o a d n e 铆o r kc 0 以n u o u s l y w l l i c hi sc a l l c dt l l ec o n t i i m 懿n e i g h b o rq u e 巧( c n n ) 0 ni 沁a d n e t w 0 嫩 t h e 缸a d i t i o n mr e s e a r c ho nm ec n ni sb a s o do n l e 疏a t i cm o d e lo fr o a dn e t w o r k 试讹c h 妇1 ew e i g h to f m ee d g ei ss e t 弱m el e i l g mo f 吐坨e d g e 1 k sk i n do f m e l l d s 、撕l lb e c o m ei i l e x a mi nt l l et r a 伍cn e t w o r k s ow ew i l ls e a r d ln l en e a r e s tn e i g h b o r b a s eo nn l ed y n 锄i cm o d e lo fm er o a dn e t w o r k ，a i l ds e tm e 心a v e l 血gt 证l e 嬲l e w e i g h to ft l l ee d g e ，w l l i c hc a nc h a n g ew i mm e 舰岱c 耐o n n a t i o n a t 吐l es a m e 缸坞 m e 通f o 锄a t i o n 仃a 1 1 s f o r m 撕o nt ot l l es y s t 锄丘o mn l ev e _ l l i c l ea l s on e e d st i m e ，b y 航c hw es h o u mf b r e c a s ta b o u tm ef i m 鹏劬l v e l i n gt i i i l e t h er b fn e u r a ln e t 、r k 、7 i ，i l lb eu s e di no u rr e s e a r c ht od oi t a r e r 缸l ef o r c a s t ，t l l ew e i g h to f m ec d g ew i l lb ed 姗g e di i lr e a lt i l l l e ，w l l i c h 丽1 l l e a dt 0 l e 脚e n tu p d a t e st o w a r d sn l ed a t a b 嬲e ，孤di t 惭1 1l e a dt 0al a 玛ec o s t h m i sp a p e r w ew i l l 如1 p r 0 v em e 础t i o n a la l g 耐l mi no r d e rt 0i 1 i l p r 0 v em e e f f e c t i v e 够o fm ea l g o r i 廿1 mb yr 即s i n gt h ee 筇号c ti nm e l 嬲tq u e 巧硒m o r e 觞p o s s i b l e f i r l a l l 弘w ec 0 m p a r em ei m p v e da 1 9 0 r i 缸nt 0m e 仃a d i t i o 砌o n e n l e e x p 妇l e n t ss h o w 廿l a tm ei n 】_ p m v c da l g o r i m mi sb e t t e rm 锄也e 仃a 成t i o n a la l g o 打恤 n b a s e d0 nm ea c c u r a c ya i 】i dt l l ee 伍c i e i l c y l 哂啊o r d s ：i n t e l l i g e n tt 细1 s p 嘶a t i o ns y s t 锄，r o a dn e 俩。血c 0 幽u sn e a r e s t n e i g h b o rq u 哪r b f n e u r a ln e 附o r k 学位论文独创性声明： 本人所呈交的学位论文是我个人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果。与我一同工 作的同事对本研究所做的任何贡献均已在论文中作了明确的说明并 表示了谢意。如不实，本人负全部责任。 论文作者( 签名) ： 丑星丝沙形年二月髟日 学位论文使用授权说明 河海大学、中国科学技术信息研究所、国家图书馆、中国学术期 刊( 光盘版) 电子杂志社有权保留本人所送交学位论文的复印件或电 子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文 档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允 许论文被查阅和借阅。论文全部或部分内容的公布( 包括刊登) 授权河 海大学研究生院办理。 论文作者( 签名) ： i 童鳖沙砀年髟月日 河海大学硕士研究生论文道路网上连续最近邻查询方法研究 第一章绪论 道路网上最近邻查询是智能交通系统中研究的重点问题之一，它用来找出交 通路网中离查询对象最近的目标对象，尤其是查询对象在路网上连续移动的情 况，这正是本文中研究的重点。 1 1 研究背景与意义 在地理信息系统( g i s ) 【1 冲，最近邻查询是经常遇到的一类查询，由于无 线通讯的广泛使用，跟踪并记录移动对象的位置成为可能，移动对象的最近邻查 询算法也成为研究的重点和难点。 最近邻( 吐l en e a r e s tn e i 曲b o r ，n n ) 查询是用来找出距离查询对象最近的目 标对象，即最近邻居，最近邻的数目可以是一个，也可以是k ( k 1 ) 个，若k 1 则称k 近邻。例如，在地理信息系统中，对一个特定的位置或目标，要求系统查 找并返回5 个离它最近的对象，当查询对象移动时，我们则称之为移动对象的连 续最近邻查询。 当然，最近邻查询也可以检索沿某路线运动的移动对象的最近邻，而在实际 应用中，最近邻查询方法必须和交通路网的实际情况结合在一起，这在智能交通 系统( n e l l i g e n tt r 趾s p o r t a t i o ns y s t e m ，i t s ) 中具有广泛的应用前景，也是本文 要研究的基于路网的移动对象连续最近邻查询。道路网上移动对象的连续最近邻 查询，是对于查询对象道路网上移动的情况下( 考虑到道路网的特殊性，其路段 的权值也在不停地改变) ，对查询对象连续的最近邻的查找。例如，在智能交通 系统中，以出租车为查询对象，道路上的加油站为目标对象，随着出租车的移动 连续查找距离出租车最近的加油站。 本文主要是对于道路网上移动对象的持续最近邻查询方法的研究，针对具体 的道路网，考虑道路网的特殊性和复杂性，给出相对快速准确的查询算法减少复 杂的计算和网络负担。 1 2 国内外研究现状 在基于路网的研究中，移动对象的运动是受到一定条件限制的，比如汽车是 在交通网络上行驶的。因此，在基于路网的条件下，最近邻查询的结果是取决于 河海大学硕士研究生论文道路网上连续最近邻查询方法研究 路网的连通性的，而不是对象的相对位置。 现有的国内外对路网上的连续最近邻查询方法主要分为查询点运动轨迹预 知和轨迹未知这两种情况： ( 1 ) 当查询对象移动的轨迹预知时，这类查询需要为查询对象的每一个位 置重复计算它的k 近邻。解决问题的关键在于：如何减少随着查询对象的移动而 带来的重复计算。 p a p a d i a s 等人提出了两种基于空间网络的k 近邻查询方法( i n e ) 3 ，该方法 的主要思想是：以发出查询的点为中心逐步进行扩张搜索，在扩张过程中比较所 有遇到的查询对象到中心的距离，这种方法是对d i j k s 讹算法的一种变形，当扩 张半径超过到第k 个对象的距离时，查询就结束了。玳e 方法的效率取决于要查 询对象的密度，如果整个路网范围比较大，而要查询的对象又比较少且很分散， 那么该方法的效率就很低，因为要搜索大部分的路网。 k o l a l l d o u z a i l 等人提出了v n 3 方法 4 ，它是基于v o r o n o i 图的路网k 近邻查 询方法。这种方法的主要思想是以v 0 r o n o i 图为基础将整个路网划分为若干个易 于计算的小区域，每一个区域称为一个c e l l 。在每个c e l l 当中是以要查询的点为 中心的，并事先计算好内部所有边及邻接顶点到中心的距离，同时计算出相邻的 c e l l 之间的邻接顶点间的距离，这样只要锁定发出查询的对象所在的c e l l 并依据 预先计算好且存储在邻接表中的距离值就可以得到k 近邻查询的结果。v n 3 方法 在查询点较分散的情况下有较好的查询性能，但当查询点较为密集时则效率较 低。另外此方法没有提出一种明确的方法来表示路网中不同类型的查询点。 ( 2 ) 查询对象移动轨迹不确定的查询，需要从如何减小重复计算的角度考 虑。 s o n g 在 5 中提出的利用前次查询结果来缩小下次查询范围的方法，然而这 种方法只适用于空间数据库，并没有考虑到路网的复杂性。 m k o l a l l d o u z a l l 等在【4 中提出的v o r o n o i 方法同样也可用于查询对象移动轨 迹不定的查询，因为目标对象固定，且已经过预处理，一旦知道查询对象目前在 哪个区域内即可确定其最近邻。 j z h 锄g 等则在 6 】中提出当查询对象q 仍在初始位置周围的一定区域( 有效 区域) 内，则最近邻结果不变。而这个有效区域可以通过r o n o i 方法来获得。 这种方法通过减少更新次数来提高效率，然而道路网发生改变时，则需要对路网 重新进行预处理。 c s j e i l s e i l 等在 7 】中讨论了公路网上的移动对象查找移动的k 近邻的方法， 提出采用c s 体系结构。对于查询对象q 发出的查询请求心n ，服务器端给出 一个最近邻候选集合m n n ( m k ) ，而由客户端完成对候选集的维护，即再计算候 选集中目标对象到查询对象的距离，给出心，然后周期性地更新候选集，以 避免查询结果的不精确。该方法以搜索候选集来替代搜索整个目标对象集，同时 2 河海大学硕士研究生论文道路网上连续最近邻查询方法研究 由求出的最近邻位置与实际位置之间的误差来决定更新，以此提高搜索效率和精 度。但是这种方法的更新时间难以把握，若更新时间过短，则计算量太大；若更 新时间过长，则计算结果误差增大。 随着卫星定位系统( 如g p s ) 和无线通讯技术的快速发展，跟踪并记录移动 对象的位置变得可行，移动对象的最近邻查询成为最近邻查询的重点和难点，特 别是目标对象和查询对象均移动的情况。而在实际应用中，查询对象最近邻查询 往往与交通路网的实时信息结合在一起，这就是本文要研究的基于路网移动对象 的连续最近邻查询。 1 3 本文的主要内容 本文研究道路网上移动对象的连续最近邻查询方，并且查询点在路网上的移 动轨迹是未知的。传统的路网移动对象最近邻查询是建立在一种静态路网模型 上，并没有考虑到交通路网的真实情况。在做一系列查询时，类似于快照，由一 系列静态查询构成，即每一次都重新作了一遍静态的最近邻搜索。 考虑到交通网络的真实情况，将路段上的行程时间作为路段的权值，同时， 由于路网交通状况实时发生变化，交通信息中心进行数据转换并发布信息也需要 一定的时间，想要准确地给出最近邻查询结果，这就需要对路段上未来行程时间 进行预测。 本文首先利用i m f 神经网络模型对路段的行程时间进行预测，预测的结果 则用来进行路段的权值更新，另外在处理权值更新的时候，通过充分合理利用前 次查询结果的有效部分，改进更新处理的方法，从而减少数据库更新。比较结果 表明，改进算法作道路网上移动对象的连续最近邻查询，其准确率高于传统算法。 1 4 本文的组织 本章是绪论部分，主要介绍最近邻查询的研究背景和意义，并介绍了目前国 内外的研究现状，简单分析了各种类型的最近邻查询方法的优点和不足，最后给 出了本文研究的主要内容。 第二章先分别详细介绍了介移动对象运动轨迹预知和未知的连续最近邻查 询，接着介绍了行程时间预测模型的研究现状。 第三章重点介绍了基于r b f 神经网络的行程时间预测模型的学习方法，并 利用已有的历史数据对神经网络进行训练，根据训练后的神经网络预测路段上未 来时段的行程时间，并给出了实验的结果。 第四章提出了一种改进的基于路网移动对象最近邻查询算法，重点在于各种 河海火学硕士研究生论文道路网上连续最近邻查询方法研究 更新的处理，减少数据库更新，提高查询效率，最后给出了查询的算法描述。 第五章实验比较路网移动对象最近邻查询的传统算法和改进算法，并分析两 个算法各自的优劣。 第六章总结和展望，总结全文工作，并对进一步的工作做出展望。 4 河海大学硕士研究生论文道路网上连续最近邻查询方法研究 第二章相关研究 本章主要讨论基于路网的移动对象连续最近邻查询的方法，该查询按照移动 对象在路网上的运动轨迹分为两类：移动对象运动轨迹预知的连续最近邻查询和 运动轨迹未知的连续最近邻查询。本文侧重研究运动轨迹未知的路网连续最近邻 查询。接着本章介绍了交通路网的行程时间预测模型的研究现状。 2 1 基于路网的连续最近邻查询 近年来，随着跟踪连续运动目标位置技术的快速发展，最近邻查询问题扩展 到移动环境这一领域。现存的许多最近邻查询方法都是基于欧几里得空间所做的 研究，这些方法考虑的是两个对象在空间中的相对位置。然而，在基于路网的条 件下，最近邻查询的结果是取决于路网的连通性的，而不是查询对象的相对位置。 本文主要介绍基于路网的移动对象连续最近邻查询方法，首先给出它的定义： 定义1 ：假设查询对象q ，目标对象p i ，i 【o 州，对象q 和p i 均在道路网 n _ n ( v ，e ) 上，并且q 在路网上运动，时间间隔t ，查询对象q 每隔t 便查询 一次最近邻，本文称这种一系列的查询为道路网上移动对象的连续最近邻查询。 解决该问题的关键在于：如何减少随着查询对象的移动而带来的重复计算。对路 网上的连续最近邻查询方法主要分为查询点运动轨迹预知和轨迹未知两种情况， 下面分别对这两种情况进行介绍。 2 1 1 路网上轨迹预知的连续最近邻查询 对于路网上轨迹预知的连续最近邻查询问题的解决方法为基于递归的空间 范围搜索方法，该方法的诞生源于以下这一属性。我们设p 和q 为道路网的两点， e u c d i s 妇，q ) 为欧氏距离，p a 山i s t 0 ，q ) 为p 到q 的道路距离。 属性l ：e u c d i s t q ，q ) p a t l l d i s t ( p ，q ) ( 式2 1 ) 尽管欧氏距离并不能用来准确估计两点间的道路距离，但它可以提供道路距 离的最低下限，如果在以欧氏距离为搜索范围内并没有目标对象，那么没有一个 基于道路网搜索范围的兴趣点会在范围之内，在这种情况下，进行路径计算是不 必要的。计算基于欧氏距离的查询的代价相对要小于每一分支点的路径搜索算 法，并且此方法在空间数据库文献中也有很好的研究。因为道路网是使用二维地 河海大学硕士研究生论文 道路网上连续最近邻查询方法研究 图网络的，所以使用上面的属性来充分利用空间范围搜索。该方法用在判断是否 有目标对象在搜索范围内。 对于轨迹固定的路网连续最近邻，现有的查询方法主要分为三类，下面分别 对这三类方法进行介绍： ( 1 ) 利用查询对象的移动轨迹信息进行查询更新： j f e n g 等在 2 提出了这样的解决方法，即以沿道路网的路径长度而非平面上 的直线距离为标准，且在移动的路线已知的情况下来查找路径上每一点的最近 邻。 如图2 1 中，查询对象的移动轨迹是从s 到e 的一段路径，以黑体实线表示， 目标对象集p ：p = t l ，t 2 t 7 ) ，要求查找这段路径上的一个连续的最近邻。在起 始位置s 找到第一个最近邻t 1 ，路径长为r 。然后在移动轨迹上寻找下一个计算 点c ，c 到t l 的路径长也为r 。以c 为圆心，r 为半径画圆，所得区域称为r - r e 酉o n ， 则在r - r e 西o n 内的对象都可能是c 的最近邻。找到r - r e 西o n 内的对象t 2 ，以c 和 t 2 为两个圆心画椭圆，椭圆长半径为r ，这个椭圆区域称为p r e 西o n ，如果两点之 间存在更短的路径，那这条最短路径必然存在于这个区域内。如果不能找到这条 路径，那这个目标点必然不是查询点的最近邻，这个方法以缩小搜索范围来提高 查询效率。 t 3 白 t 5 e ， ， 、 、 ”_ 吃霭 、 、 l沙您学移瑚l 、 、 莨c ；霭 、 j jj r o e 。 1 弘d 刀 淤 r j t 6 s ， t l t 7 、 ， - 、 图2 1 利用移动轨迹处理查询更新 ( 2 ) 基于空间距离连接的方法： j i ns o u i l g y o o 等在 8 中提出了s d j 方法，通过使用r t r e e 这样的索引结构 来分别建立目标点集合r t r e e 和既定路径r t r e e ，通过空间数据库中的一种基 本操作空间连接运算来寻找最近邻。r 缸优连接算法的核心是对两棵r 仃e e 同步 进行深度优先遍历，当两个结点的m b r 相交时，则递归地进入下一层扫描，直到叶 结点相交，输出结果为止。下面的图2 2 描述了s d j 方法的查询过程： 6 河海大学硕士研究生论文道路网上连续最近邻查询方法研究 图2 2s d j 查询方法 首先，设初始的最小偏移距离t 为无穷大，然后开始两个数据集的距离连接 操作。根据两个空间树间的树周游方，将堆中放入以下元素：例如：，f i ，d i 护， “，m b r d i s 伊， m b 赋巧，d i 胗， m b 豇m b r d i 护，其中r i 是路径节点，m b r r 是是路径节点的最小外包矩形，m b r f 是目标点的最小外包矩形，d i s t 是两点( 两 点或者一个是m b r 或者两个都是m b r ) 欧氏距离。这些元素在对中是按d i s t 的 大小顺序排列。如果堆顶部的一个元素 r i ，驴的d i s t 小于最小偏移距离t ，则将 d i s t 赋值给t ，萄为目前为止的n n 。此过程按此重复直至堆中顶部元素的d i s t 大于t 为止。 ( 3 ) 对目标对象集进行预处理，从而利用预处理结果来满足查询要求。采用 区域划分方法预先划分目标对象区域，这样在目标对象为静态的情况下，一旦路 线给出，就能很快的给出每一段路线上的最近邻。典型研究是【4 】中提出的v o r o n o i 方法。 图2 3v 讲d n o i 图 v o r o n o i 方法指对给定的目标对象，用作垂直平分线的方法，把空间分割成 多个多边形，使得每个对象都在一个闭合多边形中，且每个多边形中有且只能有 一个对象，那么在此多边形内的任意一点的最近邻就是此多边形内的目标对象。 见图2 3 ，当给出路线时，可以很明显的看出，在某个区域中的线段的最近邻就 是此区域包含的对象。 2 1 2 路网上动态连续最近邻查询 对于查询对象移动轨迹不确定的查询，则需要从如何减小重复计算的角度考 7 河海大学硕士研究生论文 道路网上连续最近邻查询方法研究 虑。m k 0 1 a 1 1 d o u z a i l 等在 4 】中提出的v 0 r o n o i 方法同样也可用于查询对象移动轨 迹不定的查询，因为目标对象固定，且已经过预处理，一旦知道查询对象目前在 哪个区域内即可确定其最近邻。 j 办a n g 等则在 6 中提出当查询对象q 仍在初始位置周围的一定区域( 有效 区域) 内，则最近邻结果不变。而这个有效区域可以通过v 0 r o n o i 方法来获得。 这种方法通过减少更新次数来提高效率，然而道路网发生改变时，则需要对路网 重新进行预处理。 k 姐a k o s 等在 9 中提出了道路网上连续最近邻查询的龇算法，对路网上 的对象进行实时追踪，并考虑了路网中路段的更新处理问题。下面给出了算法的 描述： f i n d c 蝌( q ) 1 i 而a l i z ee r i 叩t yh e 印h ；s e tq 心nd i 妒，p a n i a l e d g e s 叼；初始化 2 s e tq 弱m er o o to f l ee x p a l l s i o n 廿e eq 仃e e ； 3 4 5 6 7 8 9 对查询点q 建立扩展树 l e teb em ee d g ec o m a i l l i n gq ； i i l s e r tm ekb e s to b j e c t si nei i l t oq r e s u l t ；u p d a t eg 砌啦f ； e n - h e 印巴s 加疗a 董l de 饥dw i md i s t a l l c ea c c o r d i n gt 0 巴w ； h l s e r ts u b e d g 锱g e s 纪力a r l dg e 绷di n t op a r t i a l e d g e s ； w 1 1 i l e m e n e x t n o d e n i i l h h a s k e y d 伽，砂 q 血州击甜； d e - h e a pn ；n 已经被检查过 l 碰eb em ee d g e sb e 帆e e i lna j l di t sp r e d e c e s s o r ； 对每个n ，只考虑在相邻边上的对象 d e l e t ee 劬mp 硎a l e d g e s ； f o re a c ha d j a c e n tn o d e 刀嘶o f ne x c 印tf o ri t sp r e d e c e s s o f 1 1 1 s e r t ，z 胛嘶i m op 删a _ l | e d g e s u p d a t eg ，嚣“厅a i l dq 1 【i l i l ：d i s tw i 廿lo b j e c t so ne d g e 刀甩耐 i f 万耐l l sn o tb e e nd e j e 印e db e f o r e 判断万捌是否在堆里 如f = a 枷，+ ，z 刀耐；w ； i f 刀硝i s n o t i n h s e tna st h ep r e d e c e s s o ro f 刀“i nm e 、x p a n s i o n 仃e e ) ； i r i s e n 疗脚i n 协hw i m k e y d i s t ； e l s e 刀础已经在堆中 i f d i s ti sl e s sm 孤m ec u 玎i 锄tk e yo f ，l 耐i i lh 如果当前的值大于d i s t ，值就降低为d i s t ，并且让n 咄是 q 仃e e 的一个子结点 8 m l 乞王屯 i & z & 殳n l 1 1 1 1 1 1 l 1 1 2 河海大学硕士研究生论文 道路网上连续最近邻查询方法研究 图2 4 龇算法描述 假设e 是包含查询点q 的边。首先，i m a 初始化了一个空的最小堆h ，把e 的端点进堆，设置q 为扩展树的根，子结点是e 的端点，然后反复从h 中删除 堆结点。只要知道结点n 的距离d ( i l ，q ) ，就称该堆结点n 是验证过的。对每个n ， m 队只考虑在相邻边上的对象，并且如果有必要的话更新当前的k n n 集合。然 后直接绕过n 检查没有验证的i l a d j 。如果呦是第一次遇到的话，把它插入到h ， 施= d 协，+ 以栉硒w ，并且作为n 的子结点插入到q 缸。否则，n 嘶已经在h 中； 如果当前的值大于d i s t ，值就降低为d i s t ，、并且让n a d j 是q 骶的一个子结点。 当h 上结点的值大于q 心nd i s t 时，查询停止。在给出初始结果的时候建 立了扩展树，包含了每个验证点的最短路径。第1 2 1 3 行，在p 硎a lc d g e s 中插 入了所遇到的边。第1 1 行从p 枷a le d g e s 中是最短路径的部分的边移去；当检 查一个结点的时候，到它的最短路径通过了连接它和它的在q 慨中父结点的边。 最后如果e 的两个端点都验证过了，但e 不是q 脚的一部分，那么包含在q r e s l l l t 的一个对象就要考虑两次。为了避免这种情况，当把一个对象插入到q r e s 小， 我们首先检查它是否已经存在了，并保持最小的距离( 第1 4 行) 。 通过上述的算法，则对查询点q 建立了一个扩展树，当查询点q 在路网n 上移动，或者路段的权值发生变化时就需要充分利用上次的结果进行数据库更 新，重新建树。 然而随着交通状况发生变化，道路网上每条路段上的行程时间也随之改变。 路段的行程时间是描述城市交通网络状态的重要参数，它能直观反映道路的拥挤 情况，是进行动态路线诱导的前提和基础，同时也是搜索最短路径的依据。本文 将路段上车辆的行程时间作为路段的权值，则更接近于实际交通路网特性。行程 时间的影响因素有交通事件、天气环境状况、道路几何线性及路网维修、道路照 明设施和交通管理及控制等因素，而这些因素会实时发生变化，同时，交通信息 中心进行数据转换并发布信息也需要一定的时间，想要准确地给出最近邻查询结 果，这就需要对路段上未来行程时间进行预测。下面介绍路网行程时间预测模型 的研究现状。 9 河海大学硕士研究生论文道路网i ：连续最近邻查询方法研究 2 2 路网行程时间预测模型研究现状 目前，日趋拥堵的交通状况己经成为影响人民生活质量、制约经济进一步发 展的重要因素，同时交通拥堵问题也加剧了环境的污染程度。为了解决上述问题， 国内外许多国家都开发建设了r r s ，希望通过i t s 提高交通管理服务水平 1 0 ，1 1 。 行程时间预测作为i t s 的一个重要组成部分，它建立在数据采集的基础上， 通过一步或多步预测，并采用各种模型，获得未来时段内车辆在路段上的行程时 间。预测的行程时间必须要满足实时性、可靠性和更高的精度要求，才能为用户 方便、快捷地到达目的地提供交通诱导服务，同时还能够为交通信号控制和交通 状态的判别分析提供基础条件，控制交通流的运行状态，及时疏散拥挤车流，从 而减少燃油消耗，减轻空气污染和交通噪声，同时，也提高了行车速度和运输生 产企业的效率。 近年来，历史趋势方法 1 2 ，1 3 】、时间序列 1 5 ，1 6 、卡尔曼滤波 1 7 ，1 8 】、神经 网络 1 9 2 9 等预测模型都已经被应用到行程时间预测中来，并取得了较好的成 效。上述预测方法都是以行程时间的历史数据为依据的，为了使预测尽量准确，就 要对行程时间数据进行不断更新。本文根据道路交通信息不断变化的情况探讨行 程时间实时估算方法，得出当前时段行程时间数据，以此作为对未来时段行程时间 进行预测的数据依据。因这些模型和方法具有通用性，故也可以用于基于g p s 浮动车采集数据的行程时间预测，下面对一些经典的模型和方法进行介绍。 2 2 1 历史趋势方法 历史趋势方法( h i s t 0 巧t r e n dm o d e l ) 1 2 ，1 3 基于如下：假设交通状况是间断 性发生的，即相同类别的日子( d a yo fw e e k ) 的各路段交通流特性在对应的每一 个时间段具有相似的趋势，即具有相同历史趋势的一天里各路段在同一时段具有 相同的行程时间，从而可以简单地使用该路段的历史行程时间，该方法已经在城 市交通控制系统和车行者信息及路径诱导系统，如l i s p 、a u t o g u i d e 中得到 检验。所以历史趋势法的前提条件是建立各路段的行程时间的历史数据库。 h o 伍n a l l i l 和j a l l l ( o 提出的历史趋势法 1 4 在西柏林的动态路径诱导系统l i s p 中 得到了应用，使用的历史数据库需要建立一周每一天的以5 疵为时间间隔的每 一路段的行程时间数据。 历史趋势方法包括两部分：路网中每一条路段在一周内每一天每隔五分钟的 典型旅行时间数据和预测算法。通常每一时段的旅行时间可以从研究时段的测试 结果数据获得更新。该算法记为： “向州= 所如一十一砂如 p 助( 式2 - 2 ) i o 河海大学硕士研究生论文道路网上连续最近邻查询方法研究 红开伽州：为路段l 在时间间隔n 的新的旅行时间值 p 鲫：为路段1 在时间间隔n 的旧的旅行时间值 f “：为最近观察到的路段l 在时间间隔n 的旅行时间值 口：为平滑系数 该方法己应用于城市交通控制系统和一些动态路径诱导系统中。虽然历史趋 势方法可以在一定程度内解决不同时间、不同时段里的交通流变化问题，但静态 的预测不足取，因为它不能解决非常规和突发的交通状况，如交通事故等。 2 2 2 时间序列模型 时间序列方法( t i m es 甜a 1m o d e l ) 是一种统计方法，其定义的行程时间由确 定部分和随机部分两部分组成。确定部分来自交通系统的实时处理，随机部分来 自外部环境。时间序列模型的关键自标是减少外部环境影响。b o x j 幽模型 是常用的一种时间序列方法，也叫做a r m 队( a 1 l t o - r e g r e s s i o ni n t e g r a t e dm o 、，i n g a v e 蝣e ) 模型 1 5 】。该模型不像其他时间序列方法一样需要固定的初始化模拟， 已应用于u t c s 和高速公路流量预测。 其算法记为： 痧倒彳口切= 钟矽口口桫( 式2 3 ) ) ，：时间间隔n 的时间序列值 口舢：随机噪声 并且：西倒= j 一西j b 晚矿姊矿( 式2 4 ) e ( b ) = l - el b - e 2 分e q l 乎q 忒2 一砩 砂御可吵m ( 式2 6 ) 彳门桫= 彳臼乡门讧砂j ( 式2 - 7 ) 缈御可僻矽，b 帆) ，仰可僻叫( 式2 8 ) 此模型拥有较高的预测精度，但需要复杂的参数估计，而且计算出的参数不能 移植。当交通状况发生急剧变化时，该模型将在预测延迟方面暴露出明显的不足。 在大量不问断数据的基础上。在实际情况中，经常由于各种各样的原因容易造成 数据遗漏，导致模型精度降低，而且依赖大量的历史数据，成本很高 1 6 。 2 2 3 卡尔曼滤波模型 卡尔曼滤波( 山n mf i l t 耐n gm o d e l ) 【1 8 】是一种在现代控制理论中广泛采用 的先进的时间序列方法，该方法可以用于过滤信号和模型参数估计，同时，也可 以用于交通预测。卡尔曼滤波方法的输入参数可以是当前时间段或过去的几个时 间段的一些变量( 交通流量、研究路段或邻接路段的占有率或旅行时间) ，输出将 河海大学硕士研究生论文 道路网上连续最近邻查询方法研究 来时间段的旅行时间。其离散动态系统的线性表达式为： 五+ j = 奴+ 上砭+ 巩 ( 式2 9 ) 磊蝴+ ， ( 式2 - 1 0 ) 凰：时刻k 的状态向量( n 1 ) 瓯：时刻k 到时刻k + 1 的转移矩阵( n n ) 巩：已知协方差矩阵的具有零均值且与其他参数无关的白噪声 序列( n 1 ) 磊：时刻k 的观察向量( m 1 ) 凤：时刻k 的状态矢量与观察矢量的连接矩阵( m m ) 圪：已知协方差矩阵的观测噪声，具有零均值且与相互独立 ( m 1 ) 卡尔曼滤波已经应用于旅行时间预测，并取得了令人满意的结果，是最好的 预测方法之一。由于卡尔曼滤波采用较灵活的递推状态空间模型，因此卡尔曼滤 波方法既适应于处理平稳数据，又可用于非平稳数据处理，且对状态变量作不同的 假设，可使其描述及处理不同类型的问题，同时减少了计算机存储量和计算时间； 模型具有线性、无偏、最小均方差性。卡尔曼增益矩阵可在计算中自动改变，调 节信息的修正作用以保持滤波估计的最佳性，具有在线预测的功能。但该方法是 线性模型，所以在预测非线性、不确定性的交通流时，模型性能变差。在每次计算 时都要调整权值，因此，计算量过大，预测输出值有时要延迟几个时间段。 2 2 4 人工神经网络模型 人工神经网络( a n i f i c i a ln e u r a ln e t 、) l r o 北砧叮n ) 诞生于2 0 世纪4 0 年代。1 9 6 4 年，h u 应用自适应线性网络进行天气预报，开创了人工神经网络预测的先河；1 9 9 3 年，v ，y t h o u l k 嬲p c 首次提出用系统识别和人工神经网络进行城市道路网络交通状 态的预测 2 0 。随着神经网络的发展，基于神经网络的行程时间预测的研究也越来 越多。 人工神经网络是基于模仿大脑神经网络结构和功能而建立起来的一种信息 处理系统 2 1 ，2 2 】。它由许多简单密集并相互连接的处理单元组成，每个处理单元 对应于人脑中的生物神经元，而处理单元之间的连接类似于生物神经网络中的突 触。在一个朋叮n 模型中，每个处理单元接收到外界和其它处理单元传递过来的 信息，对其进行处理，然后将经过处理的信息再传递给其它的处理单元。 a n n 的设计包含三个要素，第一个要素是转移函数，它模仿的是生物神经 元所具有的非线性处理能力，可以将无限域内的信息变换到一个指定的有限范围 内，然后输出。第二个要素是网络结构，根据神经元间的连接方式可分为前馈 ( f e e df 0 聊a r d ) 网络和反馈( f e e db a c k ) 网络，此外网络结构还包括所有的神经元的 1 2 河海大学硕士研究生论文道路网上连续最近邻查询方法研究 数量。第三个要素是学习方式，其作用是在网络结构和转移函数确定以后，对网 络权重进行调整。学习方式主要包括有导师学习和无导师学习两种：前者强调如 何调整权重，使得网络的实际输出与外部的期望输出尽可能一致；而后者重在通 过调整参数使得网络的实际输出能够反映样本的统计分布，常用于事物的分类研 究。 b p 误差反传神经网络( b a c k p r o p a g a t i o nn e i l r a ln e 咐o r l 【) 2 3 】是一个由一些 高度相关的处理单元所组成的计算系统，是一种具有三层或三层以上的阶层型神 经网络。最基本的b p 网是三层前馈网络，即：输入层、隐层、和输出层。上下层 之间各个神经元实行全连接，而每层各神经元之间无连接。网络结构如图2 3 所 示： 误差反俺 输 置 图2 4 b p 神经网络结构图 1 )处理单元：处理单元是神经网络的基本组成部分，输入层的处理单元 只是将输入值转入相邻的连接单元权重，隐层和输出层的处理单元只 是将它们的输入值求和并根据转移函数计算输出值； 2 )连接权重：连接权重是将神经网络中的处理单元联系起来，其值随各 个处理单元的连接程度而变化； 3 ) 层：神经网络一般具有输入层、隐含层和输出层； 4 )阈值：阈值可以使网络能更自由地获取所要描述的函数关系，其值可 为恒值或可变值； 5 )转移函数：转移函数通常为非线性函数，它是将输入的数据转换为输 出的处理单元。 b p 网的学习过程是由模式的正向传播和误差反向传播所组成。在正向传播 过程中，输入信息经隐含层单元逐层处理并传向输出层，如果输出层不能得到所 期望的输出，则转入反向传播过程，将实际值与网络输出之间的误差沿原来的连 接通路返回，通过修改各层神经元的连接权重使误差减小，然后再转入正向传播， 如此反复计算，直至误差小于设定值为止。 经过训练的神经网络提取了蕴藏在样本中的非线性关系，存储起来。在运行 阶段，当向神经网络输入非线性样本时，它便能完成从输入的n 维空间到输出的 河海大学硕士研究生论文 道路网上连续最近邻查询方法研究 m 维空间的非线性映射，从而正确描述无法用数学关系描述的规律。 b p 神经网络模型虽然结构简单容易编程仿真，但是也存在着其固有的缺点： 对于网络结构的确定，其隐层节点个数的选取，只能靠经验选取；由于数学角度上 的非线性优化，此网络结构存在局部极小值问题；此学习算法相比于其他算法收敛 速度慢很多，通常需要几千步迭代或者更多 2 4 ，2 5 】。 径向基i 沿f ( r a d i a lb a s i sf u n c t i o n ) 函数神经网络是j m 0 0 d y 和c d a r k e n 于 1 9 8 9 年提出的一种新型前向神经网络 2 6 】，与传统的插值型神经网络b p 网络相 比，具有计算速度快、满足全局最优化要求的优点，所以近年来开始引起人们的 重视，被引入到函数的逼近插值计算中，成为除b p 网络外的另一种重要的插值 神经网络 2 7 】。 下面给出r b f 神经网络和b p 神经网络的比较 2 8 ，2 9 】 1 ) 从网络结构上看，b p 神经网络实行全连接，i 氇f 神经网络输入层到隐含 层单元之间直接连接，隐含层到输出层实行全连接；b p 神经网络隐含层单元的 转移函数一般选择非线性函数( 如反正切函数) ，r b f 神经网络隐含层单元的转移 函数是关于中心对称的径向基函数( 如高斯函数) ：b p 神经网络是三层或三层以 上的静态前向神经网络，其隐含层和隐含层节点数不容易确定，没有普遍适用的 规律可循，一旦网络的结构确定下来，在训练阶段，网络结构将不再不变化， r b f 神经网络是三层静态前向神经网络，隐含层单元数也就是网络的结构可以 根据研究的具体问题，在训练阶段自适应地调整，这样网络的适用性就更好了。 2 ) 从训练算法上看，b p 神经网络需要确定的参数是连接权值和阈值，主要 的训练算法为b p 算法和改进的b p 算法，但b p 算法存在许多不足之处，主要 表现为易限于局部极小值，学习过程收敛速度慢，隐含层和隐含层节点数难以确 定。更为重要的是，一个新的b p 神经网络能否经过训练达到收敛，还与训练样 本的容量，选择的算法，以及事先确定的网络结构( 比如，输入节点、隐含层节 点、输出节点、隐含层节点以及输出节点的传递函数) 网络初始化、期望误差、 和训练步数有很大的关系，相同的训练数据，对于相同的网络，两次的训练出来 的网络，在运行阶段结果并不相同。这说明，b p 网络的训练与网络的设置以及 初始化有很大的关系。 目前，很多r b f 网络的训练算法支持在线和离线训练，可以动态确定网络 结构和隐含层单元的中心点和宽度，学习速度快，不会出现局部极小点问题，比 b p 算法表现出更好的性能。 3 ) 从网络资源的利用上看，由于i m f 网络原理、结构和学习算法的特殊性， 决定了其隐含层单元的分配可以根据训练样本的容量、类别和分布来分配隐含层 单元，如果采用最近邻聚类方式训练网络，网络隐含层单元的分配就只和训练样 本的分布及隐含层单元的宽度有关，和执行的任务无关：如果采用其它的训练方 法，中心点的分配也是主要由训练样本的分布决定，与执行的任务关系不是很紧 1 4 河海大学硕士研究生论文 道路网上连续最近邻查询方法研究 密。在隐含层单元分配的基础上，输入与输出之间的映射关系，通过调整隐含层 单元和输出单元之间的权值来实现的，这样不同的任务之间的影响就比较小，网 络的资源就可以得到充分的利用。这一点和b p 网完全不同，b p 网权值和阈