基于最短路径Dijkstra算法的铁路客运中转径路优化研究

论文摘要

信息技术的不断发展促进了其在更多领域的广泛应用。在铁路旅客运输中,对铁路客运中转径路优化,既是旅客合理选择出行方案时十分关心的问题,也是提高铁路运输部门工作效率和质量的有效途径。铁路客运中转径路优化是基于铁路运输网拓扑结构的最优路径算法问题。因为具有实际的应用背景,最优路径算法考虑的因素和限制条件比经典最短路径算法复杂得多,其核心思想还是源于经典最短路径算法。本文在综合分析最短路径算法的基础上,提出从网络规模和搜索技术两方面改进Dijkstra算法。结合铁路客运网络的空间分布特点,对路网分层模型、客运中转计算模型、客运网的存储数据结构和最短路径算法的运行数据结构等关键技术进行了研究,最后实现了改进的铁路客运中转径路计算算法。主要工作包括:①对最短路径算法的存储数据结构和搜索节点采用的数据结构,及最短路径算法的分类体系进行了介绍;分析了Dijkstra算法的主要思想,并对Dijkstra算法的优化途径进行研究。②对铁路网的拓扑关系进行研究,提出了采用两级分层的层次模型来表示铁路网,以减少分析过程中搜索节点的数量;对非基点车站参与径路计算提出了动态基点化的解决方法。③对客运中转径路计算模型进行分析研究,提出了包含车站和车次信息的可扩展的计算模型。④对包含车次信息的铁路客运网络的存储结构进行研究,提出了采用车次-到站邻接表作为网络的存储结构,使搜索的结果是基于车次的而不仅是基于线路的;采用优先队列来优化算法的运行结构,提高了算法的运行效率。⑤采用三级分层的架构体系进行系统框架设计,运用面向对象方法提出用车站、车次、线路、时刻表等类表示铁路客运网络,并进行了数据库分析设计和径路计算流程设计。本文将Dijkstra算法应用于铁路客运中转径路优化问题的研究中,提出了铁路网的层次模型和新的客运中转径路计算模型,具有实际应用价值。结合铁路运输网拓扑结构的实际情况,对Dijkstra算法中的数据结构和运行结构进行了改进,对相关的研究及实际系统分析设计也具有一定的参考价值。

论文目录

• 摘要
• ABSTRACT
• 1 绪论
• 1.1 课题研究背景及意义
• 1.2 国内外研究现状
• 1.2.1 对基于图搜索策略的最短路算法研究
• 1.2.2 对最短路算法的数据结构优化研究
• 1.2.3 与实际网络空间特性相结合的搜索策略研究
• 1.2.4 最短路径算法的实时性并行化研究
• 1.3 本文研究内容
• 1.4 本文组织结构
• 2 最短路径算法的分析研究
• 2.1 最短路径算法概述
• 2.1.1 网络拓扑存储数据结构
• 2.1.2 算法运行数据结构
• 2.2 最短路径算法分类
• 2.2.1 问题类型分类
• 2.2.2 网络类型分类
• 2.2.3 实现方法分类
• 2.3 最短路径算法的标号法实现
• 2.3.1 标号算法描述
• 2.3.2 标号算法流程及复杂度分析
• 2.4 传统 Dijkstra 算法分析
• 2.4.1 传统Dijkstra 算法的主要思想
• 2.4.2 Dijkstra 算法改进分析
• 3 铁路客运网络的层次模型
• 3.1 路网特点
• 3.2 路网模型
• 3.2.1 路网层次模型
• 3.2.2 端点动态基点化
• 3.2.3 路网区域划分
• 3.3 路网拓扑关系
• 3.4 路网网络模型的求解
• 3.4.1 任意发到站间最短路径的求解
• 3.4.2 支点站间最短路径的求解
• 4 基于 Dijkstra 算法的铁路客运中转径路优化算法设计
• 4.1 铁路客运中转径路的计算模型
• 4.1.1 客运径路计算分析
• 4.1.2 主要铁路客运换乘网络计算模型分析
• 4.1.3 铁路客运中转径路计算模型
• 4.2 客运网络的邻接表存储结构
• 4.3 基于优先队列的算法运行结构
• 4.3.1 优先队列
• 4.3.2 堆结构
• 4.3.3 堆排序
• 4.4 基于四叉堆优先队列的铁路客运中转径路算法
• 4.4.1 k 叉堆操作时间分析及k 值选定
• 4.4.2 基于四叉堆优先队列的Dijkstra 算法
• 5 铁路客运中转径路优化算法实现
• 5.1 系统分析设计
• 5.1.1 系统框架设计
• 5.1.2 类设计
• 5.1.3 数据库设计
• 5.1.4 算法流程设计
• 5.2 径路信息存储
• 5.2.1 数据访问层实现
• 5.3 径路分析模块的测试
• 6 总结与展望
• 6.1 论文主要工作
• 6.2 后续工作展望
• 致谢
• 参考文献
• 附录