基于双向BFS算法的城市轨道交通有效路径研究

摘要

确定城市轨道交通有效路径是客流预测、客流清分等运营管理工作的重要基础,本文在分析乘客对换乘次数及出行成本容忍度的基础上,设计了基于广度优先算法的双向BFS(breadth-first search)算法.考虑拓扑网络中的换乘站、非换乘站、环线与虚拟换乘弧的特性,对轨道交通站点、线路、区间进行编号,并根据乘客换乘次数不超过3次的行为特征,借助相邻换乘站确定两条路径交汇的换乘站,然后通过引入广义相邻换乘站的概念筛选重复路径,标定广义费用函数计算出行成本.最终设计出从O、D点同时开展广度优先算法的双向BFS算法,该算法具有适用性强、速度快等优势.以成都地铁网络中茶店子站和磨子桥站这一对OD为例,在6条初始路径基础上经筛选最终获得2条有效路径,结果完备无冗余.