城市轨道交通有效路径问题研究
|
摘要
随着城市轨道交通建设步伐的加快,线网规模的扩大和结构的完善,轨道交通线网耦合度越来越高,不同站换乘将更加频繁,采用“无缝换乘”的运营模式将成为今后轨道交通网络化发展的必然结果。同时由于人们对出行路径的理解费用差异和路径选择的多样性,导致乘客出行路径更难掌握。因此,深入分析乘客路径选择的影响因素,确定乘客出行路径集合将变得尤为重要。只有科学合理的掌握乘客出行路径选择行为,才能准确把握乘客出行规律,确定乘客出行路径,对今后城市轨道交通客流预测、运营组织管理及不同运营商之间的客票清算提供依据和支撑。
本文以城市轨道交通乘客出行行为特性为基础,充分考虑了影响乘客路径选择的主要影响因素,拓展了广义费用函数。通过增加换乘次数限制条件重新定义了有效路径,并设计了有效路径求解算法。论文的主要研究内容和结论如下：
(1)针对城市轨道交通路网的特殊性,对换乘节点进行特殊处理,构建了轨道交通路网拓扑结构。在该网络拓扑结构基础上,对轨道交通网络基本元素之间的关系进行数学建模,包括车站关系、区段关系、线路关系等,为有效路径的求解及各元素在计算机中的存储提供数学基础。
(2)在充分考虑乘客换乘舒适度的基础上,改进乘客出行路径选择的广义费用函数。通过分析影响乘客路径选择的乘车时间、换乘时间等主要因素,为确定乘客出行有效路径范围提供前提。由于出行者对换乘费用比较敏感,通过增加换乘次数限制条件,对有效路径进行重新定义。该定义减少了不符合实际的出行路径。
(3)基于有效路径定义,提出了基于BFS的路径搜索算法。由于BFS算法是一种路径枚举算法,效率较低,提出通过关键结点确定有效路径的BFS改进算法,并进行算例验证。算例研究表明,BFS路径搜索算法相对既有算法具有运行效率高、存储空间节省等特点,对于带环网络不会遗漏满足条件的有效路径。
(4)针对不同类别乘客对出行费用理解差异,设定不同参数,对比分析了有效路径选择结果。结果表明增加换乘次数限制条件使得有效路径范围更加符合实际情况。通过求解OD点对有效路径,对基于换乘舒适度的广义费用模型进行验证,并对模型中的参数进行灵敏度分析。采用换乘流量结果与调查数据对比分析,表明换乘舒适度是影响路径选择的一个重要因素,且在某些换乘车站,考虑换乘舒适度的换乘流量结果更加贴近实际数据。
With the accelerating pace in urban rail transit construction, the expanding scale as well as improving structure in line network, the coupling coefficient of rail transit network is getting higher and different transfer between stations is more frequent. Therefore, it is the inevitable result of network development that we adopt the operation mode of seamless transfer. At the same time, due to the diversity of the route choice resulting from the cost of travel people think, it leads that it is difficult to grasp the transit path of passengers. So, it's particularly important to determine the travel path set by deeply analyzing the influencing factors effect to the path choice of passengers. So only by getting hold of the passengers'behaviors of route choice, we can accurately grasp the rules and paths, which can provide the basis and support for passenger flow forecast in urban rail transit and operation organization management as well as ticket clearing problem between operation business.
In this paper, based on the passenger' behaviors in rail transit, we fully consider the influencing factors effect to the path choice about passengers and expand the general cost function. We redefine the efficient path which transfer time has been considered as a limiting condition and design the algorithm. The contents and conclusion of this paper are summarized as follows:
(1) This paper establishes the network topology structure of rail transit based on particularity of rail transit network, which process the transfer nodes according to the particularity of rail transit network. On the account of the network topology above, the relations between the basic elements in rail transit network is presented, including stations, sections, lines and association relations between them, which provide mathematical basis for solving the efficient path and storing every element in computer.
(2) Considering the transfer comfort of transit, it improves the general cost function. Analyzing the principal influencial factors of path choice provides premise for confirming the scope of efficient paths. Because the cost function of transfer is sensitive for passengers, transfer time has been considered as a limiting condition and the efficient path is redefined, which reduces the travel routes inconsistent with actual.
(3) In view of the redefined efficient paths, we design path algorithm by using BFS. Since BFS is a path enumeration algorithm with inefficiency, the BFS algorithm that using key nodes determine the efficient path on the basis of features of rail transit network is presented. Furthermore, simple analysis of the path searching process proves the feasibility of algorithm and verifies that the modified algorithm does not only improve operating efficiency, but also save storage space.
(4) Beacuse of different understanding about cost of different passengers attributes, the paper analyzes the paths based on various parameters, the conclusion demonstrate that transfer times restriction make the efficient paths more consistent with real data. Moreover, by solving the efficient path of OD pair, the generalal cost function considering transfer comfort is verified and the sensitivity analysis of the parameters is carried out. Simultaneously, we compares transfer flow of calculated results with the real date, which shows that transfer comfort will become a major factor that influences the route choice.
本文以城市轨道交通乘客出行行为特性为基础,充分考虑了影响乘客路径选择的主要影响因素,拓展了广义费用函数。通过增加换乘次数限制条件重新定义了有效路径,并设计了有效路径求解算法。论文的主要研究内容和结论如下：
(1)针对城市轨道交通路网的特殊性,对换乘节点进行特殊处理,构建了轨道交通路网拓扑结构。在该网络拓扑结构基础上,对轨道交通网络基本元素之间的关系进行数学建模,包括车站关系、区段关系、线路关系等,为有效路径的求解及各元素在计算机中的存储提供数学基础。
(2)在充分考虑乘客换乘舒适度的基础上,改进乘客出行路径选择的广义费用函数。通过分析影响乘客路径选择的乘车时间、换乘时间等主要因素,为确定乘客出行有效路径范围提供前提。由于出行者对换乘费用比较敏感,通过增加换乘次数限制条件,对有效路径进行重新定义。该定义减少了不符合实际的出行路径。
(3)基于有效路径定义,提出了基于BFS的路径搜索算法。由于BFS算法是一种路径枚举算法,效率较低,提出通过关键结点确定有效路径的BFS改进算法,并进行算例验证。算例研究表明,BFS路径搜索算法相对既有算法具有运行效率高、存储空间节省等特点,对于带环网络不会遗漏满足条件的有效路径。
(4)针对不同类别乘客对出行费用理解差异,设定不同参数,对比分析了有效路径选择结果。结果表明增加换乘次数限制条件使得有效路径范围更加符合实际情况。通过求解OD点对有效路径,对基于换乘舒适度的广义费用模型进行验证,并对模型中的参数进行灵敏度分析。采用换乘流量结果与调查数据对比分析,表明换乘舒适度是影响路径选择的一个重要因素,且在某些换乘车站,考虑换乘舒适度的换乘流量结果更加贴近实际数据。
With the accelerating pace in urban rail transit construction, the expanding scale as well as improving structure in line network, the coupling coefficient of rail transit network is getting higher and different transfer between stations is more frequent. Therefore, it is the inevitable result of network development that we adopt the operation mode of seamless transfer. At the same time, due to the diversity of the route choice resulting from the cost of travel people think, it leads that it is difficult to grasp the transit path of passengers. So, it's particularly important to determine the travel path set by deeply analyzing the influencing factors effect to the path choice of passengers. So only by getting hold of the passengers'behaviors of route choice, we can accurately grasp the rules and paths, which can provide the basis and support for passenger flow forecast in urban rail transit and operation organization management as well as ticket clearing problem between operation business.
In this paper, based on the passenger' behaviors in rail transit, we fully consider the influencing factors effect to the path choice about passengers and expand the general cost function. We redefine the efficient path which transfer time has been considered as a limiting condition and design the algorithm. The contents and conclusion of this paper are summarized as follows:
(1) This paper establishes the network topology structure of rail transit based on particularity of rail transit network, which process the transfer nodes according to the particularity of rail transit network. On the account of the network topology above, the relations between the basic elements in rail transit network is presented, including stations, sections, lines and association relations between them, which provide mathematical basis for solving the efficient path and storing every element in computer.
(2) Considering the transfer comfort of transit, it improves the general cost function. Analyzing the principal influencial factors of path choice provides premise for confirming the scope of efficient paths. Because the cost function of transfer is sensitive for passengers, transfer time has been considered as a limiting condition and the efficient path is redefined, which reduces the travel routes inconsistent with actual.
(3) In view of the redefined efficient paths, we design path algorithm by using BFS. Since BFS is a path enumeration algorithm with inefficiency, the BFS algorithm that using key nodes determine the efficient path on the basis of features of rail transit network is presented. Furthermore, simple analysis of the path searching process proves the feasibility of algorithm and verifies that the modified algorithm does not only improve operating efficiency, but also save storage space.
(4) Beacuse of different understanding about cost of different passengers attributes, the paper analyzes the paths based on various parameters, the conclusion demonstrate that transfer times restriction make the efficient paths more consistent with real data. Moreover, by solving the efficient path of OD pair, the generalal cost function considering transfer comfort is verified and the sensitivity analysis of the parameters is carried out. Simultaneously, we compares transfer flow of calculated results with the real date, which shows that transfer comfort will become a major factor that influences the route choice.
引文
[1]毛保华.城市轨道交通系统运营管理[M].北京：人民交通出版社,2006.
[2]王灏.城市轨道交通投融资问题研究[M].北京：中国金融出版社,2006.
[3]Dial R. B. A probabilisitc multi-path traffic assigment model which obviates the need for path enumeration [J]. Transportation Research,1971,5:83-111.
[4]孟川舒.城市轨道交通一票通清分问题的研究[D].北京：铁道科学研究院.2007.
[5]何胜学,范炳全.随机交通分配中有效路径的定向树搜索算法[J].上海理工大学学报,2005,23(5)：38-41.
[6]李志纯,黄海军.随机交通分配中有效路径的确定方法[J].交通运输系统工程与信息,2003,3(1)：28-31.
[7]Angelica Lozan, Giovanni Storchi. Shortest viable hyperpath in multimodel networks [J]. Transportation Research Part B,2002,36(10):853-874.
[8]四兵锋,毛保华,刘智丽.无缝换乘条件下城市轨道交通网络客流分配模型及算法[J].铁道学报,2007,29(6)：12-17.
[9]Leurent F. Curbing the computational difficulty of Logit equilibrium assignment model [J]. Transportation Research-B,1997,31(4):315-326.
[10]秦鸣,姜培.基于有效路径的多路径交通流分配[J].交通标准化,2010,(218)：30-32.
[11]牛学勤,王炜.基于最短路搜索的多路径公交客流分配模型研究[J].东南大学学报：自然科学版,2002,32(6)：1-3.
[12]四兵锋,张好智,高逢友.求解Logit随机网络配流问题的改进Dial算法[J].中国公路学报,2009,22(1)：78-83.
[13]Bell M. G. H. Alternatives to Dial's Logit assignment algorithm [J]. Transportation Research Part B,1995,29(2):125-137.
[14]Akamatsu T. Cyclic flows, markov process and transportation stochastic assignment [J]. Transportation Research Part B,1996,30(5):369-386.
[15]Huang H. J., Lam W.H.K. Modeling and solving the dynamic user equilibrium route and departure time choice problem in network with queues [A]. Transportation Research-B [C],2002,36: 253-273.
[16]四兵锋,张好智,高自友.求解Logit随机网络配流问题的改进Dial算法[J].中国公路学报,2009,22(1)：78-82.
[17]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.
[18]Lars Relund Nielsen. Finding the K shortest hyperpaths [J]. Computers & Operations Research, 2005, (32):1477-1497.
[19]N.J. van der Zijpp. Path enumeration by finding the constrained K-shortest paths [J]. Transportation Research Part B,2005, (39):544-563.
[20]王明中.城市轨道交通一票(卡)通换乘票务清分系统的研究与实现[D].上海：上海交通大学,2004.
[21]何胜学,范炳全.随机交通分配中有效路径的分层定向算法[J].上海理工大学学报,2006, 28(2)：141-144.
[22]何胜全,严凌.交通网络中的定向寻优法[J].上海理工大学学报,2004,26(4)：356-359.
[23]王杰臣,毛海城,杨得志.图的节点-弧段联合结构表示法及其在GIS最优路径选取中的应用[J].测绘学报,2000,29(1)：47-51.
[24]叶晋,史有群,杨学斌等.遗传算法在轨道交通换乘路径求解问题上的应用[J].电脑与信息技术,2009,17(4)：24-27.
[25]赵烈秋,孔繁钰.基于GA的城市轨道交通客流分配问题[J].后勤工程学院学报,2008,24(2)：106-120.
[26]毛保华,四兵锋,刘智丽.城市轨道交通网络管理及收入分配理论与方法[M].北京：科学出版社,2007.
[27]刘剑锋等.城市轨道交通乘客路径选择模型及算法[J].交通运输系统工程与信息,2009,9(2)：81-86.
[28]Nguyen S., Pallotino S. Equilibrium traffic assignment in large scale transit networks [J]. European Journal of Operational Research,1988,37 (2):176-186.
[29]Leclercq. F. Apublic transport assignment method [J]. Traffic Engineering and Control,14: 91-96.
[30]姜虹,高自友.用遗传算法求解拥挤条件下的公共交通随机用户平衡配流模型[J].公路交通科技,2000,17(2)：37-41.
[31]周刚,王炜.地铁线路客流分配方法与算法研究[J].广东公路交通,2001(4)：32-35.
[32]吴祥云,刘灿齐.轨道交通客流量均衡分配模型与算法[J].同济大学学报(自然科学版),2004,32(9)：1158-1162.
[33]孔繁钰,李献忠.弹性需求下的轨道交通客流分配模型和算法[J].西安：西安工程大学学报,2008,22(1)：104-108.
[34]E. W. Dijkstra. A note on problem in connextion with graphs [J]. Numeric Mathematics,1959, (1):269-271.
[35]张莹.运筹学基础[M].北京：清华大学出版社,1995.
[36]赖树坤,姚宪辉,彭愚.交通网络中有效路径确定方法的探讨[J].交通标准化,2008,(1)：137-139.
[37]Dial R.B. Transit pathfinder algorithms [J]. Highway Research Record,1967,205:67-85.
[38]程琳,王炜Dial交通量分配模型和选择概率问题的研究[J].交通运输系统工程与信息,2002,2(2)：29-32.
[39]黄一华.城市轨道交通客流分配模型与算法的研究[D].北京：北京交通大学,2010.
[40]翁惠玉,俞勇.数据结构：思想与实现[M].北京：高等教育出版社,2009.
[41]冯志全等.数据结构与算法设计[M].北京：中国电力出版社,2008.
[42]邵春福.交通规划原理[M].北京：中国铁道出版社,2004.
[43]郑丽娟.基于城市轨道交通网络运营的客流分布预测研究[D].上海：同济大学,2008.
[44]李金海.城市轨道交通网络客流分配模型及算法研究[D].北京：北京交通大学,2010.
[45]高国飞.基于MNL的轨道交通乘客路径选择问题研究[D].北京：北京交通大学,2009.
[46]徐瑞华,罗钦,高鹏.基于多路径的城市轨道交通网络客流分布模型及算法研究[J].铁道学报,2009,31(2)：110-113.
[47]四兵锋,孙壮志,赵小梅.基于随机用户平衡的混合交通网络流量分离模型[J].中国公路学报,2006,19(11)：93-98.
[48]陈团生.客运专线旅客出行选择行为分析铁道学报[J].2007,29(3)：8-12.
[49]贾楠.城市轨道交通票务清分问题研究[D].北京：北京交通大学,2008.
[50]苏娟.城市轨道交通客流分配研究[D].北京：北京交通大学,2009.
[51]北京交通发展研究中心.(2010年北京交通发展年报》[R].北京：北京交通发展研究中心,2010.
[52]关宏志.非集计模型：交通行为分析的工具[M].北京：人民交通出版社,2004.
[53]Huang H. J. A combined algorithm for solving and calibrating the stochastic user equilibrium assignment model [J]. The Operational Research Society,1995,46:977-987.
[54]陆化普,黄海军.交通规划理论研究前沿[M].北京：清华大学出版社,2007.
[55]熊伟.运筹学[M].北京：机械工业出版社,2009.
[2]王灏.城市轨道交通投融资问题研究[M].北京：中国金融出版社,2006.
[3]Dial R. B. A probabilisitc multi-path traffic assigment model which obviates the need for path enumeration [J]. Transportation Research,1971,5:83-111.
[4]孟川舒.城市轨道交通一票通清分问题的研究[D].北京：铁道科学研究院.2007.
[5]何胜学,范炳全.随机交通分配中有效路径的定向树搜索算法[J].上海理工大学学报,2005,23(5)：38-41.
[6]李志纯,黄海军.随机交通分配中有效路径的确定方法[J].交通运输系统工程与信息,2003,3(1)：28-31.
[7]Angelica Lozan, Giovanni Storchi. Shortest viable hyperpath in multimodel networks [J]. Transportation Research Part B,2002,36(10):853-874.
[8]四兵锋,毛保华,刘智丽.无缝换乘条件下城市轨道交通网络客流分配模型及算法[J].铁道学报,2007,29(6)：12-17.
[9]Leurent F. Curbing the computational difficulty of Logit equilibrium assignment model [J]. Transportation Research-B,1997,31(4):315-326.
[10]秦鸣,姜培.基于有效路径的多路径交通流分配[J].交通标准化,2010,(218)：30-32.
[11]牛学勤,王炜.基于最短路搜索的多路径公交客流分配模型研究[J].东南大学学报：自然科学版,2002,32(6)：1-3.
[12]四兵锋,张好智,高逢友.求解Logit随机网络配流问题的改进Dial算法[J].中国公路学报,2009,22(1)：78-83.
[13]Bell M. G. H. Alternatives to Dial's Logit assignment algorithm [J]. Transportation Research Part B,1995,29(2):125-137.
[14]Akamatsu T. Cyclic flows, markov process and transportation stochastic assignment [J]. Transportation Research Part B,1996,30(5):369-386.
[15]Huang H. J., Lam W.H.K. Modeling and solving the dynamic user equilibrium route and departure time choice problem in network with queues [A]. Transportation Research-B [C],2002,36: 253-273.
[16]四兵锋,张好智,高自友.求解Logit随机网络配流问题的改进Dial算法[J].中国公路学报,2009,22(1)：78-82.
[17]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.
[18]Lars Relund Nielsen. Finding the K shortest hyperpaths [J]. Computers & Operations Research, 2005, (32):1477-1497.
[19]N.J. van der Zijpp. Path enumeration by finding the constrained K-shortest paths [J]. Transportation Research Part B,2005, (39):544-563.
[20]王明中.城市轨道交通一票(卡)通换乘票务清分系统的研究与实现[D].上海：上海交通大学,2004.
[21]何胜学,范炳全.随机交通分配中有效路径的分层定向算法[J].上海理工大学学报,2006, 28(2)：141-144.
[22]何胜全,严凌.交通网络中的定向寻优法[J].上海理工大学学报,2004,26(4)：356-359.
[23]王杰臣,毛海城,杨得志.图的节点-弧段联合结构表示法及其在GIS最优路径选取中的应用[J].测绘学报,2000,29(1)：47-51.
[24]叶晋,史有群,杨学斌等.遗传算法在轨道交通换乘路径求解问题上的应用[J].电脑与信息技术,2009,17(4)：24-27.
[25]赵烈秋,孔繁钰.基于GA的城市轨道交通客流分配问题[J].后勤工程学院学报,2008,24(2)：106-120.
[26]毛保华,四兵锋,刘智丽.城市轨道交通网络管理及收入分配理论与方法[M].北京：科学出版社,2007.
[27]刘剑锋等.城市轨道交通乘客路径选择模型及算法[J].交通运输系统工程与信息,2009,9(2)：81-86.
[28]Nguyen S., Pallotino S. Equilibrium traffic assignment in large scale transit networks [J]. European Journal of Operational Research,1988,37 (2):176-186.
[29]Leclercq. F. Apublic transport assignment method [J]. Traffic Engineering and Control,14: 91-96.
[30]姜虹,高自友.用遗传算法求解拥挤条件下的公共交通随机用户平衡配流模型[J].公路交通科技,2000,17(2)：37-41.
[31]周刚,王炜.地铁线路客流分配方法与算法研究[J].广东公路交通,2001(4)：32-35.
[32]吴祥云,刘灿齐.轨道交通客流量均衡分配模型与算法[J].同济大学学报(自然科学版),2004,32(9)：1158-1162.
[33]孔繁钰,李献忠.弹性需求下的轨道交通客流分配模型和算法[J].西安：西安工程大学学报,2008,22(1)：104-108.
[34]E. W. Dijkstra. A note on problem in connextion with graphs [J]. Numeric Mathematics,1959, (1):269-271.
[35]张莹.运筹学基础[M].北京：清华大学出版社,1995.
[36]赖树坤,姚宪辉,彭愚.交通网络中有效路径确定方法的探讨[J].交通标准化,2008,(1)：137-139.
[37]Dial R.B. Transit pathfinder algorithms [J]. Highway Research Record,1967,205:67-85.
[38]程琳,王炜Dial交通量分配模型和选择概率问题的研究[J].交通运输系统工程与信息,2002,2(2)：29-32.
[39]黄一华.城市轨道交通客流分配模型与算法的研究[D].北京：北京交通大学,2010.
[40]翁惠玉,俞勇.数据结构：思想与实现[M].北京：高等教育出版社,2009.
[41]冯志全等.数据结构与算法设计[M].北京：中国电力出版社,2008.
[42]邵春福.交通规划原理[M].北京：中国铁道出版社,2004.
[43]郑丽娟.基于城市轨道交通网络运营的客流分布预测研究[D].上海：同济大学,2008.
[44]李金海.城市轨道交通网络客流分配模型及算法研究[D].北京：北京交通大学,2010.
[45]高国飞.基于MNL的轨道交通乘客路径选择问题研究[D].北京：北京交通大学,2009.
[46]徐瑞华,罗钦,高鹏.基于多路径的城市轨道交通网络客流分布模型及算法研究[J].铁道学报,2009,31(2)：110-113.
[47]四兵锋,孙壮志,赵小梅.基于随机用户平衡的混合交通网络流量分离模型[J].中国公路学报,2006,19(11)：93-98.
[48]陈团生.客运专线旅客出行选择行为分析铁道学报[J].2007,29(3)：8-12.
[49]贾楠.城市轨道交通票务清分问题研究[D].北京：北京交通大学,2008.
[50]苏娟.城市轨道交通客流分配研究[D].北京：北京交通大学,2009.
[51]北京交通发展研究中心.(2010年北京交通发展年报》[R].北京：北京交通发展研究中心,2010.
[52]关宏志.非集计模型：交通行为分析的工具[M].北京：人民交通出版社,2004.
[53]Huang H. J. A combined algorithm for solving and calibrating the stochastic user equilibrium assignment model [J]. The Operational Research Society,1995,46:977-987.
[54]陆化普,黄海军.交通规划理论研究前沿[M].北京：清华大学出版社,2007.
[55]熊伟.运筹学[M].北京：机械工业出版社,2009.