城市轨道交通末班车条件下可达路径问题研究
|
摘要
城市轨道交通网络化的进程不断加快,给人们出行带来极大的方便。与此同时,城市轨道交通网络化的发展也为人们的出行带来了新的问题,例如由于各线路列车末班车时间不连续,乘客进站乘车后不能经过换乘到达目的地等。
随着轨道交通路网规模的不断扩大,乘客出行路径的选择越来越多,如何为乘客提供实时的出行可达路径是本文研究的出发点。本文针对末班车条件下的可达路径问题研究,旨在为末班车条件下的乘客出行路径诱导提供一种实用的方法。
首先,本文定义了末班车条件下可达性的概念,指出末班车条件下的可达性由三部分组成,即空间可达性、时间可达性以及可达便捷性,并对影响末班车条件下空间、时间可达性以及可达便捷性的因素进行了分析。
然后建立了城市轨道交通网络简化模型,结合本文对有效路径的定义,提出了一种改进的深度优先搜索算法,用以搜索路网中所有OD对间的有效路径集。本文针对路径中换乘站和交路端点站对路径可达性的影响,给出了路径可达性的判断规则,提出了OD间最晚可达乘车时间的推算方法和指定时间的实时可达路径集生成算法。在分析了路径可达便捷性的基础上,定义了可达路径的广义费用函数,用以对生成的OD间各条可达路径进行评价。
最后,设计实现了北京地铁末班车可达路径查询仿真系统,并以实例验证了算法的正确性。
The process of urban mass transport network continues to accelerate, to bring great convenience to the people when traveling. At the same time, the development of urban mass transport network brings new problems for people to travel, such as passengers who travel by subway cannot get to the destination by transfer due to the time of the last train of each line is not continuous.
With the constant expansion of urban mass transit network, the choice of passenger travel path becomes more and more, how to provide passengers with real-time reachable-path is the starting point for research in this article. In this paper, reachable-path under the conditions of the last trains designed for passenger travel path under the conditions of the last trains induced to provide a practical way.
First, the article defines the concept of reachability with the constrain of last trains, points that the reachability with the constrain of last trains consists of three parts, namely space reachability, time reachability and reachable convenience. And deeply analyzes the factors that affecting space and time reachability and reachable convenience under the last trains condition.
Then established a simplified model of urban mass transport network in accordance with the definition of efficient path, an improved depth-first search algorithm was proposed for searching the efficient paths set during network among all OD pairs. Considering the transfer station and the routing endpoints station play a secisive role in judging the reachability of a path, some judgment rules was proposed. Then a method to calculation the latest boarding time that can be reachable between the OD pairs was raised, and so was the algorithm for generating real-time reachable paths. Considering some factors of reachable convenience, a generalized cost function was defined to evaluate every reachable path between O and D.
Finally, the path searching simulation system with constrain of last trains in of Beijing subway was designed and implemented. And the model and algorithms in this paper was verified by living example.
随着轨道交通路网规模的不断扩大,乘客出行路径的选择越来越多,如何为乘客提供实时的出行可达路径是本文研究的出发点。本文针对末班车条件下的可达路径问题研究,旨在为末班车条件下的乘客出行路径诱导提供一种实用的方法。
首先,本文定义了末班车条件下可达性的概念,指出末班车条件下的可达性由三部分组成,即空间可达性、时间可达性以及可达便捷性,并对影响末班车条件下空间、时间可达性以及可达便捷性的因素进行了分析。
然后建立了城市轨道交通网络简化模型,结合本文对有效路径的定义,提出了一种改进的深度优先搜索算法,用以搜索路网中所有OD对间的有效路径集。本文针对路径中换乘站和交路端点站对路径可达性的影响,给出了路径可达性的判断规则,提出了OD间最晚可达乘车时间的推算方法和指定时间的实时可达路径集生成算法。在分析了路径可达便捷性的基础上,定义了可达路径的广义费用函数,用以对生成的OD间各条可达路径进行评价。
最后,设计实现了北京地铁末班车可达路径查询仿真系统,并以实例验证了算法的正确性。
The process of urban mass transport network continues to accelerate, to bring great convenience to the people when traveling. At the same time, the development of urban mass transport network brings new problems for people to travel, such as passengers who travel by subway cannot get to the destination by transfer due to the time of the last train of each line is not continuous.
With the constant expansion of urban mass transit network, the choice of passenger travel path becomes more and more, how to provide passengers with real-time reachable-path is the starting point for research in this article. In this paper, reachable-path under the conditions of the last trains designed for passenger travel path under the conditions of the last trains induced to provide a practical way.
First, the article defines the concept of reachability with the constrain of last trains, points that the reachability with the constrain of last trains consists of three parts, namely space reachability, time reachability and reachable convenience. And deeply analyzes the factors that affecting space and time reachability and reachable convenience under the last trains condition.
Then established a simplified model of urban mass transport network in accordance with the definition of efficient path, an improved depth-first search algorithm was proposed for searching the efficient paths set during network among all OD pairs. Considering the transfer station and the routing endpoints station play a secisive role in judging the reachability of a path, some judgment rules was proposed. Then a method to calculation the latest boarding time that can be reachable between the OD pairs was raised, and so was the algorithm for generating real-time reachable paths. Considering some factors of reachable convenience, a generalized cost function was defined to evaluate every reachable path between O and D.
Finally, the path searching simulation system with constrain of last trains in of Beijing subway was designed and implemented. And the model and algorithms in this paper was verified by living example.
引文
[1]李玉芳,高越.轨道交通网络化列车首末班车衔接协调方案研究[J].城市建设：下旬,2001(1)：277.
[2]徐瑞华,张铭,江志彬.基于现网运营协调的城市轨道交通首末班列车发车时间域研究[J].铁道学报.2008(2)：9-13.
[3]罗钦,徐瑞华,江志彬,陈菁菁.基于运行图的轨道交通网络动态可达性研究[J].同济大学学报(自然科学版),2010,38(1)：72-75.
[4]彭益兵,苏厚勤,何晋川.轨交末班车可达多路径换乘算法的研究与实现[J].计算机应用研究,2010,27(4)：1373-1375.
[5]郭彦云.城市轨道交通有效路径问题研究[D],北京：北京交通大学硕十学位论文.2011年6月.
[6]王丽娜.面向城市交通的简化路网模型及路径规划问题的研究[D],重庆：重庆大学硕士学位论文.2011年4月.
[7]高国飞.基于MNL的轨道交通乘客路径选择问题研究[D],北京：北京交通大学硕十学位论文.2009年6月.
[8]杨群,关伟等,基于合理多路径的路径选择方法的研究[J].管理工程学报,2002,16(4)：42-45.
[9]赖树坤,姚宪辉,彭愚.交通网络中有效路径确定方法的探讨[J].交通标准化,2008(1)：137-140.
[10]张嵩,王军,马金平.求解K最短路径的改进Dijkstra算法[J].中国经济与管理科学,2009(4)：29-31.
[11]四兵锋,毛保华,刘智丽.无缝换乘条件下城市轨道交通网络客流分配模型及算法[J].铁道学报,2007,29(6)：12-18.
[12]何胜学,范炳全.随机交通分配中有效路径的定向树搜索算法[J].交通与计算机,2005,23(5)：38-41.
[13]Tong CO,Richardson AJ. Estimation of time-dependent origin-destination matrices for transit networks. Journal of Advanced Transportation 1984;18:145-61.
[14]Tong CO,Wong SC,Poon MH,Tran MC.A schedule based dynamic transit network model— recent advances and prospective future research. Journal of Advanced Transportation 2001;35(2):175-95.
[15]Huang R. Peng Z. Schedule-based path finding algorithms for transit trip planning systems. Journal of Transportation Research Board: Transportation Research Record 2002;1783:142-8.
[16]Jin Y.Yen. Finding the K Shortest Loopless Paths in a Network: Management Science, 1971,17(11):712-716.
[17]张玺.基于出行方式的城市交通可达性研究[D].成都：西南交通大学硕士学位论文,2008年5月.
[18]罗钦.基于网络运营的城市轨道交通客流分布理论及仿真研究[D].上海：同济大学博士学位论文,2009年8月.
[19]苏星燕.城市轨道交通换乘站运营协调效率的评价研究[D].湖南:中南大学硕士学位论文,2010年5月.
[20]徐瑞华等.市域快速轨道交通线路列车运行交路研究[J].城市轨道交通研 究,2006,9(5)：36-39.
[21]杨杰,基于路网的城市轨道交通运输组织行车策略研究[D].北京：北京交通大学硕士学位论文,2006年12月.
[22]苏永涛,仉俊峰.基于图论方法的路径规划应用[J].电测与仪表,2012,49(1)：94-96.
[23]Tong,Yue Li, Bin Hong. An accurate continuous calibration system for high voltage current transfornler[J].Review of Scientific Intrusments,2011,82(2):025107-025107-9.
[24]Yue Tong,Hongbin Li,Lei Cheng,ct al.A Highly Accurate ECT calibration system Based on Virtual Instrument Technology[C]. Conference proceedings of the Seventh International Conference on Electronic Measurement&Instruments,2008:246-248.
[25]梁建斌.基于GIS管网仿真模拟系统的开发及应用[D].太原：太原理工大学硕士学位论文,2006年5月.
[26]董加强,基于邻接表的图生产算法探讨[J].西昌学院学报：自然科学版,2009,23(2)：43-45.
[27]周旭升,曾栩鸿,吝维军.基于广义邻接表的实时公交查询[J].科技信息,2010(17)：10188-10188,10157.
[28]李苏祺,张广军.基于邻接表的分水岭变换快速区域合并算法[J].北京航空航天大学学报,2008,34(11)：1327-1330,1348.
[29]叶晋.遗传算法在轨道交通换乘路径求解中的应用[D].上海：东华大学硕士学位论文,2009年3月.
[30]陈燕,刘春等.城市交通路网模型的更新方案与实现[J].交通信息与安全,2010(4)：39-42,48.
[31]杨英伟,饶鸣等.基于交通规则的路网模型建立及最优路径分析研究[J].城市勘测,2010(4)：58-61.
[32]Miller H J,Shaw S L.GIS-T data models, geograph-ic information systems for transportation:principles and applications[M]. Oxford:Oxford University Press,2001.
[33]American Transportation Research Board. Highway Capacity Manual[M]. Washington, D. C: National Research Council, 2000.
[34]Yang Yahong,Gao Jingchang. Application of design patterns for GIS platform software[J]. Journal of Jilin University: Information Science Edition,2003,21(2):153-155.
[35]粱虹,袁小群,刘蕊.一种新的公交数据模型与公交查询系统实现[J].计算机工程与应用,2007,43(3)：234-238.
[36]刘海涛.一种在赋权图中实现Dijkstra算法的矩阵方法[J].数学教学研究,2011,30(12)：47-49.
[37]Sung K, Bell M,Seong M, et al. Shortest paths in a network with time-dependent flow speeds[J]. European Journal of Operational Research,2000,121(1):32-39.
[38]Xu M H,Liu Y Q, et al.An improved Dijkstra's shortest path algorithm for sparse network[J].Applied Mathematics and Computation,2007,185(1):247-254.
[39]Fredman M L,Tarjan R E.Fibonacci heaps and their uses in improved network optimization algorithm[J].Journal of the ACM,1987,34(3):596-615.
[40]Han Y.Improved algorithm for all pairs shortest paths[J]. Inform Process Lett,2004,91:245-250.
[41]孙强,沈建华,顾君忠Dijkstra的一种改进算法[J].计算机工程与应用,2002(3)：99-101.
[42]Russell S,Norvig P. Artificial Intelligence:A Modem Approach[M].2nd ed. Prentice-Hall: Englewood Cliffs,NJ,2003.
[2]徐瑞华,张铭,江志彬.基于现网运营协调的城市轨道交通首末班列车发车时间域研究[J].铁道学报.2008(2)：9-13.
[3]罗钦,徐瑞华,江志彬,陈菁菁.基于运行图的轨道交通网络动态可达性研究[J].同济大学学报(自然科学版),2010,38(1)：72-75.
[4]彭益兵,苏厚勤,何晋川.轨交末班车可达多路径换乘算法的研究与实现[J].计算机应用研究,2010,27(4)：1373-1375.
[5]郭彦云.城市轨道交通有效路径问题研究[D],北京：北京交通大学硕十学位论文.2011年6月.
[6]王丽娜.面向城市交通的简化路网模型及路径规划问题的研究[D],重庆：重庆大学硕士学位论文.2011年4月.
[7]高国飞.基于MNL的轨道交通乘客路径选择问题研究[D],北京：北京交通大学硕十学位论文.2009年6月.
[8]杨群,关伟等,基于合理多路径的路径选择方法的研究[J].管理工程学报,2002,16(4)：42-45.
[9]赖树坤,姚宪辉,彭愚.交通网络中有效路径确定方法的探讨[J].交通标准化,2008(1)：137-140.
[10]张嵩,王军,马金平.求解K最短路径的改进Dijkstra算法[J].中国经济与管理科学,2009(4)：29-31.
[11]四兵锋,毛保华,刘智丽.无缝换乘条件下城市轨道交通网络客流分配模型及算法[J].铁道学报,2007,29(6)：12-18.
[12]何胜学,范炳全.随机交通分配中有效路径的定向树搜索算法[J].交通与计算机,2005,23(5)：38-41.
[13]Tong CO,Richardson AJ. Estimation of time-dependent origin-destination matrices for transit networks. Journal of Advanced Transportation 1984;18:145-61.
[14]Tong CO,Wong SC,Poon MH,Tran MC.A schedule based dynamic transit network model— recent advances and prospective future research. Journal of Advanced Transportation 2001;35(2):175-95.
[15]Huang R. Peng Z. Schedule-based path finding algorithms for transit trip planning systems. Journal of Transportation Research Board: Transportation Research Record 2002;1783:142-8.
[16]Jin Y.Yen. Finding the K Shortest Loopless Paths in a Network: Management Science, 1971,17(11):712-716.
[17]张玺.基于出行方式的城市交通可达性研究[D].成都：西南交通大学硕士学位论文,2008年5月.
[18]罗钦.基于网络运营的城市轨道交通客流分布理论及仿真研究[D].上海：同济大学博士学位论文,2009年8月.
[19]苏星燕.城市轨道交通换乘站运营协调效率的评价研究[D].湖南:中南大学硕士学位论文,2010年5月.
[20]徐瑞华等.市域快速轨道交通线路列车运行交路研究[J].城市轨道交通研 究,2006,9(5)：36-39.
[21]杨杰,基于路网的城市轨道交通运输组织行车策略研究[D].北京：北京交通大学硕士学位论文,2006年12月.
[22]苏永涛,仉俊峰.基于图论方法的路径规划应用[J].电测与仪表,2012,49(1)：94-96.
[23]Tong,Yue Li, Bin Hong. An accurate continuous calibration system for high voltage current transfornler[J].Review of Scientific Intrusments,2011,82(2):025107-025107-9.
[24]Yue Tong,Hongbin Li,Lei Cheng,ct al.A Highly Accurate ECT calibration system Based on Virtual Instrument Technology[C]. Conference proceedings of the Seventh International Conference on Electronic Measurement&Instruments,2008:246-248.
[25]梁建斌.基于GIS管网仿真模拟系统的开发及应用[D].太原：太原理工大学硕士学位论文,2006年5月.
[26]董加强,基于邻接表的图生产算法探讨[J].西昌学院学报：自然科学版,2009,23(2)：43-45.
[27]周旭升,曾栩鸿,吝维军.基于广义邻接表的实时公交查询[J].科技信息,2010(17)：10188-10188,10157.
[28]李苏祺,张广军.基于邻接表的分水岭变换快速区域合并算法[J].北京航空航天大学学报,2008,34(11)：1327-1330,1348.
[29]叶晋.遗传算法在轨道交通换乘路径求解中的应用[D].上海：东华大学硕士学位论文,2009年3月.
[30]陈燕,刘春等.城市交通路网模型的更新方案与实现[J].交通信息与安全,2010(4)：39-42,48.
[31]杨英伟,饶鸣等.基于交通规则的路网模型建立及最优路径分析研究[J].城市勘测,2010(4)：58-61.
[32]Miller H J,Shaw S L.GIS-T data models, geograph-ic information systems for transportation:principles and applications[M]. Oxford:Oxford University Press,2001.
[33]American Transportation Research Board. Highway Capacity Manual[M]. Washington, D. C: National Research Council, 2000.
[34]Yang Yahong,Gao Jingchang. Application of design patterns for GIS platform software[J]. Journal of Jilin University: Information Science Edition,2003,21(2):153-155.
[35]粱虹,袁小群,刘蕊.一种新的公交数据模型与公交查询系统实现[J].计算机工程与应用,2007,43(3)：234-238.
[36]刘海涛.一种在赋权图中实现Dijkstra算法的矩阵方法[J].数学教学研究,2011,30(12)：47-49.
[37]Sung K, Bell M,Seong M, et al. Shortest paths in a network with time-dependent flow speeds[J]. European Journal of Operational Research,2000,121(1):32-39.
[38]Xu M H,Liu Y Q, et al.An improved Dijkstra's shortest path algorithm for sparse network[J].Applied Mathematics and Computation,2007,185(1):247-254.
[39]Fredman M L,Tarjan R E.Fibonacci heaps and their uses in improved network optimization algorithm[J].Journal of the ACM,1987,34(3):596-615.
[40]Han Y.Improved algorithm for all pairs shortest paths[J]. Inform Process Lett,2004,91:245-250.
[41]孙强,沈建华,顾君忠Dijkstra的一种改进算法[J].计算机工程与应用,2002(3)：99-101.
[42]Russell S,Norvig P. Artificial Intelligence:A Modem Approach[M].2nd ed. Prentice-Hall: Englewood Cliffs,NJ,2003.