原文传递
最优路径算法在票务清分系统中的研究与应用
| 论文题名： | 最优路径算法在票务清分系统中的研究与应用 |
| 关键词： | 城市轨道交通;最优路径搜索;换乘路径;票务清分系统;Dijkstra算法;节点连通图 |
| 摘要： | 轨道交通因其造价高、投资大、工期长等因素的影响，整个城市轨道交通路网的建设过程中会涉及到不同的投资方、建设方和运营方。随着路网规模的不断扩大和线路交叉，形成了跨越不同运营线路的乘车情况，为了客观、公平、公正地把交易款划分给被乘运线路，产生了轨道交通清分系统。建立清分系统需要解决异线站点之间的换乘路径问题，即无向图中求解给定顶点对之间K条最优路径问题。 在研究了求解K优路径问题的基本理论和2nd最优路径搜索算法的基础上，借助于“背离”路径的概念，提出了一种新的Kth最优路径搜索算法。通过K-1次2nd最短路径搜索算法的迭代，求解出网络中任意两个给定节点之间的Kth最优路径，由于2nd最短路径搜索算法在计算上的简单性，本算法同样具有简洁、快速的特点。 使用斐波那契堆优化Dijkstra算法中的最小优先队列，使Dijkstra算法的性能达到最优。针对算法在搜索过程中产生的环路，在分析了删除边去环算法的基础上，提出用2nd算法的思想去环，在产生环路节点的背离路径中搜索次优路径作为新的背离路径，解决了算法的瓶颈问题，使整体路径求解算法的效率有了显著的提高。 在此基础上，对算法所涉及到的数据结构进行了调整，用邻接多重表来存储路网结构图，用其MARK域标记节点所在的路径以判断是否存在环路。用固定长度的队列存储最终形成的路径，使不符合要求的路径尽早的排除，进一步提高算法的效率。该算法的时间复杂度为O(VlgV+E+K*m*t)。 最后，结合上海轨道交通路网模型对算法进行了验证，证实了算法能够有效解决某些实际问题中大量节点连通图中K条渐次最优路径的问题。 |
| 作者： | 杨学斌 |
| 专业： | 计算机应用技术 |
| 导师： | 史有群 |
| 授予学位： | 硕士 |
| 授予学位单位： | 东华大学 |
| 学位年度： | 2009 |
| 正文语种： | 中文 |
检索历史
应用推荐
