地图服务系统设计及路径查找算法研究

发布时间：2017-09-24 09:10

  本文关键词：地图服务系统设计及路径查找算法研究

  更多相关文章： 地图服务 路径查找 Dijkstra算法 A*算法

【摘要】：在科技与经济日益交融，协调发展的现代社会，地图服务技术的广泛应用深刻的影响着我们每天接触到的各个领域。小范围包括人们的定位搜索，交通出行和道路导航等，大范围包括国家的物流运输，紧急救援和军事行动等。作为地理信息系统（GIS）学科的一部分，随着电子计算机技术、人工智能技术和制图渲染技术等的飞速发展与进步，地图服务技术也日趋发展成熟与完善。 地图服务的主要功能是存储、发布、组织和管理海量的空间数据，方便客户端的在线查询、检索、分析和下载等，，使得各种实时实地的空间地理信息得以高效利用，满足不同的现实需求。作为地图服务系统的重要组成部分，因为不断完善的图论理论和数据结构，路径查找功能逐步发展成为地图服务的一个重要应用，通过多种经典路径查找算法的相互结合，各种新的更切合实际的最短路径查找算法不断地被研究出来，特别是在算法步骤的易实现性、算法运算的时间和空间复杂度以及算法结果的应用范围等方面各有进展。 总体来说，在地图服务系统中，针对道路交通网络的路径查找问题有三种查找策略，分别是广度优先查找策略、深度优先查找策略和启发式查找策略。具体的几种研究较成熟的经典路径查找算法主要包括Dijkstra算法和A*算法等。其中，Dijkstra算法是一种贪心算法，其基本原则是在进行每一步的结点计算时都是通过选择一个局部的最优解以期得到一个最终总体的最优解。而A*算法是一种先通过最大可能加载计算已知信息，向最有希望结点为查找目标去查找的启发式查找算法，这种查找策略在静态路网中解决最短路问题有很好的效果。 本文对几种经典的路径查找算法做了深入分析和研究，在分层路网的基础上，考虑到实时实地的交通道路网络中变量较多的情况，将道路属性和路况信息等影响因子的不同权重值加载到路径查找算法的计算公式中，通过算法计算得出不同的路径优先级，在每个计算结点处形成不同优先级的路径集。边计算路径优先级，边查找下一路径，在减少路径查找规模的同时，使得路径查找计算的逻辑更加清晰。再结合项目背景和实际交通道路网络的不同限制条件以及用户不同的实际需求，计算出“空间距离”最短的选择路径，“时间距离”最短的选择路径和“经济距离”最短的选择路径等。最后对具体实验数据进行对比分析，验证本文设计的地图服务系统中所涉及到的路径计算方法具有一定的稳定性、优越性和高效性等。
【关键词】：地图服务 路径查找 Dijkstra算法 A*算法
【学位授予单位】：河南大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：P208
【目录】：

• 摘要4-6
• ABSTRACT6-11
• 第一章 绪论11-17
• 1.1 研究背景及意义11-12
• 1.2 国内外研究现状12-15
• 1.2.1 地图服务的发展现状与研究趋势13-14
• 1.2.2 路径查找算法的研究现状14-15
• 1.3 主要内容及组织结构15-17
• 第二章 相关理论及技术介绍17-27
• 2.1 开发语言与开发环境17
• 2.2 地图服务相关理论介绍17-20
• 2.2.1 地图服务的概述18-19
• 2.2.2 空间地理信息的表达19-20
• 2.3 道路网络拓扑结构的构建20-24
• 2.3.1 路网的分层21-22
• 2.3.2 路段的分割处理22-23
• 2.3.3 道路网络拓扑结构的构建23-24
• 2.4 路径查找算法的理论介绍24-25
• 2.5 本章小结25-27
• 第三章 系统设计27-45
• 3.1 系统开发与部署27-28
• 3.1.1 架构设计27-28
• 3.1.2 系统开发部署的计算机配置28
• 3.2 系统功能描述28-33
• 3.2.1 单点坐标附近查找功能设计29-30
• 3.2.2 固定公交路线查找功能设计30-32
• 3.2.3 非固定交通路线查找功能设计32-33
• 3.3 类与接口33-38
• 3.3.1 分析网络：NetworkManager 类33-34
• 3.3.2 限制搜索路径：SysConstraint 类34-35
• 3.3.3 高级分析功能：网络约束35
• 3.3.4 拓扑网络结构：Network、Node、Link 和 Path 类35-37
• 3.3.5 创建拓扑网络：NetworkBuilder 类37
• 3.3.6 接口实现37-38
• 3.4 数据库表设计38-41
• 3.4.1 空间地理信息的数据表设计38
• 3.4.2 空间地理分层网络的数据表设计38-41
• 3.5 系统维护41-43
• 3.5.1 网络拓扑数据维护41-42
• 3.5.2 数据库维护42-43
• 3.6 本章小结43-45
• 第四章 算法研究与实验验证45-57
• 4.1 优先级的定义45-49
• 4.1.1 路径优先级基类45-46
• 4.1.2 路径优先级分级计算流程46
• 4.1.3 路径优先级的计算方法46-49
• 4.2 以 DIJKSTRA 算法为基础的算法改进实现49
• 4.3 以 A*算法为基础的算法改进实现49-51
• 4.4 实验内容51-56
• 4.4.1 单点坐标附近查找功能实验52-53
• 4.4.2 固定公交路线查找实验53-55
• 4.4.3 非固定交通线路查找实验55-56
• 4.5 本章小结56-57
• 第五章 总结57-59
• 参考文献59-61
• 参加项目61-62
• 致谢62-63

【参考文献】

中国期刊全文数据库 前9条

1 张山山,边馥苓;地理信息系统数据模型分析[J];测绘通报;2004年08期

2 潘农菲;GIS的空间数据在关系型数据库的实现理论及应用技术[J];计算机应用研究;2002年02期

3 乐阳,龚健雅;Dijkstra最短路径算法的一种高效率实现[J];武汉测绘科技大学学报;1999年03期

4 肖乐斌,钟耳顺,刘纪远,宋关福;GIS概念数据模型的研究[J];武汉大学学报(信息科学版);2001年05期

5 李德仁,朱欣焰,龚健雅;从数字地图到空间信息网格——空间信息多级网格理论思考[J];武汉大学学报(信息科学版);2003年06期

6 艾廷华,成建国;对空间数据多尺度表达有关问题的思考[J];武汉大学学报(信息科学版);2005年05期

7 李德仁;苗前军;邵振峰;;信息化测绘体系的定位与框架[J];武汉大学学报(信息科学版);2007年03期

8 唐文武,施晓东,朱大奎;GIS中使用改进的Dijkstra算法实现最短路径的计算[J];中国图象图形学报;2000年12期

9 李楷;钟耳顺;曾志明;曹国峰;;基于分层网络拓扑结构的最优路径算法[J];中国图象图形学报;2006年07期

本文编号：910547