敏捷式网络导航服务的数据模型设计与应用算法研究

论文摘要

本文在分析导航服务的敏捷式需求的基础上建立了敏捷式网络导航服务的概念,主要研究了敏捷式网络导航服务的导航数据模型设计、拓扑关系处理算法、敏捷式最优路径规划与引导算法等内容,实现了导航结果对于出行时间、用户信息、交通网络、最优标准的敏捷相关。本文的主要研究内容和创新点如下:1、建立了敏捷式网络导航服务的概念,该服务的目标是提高导航服务的质量,设计了敏捷式网络导航服务的体系结构和功能流程。敏捷式网络导航服务概念的建立是本文的一个理论创新点。2、在总结导航数据模型相关理论的基础上设计了面向敏捷式网络导航服务的交通网络数据模型。将交通网络中面向敏捷式导航应用的属性划分为拓扑连通属性、通行阻力属性、道路可用性属性和网间衔接属性四大类。建立了所有动态通行阻力属性对出行时间和用户特征的函数依赖,并且可以化归为经济花费这一共同阻力指标。面向敏捷式网络导航服务的交通网络数据模型的建立是本文的重要创新点。3、设计了交通网络数据的拓扑关系生成及属性编辑算法。假设源数据是没有任何拓扑关系的原始采集数据,先要对该数据进行特征点提取处理,然后实施道路交汇点的特征点提取算法,接下来实施拓扑关系生成算法将交通网络的底层的几何拓扑关系自动生成并存入前面设计的交通网络数据模型中,属性编辑算法实现了对交通网络数据中所有属性的编辑。4、设计了网络拓扑图的数据模型与拓扑关系提取算法。本文设计了Graph类,其对象的数据成员用以存储网络拓扑图数据,方法成员用于后续的最优路径规划算法。设计的拓扑关系提取算法可以将交通网络数据中所有与路径规划相关的数据(不含坐标几何数据和分流车道数据)都提取到Graph对象的数据成员中。Graph类的设计是本文的重要研究内容。5、实现了动态交通信息的融合。动态交通信息有两种,分别是统计动态交通信息(SPI数据)和实时交通信息。其中SPI数据在拓扑关系提取过程中已被提取到Graph对象中。本文主要设计了临时交通管制和路段拥塞两种类型的实时交通信息的融合算法。6、设计了弧间敏捷式最优路径规划与在线路径引导算法。将城市交通中的节点间最短路径问题拓展到弧间最优路径问题,并给出了弧间最优路径问题的定义及严密数学表达。建立了兴趣点(POI)与网络拓扑图中弧的绑定关系,设计了弧间敏捷式最优路径规划算法。根据现代社会对最优路径标准的多样化需求,设计了5种最优模式表达不同的最优搜索指标,分别为距离模式、紧急模式、环保模式、经济模式、工商模式。设计了在线路径引导算法,实现服务器对客户端的跟踪导航。设计的敏捷式路径规划与引导算法实现了敏捷式导航服务的目标,是本文的重要创新点之一。7、设计了用户注册算法。用户注册技术是用户提交用户信息采用的技术,本文主要设计了用户信息的数据结构以及移动客户端与服务器端的通讯协议,设计的用户信息包括个人信息和汽车信息两方面的内容,用户信息的注册保证了导航服务与用户特征信息的敏捷相关。在文章的最后,本文对前述研究内容做了大量的试验和实践工作。通过实验得出结论:本文设计的数据结构和算法可以实现敏捷式的导航服务,有助与提高导航服务的质量。如果绝大多数城市驾车用户都使用敏捷式网络导航服务,SPI数据的自学习机制会逐渐导致车流在时间和空间上的合理分布,最终会导致城市交通网络对所有通行需求的最大、最优承载。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 引言
• 1.2 导航模式的发展
• 1.2.1 自主导航模式的不足
• 1.2.2 自主导航模式发展为网络导航服务模式
• 1.3 敏捷式网络导航服务
• 1.3.1 导航服务的敏捷需求
• 1.3.2 敏捷式网络导航服务概念的提出
• 1.3.3 敏捷式网络导航的可行性
• 1.3.4 敏捷式网络导航服务体系的总体设计
• 1.4 研究内容与术语约定
• 1.4.1 研究内容与章节组织
• 1.4.2 术语约定
• 第二章 导航数据模型基础理论
• 2.1 导航数据的内容构成
• 2.2 导航数据概念模型
• 2.2.1 导航数据总体概念模型
• 2.2.2 导航数据模型中的要素分类与表达
• 2.2.2.1 导航数据中的要素的层次化分类
• 2.2.2.2 导航数据中要素的抽象层次与要素表达规则
• 2.2.3 导航数据模型中的要素属性
• 2.2.4 导航数据模型中的要素关系
• 2.2.4.1 要素的拓扑关系
• 2.2.4.2 要素的语义关系
• 2.3 导航数据逻辑模型
• 2.3.1 导航数据要素的逻辑表达
• 2.3.2 导航数据要素属性和关系的逻辑表达
• 2.4 本章小结
• 第三章 面向敏捷式导航的交通网络数据模型设计
• 3.1 交通网络数据的内容构成
• 3.2 交通网络的数据模型设计
• 3.2.1 交通网络数据模型的一般描述及要素属性的分类与拓展
• 3.2.2 交通网络中拓扑连通属性的数据模型设计
• 3.2.2.1 路段单行属性数据模型
• 3.2.2.2 不可调头属性数据模型
• 3.2.2.3 转弯限制属性数据模型
• 3.2.2.4 转弯前分流车道的数据模型
• 3.2.2.5 立交桥的实现
• 3.2.3 交通网络中通行阻力属性的数据模型设计
• 3.2.3.1 拥塞系数对动态通行阻力属性影响的定性分析
• 3.2.3.2 统计通行时间SPI模型的建立与采集方法的设计
• 3.2.3.3 基于 SPI的阻力属性数据模型
• 3.2.3.4 道路收费属性的数据模型
• 3.2.4 交通网络中道路可用性属性的数据模型
• 3.2.4.1 道路对用户车辆的限制可用性属性数据模型
• 3.2.4.2 用户对道路类型的选择可用性属性数据模型
• 3.2.5 交通网络的分级分块设计及网间衔接属性的数据模型
• 3.2.6 其他与时间和用户信息相关的属性
• 3.3 本章小结
• 第四章 交通网络数据的拓扑关系处理及动态交通信息融合
• 4.1 拓扑关系处理的层次结构
• 4.1.1 拓扑关系处理的组织结构及算法流程框图
• 4.1.2 算法阐述中使用的地图数据格式和开发平台
• 4.2 交通网络数据的来源与预处理算法
• 4.2.1 道路网数据来源与线要素特征点提取算法
• 4.2.2 道路交汇口特征点生成算法
• 4.3 拓扑关系数据生成算法
• 4.3.1 基于 MapInfo数据格式的交通网络数据模型
• 4.3.2 拓扑关系生成算法
• 4.4 拓扑关系编辑功能设计及实现算法
• 4.4.1 基本拓扑编辑的功能划分与实现算法
• 4.4.1.1 基本拓扑编辑功能设计
• 4.4.1.2 弧段拆分算法
• 4.4.1.3 弧段合并算法
• 4.4.2 高级拓扑编辑的功能划分与实现算法
• 4.4.2.1 网内高级拓扑编辑功能设计
• 4.4.2.2 SPI信息的引入方法
• 4.4.2.3 分级分块交通网络之间的拓扑关系处理方法
• 4.5 网络拓扑图存储结构设计与拓扑关系提取与存储
• 4.5.1 网络拓扑图的存储结构设计
• 4.5.2 拓扑关系提取算法
• 4.5.3 网络拓扑图的文件存储
• 4.6 实时交通信息的融合
• 4.6.1 临时交通管制信息指令格式及融合操作
• 4.6.2 道路拥塞信息指令格式及融合操作
• 4.7 本章小结
• 第五章 敏捷式最优路径规划算法
• 5.1 最优路径问题的提出与分类
• 5.2 经典 D算法描述及算法优化思路
• 5.2.1 经典 D算法
• 5.2.2 经典 D算法的优化方法
• 5.3 最优路径问题的拓展
• 5.3.1 现代城市交通中最优路径问题的特殊性
• 5.3.2 弧间最优路径问题的定义
• 5.3.3 兴趣点要素与网络拓扑图中弧的绑定方法
• 5.3.3.1 交通网络数据阶段的 POI数据结构设计和属性编辑
• 5.3.3.2 POI到网络拓扑图中弧的匹配算法
• 5.4 基于 D算法的弧间敏捷式路径规划算法设计
• 5.4.1 敏捷式最优路径规划概念的提出及优势
• 5.4.2 弧间敏捷式最优路径规划
• 5.4.2.1 已知参数和最优搜索指标
• 5.4.2.2 算法辅助变量的设计
• 5.4.2.3 算法步骤流程图
• 5.4.2.4 路径规划结果格式
• 5.4.2.5 不同参数组合的处理方法
• 5.5 分级分块交通网络的最优路径规划
• 5.6 本章小结
• 第六章 用户注册与在线路径引导
• 6.1 用户注册技术
• 6.1.1 用户信息数据的数据模型
• 6.1.2 用户信息注册流程及通信格式
• 6.2 在线路径引导技术
• 6.3 用户 IP更新通知机制
• 6.4 本章小结
• 第七章 敏捷式网络导航服务的实验与实践
• 7.1 不同等级道路图层的合并及预处理
• 7.2 拓扑关系生成算法的程序实现
• 7.3 拓扑编辑功能的程序实现及数据录入
• 7.4 实时交通信息的引入与在线路径引导服务
• 7.5 敏捷式弧间最优路径规划算法的程序实现
• 7.6 本章小结
• 第八章 总结与展望
• 8.1 全文总结:
• 8.2 不足与展望
• 参考文献
• 作者简历 攻读硕士学位期间完成的主要工作
• 致谢