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