轨道交通网络有效路径搜索算法的改进及实现
|
摘要
城市轨道交通网络有效路径的判定是网络客流路径分析的基础和关键。本文分析了轨道交通网络节点的处理方式,给出了有效路段和冗余路段的定义和判定规则,在实际应用中发现由于网络节点的特殊处理方式,搜索得到的部分有效路径中存在冗余路段,通过设置换乘节点变量和对路径换乘节点序列的子序列的判断,提出识别冗余路段的方法,并在现有的搜索算法中增加冗余路段的判定步骤,从而改进了算法。在实例计算中,合理确定网络伸展系数的取值,运用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.
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.
引文
[1]DIAL R B.A probabilistic multi-path traffic assignment model which obviates the need for path enumeration[J].Transportation Research,1971,5:83-111.
[2]HOFFMAN W,PAVLEY R.A method for the solution of the N’th best path problem[J].Journal of the Association for Computing Machinery,1959(6):506-514.
[3]CHRISTOPHER C S,BRACE L G.Solving K-shortest and constrained shortest path problems efficiently[J].Annals of Operations Research,1989,20:249-282.
[4]杨信丰,刘兰芬,李引珍,等.基于影响度的有效路径集合的确定[J].交通运输系统工程与信息,2011(6):104-110.
[5]毛保华,四兵锋,刘智丽.城市轨道交通网络管理及收入分配理论与方法[M].北京:科学出版社,2007:137-138.
[6]RAVEAU S,MUNOZ J C,GRANGE L D.A topological route choice model for metro[J].Transportation Research Part A,2011,45:138-147.
[7]DIAL R B.A path-based user-equilibrium traffic assignment algorithm that obviates path storage and enumeration[J].Transportation Research Part B,2006(40):917-936.
[8]林湛,蒋明青,刘剑锋,等.城市轨道交通客流分配的改进Logit模型及方法[J].交通运输系统工程与信息,2012(6):145-151.
[9]钱堃,陈垚,毛保华.考虑换乘时间影响的城市轨道交通路径选择行为研究[J].交通运输系统工程与信息,2015(2):116-121.
[10]四兵锋,毛保华,刘智丽.无缝换乘条件下城市轨道交通网络客流分配模型及算法[J].铁道学报,2007(6):12-18.
[11]周薇.城市轨道交通有效路径选择的改进Dial算法[J].西华大学学报(自然科学版),2013,32(6):38-40.
[12]郭彦云.城市轨道交通有效路径问题研究[D].北京:北京交通大学,2011.
[13]韩雪,刘英舜,郭唐仪.城市轨道交通网络中断下的有效路径搜索模型[J].公路交通科技,2015(10):97-101.
[14]何胜学,范炳全.基于定向层次空间推理的有效路径树搜索算法[J].交通运输系统工程与信息,2006(2):66-71.
[15]张建旭,蒋燕,刘兴国.基于深度优先反向搜索算法确定有效路径集合[J].重庆交通大学学报(自然科学版),2015(3):93-98.
[2]HOFFMAN W,PAVLEY R.A method for the solution of the N’th best path problem[J].Journal of the Association for Computing Machinery,1959(6):506-514.
[3]CHRISTOPHER C S,BRACE L G.Solving K-shortest and constrained shortest path problems efficiently[J].Annals of Operations Research,1989,20:249-282.
[4]杨信丰,刘兰芬,李引珍,等.基于影响度的有效路径集合的确定[J].交通运输系统工程与信息,2011(6):104-110.
[5]毛保华,四兵锋,刘智丽.城市轨道交通网络管理及收入分配理论与方法[M].北京:科学出版社,2007:137-138.
[6]RAVEAU S,MUNOZ J C,GRANGE L D.A topological route choice model for metro[J].Transportation Research Part A,2011,45:138-147.
[7]DIAL R B.A path-based user-equilibrium traffic assignment algorithm that obviates path storage and enumeration[J].Transportation Research Part B,2006(40):917-936.
[8]林湛,蒋明青,刘剑锋,等.城市轨道交通客流分配的改进Logit模型及方法[J].交通运输系统工程与信息,2012(6):145-151.
[9]钱堃,陈垚,毛保华.考虑换乘时间影响的城市轨道交通路径选择行为研究[J].交通运输系统工程与信息,2015(2):116-121.
[10]四兵锋,毛保华,刘智丽.无缝换乘条件下城市轨道交通网络客流分配模型及算法[J].铁道学报,2007(6):12-18.
[11]周薇.城市轨道交通有效路径选择的改进Dial算法[J].西华大学学报(自然科学版),2013,32(6):38-40.
[12]郭彦云.城市轨道交通有效路径问题研究[D].北京:北京交通大学,2011.
[13]韩雪,刘英舜,郭唐仪.城市轨道交通网络中断下的有效路径搜索模型[J].公路交通科技,2015(10):97-101.
[14]何胜学,范炳全.基于定向层次空间推理的有效路径树搜索算法[J].交通运输系统工程与信息,2006(2):66-71.
[15]张建旭,蒋燕,刘兴国.基于深度优先反向搜索算法确定有效路径集合[J].重庆交通大学学报(自然科学版),2015(3):93-98.