（地图学与地理信息系统专业论文）城市道路网络最短路径的统计学特征及实用算法研究.pdf

华东师范大学硕十学位论文 城i 道路网络最短路径的统计学特 i f 及实用算法研究 摘要 最短路径问题的研究在汽车实时导航、应急救援等领域有广泛的应用。经典的 d q k s t r a 算法是应用最短路径解决实际问题的理论基础。但是算法在具体的城市道路 网络中执行的效率比较低，无法满足实时高效的应用需求，因此国内外很多学者对 算法的优化与完善做出了深入的研究。 传统的优化算法在设计的过程中只考虑了抽象网络的拓扑特性，忽略了具体的 道路网络存在着空间特性。随着w 曲g i s 、移动g i s 与g p s 定位技术的结合，动态 路径规划将是今后的发展方向。动态路径规划需要通过i n t e m c t 获取实时的路况信 息、更新路段权值，再调用最短路径算法求解。传统的优化算法却没有考虑到传输、 更新的数据量对算法整体性能的影响。使用控制路网规模的方法能够克服传统方法 的不足，同时又可以与传统算法组合使用，进一步提高最短路径算法的性能。 本文用新的技术路线和方法对传统的最短路径问题进行了系统研究。通过对上 海地区随机抽取的最短路径统计特征的分析和样本路径空间分布特征的观察，构建 了适用于一般道路网络的椭圆模型和适合于上海道路特征的椭圆模型参数。该模型 将两点之间的最短路径搜索范围限定在椭圆范围内，这种算法大幅度减少了冗余节 点，减轻了网络传输实时路况数据的负担，提高了算法的性能和效率。使用椭圆模 型改进后的算法在理论上搜索扫描过的空间范围约为经典算法的1 5 。 同时，本文针对上海市道路网络，在大量随机抽样的基础上，研究了欧氏距离、 马氏距离和最短路径之间的关系。研究发现最短路径的长度分别与路径的起终点连 线的欧氏距离和马氏距离之间存在着显著的线性关系。通过回归分析，分别得到最 短路径长度与两者的直线回归方程。用欧氏距离拟合的最短路径长度与样本最短路 径长度的相对误差分布集中在一7 5 至7 5 之间，通过f 检验，在口= o o l 的置信水 平下显著。而使用马氏距离拟台精度偏低。因此，在只需要求解两点之间最短路径 长度的情况下，可以将两点连线的欧氏距离代八方程直接计算。 对于上海的道路刚，通过典型抽样选取有代表性的节点，将本文提出的椭圆模 型与经典的d i j k s t r a 算法、其他学者提出的限制搜索范围模型计算最短路径算法， 进行了准确度、搜索规模和搜索性能3 个方面的比较，结果表明：本文研究的椭圆 模型准确率达到9 9 8 ，搜索规模和算法执行时问分别为经典算法的5 0 和1 6 6 。 相比于另外两种椭圆模型，本文的椭圆模型比陆锋( 1 9 9 9 ) 的算法具有更高的效率， 比h u iw a n g ( 2 0 0 3 ) 的算法具有更高的准确性，综合性能比较结果，本文提出的椭圆 模型更好。 关键字：最短路径，椭圆模型，地理信息系统 华东师范大学硕十学位论文城市道路网络最短路径的统计学特征及实h j 算法研究 a b s t r a c t m a n ys t l l d i e so ns h o r t e s t - p a t ha l g o r i t l l l n sh a v eb e e nc o n d u c t e di n6 e l d so f r c a l - t i m e n a v i g a t i o nf 研a u t o m o b i l ea l l de m e 唱e n c ys u c c o lt h ed 司k s 订aa l g o r i 廿l i i l s ，c l a s s i c a l 锄d p r o f e s s i o n a l ，a r et h ea c a d e m i cb a s i so fc o n d u c t i n gt os o l v ep r o b l e m s a si t h a s1 0 w c o n d u c t e de m c i e n c yi nu r b a i lr o a d sn c t w o r ka 1 1 dm a yn o tm e e tt 1 1 er e q u i r e 】：n e n to f e h e c 石v ea n dr e a l t i m e ，m 卸yd o m e s t i ca i l di n t e r n a t i o n a ls c h o l a r sh a v em a d ed e 印 r e s e a r c ho n 曲p m v 血gt 1 1 ea l g o n t t l m s p e o p l er e s e a r c b i n go n 订a d m o n a l 叩t i m i z e da l g 面恤n so n l yr e a l i z e da b s h a c t n e 惭o r kt 叩0 1 0 9 yi 1 1t l l ep r o c e s so fd e s i g n ，s m v i n gf o ri m p m v i n ge f f e c t i v i t ) ro fm e a l g 训m m sm m u g hu p d a t i n gc o m p u t e rd a t as t n l c t u r eo ro p e r a t i o n a lr e s e a r c hp r o b l e m s ， w h i c hn e g l e c t i n gm ee x i s t i n g 印a t i a lc h a r a c t e r i s t i c si ns p c c m cr o a d sn e t w o r k w i t ht h e d e v e l 叩m e n to fw 曲g i s ，m o b i l eg i sa n dg p s ，d y i l 咖i cp a ml a y o u t 晰1 1b et 1 1 e 胁do f 如t u r ei n l p r o v e m e n t i tc a nb eo b t a i n e di n f o 皿a t i o no fr e a lt i m er o a d sc o n d i 石o n ，u p d a t i n g w e i g h tp f o p e n yo f t h ep a mb yi m e n l e ta i l dt 1 1 e nu s e 血es h o n e s t - p a ma l g o r i t h r n st ow o r k i to m h l s t e a d ，p e o p l ew h or e s e a r c ho nt r 甜i t i o n a lo p t i m i z e da l g o r i t l l m sd o n tc o n s i d 盯t h e a c c t i o no ft r a n s m m i n g 柚du p d a t i n gd a t aq u a n t i t yo nm ep e r f o m l a n c eo ft h ew h o l e a 1 酬t l l l m s t h e r e f o r e ，t 1 1 ea l g o r i t h m so fc 伽打o l l i n gs i z eo fm a d sn e t w o r k c a no v c r c o m e 也es h o r t a g eo fm e 锰a d i t i o n a la l g o r i t h m s ，w h i c hw i l le n h a n c em ee 岱w 虹v i t yo fm e s h o n e s tp a m sa l g o l j t l l m sb yc o m b i n i n go t h e ra i g o r i t h m s n e wt c c l l t l o l o g ya n dm e t l l o d si su s e df o r 咖d y i n gs h o r t e s tp a t hp m b l e mi nm i s a n i c l e t h ee 1 1 i p s em o d e l i sd e s i 印e db yr a n d o m l yt a k i n go u tm a dn o d e st oc a l c u i a t et 1 1 e s h o n e s t 巾a t l l 胁m es h a l l 曲a ir o a d sn e m o r k ，0 b s e r v i n g t l l e s p a t i a l d i s t r i b u t i o n c h a r a c t c r i s t i cf o rs t y l e b o o k ，a j l a l y z i n gt 1 1 es t a l i s t i cc h a r a c t e r i s t j c sf o rt l l es h o r t c s t - p a 廿1 t h em o d e ld e m a r c a t e d 1 er a n g eo fs e a r c h j n gt h es h o n e s t _ p a t ha l g o r i t t l m sw i m i nt h e e l l i p s e t h ee 1 1 i p s em o d e lc a ni m p r o v e 血es h o n e s t p a i l la l g o r i m m s ，f i l t r a t i i l gr c d u n d a l l t n o d e s ，r e d u c i n gm e m o r ys p e n d 访岛d e c r e a s i n gc a l c u l a t e dt i m e ，u p d a t i n gm ew e i 曲to f r e a lt i m ed a t at r a l l s m i s s i o n 丘d mt h em a d sn e t w o r ka 1 1 du p d a t i n gt h ep e 椭a n c ea 1 1 d e 骶c t i v i t yo fa 1 9 0 删 1 i i l s t h ea r e at h ci m p m v e ds h o n e s tp a t h sa l g o r i t h mu s i n gm ee l l i p s e m o d ds e a r c h e si so n e - f i m l so ft h ec l a s s i cd u k s t r aa l g o r i t h m b a s e do nr a n d o ms 锄p l ei ns h a n g h a ir o a d sn c t w o r k ，t h e r ei sal i n e a r i t yr e l a t i o n b e t w e e nm el e n g t ho ft h es h o r t e s tp a 山sa e l dt l l ee u c i i d e a nd i s t a l l c ea n dm em a 血a t t a i l d i s t a n c eo ft h eo r i g i na 1 1 dd e s t i n a t i o ni nt h ea n a l y s i so ft h es t a t i s t i cc h a r a c t e r i s t i cf o rt 1 1 e 华东j y i | j 范大学硕士学位论文城市道路网络最矩路径的统计学特征及实用算法研究 s h o n e s t - p a m s ，1 1 1 er e g r e s s i o ne q u a t i o ni sc o n c l u d e d ，t h ei n d e p e n d e n tv 撕a b l eo f w h i c hi s m ee u c l i d e a i ld i s t a l l c e ，a n d 廿l ed e p e n d e n tv 撕a b l ei st h el e l l g t l lo ft 1 1 es h o r t e s tp a t h s t h e r e l a t i v ee r r o r sb e 腑e e nt h er e s u l to ft h es i m l l l a t i o no ft h er e g r c s s i o n 柚dt h es a m p l e si s f i o m 一7 ，5 t o7 5 t h er e g r e s s i o ni sp m v c dt ob es i g n i f l c a n to nt l l el e v e l 岱= o 0 1b y f t e s t b u t 也ee 哟r so fu s i n gt 王l em a n h a t t a nd i s t a n e ea st h ei n d e p e n d e n tv 撕a b l ei s1 a r g 能 s oi nt h ec a s e 血a t0 n l yt h e1 c n g t l lo ft h es h o n c s tp a mi sn e e d e d ，w ec a nt a k ea d v 粕t a g co f 血e e u c l i d e a i ld i s t 锄c eb e t 、v e c nt 1 1 eo r i 百n 卸dd e s t i n a t i o na n dt 圭l er e g r e s s i o ne q u a t i o nt o c a l c u l a t e a tl a s t ，w eu s et h et y p i c a ls 枷p l et oc o m p a r et h ea c c l 】r a c y t h ed a t as i z eo fs e a r c h a n dm ee 如c t i v i t y 锄o n gm ee 1 1 i p s em o d di nt h i sa n i c l e ，t h cd i j k s 昀a l g 耐t h ma n dt h e o t h e rs h o r t e s tp a ms e a r c ha r e aa l g 谢t h m t h er e s u l ts h o w st h a t 血ea c c u r a c yo ft 1 1 e d l i p s m o d e li s9 9 8 ，t h ed a l ls i z ei s5 0 o f 出ed 巧k s 唿a l g o r i t h i n ，a n dt h ee x e c u t e d t i i n ei s1 6 6 o fm ec l a s s i ca l g o r i t l l m t h ee l l i p s em o d e l i nm i sa r t i c l ei sm o r ea c c u r a t c t h a nh u i 铀g sa l g o r i m m ，a 1 1 dm o r ee 鼠c t i v em a nl 1 lf e n g so e i ti sp r o v e dt ob et 1 1 e b e s tp e l l f o 加a n c eo f t l l et h r e ec o m p a r e da l g o 订m mi ns h a n 曲a i k e yw o r d s ： s h o r t e s tp a t h ，e 1 1 i p s em o d e l ，g 1 s i 学位论文独创性声明 本人所呈交的学位论文是我在导师的指导下进行的研究工作及取得的研究成 果。据我所知，除文中已经注明引用的内容外，本论文不包含其他个人已经发表或 撰写过的研究成果。对本文的研究做出重要贡献的个人和集体，均已在文中作了明 确说明并表示谢意。 作者签名：垄逖日期： 学位论文授权使用声明 猡6 占g 本人完全了解华东师范大学有关保留、使用学位论文的规定，学校 有权保留学位论文并向国家主管部门或其指定机构送交论文的电子版 和纸质版。有权将学位论文用于非赢利目的的少量复制并允许论文进入 学校图书馆被查阅。有权将学位论文的内容编入有关数据库进行检索。 有权将学位论文的标题和摘要汇编出版。保密的学位论文在解密后适用 本规定。 学位论文作者签名：酗q 醐 日期：可咿6 ( ，g：蕊 日期：趟叟：里” 华东师范人学硕士毕业论文 城市道路刚络最短路径的统计学特征及实用算法研究 第一章引言 1 1 研究背景 城市交通问题是2 0 世纪以来工业发达国家一直为之困扰的问题。汽车被广 泛地应用到各个行业领域，成为人们生活中不可或缺的工具，从而导致了城市交 通流量发生了前所未有的迅速增长。汽车在给人们生活带来便捷的同时，也给大 城市的交通事业带来了巨大的压力。在现代交通领域，当今世界各国的大城市无 不面临着交通拥堵、交通事故频发、交通环境恶化等的问题，为了提高交通运输 效率，智能交通系统( i n t e l l i g e l l tt r a n s p o r t a t i o ns y s t e f l l ，简写i t s ) 已成为该领域研 究的一个热点【1 。3 】。 路径规划在智能交通系统( i t s ) 中扮演着出行决策的重要角色。路径规划的 目的是向用户提供根据自己喜好选定的最优目标下的最佳路径信息，优化交通流 在整个网络上的分配。概括来说，路径规划的作用按照不同类型的用户可以分为 以下几个方面： 1 ) 对于个人用户出行而言，路径规划可以帮助用户规划行程，向用户提供 最优路径信息，从而带来时间的节约或是成本花费的降低。 2 ) 对于企业用户开展业务而言，比如速递业务或者物流配送多点送货，路 径规划可以帮助企业决策者科学地分配任务、规划合理的配送线路，提高配送效 率、降低运营成本，从而为企业带来巨大的经济效益。 3 ) 对于政府进行社会管理而言，比如突发公共事件应急方案的制定，路径 规划可以让政府决策者对突发事件做出快速响应，在最短的时间内到达事件现 场，多部门协调工作，选择最佳资源，使损失减少到最低，可以产生巨大的社会 效益。 城市交通路网中路径规划的核心思想就是最短路径算法。当城市道路网被 抽象为图论意义下的网络图时，最短路径问题就变成了网络图上的优化计算问 题。对最短路径问题的研究不但具有理沦意义，而且具有重要的应用价值。 1 1 1 最短路径的含义 在地理的网络分析中，针对实际应用环境的不同，路径规划中采用的具体 优化目标不同，最短路径常常可以代表多种不同的含义。一般而言，它主要指以 下三个方面的含义【4 】： 1 ) “纯距离”意义上的最短路径。例如，供货商需要运送批货物从仓库 发送到各个购货商手中，那么，究竟选择什么样的运输路线距离最短? 显然，这 单所渭的距离是指实际的里程数，即“纯距离”。 2 ) “经济距离”意义上的最短距离。例如，某公司在世界卜某1 0 大港口设 华东师范人学硕士毕业论文 城市道路网络攮短路衽的统计学特征及实用算法研究 有货栈，为了更好地适应市场供需形势，经常要在各港口之间运送各类货物。那 么，各个港口之间最廉价的货运线路是什么? 显然，这一问题就是“经济距离” 意义下的最短路径问题。 3 ) “时间距离”意义上的最短路径。例如，某家快递公司有一批急件需要 从城市某处送往另一处，那么在由城市交通网络中选择怎样的路线最节省时间， 可以在规定的时间内将快件送达目的地? 显然，这问题就是“时间距离”意义 下的最短路径。 以上三类问题，都可以抽象为同一类问题，即赋权网络图上的最短路径问 题。在这里，不同意义下的距离都被抽象为网络图中边的权值。针对不同的问题， 其距离( 权数) 与最短路径的含义各不相同。 1 1 2 最短路径搜索算法 最短路径问题按照起终点的数目大致可以分为3 类吼1 1 求解一个节点到 路网中所有其他节点的最短路径问题；2 ) 求解路网中特定两节点间的最短路径 问题；3 ) 求解路网中所有节点问的最短路径问题。 求解最短路径问题的算法有很多，传统的最短路径算法主要有f l o v d 算法、 矩阵算法和d i j k s t r a 算法等。其中f 1 0 y d 算法用于计算网络中每一对顶点之间的 最短路径；矩阵算法主要用于计算网络中每一对顶点之间的最短路径，并且可以 同时求出次短路径；d k s 仃a 算法用于计算一个源节点到所有其他节点的最短路 径。d i j k s t r a 算法是图论中求解最短路径问题的经典算法，由于其适应网络拓扑 的变化，性能稳定，因而在地理信息系统、智能交通系统和车辆导航系统中得到 广泛的应用【6 ，”。 不过，在实际应用中还要考虑道路的单行线、转向限制等问题。经过专家 学者研究，提出了基于交通禁忌的最短路径搜索算法，考虑交通路况实时变化的 动态路径搜索算法【8 l 。但是这些算法的理论基础依然是经典的d i 1 ( s 订a 算法。 1 1 3 最短路径算法的优化 d i j l ( s 仃a 算法是求解最短路径问题的基本方法，不过，从数据结构的知识我 们可以知道，d i ! i k s 仃a 算法的时间复杂度为o ( n 2 ) ，n 为节点总数 9 】。随着网络节 点数的增加，算法的时间复杂度以平方阶递增。因此，在节点数量很人的情况下， d i j k s t r a 算法的效率是非常低的【1 “”】，将它直接应用于道路刚的最短路径计算不 能满足实时高效的要求。 最短路径的计算需要高效率。在实际应用中，我们往往会碰到这样的问题： 1 ) 对于快递业务来说，接线员可能需要在短短的1 分钟内获取速递路线，从而 根据路线的长度给出客户报价；2 ) 对于实时导航来说，司机要求在行驶过程中 华东师范大学硕上毕业论文城市道路网络最短路径的统汁学特征及实用算法研究 通过汽车导航系统获取从当前位置到目的地的最优行驶路线，其要求的响应时问 可能只有几秒钟：3 ) 对于突发公共事件的应急救援来说，政府职能部门需要尽 快安排救援人员赶到事发现场开展救援工作，安排群众安全有序地离开事故现 场，做好应急预案和救援部署工作的重中之重是救援路线的制定务必要及时、合 理。由此可见，我们要解决实际生活中的最优路径问题，不仅要做到准确，更需 要快速及时。如果计算一条准确合理的路径没有合理的响应时间，那么需要快递 的客户可能已经不耐烦地挂断了电话；驾车的司机可能已经错过了本该拐弯的路 口；突发事件可能已经因为应急救援工作没有及时到位而造成不可挽回的损失。 使用经典的d t j k s t r a 算法，尽管可以保证找到最优路径，但是其执行效率却是非 常低下的，那样必然无法满足实际应用的需求。因此，d i i l ( s 仃a 算法及其它一般 的最短路径算法虽然在理论上是正确的，但在实际应用中却不尽人意。 最短路径的计算需要具有实时性。真正意义上的路径规划应该是在最优路 径计算过程中充分考虑路况的变化、道路的状态，为用户提供动态的、实时的最 优路径，从而使用户得到准确及时的出行参考，帮助用户规划行程，得到最合理 的出行路线，并在客观上起到优化交通流在整个路网上的分配。为了能够动态计 算交通网络中的实时最短路径，我们需要考虑实时数据传输和更新所花费的时 问，并且花费的这些时问在目前的硬件配置条件下在相对固定的情况下，我们只 有通过对最短路径的算法加以改进，提高其计算性能，从而使总花费控制在一定 的响应时间内，否则计算出来的最短路径对实际应用来说几乎是毫无意义的。在 过去的研究工作中，国内外研究者已经从以下几个方面着手尝试对最短路径算法 进行性能上的优化【1 3 j ： 1 1 基于数据存储结构的优化。 2 ) 基于搜索方式的优化。 3 ) 基于路网规模控制的优化。 4 ) 基于g i s 与空间数据库的优化。 1 2 研究目的与方法 在实际生活中，我们会碰到各种各样的路径规划问题。面对瞬息万变的城 市交通网络，我们需要根据实时路况选择一种快速、有效、可行的最优路径的算 法。冈此，本文的所要解决的关键问题就是对最短路径算法进行性能上的优化， 同时能够降低计算动态最短路径传输和更新实时路况数据的开销。 基于我们对城市道路网络的观察和同常生活知识，本文拟采用控制路网规 模的方法对最短路径算法进行优化，其研究的基本思路是： 1 ) 在实际城市道路网中对给定两点进行路径规划时，从起始点o 到目标点 d 的连线方向，基本上代表了最短路径的大致走向。而在靠近起始点和目标点附 华东师范大学坝：i ：牛业论文 城市道路网络品短路径的统计学特征及实用算法研究 近处，可能会出现短距离的反向路径，即落在o d 或d o 延长线上的路径。这在 实际生活中可以解释为我们般不愿意走“回头路”；但是在刚出发和快到达的 时候，车辆为了转入合适的车道而不得不走一段“同头路”，但是这段路通常不 会很长。因此，我们可以忽略路网中一些明显与起止点连线方向背离的节点，这 些节点不需要参与最短路径的计算。 2 ) 由于两点之间直线距离最短，那么最短路径一般都是分布在起止点连线 的两侧附近。这可以理解为我们在行程中一般不愿意“绕弯路”。最短路径通过 在道路网中每个节点的概率是不同的。越靠近起止点连线两侧的节点通过的概率 越高，反之则越低。因此，我们在计算最短路径时，可以考虑只选取那些最短路 径通过概率较高的节点参与计算，而概率接近于。的那些节点，则予以剔除。 3 ) 考虑到在实际应用中，我们并不一定要找到真f 意义上的“最短路径”。 因为真正的“最短路径”并没有多大的实际价值，道路交通状况存在着瞬时性和 随机性，上一分钟的“最短路径”在这一分钟可能已并非最短。在很多时候，我 们只要能够找到次优路径也已经足够满足实际应用的需求了【5 。因此，我们能够 接受算法存在着一定的误差，可以牺牲一定的精确度来换取算法效率的提高，从 而满足汽车实时导航、应急救援等对计算效率要求较高的应用。 本文研究是以g i s 技术为基础，利用统计学的方法来对最短路径搜索的路 网规模做出控制，通过限制搜索区域过滤掉那些对计算最短路径无用的冗余节 点，但要保证计算结果的准确合理。 最短路径的研究本身就属于一个空间的范畴，我们不能忽略它的空间特性。 g i s 技术的发展为最短路径研究和路径规划系统的开发创造了有利的条件。g i s 从最初的电子地图发展至如今的w 曲g i s ，移动g i s 和“3 s ”集成技术f g i s ，g p s ， r s ) ，g i s 技术已经不仅可以为最短路径的计算、路径规划提供地理信息的支持， 并为用户提供直观的可视化操作环境，而且使汽车实时导航、动态规划路径成为 了可能 1 “。如果没有g i s 技术，最短路径问题的研究将只能停留在理论上，而 无法付诸于实际的应用。因此，g i s 技术是研究和使用最短路径算法的必不可少 的基础性工具。 统计学是一门研究如何根据事物的随机性规律柬收集、分析数据并利用于 进行推断的科学。地理学中的统计分析方法，是现代地理学发展史上计量革命的 主要成果之，是建立在概率论与数理统计基础上的一类地理数学方法，适用于 各种随机现象、随机过程和随机事件的处理。而儿乎所有的地理现象、地理过程 和地理事件都具有一定的随机性，这是由于地理学研究对象的复杂性所决定的。 由此可见，统计分析方法是现代地理学中最基本和必不可少的+ 类数学方法。总 而言之，统计学的目的就是为了从已知的数据找到数据之间内在的联系，从而对 4 华东师范火学硕士毕业论文城市道路嘲络最短路径的统计学特征及实用算法研究 未知数据进行预测或判断【4 l 。因此，我们使用统计学的方法米研究最短路径问题 也是为了能够从样本数据中总结出计算搜索范围的方法，并且可以将其推广到所 有的最短路径计算中去。 1 3 论文框架 根据本文的研究目的与思路，将在下而的章节中做出以下研究和探索： 在第二章中，本文归纳总结了一般最短路径问题的一些基本概念和求解思 路，总结了经典最短路径算法的优势和不足，根据实际应用的需求指出了优化算 法的必要性，并对目前已有的算法优化方法做出综述。根据最短路径算法研究的 发展方向，路网规模控制方法对最短路径算法的性能优化具有实际的意义，其中 重点列举了几种具有代表性的椭圆模型算法。 在第三章中本文以上海市的道路网络为基础，对任意道路节点对的最短路 径做大样本的随机抽样，研究样本最短路径的统计特征和空间分布特征。论证了 通过回归方程直接求解最短路径长度的可行性，给出回归方程；利用统计分析的 方法，构建椭圆模型限制最短路径搜索范围，控制搜索的路网规模，以达到节省 数据传输和更新的开销、提高算法效率的目的。 在第四章中本文通过典型抽样的方法抽取上海市外环线内具有代表性的节 点评价本文所提出的椭圆模型的准确性、搜索规模与搜索性能，并与经典的 d i k s 廿a 算法、目前已有的椭圆模型算法进行比较，测试其在上海地区的适用性。 第五章对本文的研究方法和得出的结论进行总结，并对可能存在的问题进 一步地研究做出展望。 1 4 小结 本节首先介绍了本文的选题背景，指出路径规划的意义所在。接着简要叙 述了最短路径问题和求解最短路径的算法以及算法中存在的不足之处。最后，提 出本文的研究目标和方法，简要叙述了论文的框架。本文将以g i s 技术为基础， 用统计学的方法来确定最短路径的搜索范围，提高计算效率，快速求解最短路径。 并与已有的限制搜索区域的最短路径算法比较准确度、搜索规模与搜索性能，评 价其对于上海道路网的适用性。 华东帅范大学硬上毕业论文 城市道路网络昂短路径的统计学特征及实用算法研究 第二章关于最短路径问题的研究 城市的道路网中任意两点都是连通的。从起点到终点可以选择不同的路线， 但是花费是各不相l 司的，从中我们想要找出一条花费最少的路线，这就是最短路 径问题。最短路径问题一直是运筹学、交通运输学、地理信息科学等学科的研究 热点【l ，国内外很多学者长期以来都对此做出过深入的研究。经典的图论、不 断完善发展的计算机数据结构及算法以及与g i s 技术的有效结合使得新的最短 路径算法不断涌现，它们在空问复杂度、时问复杂度及应用范围等方面各具特色 【1 5 17 一 2 1 道路网络描述、存储与搜索策略 最短路径搜索问题总的解决思路大致可分为以下几步1 8 】： 1 ) 路网抽象将道路网以图论的方法描述，并以一定的数据结构存储在计 算机中。 2 ) 道路权重的标定根据不同的最优目标，确定道路权重。 3 1 按照一定的搜索策略、应用一定的算法求解最短路径问题。 2 1 1 道路网络的图论描述 路网通常被抽象为图论中的“图”。图的定义如图2 1 所示，其定义如下： 设v 是一个由n 卜点v ( i - l ，2 ，n ) 所组成的集合，即v = v l ，v 2 ， v 。 ，e 是一个由m 条线e ，( i = 1 ，2 ，m ) 组成的集合，即p e l ，e 2 ， e 。 ，而且e 中任意一条线都是以v 中的点为端点；任意两条线除端点外没有其 他的公共点。那么，把v 与e 结合在一起就构成了一个图g ，记作g = f v ，e 1 。 v 中的每一个点v ( i = 1 ，2 ，n ) 称为g 的顶点，e 中的每一条线e 。( i _ l ，2 ， m ) 称为g 的边，若一条边e 连接u ，v 两个顶点，则记为e = ( u ，v ) 。 v 图2 1 路网抽象 6 4 华东师范人学硕士毕、l k 论文城市道路嘲络最短路径的统计学特和。及实用算法研究 在城市交通网络中，地理位置、地理实体等即可抽象为点，而道路则可以被 抽象为连接点与点的连线。因此，就可建立路网与图的一一对应关系： 1 ) 节点( n o d e ，记做n ) ：道路的交叉口或断头路的终点。 2 ) 边( e d g e ，记做e ) 弧( a r c ，记做a ) ：两节点之间的路段称为边：如 果规定了路段的方向，则称为弧。 3 ) 边( 口& ) 的权( w 萌曲t ，记做w ) ：是路段某个或某些特征属性的量化表 示。根据不同的最优目标，可以选择不同的路段属性，如路段长度、路段平均行 程时间等作为该路段对应的边( 弧) 的权，或称为道路权重。 2 1 2 道路网络存储 图的存储表示方法很多，主要有邻接矩阵、邻接表、十字链表、邻接多重 表等。具体选择哪一种存储结构，主要取决于具体的应用和欲施加的操作【1 9 】。 邻接矩阵和邻接表是图的两种最常用的存储结构 9 】。它们各有所长，下面从 空间及执行某些常用操作的时间两个方面来做一比较。 对于一个具有n 个顶点e 条边的图g ，若g 是无向图，则它的邻接表表示 中有n 个顶点和2 e 个边表节点；若g 是有向图，则它的邻接表表示中有n 个顶 点表和e 个边表节点。因此邻接表的空间复杂度s ( n ，e ) = o ( i l + e ) ；而邻接矩阵的空 问复杂度s ( n ) = o ( n 2 ) 吲。若图中边的数目远远小于顶点数的平方( 即e n 2 ) ，此类 i 蛩称作稀疏图( s p a r s eg r a p h ) ，这时用邻接表表示比用邻接矩阵表示节省空间( 节 省邻接矩阵中o 元素的存储空间) ；若e 接近于n 2 f 准确地说，无向图e 接近于 n ；( n 一1 ) 2 ，有向图e 接近于n + ( n 1 ) ，此类i 訇称作稠密图( d e i l s eg r a p h ) ) ，考虑到 邻接表中要附加链域，则应取邻接矩阵表示法为宜 7 】0 城市道路网中可看作是稀 疏图，因为道路数e 远远小于n 2 ，因此本文主张使用邻接表来存储城市道路网。 如果使用邻接矩阵表示的话，那就需要在计算机内存中开辟n + n 的数组来存储整 个城市道路网，但道路节点数n 往往会达到几十万，几百万，这就将造成可怕的 “维数灾” 】3 】。 表2 1 列出了4 种存储结构的实现方法、优缺点和时间复杂度。 华东帅范大学硕上毕业论文城市道路网络最短路径的统计学特征及实用算法研究 职转滋魏露经魄斑谈找辫辅颦祭陵 刽镶糖缚，疆数臻 i 辚蹦麓捌点鳓魏棼幕 l 掰絮燃盖 o f 目n ) 2 翳求辫臻点豹瞧 糍键黢 键是 i 。蒋钉巾鹅 i ， 瓣蛾糍霸，i 乏鬻0 n * m ) 娃 2 薅辩鳓壤点神辩凄 棼舞菘0 # 8 ) 2 攀耪瓣劁臻囊豹 l 躞 窜骧枯镳麓 j ，警蠲甏骥精小 拣搦较簸踽籁铝援鬣 2 + 撼毒辩臻褒麴：箍麓榭 入魔 嚣接茹熬鞭畿 l ，餐卷察摊 绪秘嫒篁激醐舔攘袭 溢盏嚣辩翔麟鲻盎意鲥辩 饕豢 表2 1 存储结构比较 2 1 3 图的搜索策略 最短路径的搜索过程是按照一定的搜索策略去遍历图中的顶点。常用的搜 索策略有三种：深度优先搜索策略、广度优先搜索策略和启发式搜索策略。 深度优先搜索( d 印t h f i r s ts e a r c h ) 是指在给定的图g 中初态是所有的顶点均 未曾访问过，任选一顶点v i 为初始出发点，并将其标记为已访问过，然后依次从 v i 出发搜索v i 的每一个邻接点v 1 ，若v 未曾访问过，则以v 1 为新的出发点继续进 行搜索。上述搜索法是递归定义的，它的特点是尽可能先对纵深方向进行搜索， 故称之为深度优先搜索。 广度优先搜索( b r e a d m f i r s ts e a r 的基本思想是：设罔g 的初态是所有顶 点未曾访问过，在g 中任选一个顶点v 为初始出发点，将其标记为访问过，然 后依次访问v i 的所有邻接点w l ，w 2 ，w t ，然后再次访问与w l ，w 2 ， w ；邻接的所有未曾访问过的顶点，依此类推，直至图巾所有和出发点v i 有路径 相通的顶点都已访问到为止。上述搜索法的特t i 是尽可能先对横向进行搜索，故 称之为广度优先搜索。 无论是广度优先还是深度优先搜索，归根结底采用的都是穷举的搜索策略， 没有采取一定的方法对搜索规模进行控制，对于大规模的网络图，由于路径组合 爆炸而导致搜索效率极其低下。 启发式搜索( h e 嘶s t i cs e a r c h ) 是基于知识的搜索策略，其优先搜索到达目标 点可能性较大的节点，从而达到减少搜索空问，加速收敛的目的。多种启发策略 华东师范大学硕士毕业论文 城市道路网络虽短路径的统计学特征及实用算法研究 相结合可以增加搜索效率。目前，启发式搜索包括最佳优先搜索、存储界限搜索 和迭代渐近算法如爬山搜索和模拟退火方法等。 2 2 最短路径的算法 路径搜索通用技术又可分为组合技术和代数方法2 种。组合技术主要是指 标号算法( l a b e l i n g a l g o r i t h m s ) 。标号算法也是绝大多数最短路径算法的核心部分 阻2 。按照不同的标识节点处理策略，标号算法又可分为标号设定( l a b e ls e t t i n g ， 简称l s ) 和标号改正( l a b e lc o 玎e c t i n g ，简称l c ) 两大体系。代数方法是通过运筹 学中的线性规划、所定义代数系统中的联立线性方程组和矩阵乘法等方法来求解 最短路径问题u “。 l s 算法又称为最短优先搜索算法，最早由荷兰数学家d i i k s t r a 于1 9 5 9 年提 出【2 3 】。d i j l ( s t r a 算法的广泛应用使之已成了l s 算法的代名词口4 1 。其他l s 算法多 为d i j k s t r a 算法的不同实现方式。l c 算法又称为列表搜索算法。其代表性算法 包括b d l m a n f o r d - m o o r e 算法( q u e u e ) 、d e s o p o p a p e 算法( d e q u e ) 、s l f 算法 2 4 】、 p a l l o 砸n o 算法( 2 q u e ) 【2 5 1 、门限算法 2 6 】和拓扑排列算法 2 7 】等。 2 2 1d i j k s t r a 算法及其实用性 d i j k s t r a 算法是目前公认的求解最短路径问题的经典算法【1 3 1 2 孙。其基本思想 是从起点出发，逐步地向外探寻最短路径，执行过程中，与每个点对应，记录下 一个数( 称为这个点的标号) ，它或者表示从起点到该点的最短路的权( 称为p 标 号) 、或者是从起点到该点的最短路径的权的上界( 称为t 标号) ，方法的每一 步是修改t 标号，并且把某一个具有t 标号的点改变为具有p 标号的点，从 而使有向图g 中具有p 标号的顶点数多一个。这样，至多经过n 1 步，就可 以求出从起点到其他各节点的最短路径。 d i i k s t r a 算法可以适用的网络类型非常广泛，性能也相当稳定，对于连通图 来说，能够确保求得任意两点之间的最短路径，因此是路径规划和车辆调度的理 论基础，在地理信息系统、智能交通系统和车辆导航系统中得到广泛的应用。但 是，d i l k s t r a 算法不能直接应用到实际中，因为其对空问存储的要求较高，算法 的执行效率相对低下，无法满足实时性的要求。 首先，d i j k s 虹a 算法是的主要思想是按节点距起点距离递增顺序产生最短距 离的过程，该方法实际l 构造了一棵以起点为根的最短路径树 28 1 。即使在构造 路径树的过程在到达终点后结束，使终点位于最短路径树的叶节点上，依然有大 量的计算冗余。这主要归【捌于算法的全向搜索 2 9 】。这是因为d i j k s 仃a 算法是基于 抽象网络的算法，它只考虑了网络的拓扑特性，而忽略了空间分布特性，在最短 路径的搜索过程中缺乏方向性，随时准备向四面八方扩展。这样导致了最终扫描 华东师范人学硕i ，毕业岔文城市道路网络蛙觚路径的统计学特征及实用算法研究 过的搜索区域基本上足以起点为圆心，起点与终点连线长度为半径的圆【2 。如 果起点与终点的距离越氏，那么搜索覆盖的范围也就越大。从计算过程来看，当 采用最原始的无序联结表作为运行结构时，d i i k s t r a 算法的时间复杂度为o ( n 2 ) ， 其中n 为节点个数，当道路网中节点总数较多的时候，这无疑将成为d 肚s t r a 算 法的瓶颈 3 0 。 其次，各个路段上的交通状况是动态变化的。对于同一个路段，高峰时段 通过所花费的时间显然要大于甚至远远大于普通时段时通过所花费的时间。因 此，路段的权值是随着交通状况的改变而动态变化的。d i k s 仃a 算法是基于一般 的网络拓扑结构的，对于权值的确定并没有任何描述。所以说，d i i k s 仕a 算法在 计算过程中忽视了路段的权值是动态变化的，其计算结果只是静态的最短路径。 也就是说，不管在哪个时段内，只要起点与终点一样，求解得到的最短路径都是 同一条。显然，这并不符合我们日常生活的实际需求。这样不仅无助于路径的规 划、方便大家的出行、交通状况的改善，结果反而会适得其反。大家都选择同一 线路导致该线路过度拥挤，最优路径反而成为最差路径，甚至造成交通的瘫痪。 因此，最短路径的获取必须是在动态确定道路权值的基础上计算而得。为了确保 这种实时性，我们在设计使用最短路径算法时就必须有后台的交通信息数据库的 支持。在计算机网络技术与数据库技术都已相当成熟的时代，我们可以通过网络 传输获取实时的路况信息，随后更新路段权值，最后调用最短路径算法求解。但 是在计算数据量较大的情况下，传输与更新数据又不可避免地增加了求解最短路 径花