启发式算法在铁路换乘的应用

详细信息

Application of Heuristic Algorithm in railway transfer

1.
China Academy of Railway Sciences, Beijing 100081, China;
2.
Institute of Computing Technologies, China Academy of Railway Sciences, Beijing 100081, China

摘要: 随着中国铁路的建设与发展,如何更加充分地利用铁路客运能力、提高列车上座率是铁路亟待解决的问题。本文针对复杂的客运路网下最短路径算法计算效率低下的问题,对比分析了常用的Dijkstra算法及启发式A*算法,择优选取启发式A*算法进行策略改进;并基于优化的客运路网结构及铁路实际业务,对其进行效率优化。实验证明,改进后的算法模型高效准确,具有明显的现实意义。
- 最短路算法 /
- 铁路换乘 /
- Dijkstra算法 /
- 启发式A* /
- 算法
Abstract: With the construction and development of China railway, how to take full advantages of railway passenger transport capacity and improve occupancy rate became urgent problems, so that the research of railway transfer based on railway network was with important theoretical and practical significance. In order to solve the low computational efficiency of common Shortest Path Algorithm, compared Dijkstra Algorithm with Heuristic A * Algorithm, this article selected the Heuristic A* Algorithm to optimize the efficiency based on the optimization of the railway network and rail services. Experiments showed that the improved algorithm model was efficient, accurate, and significance obviously.
- Shortest Path Algorithm /
- railway transfer /
- Dijkstra Algorithm /
- Heuristic A* /
- Algorithm

[1]	韩慧玲,胡红萍. Dijkstra算法在公交换乘最短路径中的应用[J]. 硅谷,2011（21）.
[2]	李秦阳,李宗平. 一类铁路乘客换乘问题的网络优化模型[J]. 兰州交通大学报,2012,31（3）.
[3]	谌应琼. Dijkstra算法在公交网络中的运用与改进[J]. 电子制作,2014（9）.
[4]	王景存,张晓彤. 一种基于Dijkstra算法的启发式最优路径搜索算法[J]. 北京科技大学学报,2007（3）.
[5]	周小镜. 基于改进A*算法的游戏地图寻径的研究[D].成都：西南大学,2011.
[6]	曼哈顿距离[EB/OL]. http://baike.baidu.com/view/741153.htm.
[7]	欧式距离[EB/OL]. http://baike.baidu.com/view/1615257.htm#ref_[1]_1615257.