都市快轨交通·第32卷第1期2019年2月 doi: 10.3969/j.issn.1672-6073.2019.01.013
《学术探讨
基于轨道交通网络特点的
K最短路算法研究
钟璧橘，楼栋，周一威
（杭州市交通规划设计研究院，杭州310000）
摘要：城市轨道交通网络发展带来出行路径选择的复杂性，为了科学掌握线路客流，组织运输，合理引导乘客路径选择，需要开展轨道多路径算法研究：同时，随着生活节奏加快，要求算法高效，注重路径获取的实时性针对轨道网络特征，将站点之间K最短路搜索转化为线路换乘组合搜索，降低搜索空间复杂度，并利用杭州轨道交通网络进行案例验证。算法明显提升轨道网络K最短路搜索效率，能够更快速响应轨道交通实际运行变化，有助于提升今后轨道交通出行服务应用。
关键词：轨道交通；K最短路：轨道网络：路径搜索
中图分类号：U231.1
文献标志码：A
文章编号：1672-6073(2019)01-0072-06
Shortest-pathAlgorithmBasedontheCharacteristicsof
Rail TransitNetwork
ZHONGBiqiang,LOUDong,ZHOUYiwei
(Hangzhou TransportPlanning andDesign Research Institute,Hangzhou310000, China)
Abstract: The complexity of travel route selection is a challenge brought about by urban rail network development. Accordingly, research on the rail multipath algorithm must be performed to scientifically master the passenger flow of each route, organize transportation, and offer a reasonable guide for passenger route selection. With the acceleration of urban life, efficiency of the algorithm is required, and the real-time performance of path acquisition is emphasized. According to the rail network characteristics, this study translates the K shortest path between stations into a line transfer combination search, reduces the complexity of the search space, and uses the Hangzhou rail network for case verification. Consequently, the algorithm significantly improves the K shortest path efficiency of the rail network, more quickly responds to the actual
rail-operating changes, and is beneficial to the future application of the rail travel service. Keywords: rail transit; K shortest path; rail network; path search
近年来全国轨道交通加速发展，拥有轨道交通的城市日益增多，城市轨道网络也日益发达。轨道交通在出行时间可靠性方面的特点，吸引了大量出行者，轨道交通出行比例不断提升。为了更好地提供轨道交通出行服务，需要全面掌握轨道线路客流特征，并依据线路客流特征科学合理地组织安排线路运营。由于
收稿日期：2018-02-09
修回日期：2018-03-05
第一作者：钟璧，男，硕士，从事公共交通、交通模型、大数
据分析研究，252421705@qq.com URBAN RAPID RAIL TRANSIT
轨道网络封闭运行，不同线路的出行均通过轨道换乘站点进行站内换乘，造成换乘客流不能直接获取，不利于详细掌握轨道交通各条线路实际客流需求，从而进行运营安排，同时随着城市轨道网络的不断发展完善，轨道网络日益复杂，同一出行起点之间存在多条换乘路径，增加了对线路实际客流的获取难度，也增加了乘客选择合理轨道出行路径的难度"]。因此进行轨道网络多路径搜索算法研究对轨道网络客流清分以及乘客出行路径选择引导具有重要意义，而K最短路求解能够满足轨道出行多路径搜索需求；同时随着