基于列车开行方案的服务网络构建及路径搜索技术研究与系统开发
|
摘要
列车开行方案是从客流到列车流的组织方案,很大程度上反映了铁路运输组织的经营策略和服务水平。旅客列车开行方案是构建铁路客运服务网络的基础,旅客对于多种出行方案进行选择的过程可以视为旅客在服务网络中的多路径出行选择过程,即客流分配过程。构建好列车开行方案所对应的客运服务网络,并对网络中的路径进行求解可以为列车开行方案的优化提供重要依据。
本文对国内外研究成果进行了总结分析,深入研究了基于列车开行方案的服务网络构建与路径搜索技术,设计了求解基础物理网络和开行方案服务网络多路径算法,并开发了列车开行方案服务网络管理系统。论文主要工作如下：
1、基于铁路基础物理网络,构建了列车开行方案服务网络,该网络节点集由车站节点、列车停站节点和列车发站节点构成,弧段集由上车弧段、乘车弧段、停车弧段、换乘弧段和下车弧段构成,从而为研究列车开行方案客流分配问题提供了基础。
2、研究了基础物理网络和列车开行方案服务网络两种网络下合理路径集合的求解问题。首先定义了合理路径,对网络进行简化,然后对路径的搜索区域进行分析并构造了路径的表示方法,在此基础上分别设计了求解基础物理网络和开行方案服务网络多路径算法,最后求解出合理路径集合。
3、基于构建的网络和路径搜索算法,设计开发了列车开行方案服务网络管理系统,该系统适用于以高速铁路为骨干的全国铁路网,采用窗体应用程序标准设计界面,具有基础物理网络数据生成、查询、维护、优化,基础物理网络路径求解和列车开行方案服务网络路径求解等功能,在铁路客运服务网络的构建技术方面有一定创新,能为列车开行方案的优化编制提供重要的路径决策信息。
The train service plan describes the scheme from passenger flow to train flow which reflects the railway transport operational strategy and service level. Passenger train service plan is the basis of constructing railway passenger service network. Passenger's selection from various travel plans can be regarded as the travel choice process in service network, namely the passenger flow distribution process. Building the corresponding passenger service network according to the train service plan, and serching the path in the network can provide an important basis for the optimization of the train service plan.
According to the current research achievements, this paper thoroughly studies passenger service network construction technology based on the train service plan and path search technology, then, the detail algorithms for solving multi-path in basic railway network and in train service network are designed respectively, on these basis, the train service network management system is developed. The major topics are as follows:
(1)Based on basic railway network, the train service network for studying passenger flow distribution is constructed. The network node set is formed by station node, train stop node and train departing node, and the network arc set is formed by getting on arc, riding arc, stopping arc, transferring arc and getting off arc.
(2)The paper studied the reasonable path set in basic railway network and in train service network. First the reasonable path is defined and the network is simplified, then the search area of path is analyzed and the expression method of path is constructed, and based on this, the detail algorithms for solving multi-path in these two kinds of network are designed respectively, and finally the reasonable path set is solved.
(3)Based on the network and path search algorithm, a train service network management system is designed and developed, which is suitable for the national rail network with the high speed railways as its backbone.The interface is designed by use of the form application standard. The system functions are mainly including the basic railway network data generation, query, maintenance, optimization, the basic railway network route solution and train service network path search. The system has certain innovation and can provide important path decision-making information for the optimization of train service plan.
本文对国内外研究成果进行了总结分析,深入研究了基于列车开行方案的服务网络构建与路径搜索技术,设计了求解基础物理网络和开行方案服务网络多路径算法,并开发了列车开行方案服务网络管理系统。论文主要工作如下：
1、基于铁路基础物理网络,构建了列车开行方案服务网络,该网络节点集由车站节点、列车停站节点和列车发站节点构成,弧段集由上车弧段、乘车弧段、停车弧段、换乘弧段和下车弧段构成,从而为研究列车开行方案客流分配问题提供了基础。
2、研究了基础物理网络和列车开行方案服务网络两种网络下合理路径集合的求解问题。首先定义了合理路径,对网络进行简化,然后对路径的搜索区域进行分析并构造了路径的表示方法,在此基础上分别设计了求解基础物理网络和开行方案服务网络多路径算法,最后求解出合理路径集合。
3、基于构建的网络和路径搜索算法,设计开发了列车开行方案服务网络管理系统,该系统适用于以高速铁路为骨干的全国铁路网,采用窗体应用程序标准设计界面,具有基础物理网络数据生成、查询、维护、优化,基础物理网络路径求解和列车开行方案服务网络路径求解等功能,在铁路客运服务网络的构建技术方面有一定创新,能为列车开行方案的优化编制提供重要的路径决策信息。
The train service plan describes the scheme from passenger flow to train flow which reflects the railway transport operational strategy and service level. Passenger train service plan is the basis of constructing railway passenger service network. Passenger's selection from various travel plans can be regarded as the travel choice process in service network, namely the passenger flow distribution process. Building the corresponding passenger service network according to the train service plan, and serching the path in the network can provide an important basis for the optimization of the train service plan.
According to the current research achievements, this paper thoroughly studies passenger service network construction technology based on the train service plan and path search technology, then, the detail algorithms for solving multi-path in basic railway network and in train service network are designed respectively, on these basis, the train service network management system is developed. The major topics are as follows:
(1)Based on basic railway network, the train service network for studying passenger flow distribution is constructed. The network node set is formed by station node, train stop node and train departing node, and the network arc set is formed by getting on arc, riding arc, stopping arc, transferring arc and getting off arc.
(2)The paper studied the reasonable path set in basic railway network and in train service network. First the reasonable path is defined and the network is simplified, then the search area of path is analyzed and the expression method of path is constructed, and based on this, the detail algorithms for solving multi-path in these two kinds of network are designed respectively, and finally the reasonable path set is solved.
(3)Based on the network and path search algorithm, a train service network management system is designed and developed, which is suitable for the national rail network with the high speed railways as its backbone.The interface is designed by use of the form application standard. The system functions are mainly including the basic railway network data generation, query, maintenance, optimization, the basic railway network route solution and train service network path search. The system has certain innovation and can provide important path decision-making information for the optimization of train service plan.
引文
[1]Goossens, J., van Hoesel, C., Kroon, L,2005.On solving multi-type railway line planning problems. European Journal of Operational Research 168,403-424.
[2]Scholl, S.,2005.Customer-oriented Line Planning [Dissertation],University of Kaiserslautern.
[3]Chi-Kang LEE,Wen-jin HSIEH,2001.A demand oriented service planning process.The World Congress On Railway Research.Koln,Germany.
[4]Ricardo Garcia, Angel Marin. Network equilibrium with combined modes:models and solution algorithms[J]. Transportation Research Part B,2005,39(3):223-254.
[5]Dijkstra E.W.A note on two problems in connection with graphs.Numberische Mathmatic.1959,1(1):269-271.
[6]Shier R D.On Algorithm for finding the K shortest Pathes in a Network[J].Networks,1979,9(9):195-214.
[7]Yen J.Y.Finding the k shortest loopless pathes in a network[J]. Management Science,1971,17:712-716.
[8]LIU G,RAMAKRISHNAN K G.A*Prune:An Algorithm for Finding k-Shortest Paths Subject to Multiple Constraints[C].Proceedings of the INFOCOM 2001 Conference,IEEE,Anchorage,Alaska, 2001:743-749.
[9]ZUWAIRIE I,YUSEI T.Mohd Saufee Muhammad,et al.DNA Implementation of k-Shortest Paths Computation[C].2005 IEEE Congress on Evolutionary Computation,Edinburgh,UK,2005,1(12):707-713.
[10]Park D. Multiple Path based vehicle routing in dynamic and stochastic transportation networks[dissertation][M].Texas A&M University,1998.
[11]TANG Z,YU Y.A Parallel Algorithm for Finding K Expected Shortest Paths in Stochastic and Timedependent Networks[J].Proceedings of the 6th World Multiconference on Systemics,Cybemetics and Informatics(XlI).Orlando,Florida:SCI,2002,279(4752):362-367.
[12]MACGEGOR M H,GROVER WD.Optimized k-Shortest Path Algorithm for facility Restoration[J].Software Practice and Experience,1994,24(9):823-828.
[13]J.A.Azevedo,J.J.E.R.S,Madeira,E.Q.V.Martins and F.M.A.Pires,A shortest paths ranking algorithm,1990,Proceedings of the Annual Conference AIRO'90,Models and Methods for Decision Surport,Operation Research Society of Italy,1001-1011.
[14]QIUJIN W,JOANNA H.Using K-shortest Paths Algorithms to Accommodate User Preferences in the Optimization of Public Transport Travel[C],ASCE,The 8th International Conference on Applications of Advanced Technologies in Transportation Engineering,U.S.A,2004:181-186.
[15]MATTHEW W,CARLYLE R,KEVIN W.Near Shortest and K-shortest Simple Paths[J],Networks,2005,46(2):98-109.
[16]MACGEGOR M H,GROVER WD.Optimized k-Shortest Path Algorithm for facility Restoration[J].Software Practice and Experience,1994,24(9):823-828.
[17]JOHN.HERSHBERGRE.Finding the K-shortest Simple Paths:A new Algorithm and Its Implementation[J]. ACM Transactions onalgorithm.California:SCI,2007,3(4):45-64.
[18]JOHN H,MATTHEW M,SUBHASH S,Finding the K-shortest Simple Paths:11-14.
[19]张彦.铁路客票中转换乘多径路选择问题研究[J].铁道运输与经济,1997,(8)：11-13.
[20]王华,季令.我国铁路客运合理径路选择研究[J].上海铁道大学学报,1999,20(4)：51-54.
[21]史峰,马均培,向联慧,等.客运中转径路的换乘模型和算法[J].铁道学报,1999,21(5)：1-4.
[22]向联慧.客运中转换乘的优化模型与算法[D].长沙：长沙铁道学院,2000.
[23]史峰,邓连波.旅客换乘网络优化设计[J].铁道科学与工程学报,2004,1(1),78-82.
[24]付慧伶.高速铁路列车开行方案编制理论与方法研究[D].北京：北京交通大学,2010.
[25]杨同庆.基于弹性需求的客运专线开行方案优化设计研究[D].北京：北京交通大学,2009.
[26]邓连波.客运专线相关旅客列车开行方案优化研究[D].长沙：中南大学,2007.
[27]闫铭,翟轲,周博拓.基于旅客列车开行及停站方案的客流分配[J].交通科技与经济,2009,4：1-5.
[28]曾鸣凯,黄鉴,彭其渊.客运专线旅客列车开行方案的客流分配方法[J].西南交通大学学报,2006,41(5)：1-4.
[29]王莹,李尔涛,刘军.基于服务网络设计的“五定”班列开行方案优化方法研究[J].物流技术,2009,28(2)：2-4.
[30]张依莹,彭其渊.综合运输旅客换乘网络优化模型[J].西南交通大学学报,2009,44(4)：517-519.
[31]吴祥云,刘灿齐.轨道交通客流量均衡分配模型与算法[J].同济大学学报,2004,32(9)：1158-1163.
[32]霍亮.铁路旅客乘车行为分析与客流分配方法研究[D].长沙：中南大学,2006.
[33]霍亮.拥挤条件下的铁路随机用户平衡配流模型[J].铁道运输与经济,2008,30(9)：88-94.
[34]宋一凡,高自友.能力限制条件下的公交平衡分配模型和求解算法[J].铁道学报,1999,21(5)：10—14.
[35]徐琳.应用层次分析法确定旅客列车开行方案的研究[J].铁道经济研究,2001(3)：46-48.
[36]王喆,彭其渊,谢小淞.基于遗传算法的铁路旅客列车开行路径优化的研究[J].铁路计算机应用,2006,15(12)：4-6：
[37]李旭华,王建中.基于数据库的城市道路中的最短路径搜索[J].电脑开发与应用,2005,18(1)：14-15.
[38]王明中,谢剑英,陈应麟.一种新的K-PATH最短路搜索算法[J].计算机工程与应用.2004,30：49-50.
[39]付梦印,李杰,邓志红.限制搜索区域的距离最短路径规划算法.北京理工大学学报.24(10)：881-884.
[40]孙健鹤.城市道路网络最短路径的统计学特征及试用算法研究[D].上海：华东师范大学,2006.
[41]荣玮.基于道路网的最短路径算法的研究和表现[D].武汉：武汉理工大学,2005.
[42]李臣波.网络的K最短路算法研究[D].哈尔滨：哈尔滨理工大学,2008.
[43]孙雨耕,胡华东,杨挺.一种应用于路由规划的实用无环K路算法[J].计算机工程,29(22)：128-132.
[44]李成江.新的K最短路算法[J].山东大学学报,2006,41(4)：40-44.
[45]杨群,张国伍.基于“节点删除”的多路径获取方法的研究[J].北方交通大学学 报,2002,26(2)：77-81.
[46]陈阳,王波.可替换路径选择的研究[J].盐城工学学院学报,2005,18(3)：23-27.
[47]向万里,刘洪升.城市公交网络出行路径选择的计算机算法研究[J].兰州交通大学学报,2006,25(1)：121-124.
[48]陈文杰.路径选择中合理路径集的研究与应用[D].广州：中山大学,2008.
[49]王建林.基于换乘次数最少的城市公交网络最优路径算法[J].经济地理,2005,25(5)：673-676.
[50]何胜学,范炳全.公交网络最优路径求解算法[J].交通运输工程与信息学报,2007,5(1)：22-27.
[51]孔千,刘中等,铁路网络结构存储及货运径路问题研究[J].军事交通学院学报,2009,11(5)：10-15.
[52]张羽成,吕红霞,王宝杰.基于图论的列车运行径路分析与构造[J].西南交通大学学报,2000,35(3)：273-276.
[53]张永梅,韩焱,陈立潮.城市公交查询系统的研究与设计[J].计算机应用,2005,25(2)：422-425.
[54]张玉春,张世巍,李冬云.公交查询系统的开发与设计[J].长春大学学报,2009,19(8)：22-26.
[55]刘光明,蔡先华等.一种城市公交查询的算法及其应用[J].交通运输工程与信息学报,2005,3(2)：87-91.
[56]邱涛.基于最优路径算法的公交WebGIS系统的研究和开发[D].武汉：武汉理工大学,2008.
[57]杨兆升.城市交通流诱导系统[M].北京：中国铁道出版社,2004,11.
[58]张胜.基于.NET技术的WebGIS系统的研究与实现策略[D].长沙：湖南大学软件工程,2006.
[59]周涛.WebGIS的实现技术及发展趋势[J].信阳师范学院学报(自然科学版),2003,16(1)：108-109.
[60]陈箫枫,蔡秀云,唐德强.最短路径算法分析及其在公交查询中的应用[J].工程图学学报,2001(3)：20-24.
[2]Scholl, S.,2005.Customer-oriented Line Planning [Dissertation],University of Kaiserslautern.
[3]Chi-Kang LEE,Wen-jin HSIEH,2001.A demand oriented service planning process.The World Congress On Railway Research.Koln,Germany.
[4]Ricardo Garcia, Angel Marin. Network equilibrium with combined modes:models and solution algorithms[J]. Transportation Research Part B,2005,39(3):223-254.
[5]Dijkstra E.W.A note on two problems in connection with graphs.Numberische Mathmatic.1959,1(1):269-271.
[6]Shier R D.On Algorithm for finding the K shortest Pathes in a Network[J].Networks,1979,9(9):195-214.
[7]Yen J.Y.Finding the k shortest loopless pathes in a network[J]. Management Science,1971,17:712-716.
[8]LIU G,RAMAKRISHNAN K G.A*Prune:An Algorithm for Finding k-Shortest Paths Subject to Multiple Constraints[C].Proceedings of the INFOCOM 2001 Conference,IEEE,Anchorage,Alaska, 2001:743-749.
[9]ZUWAIRIE I,YUSEI T.Mohd Saufee Muhammad,et al.DNA Implementation of k-Shortest Paths Computation[C].2005 IEEE Congress on Evolutionary Computation,Edinburgh,UK,2005,1(12):707-713.
[10]Park D. Multiple Path based vehicle routing in dynamic and stochastic transportation networks[dissertation][M].Texas A&M University,1998.
[11]TANG Z,YU Y.A Parallel Algorithm for Finding K Expected Shortest Paths in Stochastic and Timedependent Networks[J].Proceedings of the 6th World Multiconference on Systemics,Cybemetics and Informatics(XlI).Orlando,Florida:SCI,2002,279(4752):362-367.
[12]MACGEGOR M H,GROVER WD.Optimized k-Shortest Path Algorithm for facility Restoration[J].Software Practice and Experience,1994,24(9):823-828.
[13]J.A.Azevedo,J.J.E.R.S,Madeira,E.Q.V.Martins and F.M.A.Pires,A shortest paths ranking algorithm,1990,Proceedings of the Annual Conference AIRO'90,Models and Methods for Decision Surport,Operation Research Society of Italy,1001-1011.
[14]QIUJIN W,JOANNA H.Using K-shortest Paths Algorithms to Accommodate User Preferences in the Optimization of Public Transport Travel[C],ASCE,The 8th International Conference on Applications of Advanced Technologies in Transportation Engineering,U.S.A,2004:181-186.
[15]MATTHEW W,CARLYLE R,KEVIN W.Near Shortest and K-shortest Simple Paths[J],Networks,2005,46(2):98-109.
[16]MACGEGOR M H,GROVER WD.Optimized k-Shortest Path Algorithm for facility Restoration[J].Software Practice and Experience,1994,24(9):823-828.
[17]JOHN.HERSHBERGRE.Finding the K-shortest Simple Paths:A new Algorithm and Its Implementation[J]. ACM Transactions onalgorithm.California:SCI,2007,3(4):45-64.
[18]JOHN H,MATTHEW M,SUBHASH S,Finding the K-shortest Simple Paths:11-14.
[19]张彦.铁路客票中转换乘多径路选择问题研究[J].铁道运输与经济,1997,(8)：11-13.
[20]王华,季令.我国铁路客运合理径路选择研究[J].上海铁道大学学报,1999,20(4)：51-54.
[21]史峰,马均培,向联慧,等.客运中转径路的换乘模型和算法[J].铁道学报,1999,21(5)：1-4.
[22]向联慧.客运中转换乘的优化模型与算法[D].长沙：长沙铁道学院,2000.
[23]史峰,邓连波.旅客换乘网络优化设计[J].铁道科学与工程学报,2004,1(1),78-82.
[24]付慧伶.高速铁路列车开行方案编制理论与方法研究[D].北京：北京交通大学,2010.
[25]杨同庆.基于弹性需求的客运专线开行方案优化设计研究[D].北京：北京交通大学,2009.
[26]邓连波.客运专线相关旅客列车开行方案优化研究[D].长沙：中南大学,2007.
[27]闫铭,翟轲,周博拓.基于旅客列车开行及停站方案的客流分配[J].交通科技与经济,2009,4：1-5.
[28]曾鸣凯,黄鉴,彭其渊.客运专线旅客列车开行方案的客流分配方法[J].西南交通大学学报,2006,41(5)：1-4.
[29]王莹,李尔涛,刘军.基于服务网络设计的“五定”班列开行方案优化方法研究[J].物流技术,2009,28(2)：2-4.
[30]张依莹,彭其渊.综合运输旅客换乘网络优化模型[J].西南交通大学学报,2009,44(4)：517-519.
[31]吴祥云,刘灿齐.轨道交通客流量均衡分配模型与算法[J].同济大学学报,2004,32(9)：1158-1163.
[32]霍亮.铁路旅客乘车行为分析与客流分配方法研究[D].长沙：中南大学,2006.
[33]霍亮.拥挤条件下的铁路随机用户平衡配流模型[J].铁道运输与经济,2008,30(9)：88-94.
[34]宋一凡,高自友.能力限制条件下的公交平衡分配模型和求解算法[J].铁道学报,1999,21(5)：10—14.
[35]徐琳.应用层次分析法确定旅客列车开行方案的研究[J].铁道经济研究,2001(3)：46-48.
[36]王喆,彭其渊,谢小淞.基于遗传算法的铁路旅客列车开行路径优化的研究[J].铁路计算机应用,2006,15(12)：4-6：
[37]李旭华,王建中.基于数据库的城市道路中的最短路径搜索[J].电脑开发与应用,2005,18(1)：14-15.
[38]王明中,谢剑英,陈应麟.一种新的K-PATH最短路搜索算法[J].计算机工程与应用.2004,30：49-50.
[39]付梦印,李杰,邓志红.限制搜索区域的距离最短路径规划算法.北京理工大学学报.24(10)：881-884.
[40]孙健鹤.城市道路网络最短路径的统计学特征及试用算法研究[D].上海：华东师范大学,2006.
[41]荣玮.基于道路网的最短路径算法的研究和表现[D].武汉：武汉理工大学,2005.
[42]李臣波.网络的K最短路算法研究[D].哈尔滨：哈尔滨理工大学,2008.
[43]孙雨耕,胡华东,杨挺.一种应用于路由规划的实用无环K路算法[J].计算机工程,29(22)：128-132.
[44]李成江.新的K最短路算法[J].山东大学学报,2006,41(4)：40-44.
[45]杨群,张国伍.基于“节点删除”的多路径获取方法的研究[J].北方交通大学学 报,2002,26(2)：77-81.
[46]陈阳,王波.可替换路径选择的研究[J].盐城工学学院学报,2005,18(3)：23-27.
[47]向万里,刘洪升.城市公交网络出行路径选择的计算机算法研究[J].兰州交通大学学报,2006,25(1)：121-124.
[48]陈文杰.路径选择中合理路径集的研究与应用[D].广州：中山大学,2008.
[49]王建林.基于换乘次数最少的城市公交网络最优路径算法[J].经济地理,2005,25(5)：673-676.
[50]何胜学,范炳全.公交网络最优路径求解算法[J].交通运输工程与信息学报,2007,5(1)：22-27.
[51]孔千,刘中等,铁路网络结构存储及货运径路问题研究[J].军事交通学院学报,2009,11(5)：10-15.
[52]张羽成,吕红霞,王宝杰.基于图论的列车运行径路分析与构造[J].西南交通大学学报,2000,35(3)：273-276.
[53]张永梅,韩焱,陈立潮.城市公交查询系统的研究与设计[J].计算机应用,2005,25(2)：422-425.
[54]张玉春,张世巍,李冬云.公交查询系统的开发与设计[J].长春大学学报,2009,19(8)：22-26.
[55]刘光明,蔡先华等.一种城市公交查询的算法及其应用[J].交通运输工程与信息学报,2005,3(2)：87-91.
[56]邱涛.基于最优路径算法的公交WebGIS系统的研究和开发[D].武汉：武汉理工大学,2008.
[57]杨兆升.城市交通流诱导系统[M].北京：中国铁道出版社,2004,11.
[58]张胜.基于.NET技术的WebGIS系统的研究与实现策略[D].长沙：湖南大学软件工程,2006.
[59]周涛.WebGIS的实现技术及发展趋势[J].信阳师范学院学报(自然科学版),2003,16(1)：108-109.
[60]陈箫枫,蔡秀云,唐德强.最短路径算法分析及其在公交查询中的应用[J].工程图学学报,2001(3)：20-24.