（模式识别与智能系统专业论文）交通诱导系统的研究与设计.pdf

摘要 论文题目：交通诱导系统的研究与设计 学科专业：模式识别与智能系统 研究生：蔡恒 指导教师：马炫副教授 摘要 签名： 签名： 路径诱导系统作为信息处理技术的一种，是以计算机技术为依托，以具有空间。内涵的 地理数据为处理对象，运用系统工程和信息科学的理论，采集、存储、处理、分析以及显 示最佳路线的计算机系统。系统根据用户的需求提供参考路线，实现电子地图的显示、查 询以及分析功能。 ： 目前路径诱导系统主要是借助第三方软件进行二次开发，本文介绍了基于面向对象技 术的思想开发图形系统，给出了运用面向对象的可视化编程语言v i s u a lc 抖从底层独立 进行交通诱导系统的设计方法。详细叙述了系统总体框架的设计、图形元素的组织和存储、 网络拓扑关系的构造和存储、系统数据库的设计。 在路线寻优中，传统的最优路径算法以d i j k s t r a 算法为代表。这些算法均属于贪心 算法，存在典型的局部最小问题，而且属于一种单目标最优算法。由于现实中存在的往往 呈现为多目标属性，而且需要优化的多个目标之间又是相互冲突的。遗传算法是模拟达尔 文的遗传选择和自然淘汰的生物进化过程的一种新的迭代的全局优化搜索算法，已经广泛 地应用到组合优化问题求解中。从而多目标遗传算法应运而生，它使得进化群体并行搜寻 多个目标，并逐渐找到问题的最优解。 本文基于多目标优化问题p a r e t o 最优解的概念，给出了一种求解非支配集的多目标 最优路径的遗传算法，重点讨论了算法实现非支配集的构造和适应度的计算。将该算法应 用于交通方案优化设计，要求路径、时间、舒适安全指数三个目标能同时达到最优，通过仿 真实验对优化结果进行了分析比较。研究结果显示出本算法对交通方案多目标优化设计具 有良好的应用前景。 关键字：路径诱导系统、电子地图、最优路径、多目标遗传算法 a b s t l a c t t i t l e ：t h er e s e a r c ha n dd e s l g no ft r a f f i cg u l d a n c e s y s t e m m a j o r ：p a t t e r nr e c o g n i t i o na n di n t e l l i g e n ts y s t e m n a m e ：h e n gc a i s u p e r v i s o r - a s s o c i a t ep r o f x u a nm a a b s t r a c t s i g n a t u r e ：地 s i g n a t u r e ：甾么鹋幽 t h er o u t eg u i d a n c es y s t e mi sak i n do fi n f o r m a t i o np r o c e s s i n g t e c h n i q u e ，t a k et h e c a l c u l a t o rt e c h n i q u ea st or e l yo n ，t a k et h eg e o g r a p h yd a t ao ft h es p a c ec o n t e n ta st oh a n d l e o b j e c t ，c o l l e c t ，s a v e ，h a n d l e ，a n a l y z ea n ds h o wt h eb e s tr o u t ew i t ht h es y s t e me n g i n e e r i n ga n d t h ei n f o r m a t i o ns c i e n c e t h es y s t e mp r o v i d e st h er e f e r e n c er o u t ea c c o r d i n gt ot h en e e do ft h e c u s t o m e r ，c a r r y i n go u tt h em a n i f e s t a t i o no ft h ee l e c t r o n i c sm a p ，s e a r c ha n da n a l y t i c a lf u n c t i o n t h e r o u t eg u i d es y s t e mc u r r e n t l ym a i n l y i sa s kf o rh e l pt h ea n o t h e rs o f t w a r et oc a r r yo n d e v e l o p m e n t t h i sp a p e r i n t r o d u c et h ed e v e l o p m e n to fs k e t c h s y s t e ma c c o r d i n gt o t h e o b j e c t - o r i e n t e dt e c h n o l o g y , p r e s e n tt h ed e s i g nm e t h o do ft r a f f i cg u i d a n c es y s t e mf r o mt h ef i r s t f l o o rw i t ho b j e c t o r i e n t e dp r o g r a m m i n gl a n g u a g e t h em a i ns t r u c t u r e ，t h es a v i n go fe l e c t r o n i c m a p ，t h es a v i n go fn e t w o r kr e l a t i o n ，t h ed e s i g no fd a t a b a s ea r ep a r t i c u l a r l yi l l u s t r a t e d t r a d i t i o n a lb e s tr o u t et a k e st h ed i j k s t r aa l g o r i t h ma st or e p r e s e n t t h e s ea l g o r i t h m sa l l b e l o n gt og r e e da l g o r i t h m ，h a v et h ep a r t i a lm i n i m u mp r o b l e m ，a n db e l o n gt ot h eb e s ta l g o r i t h m o fs i n g l eo b j e c t i v e b u tm u l t i - o b j e c t i v ei sp r e s e n ti nr e a l i t y , a n dc o n f l i c tw i t ho n ea n o t h e r g e n e t i ca l g o r i t h mi sak i n do fn e w g l o b a ls e a r c ho f t h el i v i n gc r e a t u r ee v o l u t i o np r o c e s st h a t i m i t a t e st h ed a r w i n i a ng e n e t i cc h o i c ea n dn a t u r a ls e l e c t i o n ，h a v i n ga l r e a d ya p p l i e dt oa c o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m t h u sm u l t i o b j e c t i v eg e n e t i ca l g o r i t h me m e r g ew i t ht h e t i d eo ft i m e s ，i tm a k e st h ee v o l u t i o nc o m m u n i t ys e a r c hs e v e r a lo b j e c t i v ea b r e a s t ，a n df i n do u t t h eb e s ts o l u t i o no fp r o b l e mg r a d u a l l y t h i sp a p e rg i v eak i n do fw a yt os o l v em u l t io b j e c t i v ea c c o r d i n gt op a r e t oc o n c e p t ，a n d d i s c u s st h ea l g o r i t h mh o wt or e a l i z et h es t r u c t u r eo fn o n d o m i n a t ea n dc a l c u l a t ea d a p t t h e a l g o r i t h ma p p l yt od e s i g ni nt h et r a n s p o r t a t i o np r o j e c t ，r e q u e s t i n gr o u t e ，t i m e ，c o m f o r ts a f e t y i n d e xc a na t t a i ns u p e r i o ri nt h em e a n t i m e ，p a s s a ne x p e r i m e n t c a r r yo nt h ea n a l y s i sc o m p a r i s o n t h er e s e a r c hd i s p l a y st h i sa l g o r i t h mh a v eag o o da p p l i e df o r e g r o u n dt ot h et r a n s p o r t a t i o n p r o j e c t k e y w o r d s ：r o u t eg u i d a n c es y s t e m ，e l e c t r o n i cm a p ，r o u t eo p t i m i z a t i o n ，m u l t i o b j e c t i v e o p t i m i z a t i o ng e n e t i ca l g o r i t h m 独创性声明 秉承祖国优良道德传统和学校的严谨学风郑重申明：本人所呈交的学位论文是我 个人在导师指导下进行的研究工作及取得的成果。尽我所知，除特别加以标注和致谢 的地方外，论文中不包含其他人的研究成果。与我一同工作的同志对本文所研究的工 作和成果的任何贡献均己在论文中作了明确的说明并已致谢。 本论文及其相关资料若有不实之处，由本人承担一切相关责任 论文作者签名：叠丝 枷年弓月够日 学位论文使用授权声明 本人壅堕在导师的指导下创作完成毕业论文。本人已通过论文的答辩， 并已经在西安理工大学申请博士硕士学位。本人作为学位论文著作权拥有者，同意 授权西安理工大学拥有学位论文的部分使用权，即：1 ) 已获学位的研究生按学校规定 提交印刷版和电子版学位论文，学校可以采用影印、缩印或其他复制手段保存研究生 上交的学位论文，可以将学位论文的全部或部分内容编入有关数据库进行检索；2 ) 为 教学和科研目的，学校可以将公开的学位论文或解密后的学位论文作为资料在图书馆、 资料室等场所或在校园网上供校内师生阅读、浏览。 本人学位论文全部或部分内容的公布( 包括刊登) 授权西安理工大学研究生部办 理。 ( 保密的学位论文在解密后，适用本授权说明) ，7 论文作者签名：撞笠蔓 导师签名，碰5沁孑年岁月2 扩日 绪论 1 绪论 1 1研究背景 近年来，车辆的广泛普及给人们的生活带来了方便，但同时也给出行者带来了许多困 惑；复杂的交通网络使人们无所适从；频繁发生的交通堵塞使人们难于选择最佳的出行路 线；处在陌生的地理环境中无法准确的了解周围的交通条件；需要服务时却可能不了解周 围服务设施的分布而难以就近得到需要的服务。这种状况表明，如何在短时间、路程最少、 成本最低的情况下到达目的地，是人们所急需解决的问题。 路径诱导系统这一崭新概念伴随着科学技术的进步而出现，为解决出行者问题带来了 新的思路。路径诱导系统将先进的计算机处理技术、信息技术、数据通信技术及电子自动 控制技术等有效地综合运用于整个系统当中，将人、路、车有机地结合起来，以达到最佳 的和谐统一，从而建立起的一种在大范围内、全方位发挥作用的实时、准确、高效的最优 出行路线系统。 路径诱导系统它能帮助驾驶员避开拥挤和事故、避免因不熟悉城市交通环境而迷路、 也有利于增加安全。路径诱导系统就是利用计算机技术，通过向驾驶员提供最佳行驶路线 来达到诱导出行行为、减少车辆在路上的逗留时间。同时，它还能避免因盲目行驶或凭经 验行驶造成交通堵塞。 一 国内现有的路径诱导系统一般是单目标路径诱导，它利用地图数据库的信息，根据单 目标路径算法提供路径诱导。随着人们认识到在现实中最短路径不一定是最优路径，人们 开始了对多目标路径算法的研究，与单目标路径诱导系统相比，不同之处在于多目标路径 诱导系统更加接近于现实。多目标路径诱导系统是路径诱导系统发展的必然趋势。 1 2 研究情况介绍 欧洲对路径诱导系统的研究开始是基于红外信标通信展开的，德国和英国分别在8 0 年代末期开发出了用于示范的l i s b 系统和a u t o g u i d e 系统，而后英国推出了世界上第一 个车载路径诱导系统t r a f f i cm a s t e r 。进入九十年代，德国西门子公司开发的i s c o u t 系 统具有一定的国际影响，它不但安装于德国柏林等欧洲城市，亦应用到了美国m i c h i g a n 的o a k l a n dc o u n t r y ，该系统是基于红外信标通信方式的中心决定式路径诱导系统。中心 型路径诱导系统( 或中心决策的路径诱导系统) 路径计划则由交通控制中心的计算机系统 计算产生。中心的计算机系统根据实际路况和交通条件为每一特定的车辆选择最优路径， 并将选择结果通过路侧通信装置传送给车辆。德国斯图加特的s t o r m 项目致力于开发双 模式路径诱导系统：即在安装红外信标的区域开发基于红外信标的中心决定式路径诱导， 西安理工大学硕士学位论文 同时在广域内开发基于r d s t m c 交通广播的路径诱导。日本的车载路径诱导系统处于世 界领先地位，日本的d r g g 采用局部决策的路径诱导和中心决策的路径诱导相结合的混合 式路径诱导策略1 1 1 。 我国对路径诱导系统的研究起步较晚，目前处于对定位系统、电子地图、通信系统等 问题的研究阶段，投入使用的基本上都是以无线广播为主的初级诱导手段。基于g p s 集 群通信和可变标志牌的诱导系统正处于研究和实验阶段，而对比较全面的路径诱导系统的 研究还处于起步阶段。下面对我国的路径诱导系统做一简单介绍【2 1 。 上海交警总队和同济大学于1 9 9 5 年6 月完成的动态标志路线引导系统通过可变标志 牌和广播实现交通流诱导。由于可变标志牌仅显示单一路段交通信息，只适合诱导路段比 较单纯的高速公路网，而在行驶路径较为复杂的城市路网中，则会因为诱导路径过短而产 生误导现象。哈尔滨运用g p s 和集群通讯系统设计的实验性指挥调度系统，适合于公安、 消防、一电力等特殊交通集团做分组调度使用。由清华大学、北京人民广播电台和中科院 遥感所共同研制的车辆定位导航系统利用调频广播副载波传送差分g p s 信号，供车载 g p s 接受修正自己的位置。 1 3多目标算法的研究现状 多目标优化问题一直是科学和工程研究领域的一个难题和热点问题，不仅因为许多工 程问题本身就是一个多目标优化问题，而且在多目标优化领域内还存在着许多尚未解决的 难题。针对多目标这一问题，许多研究学者提出了一些经典的算法，对于已有的多目标优 化算法大体上分为两类：一类是基于偏好的方法，另类是产生式方法。基于偏好的方法 有线性加权法、理想点法、完全分层法等。产生式的方法有向量评价遗传算法【习、多目标 遗传算法i4 1 、非支配分层遗传算法【5 1 、小组决胜遗传算法【6 】等。 线性加权法根据各个目标在决策者心中的重要程度，分别给每个目标赋予权系数；理 想点法主要根据决策者事先对各个目标给出期望值，最优的解是与期望值最接近的解；完 全分层法将目标按重要程度排列成一个次序，把最后一个目标的最优解作为最终解。向量 评价遗传算法分别利用每一个目标从中群众选择部分优秀个体，组成相应的下代种群，然 后混合全部子种群并打乱此讯，从中均匀随机地选个体进行杂交和变异；多目标遗传算法 是对每个个体而言，排序中首先找到严格支配它的解数目n ，然后标记序号为行+ l ，标记 越大，适应度越高；非支配分层遗传算法是首先把种群中的所有非支配个体分配到第1 层，然后将这些个体从种群中移除，其次将剩余种群中的非支配个体分配到第2 层，依次 类推。小组决胜采用了竞争的方法进行适应度分配，将选出的两个候选个体和一定数量的 个体进行比较，来找处非劣解。以上这些求解多目标算法的研究成果解决了许多领域中的 多目标问题。近年来，有不少学者将这些经典的算法在特定领域的应用研究上，针对特定 领域的多目标问题，加以适当性的改进，得到不错的效果。 、 绪论 1 4 课题研究的意义 传统采用面向工程的路径诱导系统软件常用开发模式为平台式，即购买一个平台( 如 m a p i n f o ，a r c i n f o 等) ，在此基础上开发所需的系统。分析来看，用户对系统提出各种 各样的要求，由于用户的多样性他们对系统功能和价格的要求也不一样。另一方面随着路 径系统的发展，使系统平台的模块增多，功能增加，系统更大，对硬件配置的要求越来越 高，整套软件的价格自然越来越昂贵。显然使用“平台式”的开发模式不太符合中国的国 情。我们这个系统使用“构建式”开发模式，即从确定空间模型、数据模型这些最基础， 最核心的概念入手，完全构建自己的应用系统，每一步都是自行开发的，这样对于不同的 系统不会造成重复开发，又节约了成本。同时还具有以下三个优点： ( 1 ) 较强的灵活性。灵活性是利用v c + + 开发系统的最大优点，因为系统的所有流 程和数据都可以在设计者的控制之下，可以根据系统的具体要求实现具体的操作功能，在 一些g i s ( 特别是小型g i s 系统) 系统开发时，具有无可比拟的优势。它可以根据系统的 需要来实现功能，设计的系统短小精悍，软硬件要求低，运行速度快。 ( 2 ) 易于扩展成各种系统。用专业开发工具开发时，开发者所做的只是在别人系统 基础上的简单开发和应用，完全受开发工具的制约。而用v c 从底层开发，可以在开发过 程中不断完善，把系统的开发从应用项目级提高到开发工具级。 。 ( 3 ) 有系统的版权。开发者自身具有系统版权，在一些行业的大规模推广中具有无 可比拟的优势。 对于如何选择一条合理的出行路线是近年来研究的热点，如最短路径问题。关于最短 路径问题人们从很早以前就开始了研究，如上世纪5 0 年代的d i j k s t r a 算法，6 0 年代的f l o y , t 算法等等。随着现代科技的发展，人们又在解决最短路径问题中引入了遗传算法和模拟退 火算法，以及新提出的仿生类进化算法一蚂蚁算法等等。可以说一般的最短路径问题已经 基本可以解决。 本文分析了有关的研究成果，他们在解决路径最优的问题时基本上都是采用了前面阐 述的方法，针对交通所具有的特征，最优路径往往需要路程、时间、风险等多个目标能同 时达到最优。本课题使用遗传算法，设计出一种新的多目标算法，结合用户的偏好程度， 提供最优路线，给人们出行节约更多的时间和金钱。 。 1 5 论文的主要内容 本文的研究主要内容是依据上海市地图的一部分，开发出相应的路径诱导系统框架， 并构建网络拓扑图以及相应的数据库。同时本文在研究各种最优路径选择算法的基础上提 出了基于遗传算法的多目标最优路径选择算法，并验证了其可行性。 3 西安理工大学硕士学位论文 4 1 6 本章小结 本章分析探讨了路径诱导系统的研究背景与开展意义，介绍了路径诱导系统在国内外 的研究现状和多目标算法的研究现状。最后列出了论文研究的主要内容。 路径诱导系统框架研究 2 路径诱导系统框架研究 用v c + + 开发路径诱导系统，其实现的难度是较大的。一个最基本的路径诱导系统， 需要包含如下的组成部分：管理空间坐标数据的图形系统，管理性质数据的数据库管理系 统，以及实现图形系统与数据库管理系统双向连接系统。一些g i s 系统专业开发工具，如 m a p i n f o 等，也是用c + + 通过如上的思路，在图形系统基础上开发完成的。 2 1路径诱导系统的设计 2 1 1系统总体框架 在开发的初始阶段，首先利用面向对象方法对方法库进行分析和系统设计，得到方法 库的基本结构框架。从用户的角度来看，路径诱导系统最根本的任务是用于最优路径的查 询，还包括对各个站点信息的查询，为驾车者出行提供方便。站点数据的查询和路网分析 功能由底层数据库、功能模块、用户图形界面、最优路径算法四大部分组成。底层数据库 主要包括图形属性数据，通过o d b c 与底层数据库进行接口；各功能模块、图形界面设 计采用v c 实现。系统将空间地理信息和属性信息结合起来，使城市地理信息通过电子地 图的方式非常形象地显示出来，提供用户空间数据以及相关属性数据的浏览、查询、分析 、和显示，同时提供用户出行参考路线。系统的总体框架如图2 - 1 所示。 用户 r 交通诱导系统 王 王 l一 拓扑关系文件属性数据库 一一 图2 1 系统的总体框架 f i g u r e2 - 1t h et o t a lf r a m eo fs y s t e m 由图可以看出所有数据都存储在空间数据文件和属性数据文件当中，空间数据文件存 储的是网络拓扑图的结构，属性数据库存储的是站点的信息，包括i d 号、名称、坐标值 矗盘在盘 寸寸o 。 建立系统总体框架的基本工作流程： 5 西安理工大学硕士学位论文 ( 1 ) 开发软件用户界面。 ( 2 ) 组织图形元素，建立网络拓扑图，设置好点与点之间的相关，对拓扑结构保存 到空间数据文件中。 ( 3 ) 设计一个属性数据库，存储站点信息。 ( 4 ) 建立系统与属性数据库的连接。 2 1 2 系统设计的总体目标 路径诱导系统是一个面向自驾游用户的路径查询系统。系统的构建目标应从用户的需 求出发，根据尽可能根据用户的偏好提供最优的路线作为参考。由于自驾车用户在驾车的 过程中，需要以最快捷、最便利的方式到达目的地。因此，本文研究的路径诱导系统旨在 通过友好的人机交互界面，为用户提供快捷完备，并提供路线经过站点的信息功能。路径 诱导系统充分运用数据库，以确保大量信息的存储以及查询的效率。具体目标如下： ( 1 ) 可以根据需要扩大或删除站点信息，能够存取图形元素，能够更改网络拓扑图 结构。 ( 2 ) 建立后台信息服务中心，即数据库，为路径查询提供保证。 ( 3 ) 设计友好的查询交互界面，不仅能够在对话框里输入两点地名进行查询，也可 以用鼠标在地图上点击两地进行查询，以满足用户需求。 ( 4 ) 可提供最短路径查询，也可按用户偏好提供多目标最优路径查询。 2 1 3 系统设计的原则 系统按照以下原则进行设计： ( 1 ) 设计的程序应及时释放无用的内存资源，做到内存资源使用和释放的实时性。 ( 2 ) 文件保存避免出现大量附属信息的存储。 ( 3 ) 数据库应保证结果的合理性和过程的高效性。 ( 4 ) 系统应具有可扩展性和稳定性。 2 1 4 面向对象的图形系统设计模型 应用面向对象的系统分析方法，针对第一阶段对矢量图形系统功能的分析，可以确 定该系统的主要研究对象为：图元组织对象，对圆( c i r c l e ) 、直线( l i n e ) 、文本标注( t e x t ) 分别进行组织建立；管理各种图形元素的文档对象( d o c ) ；显示各种图形元素的视图对象 ( v i e w ) ；表征各种图元信息的属性对象( p r o p e r t y ) 。 6 链表基类c c i r c u i t b a s e 站点名称、i d 、颜色、 坐标、 获得下一个站点 获取颜色、改变颜色 设置i d 、得到i d 设置坐标、获取坐标 获取名称、设置名称 文档类c v i u s a l c i r c u it d o c 管理图元对象指针 管理图元参数对象 增加图元对象 得到图元数量 获取图元指针 删除图元对象 获取图元对象数组上标 图类c v i u s a l c i r c u i t v i e w 管理图形对象指针 显示所有站点 路线查询、站点查询 显示圆、直线、文本 应用程序类 站点 获得i d 号的站点信息 增加站点 删除站点 图2 2 基本图形对象属性与链表及关系图 f ig u r e2 - 2t h eb a s i cs k e t c ho b j e c ta t t r i b u t ea n da b u t m e n tc h a i na n dt h er e l a t i o nd i a g r a m 7 西安理工大学硕士学位论文 2 2图形系统的开发 图形系统是路径诱导系统最重要的组成部分，也是用v c + + 开发g i s 系统的重点和难 点所在。不同的应用领域对图形系统的要求不一样，其需要的图形系统的功能是有差别的： 有的需要矢量图( v e c t o r b a s e di m a g e ) ，有的则需要位图( b i t m a p ) ；有的只需要处理普 通的图形元素，有的则还需要丰富的图形元素和线形等等。 本系统的图形开发部分包括了类组织、文档管理、图形选中、图形删除、图形存取等 各个方面。 2 2 1组织图形元素类 对于一个图形系统来说，都有一个信息组织的问题。即：如何组织图形所需要的信息 才能有效的节省存储空间? 才能提高程序处理的速度? 这里所说的信息为图形信息和非 图形信息，构成物体的点、线的位置、相互关系及几何尺寸等属于图形信息；而表示图形 的线型、颜色等属于非图形信息。对各类图形元素进行分析，可以发现各类图形元素具有 一些相同的属性和操作功能，如图形元素的颜色、线型、线宽等属性。把这些图形元素中 共性的东西( 属性和操作) ，组织存放在一个图形元素基类c d r a w b a s e 中，具体的图形元 素类则由c d r a w b a s e 来派生。在c d r a w b a s e 类中，定义一个成员变量，这个成员变量用 来惟一地确定一类图形元素中的一个图形元素，具有十分重要的作用。 每个图形元素是图形元素类创建的一个对象，而要较好的管理图形对象，则选择基于 c + + 模板的类具有更好的类型安全性，也不需要使用类型强制转换。使用基于模板类的方 法如下，在创建这个对象时得到指向这个对象的指针，建立一个对象指针数组( 如定义一 个管理基类指针对象：c t y p e d p t r a r r a y md r a w a r r a y ) 来管理这 些指针，以达到管理所有图形元素对象的目的。其中图形元素对象的指针被保存在文档类 对应得c o b a r r a y 对象中。 在路径系统中的图形系统，不仅需要具备绘图功能，还需要具有图形之间能够建立起 相关，即拓扑结构，并且能够进行图形的增加和删减。为了能够随时对网络图进行修改， 需要生成链表基类c c i r c u i t b a s e ，它的功能主要包括：获取站点信息，包括i d 、坐标、名 称、进行图形的扩展和删除、定义或修改拓扑结构、得到相邻站点的信息、得到图形元素 的数目等。 2 2 2 绘制站点图层 根据路网添加站点，对每个站点赋予不同的标识号，点击鼠标时鼠标响应函数 o n l b u t t o n d o w n 、o n l b u t t o n u p 绘制站点。用鼠标左键单击要设置处，出现红色站点， 8 路径诱导系统框榘研究 同时显示出站点标号，添加完后，生成站点困层，同h , i 为了避免出现一个站点与很多个站 点相关联的情况，需要添加街道与街道的交叉点，【三l 保证一个站点虽多只和四个站点干h 关， 这样简化了拓扑结构、提高了算法的搜索速度。同时站点图层巾的每个站点标号与数据库 中的站点表数据进行数掘绑定并且每增加一个站点图2 7 巾的左边列表中自动增力一个 站点标号。所有站点都保存在c a r r a y m变量中，用于存储己创建ararray 站点对象指针的数组。其中需要将站点设备屯标转换为逻辑坐标。图2 - 3 为绘制站点图层 程序流程图。 焦卉“$ 加阁杯”按 * 始镕加# 点 弹小 珥硅添m * 点竹息 图2 - 3 站点图层程序流程图 f i g u r e2 3f ks m t j o n o r d e r sd i a g r a m l a i r p r o c e d u r e 目o w 曲盯t 添加节点后的地图如图2 - 4 盔_ 4 譬t 五誓i 霍函i 盔i i i i i i i i i i i i i 蓄蚕萄 一10 p e ；c 咄 l - g u8f ! 二二! 图2 - 4 添加节点后的地图 f lg u r e2 - 4a d d t h e m a p o f t h en o d e 西安j e - y - 大学硕士学位论文 2 2 3 图形的存取 系统的文档需要存盘做永久备份。对于图形系统来说，要把图形以文件的形式保存起 来，并能够打开文件重新编辑图形。应用程序的文档是基于对象的，而保存文档资料时， 不可能把对象整个存储，重点在于存储对象中的成员变量，同时需要存储一些类的信息， 使系统在打开保存图形的文件时，可以利用类的信息和保存的成员变量重新创建对象，而 不损失任何信息。 在传统的应用程序，一般直接对二进制文件进行操作来完成数据资料的存取操作，如 利用c f i l e 文件对象、f s t r e a m 文件流等。但在面向对象中利用二进制文件流操作直接存储 数据资料存在过程比较繁琐，例如应用程序中有大量的点对象，可以在点类中增加一个成 员函数完成对点类的成员变量的存储，但是在把点的数据资料从存储对象中读取出来的时 候，需要首先创建一个点对象，然后调用点类的读取函数读取直线的成员变量。 串行化就是为了适应在面向对象中解决对象的存储和创建设计的。只需在图形类的头 文件中使用声明d e c l a r es e r i a l ( 图形类名) ，在实现部分使用i m p l e m e n ts e r i a l ( 图形类名，基类名，1 ) ，通过一个c a r c h i v e 对象来完成管理对象的数据资料的功能， 而一个c a r c h i v e 对象是在一个c f i l e 对象基础上建立起来。通过c a r c h i v e 对象利用 c a r c h i v e 类提供的功能来对图形对象的数据进行管理。 2 2 4 站点的查询 交互系统中，站点选取是实现站点查询和最优路径查询的关键。它主要与检索方法有 关。当用户点击坐标( ，y 。) 后，可得到一个选取站点邻域( 吒4 - a ，y 。- 4 - a ) ，如果在站点 邻域内有站点，则选取离用户点击坐标( ，y 。) 最近，若不符合用户所需要的站点，可通 过删除，重新进行站点的选取。如果站点完全在窗口之外，该站不被选中，需重新选取站 点。 2 3 构建网络拓扑关系 要对城市道路网进行最优路径分析，首先必须将现实中的城市道路网络实体抽象化为 网络图论理论中的网络图，然后通过图论中的网络分析理论来实现道路网络的最优路径分 析。在实际应用中，城市道路其网络空间特征中的站点坐标和交叉路口坐标位置是在地图 上借助图形来识别和解释的；而为了能够高效率地进行最优路径分析，必须首先将其按站 点的关系抽象为图的结构。这就需要先对原始城市地图进行预处理，建立其相应的网络拓 扑关系。 打开一幅电子地图，对相应的站点进行属性及空间信息设置，系统采用邻接表的链式 1 0 路径诱导系统框架研究 存储结构，如图2 5 、2 6 t 7 】所示。对设置好的网络图进行拓扑结构的构造，建立起各个站 点的相联关系。 名称编号 壬站点 ，、 ，娑望点2 主站点 辅蹦剌 m 名矗站点5 圭站点 图2 - 5 邻接链 f i g u r e2 - 5a b u t m e n tc h a i n 2 3 1 拓扑关系的数据模型 制。| i 赶 嘛 址u 美u 主0 编号l 主2 编号i 0 坐标值| 主2 坐标值i ! 班：鲤土| - - - 坐硎坐橱i陲标i 坐标i 一 主。编号i 主l 编号i 图2 6 邻接链存储 f i g u r e2 - 6t h es t o r a g eo fa b u t m e n tc h a i n 拓扑关系数据模型以拓扑关系为基础组织和存储各个几何要素，其特点是以点的拓 扑连接关系为中心，它们的坐标存贮具有依赖关系。该模型的主要优点是数据结构紧凑， 拓扑关系明晰。 本文研究的路径查询系统选用面向实体的数据模型。该模型以独立、完整、具有地理 意义的实体为基本单位对地理空间进行表达。每个对象( 独立的地理实体) 不仅具有自己独 立的属性( 含坐标数据) ，而且具有自己的行为( 操作) ，能够自己完成一些操作。该模型能 够很好地克服拓扑关系数据模型的几个缺点，具有实体管理、修改方便，查询检索、空间 分析容易的优点，非常适合本文研究的路径查询系统的实际需求。 本文研究的路径诱导系统所涉及的数据包括四大类别： ( 1 ) 站点的空间数据( 站点坐标信息) 。 ( 2 ) 站点的属性数据( 对象名字，基本属性) 。 ( 3 ) 站点间的拓扑关系数据( 关联的点，路段信息) 。 在具体组织和存储时，对实体的坐标数据和属性数据，存放在属性数据库中保存。对 空间信息的存储，系统采用文件存储方式，拓扑结构上的每一个站点的拓扑信息按顺序依 次存储到文件中，使用文件的写入操作进行保存。拓扑结构信息会一直保存在文件中，以 后打开同一幅电子地图，会同时访问到文件，进行文件的读操作，重新恢复站点的拓扑信 息。 建立系统与数据库的连接，对属性数据，系统采用a c c e s s 来存储，每个站点属性 的关键字均用其对应的唯一标识，由此便实现了电子地图中各站点与数据库各属性一一对 应的关系。 西安理工大学硕士学位论文 设置站点间的拓扑连接如图2 7 i 龇! 塾丛! ：i 巍 ： 塑塑懦 柳 移脒目r 琵 确认谴次i 殳置围 v 完成所有 殳置必】 刚2 7 站点间的拓扑连接 f i g u r e2 - 7 t h ec o r l n e c o f t h ea m o n gs l a t i o n 若需对站点进行拓扑连接或修改拓扑连接，只需要打开如图2 7 的对皤框，双击左边 需要设置的站点，通过“添加”设黄需要关联的点或通过“移除”删除不需要相关联的点。 若正确无误可点击“确认这次设置”，则重新更改了该站点的相关联点。 有的时候两个站点问可能小是一条直线，所以需要设簧一些辅助站点，如图2 _ 8 所示， 选择阿个漆加的站，在站点之叫添加辅助的站点。 n ；盂盟蓝孟簟幽 现有主地点 ：“垦塑到地 。： ：! 移睬回r 5 3 一 巨_ 斩5 f i 匦回主地点2 n 器移除回 5 9 一 6 0 6 i 。_ _ 嚣确认这发设置圄l 嚣 。 完成所有设置乜】 圈2 - 8 辅助站点的设置 f i g u r e 2 8 t h es 目o f a s s i s t a n ts t a t i o n 路径诱导系统框架研究 2 3 2 路网的存储结构 因为路网的基本表达方法是赋权图，因此其存储结构也类似于图的存储结构。也就是 说，路网可以用图的存储结构来存储。下面首先介绍图的有关存储结构，当然也可以作为 路网基本的存储结构，然后在此基础上，研究两种适合路网特点的存储结构。 从路网的直观结构考虑，很自然地会想到用图来表示路网，站点对应结点，两结点之 间的路段对应边，路段的某种量化属性作为权值，这样用一个赋权图就可以初步地描述路 网；而且用图来表示路网也符合最优路径的计算和选择的需要。下面介绍论文中与图相关 的基本定义和术语。 图是一种结构复杂的数据结构，表现在不仅各个结点的度可以千差万别，而且结点之 间的逻辑关系也错综复杂。一个图的信息包括两部分，即图中结点的信息以及描述结点之 间关系的一边的信息。因此无论采用什么方法建立图的存储结构，都要完整、准确地反映 这两方面的信息。其中采用邻接矩阵和邻接表是图的两种基本存储方式，下面分别予以说 明 s i 9 1 。 邻接矩阵 所谓邻接矩阵的存储结构，就是用一维数组存储图中结点的信息，用二维数组及矩阵 表示图中各结点之间的邻接关系。 。 设g = ( v ，e ) 是具有咒个顶点的图，则g 的邻接矩阵是具有如下性质的n 阶方阵：1 雒川球熟蹴黼 浯， 若g 是g = ( v ，e ) 是具有，1 个顶点的网络，则邻接矩阵可定义为： 雒叫。象纛蹴端 倍2 ， 使用邻接矩阵存储路网的优点： ( 1 ) 方便求结点的度。即邻接矩阵的第i 行( 或第f 列) 非零元素( 或非o o 元素) 的个数正 好是第i 个结点的度。 ( 2 ) 容易确定路网中任意两个结点之间是否有路径相连。即邻接矩阵中非零元素对 应的两个结点是相连的。 ( 3 ) 能够表达路网中的单行线。 邻接表 邻接表是图的一种顺序存储与链式存储结合的存储方法。就是对于图g 中的每个结 点，将所有邻接于u 的结点链成一个单链表，这个单链表就称为结点u 的邻接表。在邻接 表表示中有两种结点结构，如图2 9 、2 1 0 所示。 1 3 西安理工大学硕士学位论文 图2 - 9 头节点结构 f i g u r e2 - 9t h es t r u c t u r eo fh e a d n o d e 图2 - 1 0 表节点结构 f i g u r e2 - 1 0t h es t r u c t u r eo ft a b l en o d e 一种是顶点表的结点结构，它由顶点域( v e r t e x ) 和指向第一条邻接边的指针域 ( f i r s t e d g e ) 构成，另一种是表( 即邻接表) 结点，它由邻接点域( a d j v e x ) 和指向下一条接边 的指针域( n e x t ) 构成。用邻接表存储路网的优点是在邻接表上容易找到任一结点的第一个 邻接点和下一个邻接点。同时，根据稀疏图的定义，稀疏图有m o ( n ) 条边。因此，用一 个邻接表描述稀疏图需要的存储空间是o ( n ) ，显然优于用邻接矩阵描述稀疏图需要的存 储空间o ( n 2 ) 。 但是由于邻接表法是通过链表来组织邻接于同一个结点的路段信息，不是将由同一个 结点发出的所有路段存放在一起，而是通过指针来查询，在进行查询或者搜索时就需要遍 历整个的链表，对路径搜索的速度会有所影响。 图的邻接表如图2 - 1 1 所示。 场乃 12 3 o 2 3 01 0 1 图2 1 l 邻接表 f i g u r e2 1 1a d j a c e n c yl i s t 2 3 3 系统所采用的数据结构 在图形系统中；用户对图形的增、删、改等处理操作实质上是通过对图形数据结构 的相应操作来实现的。图形的存储需要占用大量的内存单元，不仅需要记录点、线等信息： 而且还要记录它们之间的拓扑关系信息，另外由于复杂图形和简单图形之间需要存储的信 息量的差别会很大，因此图形的存储结构设计是绘图系统设计的一个重要方面，它直接影 响着系统的性能和资源的利用率。 用数组存放数据时，必须事先定义固定的长度( 即元素个数) 。比如，有的班级有5 0 人，而有的班级只有3 0 人，如果要用同一个数组先后存放不同班级的学生数据，则必须 定义长度为5 0 的数组。如果事先难以确定一个班的最多人数，则必须把数组定得足够大， 以能存放任何班级的学生数据。显然这将会浪费内存资源。 1 4 路径诱导系统框架研究 另外，由于图形系统需要经常进行站点单元的插入、删除、修改和编辑等操作，因 此会引起大量站点的移动，采用数组这样的存储结构很难实现上述要求。而链式存储结构 通过在每个站点中包括一定数量的指针域，用指针来体现元素之间逻辑上的联系。这种存 储结构可把人们从计算机存储单元的相继性限制中解放出来，可以把逻辑上相临的两个元 素存放在物理上不相临的两个存储单元中，还可以在线性编址的计算机存储器中表示站点 之间的非线性关系。另外，由于每个站点是通过指针来实现链接的，因此可以不用像数组 那样必须事先定义固定的存储单元，而可以在程序运行过程中根据需要动态地申请节点单 元。而且实现插入、删除操作灵活方便，不必移动站点，只要改变站点中的指针值即可。 弥补了线性存储结构的不足。 本系统中图形数据的存储主要采用线性链表结构，线性链表就是链式存储的线性表， 可以进行查找、插入、删除等操作。 为了更充分地利用有限的内存资源，本系统在内存的动态分配和回收等方面作了大 量的工作，在建立图形元素，如点、线等单元时，用n e w 关键字在堆内存中申请适量的 内存，当执行删除站点操作的时候，用d e l e t e 关键字来完成这段内存单元的释放，通过 不断地在适当的时候申请内存和释放内存来实现内存的动态分配和回收，以达到充分利用 有限的内存资源的目的。 2 4 路网属性数据库的设计与实现 路网属性数据库是存储路网基本要素结点、路段属性信息的数据库。对于进行最优路 径选择以及对道路进行查询定位等，路网的属性数据库是必须的。路网属性数据库往往和 电子地图结合在一起的。由于电子地图不具有路网属性数据库，可以单独设计路网属性数 据库，然后再与电子地图关联起来。路网属性数据库规划，