基于铁路有效路径的换乘方案快速搜索方法

Fastsearch algorithm of transfer scheme based on effective paths in railway networks

研究铁路旅客换乘方案的快速搜索方法可为铁路售票系统提供支持。通过分析铁路旅客出行路径特征,引入非最短系数概念,给出有效路径的判定条件,设计有效路径的搜索算法。基于有效路径集,设计前序弧数法搜索任意计划出发时间的旅客最优换乘方案。整体算法由2个部分组成,一是整个铁路网络有效路径的预先生成和存储;二是给定计划出发时间和起讫站点的最优换乘方案的快速搜索。算法既考虑了铁路旅客的出行路径特征又突出了"快速搜索"的特点。基于2014年中国高速铁路网络及运行图进行算例分析,结果显示算法具有较高的运算效率和很强的实用性。

Research on fast search algorithm of transfer scheme for railway passengers can provide supports to ticket booking system. Through analyzing characters of rail passenger travel paths, this paper designs decision conditions of an effective path by non-shortest coefficient and develops a search algorithm for effective paths. Based on the set of effective paths, a fast search algorithm of transfer scheme with minimum cost at any expected departure time is proposed by a front-arc-number method. The whole algorithm in this paper includes two parts： firstly, producing and storing effective paths of the whole railway network in advance; secondly, searching a transfer scheme with minimum cost on effective paths with the given departure time and O-D pair. This algorithm captures passenger＇s travel characters and lights the fast-search feature. Numerical experiment is conducted based on China high-speed railway network and train schedule in 2014, and results verify the effectiveness and utility of the algorithm.