轨道交通网络有效路径搜索算法的改进及实现

Improvement and Realization of Effective Path Search Algorithm for Rail Transit Network

城市轨道交通网络有效路径的判定是网络客流路径分析的基础和关键。本文分析了轨道交通网络节点的处理方式,给出了有效路段和冗余路段的定义和判定规则,在实际应用中发现由于网络节点的特殊处理方式,搜索得到的部分有效路径中存在冗余路段,通过设置换乘节点变量和对路径换乘节点序列的子序列的判断,提出识别冗余路段的方法,并在现有的搜索算法中增加冗余路段的判定步骤,从而改进了算法。在实例计算中,合理确定网络伸展系数的取值,运用Python脚本语言编程实现改进后的算法。程序运行结果表明改进后的算法能正确筛选出轨道交通网络的有效路径,并输出完整的有效路径信息,验证了算法的有效性。

For the path analysis of network passenger flow,the effective path judgment of urban rail transit network is fundamental and critical.This article analyzes handling method of rail transit network node,and the definition and determination rules of effective and redundant sections are given.It is found in practical application that there are redundant sections in some of the effective paths that are searched.Redundant sections exist because of the special handling method of network nodes.The definition of redundant sections is given based on section features.By setting transfer node variable and judging the subsequence of path transfer node sequence,a method for identifying paths with redundant sections is proposed.Also,an improved algorithm is presented by adding redundant section judging process to existing searching algorithms.In the case study,the value of path extension coefficient is reasonably chosen and the improved algorithm is implemented by Python.The simulation result shows that the improved algorithm can correctly filter the effective paths of transit network and can output the full information of effective paths,thus validity of the algorithm is validated.