交通网络限制搜索区域时间最短路径算法

交通网络限制搜索区域时间最短路径算法 () () V o l. 4 A , N o. 10 中国图象图形学报第4卷 A 版第10期 O c t. 1999 1999年10月Jo u rn a l o f Im age an d G rap h ic s 交通网络限制搜索区域时间最短路径算法 陆锋卢冬梅崔伟宏 ( ) 中国科学院遥感应用研究所, 北京 100101 摘 要 在基于四叉堆优先级队列的改进型最短路径算法的基础上, 进一步提出了利用交通网络的空间分 D ijk st ra 布及方位特征构造限制区域的时间最短路径算法。在对城市交通网络空间分布特征进行统计 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 的基础上, 针对具 体的起、终节点, 设定合理的椭圆限制搜索区域, 以减少算法的搜索规模。针对椭圆限制搜索区域算法由于计算量大 而效率不高的弱点, 提出了矩形限制搜索区域算法, 达到既减小算法搜索规模, 又提高算法运行效率的目的。试验结 果显示了本文提出的限制搜索区域算法的合理性与有效性。 关键词 最短路径算法 交通网络 限制区域 地理信息系统 值得注意的是, 考虑到道路等级、交通状况等因 素, 距离最短路径并不一定所耗时间最短, 在城市街 0 引言 区构成的交通网络中, 由于街道的拥挤程度、路面状 况、车道数及其在道路交叉口转弯所耗时间的不同, 最短路径问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 一直是计算机科学、运筹学、交通 工程 路基工程安全技术交底工程项目施工成本控制工程量增项单年度零星工程技术标正投影法基本原理 学、地理信息学等学科的一个研究热点。经典的 更使得距离最短路径与时间最短路径之间存在差 图论与不断发展完善的计算机数据结构及算法的有 异。而时间最短路径对城市交通显然更有意义。本文 效结合使得新的最短路径算法不断涌现, 各具特 中所实现的最短路径算法为时间最短路径算法。 1- 6 色。由于这些算法主要诞生于计算机科学及运 时间最短路径算法的实现较之距离最短路径复筹学领域, 在算法的设计过程中只考虑了抽象网络 杂。除了考虑弧段的时间阻抗外, 还需考虑道路交叉 的拓扑特性, 力求通过各种新型的计算机数据结构 口的等待时间, 即转弯阻抗。除作者在文献7 中所 和运筹学方法, 从理论上减少算法的时间复杂度, 而 描述的数据结构外, 道路的转弯阻抗信息用链 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 数 忽略了具体的网络可能具有的空间分布特性。而这 据结构来实现, 如表1所示。 一点正是描述交通网络结构的稀疏图与其它描述拓 表1 转弯阻抗数据结构 扑结构的平面图的根本区别所在。如何有效利用交 通网络空间分布特性对最短路径算法进行改进, 以 2. N o deid T u rn noF no de T no de Im p edance 减少算法的搜索规模, 提高算法运行效率, 是本文所 1 f n , f n,tn , tn ,im p , im p ,tn 1112 1112 1112 1 要探讨的问题。 , ,, ,, ,2 f n 21f n22 tn 21tn 22 im p 21im p 22 tn 2 , ,, ,, ,f ns1f ns2 tns1tns2 im p s1im p s2 s tns 1 算法实现 考虑转弯阻抗的时间最短路径算法与距离最短 路径算法实现方法类似, 区别在于时间最短路径算 法需在启发策略的优化条件中加入节点转 B e llm an 1. 1 数据结构弯的时间阻抗因子, 以决定节点的累计权值。 算法采用四叉堆优先级队列作为运行数据结 1. 2 椭圆限制搜索区域算法构, 采用逆邻接表作为网络拓扑数据结构, 以改进型 算法作为单源最短路径的实现方法。基于 D ijk st ra 产生于计算机科学及运筹学的最短路径算法,四叉堆优先级队列及逆邻接表的改进型算 D ijk st ra 因只考虑网络的拓扑特征或阶段特征, 而忽略了网 法作者已在文献7 中详细描述, 在此不再赘述。 络的空间分布特征, 使得其搜索过程缺乏方向性, 得 收稿日期: 1999201220; 收到修改稿日期: 1999207226 到的是一棵以起点为根的最短路径树。即使构造此考虑。 8 , 椭 圆算法最早见于文献 路径树的过程在到达终止节点后即结束, 使终止节 在文献9 、10 点位于最短路径树的叶节点上, 依然有大量的计算 中又得到应用和发展。算法中椭圆限制的关键是解是冗余的。这主要归因于算法的全向搜索。 求合适的椭圆长轴, 以结合起终点坐标构造限 M D 制椭圆。我们采用统计分析方法完成这一工作。 我们知道, 给定了一定的起始与终止节点, 也就 决定了最短路径所对应的大致极限距离。由此 M D 首先, 在交通网络节点集合中系统抽取具有代可构造出以起点为中心、为半径的圆。以起点为 M D 表性的一定数目的节点, 构造两个节点集合 与A 原点、由极限距离所决定的地理服务范围内的节点 B 。则其笛卡尔乘积为集合是圆内节点集合的真子集。而圆外的节点由于 ) () () (C = A ×B = { a , b| a ?A ? b ?B }已超出了所估计的极大距离, 在算法中可不予考虑。 更进一步, 设节点 至起点 、终点 的欧氏 距离中的每个元素可看成是待求最短路径的起终节 N S G C 分别为|| 与|| , 我们可以把判断条件改S N N G 点, 其欧氏距离为 , 时间最短路径所对应长度为E ab 为 + > , 的临界点构成了以 、|||| S N N G M D N S G , 则可设比值系数 = ƒ。对于所抽取样P ab R ab P ab E ab为焦点, 以为长轴的椭圆, 如图1 所示。其直观 M D 本, 可得到比值系数集合 R , 对 R 中元素进行统计意义为, 即使在 与、与 之间存在直线路径, S N N G 中总数为满足分析, 可以得到某一特定值 , 使得 ΣR由于二者之和已经大于所估计的 至 的最短路S G 一定置信水平的元素, 其值不大于 。因此, 我们就 Σ 径的极大值, 在算法运行过程中对此节点不予M D 可以用 作为乘常数, 利用起、终点坐标求得椭圆长 Σ 轴。M D 图1 椭圆限制搜索区域图2 样本元素比值系数分布 以北京市为例, 我们在北京市交通网络中系统, 仍需执行大量的乘积与开方计知的变形椭圆方法 算, 占用较多的时间。若最佳路径算法采用早期的深 地抽取400个节点, 构造了集合、。则 中共包括A B C 度优先搜索算法, 因其在子树的搜索与计算上需耗 4 0 0 0 0 个元素。对 C 中的每个元素分别解求 E ab、 费大量时间, 这时椭圆限制搜索区域算法相对表现 与 值, 然后对 组成的集合 进行统计,P ab R ab R ab R 出较好的效率。而若采用作者在文献7 中所提出的 得到在9 5 ? 的置信水平下, 1. 3 7 9。图2 为 约为 Σ C 基于四叉堆优先级队列及逆邻接表的改进型 D ijk 2 中元素所对应的时间最短路径长度 与欧氏距P 陆 锋等: 交通网络限制搜索区域时间最短路径算法851 第10期 的极值分别为 1. 3 矩形限制搜索区域算法2 2 2 2 x m = a ? A co sΗ+ B sin Η()4 针对椭圆限制搜索区域算法效率不高的缺点,2 2 2 2 y = m b ? A sin Η+ B co sΗ我们提出矩形限制搜索区域算法。它既继承了椭圆 由 、的极值所对应的切线即构成了椭圆的最小 x y 搜索算法对搜索规模合理地进行限制的思想, 又避 包含矩形。如图3所示。免了算法中大量的乘积与开方计算, 具有较椭圆搜 索算法更高的效率。其基本思想为求出限制椭圆的 最小包含矩形, 以此作为限制区域, 以减少算法的搜 索规模。 在椭圆限制搜索算法中, 得到乘常数 后, 由起 Σ ()() 终节点坐标 , 、, 可得椭圆方程为: x s y s x g y g 2 () () c o sΗx - a + sin Ηy - b] + 2 A 2 () () - s in Ηx - a + co sΗy - b] ()= 1 1 2 B 其中: y + y y s x + x s gy -s g g ) ,( a = ,b = Η= a rc tg 图3 矩形限制搜索区域x - 2 2 g x s ()2 以椭圆的最小包含矩形作为限制搜索区域, 对 Σ 2 2新扩展出的节点, 判断其是否落在限制搜索区域内, ) ) ((y +x A = y g -s x g -s 2 只需将其坐标与矩形边界进行比较即可, 不需要其 ()3 2 2 ()() + y g - y s x g - x s 2 它复杂运算。基于矩形限制的时间最短路径算法伪 A - B = 4 码描述如下。 得到椭圆方程后, 分别对 , 求偏导数, 可得 , x y x y = 0; [ = ;[ D v 0 f ina lv 0 T RU E () ;m ak e- h eap A ( ) = 0; < + + ƒƒ将 邻接节点对应权值插入堆中 ; fo r iiv 0 ad j- num iv 0 - ) (; , [ [ h eap - in se r t A D v 0 ad ji- () e llip sep a ram e te r ; 由 u , u , v , v , Σ 计算A , B , a , b, Η, 构造椭圆方程 ƒƒ- 0x 0y 0x 0y () ƒƒ计算 , , , , 构造限制矩形; rec tang le- p a ram e te r x m in x m ax y m in y m ax ( ) = 1; < ; + + {fo r iini ) (, ;ƒƒ从堆中抽出权值最小节点, 标识为已处理节点 h eap - ex t rac t- m in A v ) () )((if ! v > x && v < x && v > y && v < y x m in x m ax y m in y m ax ƒƒ判断节点是否落在限制矩形内 co n t inue; () = = ; 到达终点后退出 ƒƒif v u 0 b reak = ;[ f ina lv T RU E () = 0; < ; + + {fo r w w v - ad j- num w ()= [ . []. ƒƒ寻找 对应路段; edgeN o de Info v f ir st w index- w ayvw () = = [ . ƒƒ决定路段方向阻抗if v W ay Info edge fno de = [ . [ [;c v v - ad jw W ay Info edge f t- im p e lse [ = [ . [;c v v - ad jw W ay Info edge tf- im p = 0;tu rn- im p ( ) = 0; < [ . + + { 决定节点转弯阻抗; ƒƒfo r j j N o deT u rn v num - tu rnj ( () . = = [ ][ [ if N o deT u rn v f r- no de j F a th e r v && () ) [ . = =[ { N o deT u rn v to _ no de j w () tu rn- im p = [ . [ ]; N o deT u rn v im p j ;b reak } } ) ) ({ ! [ [(+[< [ [if f ina lv - ad jw + [ [ - ad jw tu rn- im p D v - ad jw v && D v c v ƒƒ所耗费时间下降 () = ={ ƒƒ未插入堆中的节点 [ [if D v - ad jw IN F IN IT Y = [ + [ +[ [[;D v - ad jw D v c v v - ad jw tu rn - im p ) (; , [ [H eap - in se r t A D v - ad jw } { ƒƒ已插入堆中但需松弛节点e lse = [ + [ + [ [[D v - ad jw D v c v v - ad jw - im p; tu rn (, , [ [H eap - dec rea se- k ey A po sD v - ad jw ) ; } } } } 当起终节点之间方位角 = 2 时, 限制矩形 ƒΗk Π 。虽然搜索范围有所扩大, 但从下27. 32% - 36. 29% 面积取得最小值, 为4。此时限制矩形与限制椭圆 A B 面的分析可以看出, 这种代价仍然是值得的。面积比值为: S 矩 4 2 算法效率分析== 1. 2732 S Π 椭 ( ) 当 = 2+ 14时, 限制矩形面积取得最大 ƒΗk Π 为验证椭圆限制搜索区域算法与矩形限制搜索2 2 ) (值, 为2 + , 此时限制矩形与限制椭圆面积比 A B 区域算法的效率, 我们在北京市交通网络的中心及 值为: 边缘区域随机抽取6 组共60 个节点, 各区域分别以 2 S 矩4Σ- 2 , l r 表示, 计算各组节点之间无cc1 cc2 , R u l , R u r , R l l , R R R =2 S 椭 ΠΣ Σ- 1p 限制区域、椭圆限制区域及矩形限制区域下的时间 时, 比值为1. 3629。即矩形限制搜索区1. 379= 当 Σ最短路径耗费 时间, 结果如表2所示。C PU 域算法较之椭圆限制搜索区域算法扩大搜索范围 () 单位 ƒ1000次 表2 不同限制区域下样本最短路径算法平均运行时间比较s - - - - - - - - R cc1R u l R cc1 R l r R cc1R cc2 R u l R u r R u l R cc1 R u lR ll R u l R lr R ll R u r 无区域限制127 104 36 81 75 111 130 120 椭圆限制 70 41 19 41 59 111 136 134 矩形限制 68 42 18 38 58 95 120 115 可以看出, 当起点位于网络中心区域, 算法搜索, 由于矩形限制算法较之椭圆限制算限制算法。此外 范围可向多方向扩展时, 椭圆限制算法与矩形限制法增大了搜索范围, 从而进一步提高了最短路径一 陆 锋等: 交通网络限制搜索区域时间最短路径算法853 第10期 . r ithm s fo r th e sho r te st p a th p ro b lemJo u rna l o f th e A sso c ia t io n2 交通网络结构的稀疏图与其它描述拓扑结构的平面( ) fo r Com p u t ing M ach ine ry, 1990, 37 2: 213, 223. 图的根本区别所在。本文中, 我们提出了利用交通网 O rda A , Rom R. Sho r te st2p a th and m in im um 2de lay a lgo r ithm s 5 络的空间分布特征构造限制搜索区域的时间最短路 in ne tw o rk s w ith t im e2dep enden t edge2leng th. Jo u rna l o f th e A s2 径算法。在对城市交通网络空间分布特征进行统计 ( ) , 625., 1990, 37 3: 607so c ia t io n fo r Com p u t ing M ach ine ry 分析的基础上, 针对选定的起、终节点, 我们首先利 , , . C h e rk a ssk y B V Go ldbe rg A V R adzik TSho r te st p a th s a lgo 2 6 用椭圆算法设定合理的椭圆限制搜索区域, 并在此 : . r ithm sT h eo ry and exp e r im en ta l eva lua t io nM a th em a t ica l P ro 2 基础上进一步提出矩形限制搜索区域, 从而有效地 , 174., 1996, 73: 129g ramm ing 减少了算法的搜索规模, 提高了运行效率。试验结果 陆 锋, 卢冬梅, 崔伟宏, 基于四叉堆优先级队列及逆邻接表的改7 显示了本文提出的限制搜索区域时间最短路径算法 ( )进型算法. 中国图象图形学报待发表.D ijk st ra 的合理性与有效性。 , . S t ig N o rdbeck B eng t R y sted tCom p u te r C a r to g rap h y Sho r te st 8 . : , 1969.Ro u te P ro g ram sSw edenT h e Ro ya l U n ive r sity o f L und 崔伟宏. 空间数据结构研究, 北京: 中国科学技术出版社, 1995. 9 参 考 文 献 10 陈行星, 崔伟宏. 城市快速反应系统实验研究. 环境遥感, 1996, ( ) 11 3: 227, 233. , . 1 H ung M SD ivo k y J JA com p u ta t io na l study o f eff ic ien t sho r t2 . , 1988,e st p a th a lgo r ithm sCom p u te r s and O p e ra t io n s R e sea rch 15: 567, 576. 陆 锋 1991年毕业于武汉测绘科 技大学航测与遥感系摄影测量与遥感专 . B e r t sek a s D PA S im p le and fa st labe l co r rec t ing a lgo r ithm fo r 2 业, 现于中国科学院遥感应用研究所攻 . , 1993, 23: 703, 709.sho r te st p a th sN e tw o rk s 读博士学位。主要从事地理信息系统及 , . F redm an M L T a r jan R EF ibo nacc i h eap s and th e ir u se s in im 2 3 全球定位系统的应用研究。 . p ro ved ne tw o rk op t im iza t io n a lgo r ithm sJo u rna l o f th e A sso c ia2 ( ) , 615., 1987, 34 3: 596t io n fo r Com p u t ing M ach ine ry , , , . 2A h u ja R K M eh lho rn K O r lin J B T a r jan R EF a ste r a lgo 4 卢冬梅 1992年毕业于北京计算机学院软件工程专业,1962年毕业于莫斯科测绘大学, 现为中国科学崔伟宏 现为中国科学院遥感应用研究所助理研究员, 研究方向为全 院遥感应用研究所研究员, 博士生导师。研究方向主要包括 球定位系统应用系统开发。 地理信息系统、空间数据结构、空间决策支持系统、全球定位 系统应用及农业信息网络等。 T im e Shor te st Pa th A lgor ithm f or Re str ic ted Sea rch in g A rea in Tran spor ta t ion Ne twork s L u F en g, L u D o n gm e i an d C u i W e iho n g (), , 100101T h e I nstitu te of R em ote S ensing A p p l ica tionsC h inese A cad em y of S ciencesB eij ing A bstrac t T ran spo r ta t io n ne tw o rk s h ave app a ren t ch a rac te r ist ic s o f sp a t ia l d ist r ibu t io n, w h ich is th e ba sic d iffe rence be tw een th e sp a r se g rap h s de sc r ib ing th e t ran spo r ta t io n ne tw o rk s and o th e r p lana r g rap h s de sc r ib ing topo lo g ica l st ruc tu re o r h ie ra rch i2 . . ca l st ruc tu reA t im e sho r te st p a th a lgo r ithm ba sed o n th e re st r ic ted sea rch ing a rea is p re sen ted in th is p ap e rO n th e ba sis o f , , quada ry p r io r ity queue and inve r se ad jacen t list da ta st ruc tu rea re st r ic ted sea rch ing a rea a lgo r ithm is e stab lish edba sed o n , th e sta t ist ica l ana ly sis o n th e sp a t ia l d ist r ibu t io n o f t ran spo r ta t io n ne tw o rk sw ith th e app rop r ia te re st r ic ted e llip se and rec t2 . ang le a rea s fo r appo in ted sta r t and de st ina t io n no de sT h e re st r ic ted rec tang le sea rch ing a rea is p ro ved m o re app rop r ia te a s . , th e re st r ic ted a reaCo n side r ing th e d iffe ren t ro ad t rave lling im p edance and tu rn im p edancea t im e sho r te st p a th a lgo r ithm is . . p re sen tedT h e p re sen ted a lgo r ithm s can eff ic ien t ly dec rea se th e sea rch ing sca le and im p ro ve th e runn ing eff ic iencyIt h a s 2.been p ro ved by som e te st s o n th e rea lw o r ld t ran spo r ta t io n ne tw o rk , , , Keywords Sho r te st p a th a lgo r ithm T ran spo r ta t io n ne tw o rk R e st r ic ted sea rch ing a reaG IS