（计算机软件与理论专业论文）分层路径诱导算法与策略研究.pdf

摘要 分层路径诱导算法与策略研究 李建元 摘要：在智能交通系统中的路径诱导子系统中，查询最优路径是其中的 一项基本的功能。许多研究者已经从理论上和实验上对该问题进行了广 泛的研究。目前为止，道路网中的路径诱导算法主要有平面算法和分层 算法两大类。平面算法是指如d i j k s t r a 算法、a 算法和a 算法等的图搜 索算法，而分层算法由平面算法和一组在层次数据结构上进行推理的规 则组成。在分层算法的每一层可使用某种平面算法，而推理规则将规定 如何运用层次数据结构。与平面算法相比，分层算法通常在搜索一条满 意的路径时具有较好的性能，这是因为分层数据结构使得某个搜索过程 在子网中进行，子网的小数据规模可使得搜索过程高效执行。而随着问 题规模的变大，平面算法却会较快地产生“组合爆炸”问题。已有的最 近e 节点分层算法在提升低层节点时不够准确，而最佳e 节点分层算法 又效率太低。为此，本文提出了一种分层a 算法。其实质是在低层向高 层过渡时采用启发式定向搜索的方法确定e 节点，而在高层路网中搜索 时采用a 算法。目的是在求解速度较快的前提下，搜索出相对可靠的e 节点。西安市道路网的测试数据表明，分层a 算法的平均求解效率是 d i j k s t r a 算法的7 5 4 8 倍，平均路径长度与平均最短路径长度的偏差仅为 0 8 6 5 k m ，平均高层路径比重达到6 9 7 。通过比较分层a + 算法、最近e 节点分层算法和d i j k s t r a 算法的性能，笔者认为分层a + 算法具有较好的 实用性。 另外，在中心式路径诱导系统中，计算中心需要传送必要的地图数 据给车辆。为了缩短计算中心与车辆之间的数据传送时间，本文提出并 实现了一种t m s c r 数据准备模型，即在包含起止点的一个网格集合的 外接矩形区域中，提取起点网格内的低层路段、终点网格内的低层路段 和所有高层路段的并集，发送给车辆。实验表明，实现该模型的时间代 价很小，t m s c r 模型与传统的方法相比，可以大大节省通信时间，从而 为车辆提供优质的服务。 最后，笔者基于m a p x t r e m e 2 0 0 56 6 和n e t2 0 0 5 设计并实现了西安 市路径查询原型系统。该系统由三部分组成，即空间数据库、核心算法 层和用户界面。路径求解模块是一个d l l 文件，是通过建立v c + + 类库 摘要 项目而生成的。由于m a p x t r e m e 2 0 0 56 6 只提供了v b 和v c # 两种模板， 所以本文采用v b 应用程序来调用c + + 编写的d l l 模块完成了系统的实 现。 关键词：智能交通系统：路径诱导系统；分层a 算法；网格集外接矩形； 数据准备；系统设计与实现 2 摘要 s t u d y o fh i e r a r c h i c a lp a t hg u i d a n c e a l g o r i t h ma n ds t r a t e g i e s l ij i a n - y u a n a b s t r a c t ：o p t i m a lp a t h f i n d i n gi so n eo ft h ep r i m a r yf u n c t i o n so fp a t h g u i d a n c es u b s y s t e m i n 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 ) m a n y r e s e a r c h e r sh a v ee x t e n s i v e l ys t u d i e di nt h i sf i e l dw h e t h e rf r o mt h e o r yo r p r a c t i c e t w ok i n d so fa l g o r i t h m ，w h i c ha r ef l a ta l g o r i t h ma n dh i e r a r c h i c a l a l g o r i t h mh a v eb e e np r o p o s e df o ro p t i m a lp a t hf i n d i n gi nar o a dn e t w o r k a f l a ta l g o r i t h mi sak i n do fn o n h i e r a r c h i c a lg r a p h s e a r c ha l g o r i t h ms u c ha s d i j k s t r aa l g o r i t h m ，as e a r c ha l g o r i t h m ，a + s e a r c ha l g o r i t h ma n ds oo n a h i e r a r c h i c a la l g o r i t h mc o n s i s t so fan o n h i e r a r c h i c a la l g o r i t h ma n das e to f r u l e sf o rr e a s o n i n go nah i e r a r c h i c a ld a t as t r u c t u r e ，i no t h e rw o r d s ，a n o n h i e r a r c h i c a la l g o r i t h mp r o v i d e sas o l u t i o nf o ras i n g l el e v e lo ft h e h i e r a r c h ya n dt h er u l e ss t a t eh o wt o u s et h eh i e r a r c h i c a ld a t as t r u c t u r e g e n e r a l l ys p e a k i n g ，ah i e r a r c h i c a la l g o r i t h mh a sb e t t e rp e r f o r m a n c et h a na n o n h i e r a r c h i c a la l g o r i t h mw h e nt os e a r c has a t i s f y i n g p a t h i nar o a d n e t w o r k ，b e c a u s eh i e r a r c h i c a ld a t as t r u c t u r ec a nr e d u c et h en u m b e ro fn o d e s i n v o l v e di nas e a r c hp r o c e s sa n da l l o w sp e r f o r m i n gt h es e a r c hp r o c e s s e f f i c i e n t l y i nas u b n e t w o r k w h i l e p e r f o r m a n c e o fn o n h i e r a r c h i c a l a l g o r i t h mt e n d st od e t e r i o r a t ea st h en e t w o r ks i z ei n c r e a s e s c o n s i d e r i n gt h e e x i s t e n tn e a r e s te n t r a n c em e t h o di sn o tp r e c i s e l yt op r o m o t i n gt h en o d e so f al o w e rl a y e rr o a dn e t w o r kt oah i g h e rl a y e r ，a n da n o t h e re x i s t e n to p t i m a l e n t r a n c em e t h o dc a nn o tp r o m o t et h e me f f i c i e n t l y , an o v e ly e ts i m p l e h e u r i s t i cd i r e c t i o n a ls e a r c ht e c h n i q u ei s p r o p o s e df o rs e a r c har e l i a b l e e n t r a n c ei nt h i sp a p e r ，a n dt h eh i e r a r c h i c a la p a t hf i n d i n ga l g o r i t h m ， w h i c hi n c o r p o r a t e sa + s e a r c ht e c h n i q u ea n dh e u r i s t i cd i r e c t i o n a ls e a r c h t e c h n i q u e ，i st e s t e do nt h er o a dn e t w o r ko fx i a nc i t yw i t hat w o l a y e rr o a d n e t w o r k t h ee x p e r i m e n t a lr e s u l t ss h o wt h a tt a k i n gt h ed i j k s t r aa l g o r i t h m a sab e n c h m a r kt h eh i e r a r c h i c a la + p a t hf i n d i n ga l g o r i t h mh a sb e e nf o u n dt o a b o u t7 5 4 8t i m e sf a s t e rt h a nt h ed i j k s t r a a l g o r i t h m i na v e r a g e t h e d i f f e r e n c eb e t w e e nt h ea v e r a g ep a t hd i s t a n c eg a i n e db yh i e r a r c h i c a la + p a t h 3 摘要 f i n d i n ga l g o r i t h ma n da v e r a g es h o r t e s tp a t hi so n l yo 8 6 5k i l o m e t e r sa n dt h e p r o p o r t i o no ft h eh i g h e s tl a y e rr o a di su pt o 6 9 7 t h ep e r f o r m a n c e c o m p a r i s o na n da n a l y s i sa m o n g t h r e e a l g o r i t h m s ( d i j k s t r aa l g o r i t h m ， h i e r a r c h i c a la + p a t hf i n d i n ga l g o r i t h ma n dh i e r a r c h i c a ln e a r e s t e n t r a n c e p a t hf i n d i n ga l g o r i t h m ) i n d i c a t et h a th i e r a r c h i c a la + p a t hf i n d i n ga l g o r i t h m i sm o r ep r a c t i c a lt h a nd i jk s t r aa l g o r i t h mo rh i e r a r c h i c a ln e a r e s t e n t r a n c e p a t hf i n d i n ga l g o r i t h m b e s i d e s ，t r a f f i cc e n t e rn e e d ss e n ds o m ei n d i s p e n s a b l em a pd a t a t o v e h i c l e si nac e n t r a l l yd e t e r m i n e dr o u t eg u i d a n c es y s t e m t on a r r o wd o w n t h ec o m m u n i c a t i o nt i m e ，p r o p o s ead a t ap r e p a r em o d e ln a m e dt r a n s p o r t a t i o n m e s h e ss e t c i r c u m r e c t a n g l ei nt h i sp a p e r t h i sm o d a ls t a t e s t h a tt r a f f i c c e n t e rs h o u l ds e n das p e c i a ld a t as e t t ov e h i c l e st h a tc o n s i s t so ft h el o w l e v e lr o a ds e g m e n t si no g r i da n dd - - g r i da n da l lh i g hl e v e lr o a ds e g m e n t s i n v o l v e di nt h em e s h e ss e tc i r c u m r e c t a n g l ew h i c hc o n t a i n so - n o d ea n d d n o d e e x p e r i m e n t si n d i c a t et h a tt h ei m p l e m e n t a t i o np r o c e s si s m u c h e f f i c i e n t l yi nap e r s o n a lc o m p u t e r t h em o d e lw i l lg r e a t l yc o n t r i b u t et ot i m e s a v i n g si nt h ec o m m u n i c a t i o nb e t w e e nt r a f f i cc e n t e ra n dv e h i c l e s s ot h a t p r o v i d eab e t t e rs e r v i c et ov e h i c l e sw h e nc o m p a r e dw i t ht r a d i t i o n a lm e t h o d f i n a l l y , ap a t hf i n d i n gs y s t e mi sd e s i g n e da n di m p l e m e n t e db a s e do nt h e m a p x t r e m e 2 0 0 56 6a n dv i s u a l s t u d i o n e t2 0 0 5 ，w h i c hi sc o m p o s e do f t h r e ep a r t s ：s p a t i a ld a t a b a s e ，l a y e ro fc o r ea l g o r i t h m s ，a n du s e ri n t e r f a c e t h i ss y s t e md e p e n d so nad l lm o d u l et os e a r c ht h ep a t ht h a tu s e r sn e e d ， a n dt h ed l lm o d u l ei si m p l e m e n t e db yt h ep r o g r a m m i n gl a n g u a g ec + + v i a c r e a t i n gav c + + l i b r a r yp r o j e c t m a p x t r e m e 2 0 0 5 6 6o n l ys u p p o r t st h e p r o g r a m m i n gl a n g u a g ev i s u a l b a s i ca n dv i s u a lc 样s ot h em e t h o dt h a t v i s u a lb a s i ca p p l i c a t i o np r o g r a mc a l l st h ec + + d l lm o d u l ei sa d o p t e dt o i m p l e m e n tt h es y s t e m k e y w o r d s ： 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 ；p a t hg u i d a n c es y s t e m ； h i e r a r c h i c a la + a l g o r i t h m ；c i r e u m - r e c t a n g l eo fm e s h e ss e t ；d a t ap r e p a r e ； s y s t e md e s i g na n di m p l e m e n t a t i o n 4 学位论文独创性声明 本人声明所呈交的学位论文是我在导师的指导下进行的研究工作及 取得的研究成果。尽我所知，除文中已经注明引用的内容外，论文中不 包含其他个人已经发表或撰写过的研究成果，也不包含为获得陕西师范 大学或其它教育机构的学位或证书而使用过的材料。对本文的研究做出 重要贡献的个人和集体，均已在文中作了明确说明并表示谢意。 作者签名： 日期：丝丑：! ：i 口 f 学位论文使用授权声明 本人同意研究生在校攻读学位期间论文工作的知识产权单位属陕西 师范大学。本人保证毕业离校后，发表本论文或使用本论文成果时署名 单位仍为陕西师范大学。学校有权保留学位论文并向国家主管部门或其 它指定机构送交论文的电子版和纸质版；有权将学位论文用于非赢利目 的的少量复制并允许论文进入学校图书馆、院系资料室被查阅；有权将 学位论文的内容编入有关数据库进行检索；有权将学位论文的标题和摘 要汇编出版。 作者签名：姚日期犁 l 第一章绪论 1 1 研究背景 1 1 1 智能交通系统概述 第一章绪论 ( 1 ) 采用智能交通系统的动因 随着世界经济和我国经济的发展，城市交通问题日益突出，各国均 表现出交通基础设施严重不足，交通阻塞现象严重，交通引起的污染愈 发严重，严蓖地影响了社会和经济的可持续发展。美国、同本和欧洲一 些发达国家竞相在2 0 世纪九十年代开始了对智能交通系统的研究，研究 的主要问题是i t s 标准化和综合交通智能化等，为了尽快改善城市交通 状况，这些国家均启动了巨额投资计划。我国的北京、上海和广州等大 城市在“九五”期间也进行了大规模的交通设施建设，例如进行道路扩 建，快速路工程和地铁工程的建设等。虽然这些措施能够缓解城市交通 拥挤状况，改善交通环境，提高行车的安全性，但是由于城市受到经济、 地理和环境的约束，不可能无限制地增加交通网络中的道路。同时，交 通量的持续增加势必诱发新的交通需求，所以我国大中型城市的交通问 题日益严重起来。以北京市为例，来阐述我国交通压力的日趋严峻。北 京市常住人口规模在2 0 0 3 年已超过1 4 0 0 万，到2 0 0 8 年人口总数将突破 1 6 0 0 万。城市人口的快速膨胀无疑加剧了城市资源和环境的压力，给交 通状况带来巨大的压力。据统计，2 0 0 6 年北京市民用汽车拥有量已突破 3 0 0 万辆，约占全国民用汽车拥有量的l o ，北京市对交通基础设施在 “九五”期间投资达4 0 0 亿元，占g d p 的4 3 ；“十五”期间预计投入 8 3 8 亿元，占g d p 的5 1 5 。这样的投资力度在全世界都是少见的，但 实际的北京市交通并没有得到根本缓解。从1 9 9 5 年到2 0 0 1 年的1 1 年中， 北京市区交通流量以平均每年超过1 5 的速度递增。最新统计资料显示， 在高峰小时内的双向断面车流量，二环路为l 万辆，三环路为1 1 万辆， 四环路为1 3 万辆。在这种情况下，应该积极挖掘交通设施的潜力来改 善交通环境。 2 0 0 0 年初，建设部、公安部进一步提出了解决城市交通拥堵和改善 第一章绪论 交通秩序的“畅通工程”。于是，“十五”期间，国家科技部将i t s 列为 “十五”重大专项，并确定北京、上海、天津、重庆、广州、深圳、济 南、青岛、杭州、中山等城市作为i t s 的示范城市。智能交通系统的发 展为治理城市交通问题提供了新思路。它是世界交通工程科学技术的前 沿，其实质就是利用高新技术对传统的交通系统进行改造的一种信息化、 智能化、社会化的新型交通系统。 ( 2 ) 城市智能交通管理所能带来的经济效益i l 】 交通安全方面 美国国家公路交通安全局估计，如果所有商业车辆都使用智能交通 的防撞避撞、车尾碰撞警告系统、道路偏离警告系统等，将使商业车辆 的碰撞交通事故减少1 7 以上，这将意味着每年能节约2 5 0 亿美元的交 通事故损失。美国2 0 0 1 年制定的新世纪头1 0 年的i t s 发展规划中明确 指出：在交通安全方面，通过i t s 建设，到2 0 1 1 年，减少交通事故1 5 ， 每年减少死亡人数5 0 0 0 7 0 0 0 人。日本同样认为，采用了i t s 后的交通 安全性将大大增强。 交通拥挤方面 根据美国i t s 协会的测算，采用i t s 技术后，现有高速公路的交通 流量可以从1 9 8 8 年的1 9 兆台m i l e 增加到3 8 兆台m i l e ；而且因为可以 实时提供旅行、线路选择和停车场设置等情报，还可以大大增加驾驶员 和乘客的自由选择程度。根据日本的计算，采用i t s 后，由于减少交通 拥挤可减少1 2 3 兆日元年的经济损失。 交通环境和能耗方面 采用城市智能交通管理技术将能够尽可能减少交通运输对大气质量 的影响，降低燃油耗费，减轻噪音污染以及其他交通因素构成的对人们 日常生活的安全和健康水准的危害程度。根据美国i t s 协会的测算，到 2 0 1 1 年左右美国i t s 建设因为环节交通拥堵每年可节省2 0 0 亿美元支出、 1 0 亿加仑的汽油消耗和1 3 的出行时间。根据日本的计算，采用i t s 后 燃油消耗降低2 5 ，c o 降低1 5 ，n 0 2 降低3 0 。 其他经济效益 采用i t s 后还可以节约基础设施投资成本、降低政府的运营成本提 高劳动生产率以及培育发展新型产业提供就业机会等。 ( 3 ) 智能交通管理系统的体系结构 i t m s 体系结构是指将i t m s 中各种应用系统、i t m s 中用户主体以 2 第一章绪论 及用户服务和用户需求等有机地联系起来的内在逻辑描述。i t m s 体系结 构示意见图1 1 。为了保证各项服务的实现，合理地应用智能交通管理系 统中的数据资料，智能交通管理系统需包含以下四个部分：信息采集系 统、信息管理系统、信息发布与诱导系统以及信息传输系统。 信息采集系统包括交通流监测系统、闭路电视监控系统、警员与车 辆定为系统、电子警察系统等。信息采集系统通过各类信息采集终端获 得各种交通信息、道路信息、气象信息等，然后通过信息传输系统报送 到信息管理系统。信息管理系统包括机动车与驾驶员管理系统、交通违 章管理信息系统、交通事故管理信息系统、交通设施管理系统、警务管 理系统等。信息管理系统通过对各个子系统数据、语音、图像等各类信 息进行加工处理，将原始的数据和信息层次化、结构化、集成化和语义 化，变成能够使用的有效信息束不断的更新交通信息数据库，掌握实时 路况，提出相应的交通管理控制方案，并通过信息发行与查询系统、交 通诱导系统使道路使用者了解最新路况。信息发布与诱导系统包括交通 信息发布与查询系统、交通诱导系统。信息发布与诱导系统通过可变信 息板、交通电台、电视台、网站等交通媒体来实施交通管理信息、实时 交通或历史信息准确地发布及对交通流的诱导调节。 图1 1i t m s 体系结构 第一章绪论 1 1 2 路径诱导系统的分类 路径诱导系统是智能交通系统的一个核心模块。国内外许多学者对 此问题进行了深入研究。从路网数据库是否动态更新的角度，路径诱导 系统分为静态路径诱导系统和动态路径诱导系统。由于路况信息是动态 变化的，所以依赖静态路网数据库的路径诱导系统有大大的局限性，而 动态路径诱导系统显然将成为研究和应用的趋势。按照在交通信息中心 计算路径还是在车载单元计算路径可以将路径诱导系统分为中心式动态 路径诱导系统c d r g s ( c e n t r a l l yd e t e r m i n e dr o u t eg u i d a n c es y s t e m ) 和 分散式动态路径诱导系统d d r g s ( d i s t r i b u t e dd y n a m i cr o u t eg u i d a n c e s y s t e m ) 两种【2 】。在c d r g s 中，交通信息中心负责路径的计算，然后通 过通信网络将路径发送到车载单元。而在分散式系统中由车载单元自主 计算路径。两种系统的区别见图1 2 。c d r g s 又可以细分为b c d r g s 和i c d r g s 两种，前者指广播式的中心决定式路径诱导系统，后者指交互式 的中心决定式路径诱导系统。在i - c d r g s 中，信息中心主机根据实时交 通数据计算路径，并通过通信网络发送给路径请求单元。中心计算机的 配置一般较高，因为可能需要处理并发的路径请求，结合通信过程中的 时间消耗，还必须考虑诱导系统在大负荷情况下的响应的实时性问题。 。臂 l 叫i 丽刃j 交通信息中- 廿一 审 蒌 豳 圈圈 审 一 ( a ) c d r g s 框图( b ) d d r g s 框图 图1 2c d r g s 和d d r g s 的框图 4 第一章绪论 虽然依靠超级计算机可以加快响应的速度，但把加快响应速度这个 任务光抛给昂贵的硬件将大大增加投入的成本，所以从算法的角度去加 快响应速度可以起到降低硬件成本的作用。在d d r g s 中，车载计算系 统的配置一般不会很高，目前的路径诱导产品大多是面向普通应用的移 动手持计算平台，如个人数字助理( p d a ) 。与普通机相比，这种便携设 备运算能力还有相当大的差距，故也需要从程序设计的角度来提高计算 的速度。 1 2 交通网络中寻路算法的研究现状 1 2 1 平面寻路算法的分类 最短路径算法是图论的经典问题，并且在实际的交通网络中得到广 泛的应用。国内外大量专家学者对此问题进行了深入的研究。以经典的 图论为基础，利用较为丰富的计算机数据结构及算法，使得新的最短路 径算法不断涌现。这些研究在时间复杂度、空间复杂度、易实现性及应 用范围等方面各具特色 3 , 4 1 。对于串行计算机的最短路径算法，已经几乎 到达理论上的时间复杂度极限【3 1 。该部分对最短路径算法从三个角度进 行了系统分类，对已有的各种具有较高效率的串行最短路径算法从时间 和空间复杂度等方面进行了比较，对国内外一些相关研究进行了评述。 按照起终节点及路径的数目，最短路径问题大致可分为3 种类型， 即单对节点间最短路径、所有节点问最短路径、k 条路径，如图1 - 3 所 示。当加入一些需求因素进行限制后，又可派生出其他一些特殊的最短 路径问题，如限制路段数目最短路径、限制转弯次数最短路径等。其中， 最基本的而且应用最广泛的当然是单对节点间的最短路径。所有节点间 最短路径问题可以分解成单对节点间最短路径问题，其应用很少见。为 了消除因用户“自私”行为导致的最优路径的振荡，并且充分平衡网络 中的负载，一般希望i t s 能对用户推荐多条满意的路径，这也就是所谓 k 路问题。常见的k 路算法是由d i j k s t r a 算法发展起来的二重扫除法， 这是一种非确定性多项式时间复杂性的算法，对大型交通网络难以满足 实时性的要求。由于遗传算法、神经网络等软计算方法的计算时间对网 络尺寸不敏感，解决大规模网络中k 路问题具有一定优势。但神经网络 和遗传算法涉及到大量的迭代而计算速度较慢，只有借助一些硬件如现 场可编程逻辑器件芯片来实现，才可以非常快1 5 l 。 第一章绪论 图1 3按照起终节点及路径的数目分类 按照采用的数据结构不同主要分为3 种类型，即邻接矩阵、邻接表 和其它辅助存储结构，如图1 4 所示。最原始的方法是采用邻接矩阵存 储网络拓扑数据，这种方法可以在0 ( 1 ) 时间内完成( i ，j ) 是否是一条网络 边的查询，但对最短路径算法最关键的关联节点查询，其复杂度均为0 ( n ) 。这就决定了基于邻接矩阵的最短路径算法时间复杂度是不可能降低 的。另外，采用邻接矩阵存储网络拓扑数据的空间复杂度为o ( n 2 ) 。这样 ，对于一个包含1 0 4 个节点以上的交通网络( 如北京市的路网) ，仅邻接 矩阵就至少需要1 0 0 m 的存储空间，显然，采用邻接矩阵时的空间复杂 度太大。故邻接矩阵的表达方法只适用于小型网络。在具有1 0 4 以上个 节点的大中型网络中，采用邻接矩阵存储拓扑数据是不现实的。邻接表 是另一种存储网络拓扑的数据结构，它是一种链式存储结构，在网络相 关算法中应用广泛。在交通领域内，将网络的顺序邻接表与逆向邻接表 通常称为f o r w a r ds t a r ( f s ) 表与b a c k w a r ds t a r ( b s ) 表1 6 】。对于节点查询 而言，邻接表中关联节点查询时问复杂度仅为o ( e n ) 。此外，对于交通 网络等稀疏图，采用邻接表数据结构存储网络拓扑数据不存在存储空间 的浪费，尤其是当与路段或节点相关的信息较多时更是如此。邻接表数 据结构已被证明是网络表达中最有效率的数据结构，在最短路径算法中 得到了广泛应用7 ，8 ，9 ，1 0 ，1 1 】。既然邻接表为降低最短路径算法的时间复杂 度提供了可能，就可以引入其他的辅助数据结构以达到真正降低时间复 杂度的目的，如k 叉堆优先级队列和桶结构等。不同的实现方法决定了 不同的时间复杂度，事实上，只有当采用无序表作为运行结构时，d i j k s t r a 算法时间复杂度才为o ( n 2 ) 。当采用k 叉堆、二项堆或f i b o n a e c i 堆优 先级队列来实现d i j k s t r a 算法时，其时间复杂度为o ( m l o g n ) 或o ( m + n l o g n ) ”，采用桶结构基数堆实现的d i j k s t r a 算法，在假定弧段整数权值前 6 第一章绪论 提下，复杂度为o ( m + n l o g c l o g l o g c ) ( c 为最大整数权值) ，而基数堆和f 堆相结合的d i j k s t r a 算法复杂度仅为o ( m + n ( 1 0 9 c ) 2 ) 【1 3 】。 图1 4 按照采用的数据结构不同分类 另一种最短路径算法分类方法是按实现技术分类”，分类方法如图 1 5 所示。按实现技术可分为组合技术和代数方法两种。组合技术主要是 指标号算法。标号算法也是绝大多数最短路径算法的核心部分。按照不 同的标识节点处理策略，标号算法又可分为标号设定( 简称l s ) 和标号 改正( 简称l c ) 两大体系。代数方法通过运筹学中的线性规划形式化、 所定义代数系统中的联立线性方程集形式化以及矩阵乘法等方法来解求 最短路径问题。l s 算法又称为最短优先搜索算法，最早由荷兰数学家 d i j k s t r a 于1 9 5 9 年提出。基于堆结构和桶结构优先级队列的l s 算法是 研究得最深入、应用也最广泛的l s 算法。d i j k s t r a 算法的广泛应用使之 己成了l s 算法的代名词。其它l s 算法多为d i j k s t r a 算法的不同实现方 式。l c 算法又称为列表搜索算法。其代表性算法包括b e l 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 ) 、p a l l o t t i n o 算法【l5 1 、门限算法 d 6 1 、拓扑排列算法【1 7 1 和s l f 算法【1 8 】等。实际上，所有的l s 或l c 算法 都可总结为一种更为一般性的算法的特例。不同之处在于处理图中所标 识节点时采用的优先级队列系统各不相同f 1 5 1 。l s 算法在优先级队列处理 的每一步，都能得到一条由源点到其余节点的最短路径，当求解单源单 目标最短路径时，终点跳出优先级队列时即可结束。但l s 算法不能处理 含负权边的网络；而l c 算法处理节点时，可能需要多次进出优先级队 列，单源单目标最短路径需到算法结束时才能得到。l c 算法可处理含负 权边的网络。长期以来，专家学者们对l s 和l c 算法的效率比较进行了 深入的研究。对于稠密图，d a n t z i g 算法优于d e s o p o p a p e 算法；而对 于稀疏图，虽然有指数形式的最坏时间界，d e s o p o p a p e 算法仍然是最 7 第一章绪论 优的d 6 。文献【4 】的研究结果表明，对于不同网络形式，各种算法效率差 异很大，但并没有一种算法针对各种网络形式均有较好的效率。对于稠 密网络，双桶d i j k s t r a 算法( d i k b d ) 和门限算法效率最高；对于非平面的 规则格网型网络，d i k b d 算法和堆结构的d i j k s t r a 算法( d i k h ) 效率最高； 对于无环图，d i k b d 算法和拓扑排列算法效率最高1 4 1 。 值得注意的是，理论上最优的算法不一定在实践中最优。所以，在 实际的应用中还需要结合人的思维、出行习惯以及交通设施的特点等方 面，以设计出真正实用的算法。 图1 5 按实现技术分类 1 2 2 分层寻路算法的研究现状 最短路径问题致力于求解最小权重的路径，但考虑到出行者多样化 的实际需求，大多数的驾驶者并不喜欢选择这种路径。调查表明，许多 驾驶者并不单纯采用最短路径，在保证路径长度较短的情况下，他们倾 向于尽量走等级较高的、较为熟悉和安全的道路f 1 9 i 。这类问题可以称为 近似最短路径问题，与最短路径问题相比较，在求解近似最短路径问题 时的时间复杂度可以进一步降低，或者在同一时间复杂度下求解效率更 高。采用a 算法求解路径和分层路径算法就属于典型的近似最短路径问 题。 由于道路具有很自然的分层结构，这样就蕴含了一种有效的分层寻 路算法的思想。其基本思想是首先进行抽象空间的搜索而不是在整个原 问题空间搜索。抽象能减少问题的复杂性，主要原因是总的复杂性为单 个搜索复杂性的总和而不是积 2 0 l 。实验证明，这种方法在减小复杂问题 的搜索空间方面是非常有效的1 2 1 】。文献 2 2 详细地分析和形式化了问题 抽象，假设某算法的时间复杂度为o ( b 4 ) 。对于单层抽象，分层算法能 g 第一章绪论 将时间复杂度从o ( b o ) 减小到o ( b “2 ) ；对于多层抽象，一个具有b 4 种 状态的问题空间的最佳分层数为l n b 4 。后继抽象层的大小比率为e 。这种 最佳抽象分层能将时间复杂度从o ( b 4 ) 减小到o ( d l o g b ) 。为了实现分 层寻路算法，地图数据库需要分层构造，抽象层需要重建。一些学者提 出并实现了有助于路径规划的分层数据库 2 3 , 2 4 1 。以道路网分层数据库为 数据源，研究者们已经提出了几种分层寻路算法，其中有代表性的是文 献 2 5 】提出的最近e 节点法，文献 2 6 提出的最佳e 节点法。这两种方法各 有利弊，最近e 节点法虽简单但准确性较差，最佳e 节点法能够保证最优 解但搜索效率较低1 5 , 2 7 1 。最近e 节点只需要搜索离当前点最近的高层路网 节点，所以计算速度较快；而在最佳节点分层算法中，假设函数埏( x ，y ) 为低层网格g 上从节点x 到节点y 的最短路径代价，p ( x ，y ) 为节点x 到节点y 在顶层网格上最短路径代价，n o 和n d 分别为0 网格和d 网格的e 节点集 合。路网中n o = e 1 ，e 2 ，e 3 ，e 4 ，n d = e 5 ，e 6 ，e 7 ，e 8 。如果起始节点o 和 终点d 问的最佳分层路径通过e 节点e o n o 和e d n d ，则e o 和e d 通过下 式决定： ( e o ，e d ) = a r g m i n f o ( o ，i ) + p ( i ，j ) + f d 0 ，d ) ) ，其中( i j ) n o x n d 。 尽管最佳节点分层算法保证了最优解，但是它的计算量较大，大大超过 了最近节点算法。另外，文献2 7 提出了一种应用上较为成熟的启发式 分层算法：他们通过修剪和合并，使得道路网的数据规模大大减小，然 后提出了启发式节点提升技术，以较好地完成层次切换，新加坡测试数 据表明，启发式分层算法与a 算法相比，最优路径的准确率误差平均为 3 3 1 ，速度要快5 2 倍。 1 3 所做的工作 ( 1 ) 分层路网空间数据的建模和存储访问 分析了m a p i n f 0 7 0 的数据格式和o r a c l e9 i 数据库支持的数据 格式，掌握了o r a c l es p a t i a l 组件和0 0 4 0 的使用方法。 提出了道路网数据的分层依据、分层方法和可靠性验证方法，利 用o r a c l e9 i 完成了分层路网数据统一存储，并利用0 0 4 0 接口实现了 空间数据库的编程访问。 ( 2 ) 编程实现了d i j k s t r a 算法、a 算法、a t 算法、最近e 节点分层 算法等，提出并实现了一种分层a 算法，通过对西安市2 2 7 5 条路径的 9 第一章绪论 测试，比较和分析了分层a 算法、最近e 节点分层算法和d i j k s t r a 算法 的性能，揭示了分层a 算法的实用性。 ( 3 ) 提出并实现了一种t m s c r 数据准备模型，即在包含起止点的 一个网格集合的外接矩形区域中，提取起点网格内的低层路段，终点网 格内的低层路段和所有高层路段的并集，发送给车辆。实验表明，实现 该模型的时间代价很小，t m s c r 模型与传统的方法相比，可以大大节省 通信时间，从而为车辆提供优质的服务。 ( 4 ) 基于o r a c l e 9 i 空间数据库，利用n e t 2 0 0 5 和m a p x t r e m e 2 0 0 5 6 6 实现了一个路径查询原型系统。 详细分析了m a p x t r e m e 2 0 0 5 的体系结构和主要功能； 对基于空间数据库的路径查询原型系统进行了总体设计； 阐述了所用的关键技术和实现细节，如d l l 的创建和调用、地图 的显示、路径的显示等。 1 0 第二章路网的数据模型与存储访问 第二章路网的数据模型与存储访问 2 1g i s 中的数据模型与数据结构 1 9 6 3 年加拿大测量学家r t t o m l i n s o n 提出地理信息系统( g i s ) 并 建立世界上第一个g i s 一加拿大地理信息系统( c g i s ) ，至今已有4 0 多 年的历史。g i s 发展至今，技术逐渐成熟，g i s 在许多部门得到应用。 这期间流行的大多数g i s 软件将几何数据与属性数据分开来存储和管 理。属性数据存储在关系数据库的若干属性表中，而空阳j 数据则保存于 若干文件或另一数据库中，二者通过一定的索引机制联系起来。随着数 据库技术的发展，为了更好地管理空间数据，基于对象关系模型的g i s 数据统一存储的方法将逐渐成为主流。 2 1 16 i s 中的几种数据模型 g i s 数据与普通的数据相比，具有自己的特点：类型多样，实体问 的关系较为复杂，数据量很大，每个几何实体所占的字节长度不等。这 些特点决定了利用传统的数据库系统管理地理空间数据存在着明显的不 足，g i s 应该有自己的数据库空间数据库。之所以建立空间数据库， 是为了让用户方便灵活地查询出所需的地理空间数据，并能对空间数据 进行插入、删除和更新等操作。由于传统的关系数据库系统主要针对的 是简单的对象，不能有效地支持复杂对象( 如图形和影像) 为主体的工 程应用。空间数据库必须要具备对地理对象进行模拟和推理的功能，才 能真正表现出优势。 传统的数据库系统在管理地理空间数据时有几个方面的局限性 2 8 1 ： ( 1 ) 传统数据库系统管理的是不连续的、相关性较小的数字和字符； 而地理信息数据是连续的，且具有较大的空间相关性； ( 2 ) 传统数据库系统管理的实体类型较少，并且实体类型之间通常 只有简单、固定的空间关系；而地理空间数据的实体类型繁多，实体类 第二章路网的数据模型与存储访问 型之间存在着复杂的空间关系，并且具有拓扑关系。 ( 3 ) 传统数据库系统存储的数据通常为等长纪录的数据；而地理空 间数据通常由于不同空间目标的坐标串长度不定，具有变长纪录，并且 数据项也可能很大，很复杂。 ( 4 ) 传统