高速旅客列车运行调整问题的图论模型与启发式算法
|
摘要
列车在运行过程中,受各种因素和突发事件的影响,不可避免的会发生运行紊乱,使列车运行的实际状态偏离预定值。列车运行调整的目的是尽量按“计划时间表”运行。列车运行调整就是在列车出现晚点时,改变列车在车站的到发时间及区间运行时分,提高正点率。列车运行调整问题是一个非常复杂的问题,需要考虑的因素很多,属于超大规模的组合优化问题。目前国内外对列车运行调整优化问题虽进行了广泛研究,取得了显著的成就,但在构造模型和算法方面还存在一定不足。
本文考虑线路条件为双线自动闭塞的单方向列车运行调整问题,从组合优化和列车运行调整基本方法出发,结合我国铁路调度现状和高速旅客列车运行调整的特点和优化策略,对传统列车运行图进行修改,提出了改进的图论模型,并且以调度区段内所有列车在所有站的到发晚点及通过区间晚点时间的加权总和最小为优化目标,建立相应的0-1整数规划模型。列车运行调整问题是NP-hard问题,且需要满足实时性要求和相关约束条件,要求在很短的时间内求解结果。因此,本文给出了一种求解速度较快、精度较高的启发式算法。根据启发式算法的求解流程,编写程序对给定的算例进行求解,得出高速旅客列车在不同晚点发生时刻的列车时刻表和相应的列车运行图,并对算例结果进行了分析比较。结果表明,本文提出的启发式算法能有效的利用车站和车站间的冗余时间对列车运行进行调整,从而减少列车晚点发生的概率,使晚点列车本身及其后续列车造成的晚点损失尽可能小。
Because the impact of various factors and unexpected events, train will inevitably be disorders during operation, and it will lead to the actual operation deviated from the planned value. The purpose of train operation adjustment is to run according to the published original timetable when delay occurs. Train operation adjustment is aimed to assure the rate of punctuality by means of changing arrival time, departure time and travel time when delay occurs. Actually, train operation adjustment is a very complex issue, and many factors need to be considered, so it belongs to large-scale combinatorial optimization problems. A wide range of researches on train operation adjustment have been done, although it has achieved remarkable success, some deficiencies still exist in the structural model and algorithm.
In this paper, we consider the optimal adjustment problem of train operations in one-track one-way line with automatic block signal system. From the combinatorial optimization and methods of train operation adjustment, combined with the practical situation of railway scheduling and the characteristics and optimization strategies of high-speed passenger railway in China, we modify the traditional train diagram and propose an improved graph theoretic model. And with the minimized weighted sums of departure-arrive delays in all stations and travel delays in all sections as the objective function, we propose the corresponding 0-1 integer programming model. Train operation adjustment is NP-hard problem and needs to meet the real-time requirements and related constraints, and solve the result in a very short time. Therefore, this paper gives an approximation algorithm with high solving speed and accuracy. According to the solving process of heuristic algorithm, we program and solve the given example, get the train timetable and corresponding train diagram of high-speed passenger trains at the different time delays, and then we analyze and compare the numerical results. Overall, the proposed heuristic algorithm can effectively make use of redundancy time in stations and segments to carry out adjustments to decrease possibility of train delay occurring, and cause delay losses of train themselves and their follow-up as small as possible.
本文考虑线路条件为双线自动闭塞的单方向列车运行调整问题,从组合优化和列车运行调整基本方法出发,结合我国铁路调度现状和高速旅客列车运行调整的特点和优化策略,对传统列车运行图进行修改,提出了改进的图论模型,并且以调度区段内所有列车在所有站的到发晚点及通过区间晚点时间的加权总和最小为优化目标,建立相应的0-1整数规划模型。列车运行调整问题是NP-hard问题,且需要满足实时性要求和相关约束条件,要求在很短的时间内求解结果。因此,本文给出了一种求解速度较快、精度较高的启发式算法。根据启发式算法的求解流程,编写程序对给定的算例进行求解,得出高速旅客列车在不同晚点发生时刻的列车时刻表和相应的列车运行图,并对算例结果进行了分析比较。结果表明,本文提出的启发式算法能有效的利用车站和车站间的冗余时间对列车运行进行调整,从而减少列车晚点发生的概率,使晚点列车本身及其后续列车造成的晚点损失尽可能小。
Because the impact of various factors and unexpected events, train will inevitably be disorders during operation, and it will lead to the actual operation deviated from the planned value. The purpose of train operation adjustment is to run according to the published original timetable when delay occurs. Train operation adjustment is aimed to assure the rate of punctuality by means of changing arrival time, departure time and travel time when delay occurs. Actually, train operation adjustment is a very complex issue, and many factors need to be considered, so it belongs to large-scale combinatorial optimization problems. A wide range of researches on train operation adjustment have been done, although it has achieved remarkable success, some deficiencies still exist in the structural model and algorithm.
In this paper, we consider the optimal adjustment problem of train operations in one-track one-way line with automatic block signal system. From the combinatorial optimization and methods of train operation adjustment, combined with the practical situation of railway scheduling and the characteristics and optimization strategies of high-speed passenger railway in China, we modify the traditional train diagram and propose an improved graph theoretic model. And with the minimized weighted sums of departure-arrive delays in all stations and travel delays in all sections as the objective function, we propose the corresponding 0-1 integer programming model. Train operation adjustment is NP-hard problem and needs to meet the real-time requirements and related constraints, and solve the result in a very short time. Therefore, this paper gives an approximation algorithm with high solving speed and accuracy. According to the solving process of heuristic algorithm, we program and solve the given example, get the train timetable and corresponding train diagram of high-speed passenger trains at the different time delays, and then we analyze and compare the numerical results. Overall, the proposed heuristic algorithm can effectively make use of redundancy time in stations and segments to carry out adjustments to decrease possibility of train delay occurring, and cause delay losses of train themselves and their follow-up as small as possible.
引文
[1]贾利民,张锡第,蔡秀生,张一生,杨梯惠.铁路运输自动化——现状,问题与挑战[A].中国控制会议论文集[C],1994：9-22
[2]http://www.railcn.net/news/railway-express/103140.html铁道部：2012年将建成四纵四横高速铁路专线网
[3]薛文,贾利民,张锡第.智能化铁路行车指挥系统若干问题的研究[A].第一届中国智能控制与智能自动化学术会议论文集[C],1994：28-33
[4]Frank, O.. Two-Way Traffic in a Single Line of Railway[J]. Operations Research,1965,14(5): 801-811
[5]Peat, Marwick, Mitchell & Co. Train dispatching simulation model:capabilities and description. USA Report No.DOT-FR-4-5014-1,1975
[6]Petersen, E. R., Taylor A. J.. A Structured Model for Rail Line Simulation and Optimization[J]. Transportation Science,1982,16(2):192-206
[7]Abe, K., Araya, S.. Train traffic simulation using the longest path method[J]. Transactions of Information Processing Society of Japan,1986,27(1):103-111
[8]Petersen, E. R., Taylor, A. J.. Line Block Prevention in Rail Line Dispatch and Simulation Models[J]. INFOR journal,1983,21 (1):46-51
[9]Carson, J. S, Atala, O. M.. Using computer simulation for rapid transit operating strategies[A]. Proceedings of the 22nd conference on Winter simulation[C],1990:798-801
[10]KePing Li, ZiYou Gao, Bin Ning. Cellular automaton model for railway traffic[J]. Journal of Computational Physics,2005,209(1):179-192
[11]KePing Li, ZiYou Gao, Bin Ning. Modeling the railway traffic using cellular automata model[J]. International Journal of Modern Physics C,2005,16(6):921-932
[12]Keping Li, Ziyou Gao, Lixing Yang. Modeling and simulation for train control system using cellular automata[J], Science In China Series E,2007,50(6):765-773
[13]Dorfman, M.J., Medanic, J.. Scheduling trains on a railway network using a discrete event model of railway traffic[J]. Transportation Research Part B,2004,38 (1):81-98.
[14]Feng Li, Ziyou Gao, Keping Li, Lixing Yang. Efficient scheduling of railway traffic based on global information of train[J]. Transportation Research Part B,2008,42 (10):81-98.
[15]周磊山,秦作睿.列车运行计划与调整的通用算法及其计算机实现[J].铁道学报,1994,16(3)：56-65
[16]周伟.基于DEDS模型预测的高速列车群运行调整新方法研究[J].西安：西安交通大学,1997
[17]B.Szpigel. Optimal train scheduling on a single track railway[J]. Operations Research'72. North-Holland Publishing Company, Amsterdam, Netherlands,1973:343-352
[18]Kraya, D., Harker, P.T., Chen., B.T.. Optimal pacing of trains in freight railroads:model formulation and solution[J]. Operation Research,1991,39(1):82-99
[19]Sauder, R. L., Westerman, W. M.. Computer Aided Train Dispatching:Decision Support Through Optimization[J]. Interfaces,1983,13:24-37
[20]Jovanovic D.. Improving railroad on-time performance:models, algorithms and applications[D]. Philadelfia:University of Pennsylvania,1989
[21]Araya S., Abe K., Fukumori K.. An Optimal Rescheduling for Online Train Traffic Control in Disturbed Situations[A]. Proc.22nd IEEE Conf. on Decision and Control[C],1983:489-494
[22]Cury, J., Gomide, F., Mendes, M. J.. A methodology for generation of optimal schedules for an underground railway system[J]. IEEE Transactions on Automatic Control,1983,25(2): 217-222
[23]程宇,秦作睿.列车运行调整专家系统的研究[J].铁道学报.1992,14(2)：43-51
[24]Dejan Jovanovi , Patrick T. Harker. Tactical Scheduling of Rail Operations:The SCAN I System[J]. Transportation Science,1991,25(1):46-64
[25]曹家明.单线铁路列车运行调整优化模型及算法.铁道学报[J].1994.16(3)：72-78
[26]Ostlund, B.. Computer-Based Planning Systems for the Swedish National Rail Administration[J]. Computer in Railway,1992,2:35-45
[27]Cai X., Goh C. J. A Fast Heuristic for the Train Scheduling Problem[J]. Computer Operations Research,1994,21(5):499-510
[28]赵鹏,胡安洲.高速铁路运行调整弹性研究[J].北方交通大学学报.1995,19：20-24
[29]彭其渊,朱松年,闰海峰.列车运行图可调整度评价系统研究[J].西南交通大学学报.1998,33(4)：367-371
[30]张星臣,杨浩,胡思继等.京沪高速铁路高中速列车共线混行模式下中速列车晚点影响的仿真分析[J].铁道学报,1998,20(5)：1-8
[31]StephenG. Ritehie. A Knowledge-based Decision Support Architecture for Advanced Traffic Management[J]. Transportation Research Part A,1990,24(1):27-37
[32]Araya S., Pukumori K.. ESTRAC Ⅱ:An Expert System for Train Traffic Control in disturbed situations[A]. Proc. of 6th European Con. on Artificial Intelligence[C],1984:23-32
[33]Komaya K. et al.. An Expert System for Train Traffic Control[J]. MITSUBISHI ELECTRIC ADVANCE,1998,43:25-28
[34]Kataoka K., K. Komaya.. Computer-aided railway scheduling systems for high-density train operations[J]. Railway Operations,1994:43-50
[35]Hyoudou M., et al. An expert system for train operation adjustment of SHINKANSEN[J]. IFAC Transporation Systems,1997:1145-1150
[36]Beurrier A, et al. Empty Freight Railcar Assignment by Expert System[J]. IFAC Control, Computers, Communication in Transportation,1989:105-109
[37]Levine P., Pomerol J.Ch.. Railcar Distribution at the French Railways[J]. IEEE Expert,1990, 5(5):61-69
[38]Schaefer H., Pferdmenges S.. An Expert System for Real-time Train Dispatching[J]. Computers in Railway,1994,2:27-33
[39]程宇,孔庆钤.用计算机编制列车运行调整计划的研究[J].铁道学报,1988,10(2),40-50
[40]Yu Cheng. Optimal train traffic rescheduling simulation by a knowledge-based system combined with critical path method[J]. Simulation Practice and Theory,1996,4(6):399-413
[41]Yu Cheng. Hybrid simulation for resolving resource conflicts in train traffic rescheduling[J]. Computers in Industry,1998,35(3):233-246
[42]李鹏,张一军.内部协同式列车运行调整专家系统的研究[J].中国铁道科学,1998,19(3)：1-9
[43]贾利民.模糊控制与决策及其在铁路自动化中的应用[D].铁道部科学研究院博士学位论文,1991
[44]CHANG C.S., and THIA B.S.. Online rescheduling of mass rapid transit systems: fuzzy expert system approach[J]. IEE Proc. Electric Power Applications,1996,143(4):307-316
[45]Alexander, et al. Fuzzy Expert System for Real-time Dispatching of MAGLEV Train Traffic[J]. IFAC Control Computers, Communication in Transportation,1999:681-685
[46]查伟雄,陈治亚,李夏苗.复线列车运行调整理论与方法的研究[J].铁道学报,2000,22(1)：12-16
[47]李平.面向对象遗传算法及其在铁路行车指挥中的应用[D].铁道部科学研究院博士学位论文,2001
[48]董守清,王进勇,闫海峰.双线铁路列车运行调整的禁忌搜索算法[J].中国铁道科学,2005,26(4)：114-119
[49]王进勇.分局调度系统列车运行调整优化模型与算法[D].西南交通大学,2003
[50]孙永福.中国高速铁路的成功之路[J].铁道学报,2009,31(6)：2-3.
[51]钱立新.世界高速铁路的发展水平和中国高速铁路的技术进展[J].铁路采购与物流,2009,9：19-21
[52]铁道部经济规划研究院.世界高速铁路发展趋势[J].铁道经济研究,2006,(01)：35-37
[53]马建军,胡思继,许红等.京沪高速铁路列车运行图编制基本理论的研究[J].北方交通大学学报,2002,26(2)：47-50
[54]金辰虎.高、中速旅客列车混行条件下的行车安全问题[J].中国铁路,1995,2(1)：12-15
[55]汤奇志,时颜,尹红.京沪高速铁路列车运行调整问题的探讨[J].中国铁路,2001,12(1)：37-38
[56]聂磊,张星臣,赵鹏等.高速铁路列车运行调整策略的研究[J].铁道学报,2001,23(4)：1-6
[57]王宏刚,张一军,张琦等.京沪高速铁路列车运行的调整[J].交通运输工程学报,2004,4(1)：67-69
[58]王慧妮.客运专线列车运行调整模型及算法研究[D].西南交通大学,2006
[59]杨浩.铁路运输组织学(第二版)[M].北京：中国铁道出版社,2006,268-285
[60]Caprara, A., Fischetti, M., Toth, P.. Modeling and solving the train timetabling problem[J]. Operations Research,2002,50 (5):851-861.
[61]Caprara, A., Monaci, M., Toth, P., Guida, P.L.. A lagrangian heuristic algorithm for a real-world train timetabling problem[J]. Discrete Applied Mathematics,2006,154(5):738-753.
[62]Ahuja, R.K., Magnanti, T.L., Orlin, J.B.. Network Flows: Theory, Algorithms, and Applications[M]. Prentice Hall, NJ.1993
[63]Matteo Fischetti, Domenico Salvagnin, Arrigo Zanette. Fast Approaches to Improve the Robustness of a Railway Timetable[J]. Transportation Science,2009,43(3): 321-335
[64]M.R. Garey, D.S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness[M]. New York: Freeman,1979
[65]Cai, X., Goh, C.J., Mees, A.I.. Greedy heuristics for rapid scheduling of trains on a single track.[J]. ⅡE Transactions,1998,30 (5):481-493.
[66]http://zhiqiang.org/blog/science/computer-science/preliminary-computer-theory-p-vs-np-an-ove rview-of-the-problem.html理论计算机初步：P vs NP-问题概述
[67]http://zhiqiang.org/blog/science/computer-science/preliminary-computer-theory-p-vs-np-past-pr esent-and-future.html理论计算机初步：P vs NP-历史,现状和未来
[68]Stephen A. Cook. The complexity of theorem proving procedures[A]. Proceedings of the Third Annual ACM Symposium on Theory of Computing[C],1971:151-158.
[69]Pearl, J. Heuristics: Intelligent Search Strategies for Computer Problem Solving[M]. Addsion-Wesley,1984
[70]http://hi.baidu.com/rangemq/blog/item/d55df0fc3c19f2f8fd037f48.html关于P, NP, NPC和NP-hard的通俗解释
[71]http://www.dreamflier.net/log/userl/3/1486.html关于NP-hard NP-complete问题定义典故与解释证明
[72]刑文训,谢金星.现代优化计算机方法(第2版)[M].北京：清华大学出版社,2005：1-50
[73]加里M R,约翰逊D S,张立昂等译.计算机和难解性：NP完全性理论导引[M],北京：科学出版社,1987
[74]Reeves C R (ed). Modern Heuristic Techniques for Combinatorial Problems[M].Oxford: Blackwells Scientific Publication,1993
[75]Polya, G. How to solve it[M]. Princeton: Princeton University Press,1948
[76]Lawler E L. Combinatorial optimization: networks and matroids[M]. USA: Oxford University Press,1976
[77]Papadimitriou C H, Steiglitz K. Combinatorial Optimization: Algorithms and Complexity[M]. New Jersey: Prentice-Hall INC,1982
[78]Klee V, Minty G J. How good is the simplex algorithm?[J]. In Shisha O. ed. Inequalities Ⅲ, New York: Academic Press Inc,1972:159-175.
[79]胡思继.铁路行车组织(高)[M].北京：中国铁道出版社,2007
[80]Wong, W.G, Han, B.M., Ferreira, L., Zhu, X.N., Sun, Q.X.. Evaluation of management strategies for the operation of high speed railways in China[J]. Transportation Research Part A, 2002,36(3),277-289.
[81]Higgins, A., Kozan, E., Ferreira, L.. Optimal scheduling of trains on a single line track[J]. Transportation Research Part B,1996,30 (2),147-161.
[82]Zhou, X. and Zhong, M.. Single-track train timetabling with guaranteed optimality, Branch-and-bound algorithms with enhanced lower bounds[J]. Transportation Research Part B, 2007,41(3):320-341.
[83]Valentina Cacchiani, Alberto Caprara, Paolo Toth. Scheduling extra freight trains on railway networks[J]. Transportation Research Part B:Methodological.2010,44(2):215-231
[84]Lixing Yang, Keping Li, Ziyou Gao, Train timetable problem on a single-line railway with fuzzy passenger demand[J], IEEE Transactions on Fuzzy Systems,2009,17(3):617-629
[85]Yu-Hern Chang, Chung-Hsing Yeh, Ching-Cheng Shen. A multiobjective model for passenger train services planning: application to Taiwan's high-speed rail line[J]. Transportation Research Part B:Methodological,2000,34(2):91-106
[86]Xuesong Zhou, Ming Zhong. Bicriteria train scheduling for high-speed passenger railroad planning applications[J]. European Journal of Operational Research,2005,167(3):752-771
[2]http://www.railcn.net/news/railway-express/103140.html铁道部：2012年将建成四纵四横高速铁路专线网
[3]薛文,贾利民,张锡第.智能化铁路行车指挥系统若干问题的研究[A].第一届中国智能控制与智能自动化学术会议论文集[C],1994：28-33
[4]Frank, O.. Two-Way Traffic in a Single Line of Railway[J]. Operations Research,1965,14(5): 801-811
[5]Peat, Marwick, Mitchell & Co. Train dispatching simulation model:capabilities and description. USA Report No.DOT-FR-4-5014-1,1975
[6]Petersen, E. R., Taylor A. J.. A Structured Model for Rail Line Simulation and Optimization[J]. Transportation Science,1982,16(2):192-206
[7]Abe, K., Araya, S.. Train traffic simulation using the longest path method[J]. Transactions of Information Processing Society of Japan,1986,27(1):103-111
[8]Petersen, E. R., Taylor, A. J.. Line Block Prevention in Rail Line Dispatch and Simulation Models[J]. INFOR journal,1983,21 (1):46-51
[9]Carson, J. S, Atala, O. M.. Using computer simulation for rapid transit operating strategies[A]. Proceedings of the 22nd conference on Winter simulation[C],1990:798-801
[10]KePing Li, ZiYou Gao, Bin Ning. Cellular automaton model for railway traffic[J]. Journal of Computational Physics,2005,209(1):179-192
[11]KePing Li, ZiYou Gao, Bin Ning. Modeling the railway traffic using cellular automata model[J]. International Journal of Modern Physics C,2005,16(6):921-932
[12]Keping Li, Ziyou Gao, Lixing Yang. Modeling and simulation for train control system using cellular automata[J], Science In China Series E,2007,50(6):765-773
[13]Dorfman, M.J., Medanic, J.. Scheduling trains on a railway network using a discrete event model of railway traffic[J]. Transportation Research Part B,2004,38 (1):81-98.
[14]Feng Li, Ziyou Gao, Keping Li, Lixing Yang. Efficient scheduling of railway traffic based on global information of train[J]. Transportation Research Part B,2008,42 (10):81-98.
[15]周磊山,秦作睿.列车运行计划与调整的通用算法及其计算机实现[J].铁道学报,1994,16(3)：56-65
[16]周伟.基于DEDS模型预测的高速列车群运行调整新方法研究[J].西安：西安交通大学,1997
[17]B.Szpigel. Optimal train scheduling on a single track railway[J]. Operations Research'72. North-Holland Publishing Company, Amsterdam, Netherlands,1973:343-352
[18]Kraya, D., Harker, P.T., Chen., B.T.. Optimal pacing of trains in freight railroads:model formulation and solution[J]. Operation Research,1991,39(1):82-99
[19]Sauder, R. L., Westerman, W. M.. Computer Aided Train Dispatching:Decision Support Through Optimization[J]. Interfaces,1983,13:24-37
[20]Jovanovic D.. Improving railroad on-time performance:models, algorithms and applications[D]. Philadelfia:University of Pennsylvania,1989
[21]Araya S., Abe K., Fukumori K.. An Optimal Rescheduling for Online Train Traffic Control in Disturbed Situations[A]. Proc.22nd IEEE Conf. on Decision and Control[C],1983:489-494
[22]Cury, J., Gomide, F., Mendes, M. J.. A methodology for generation of optimal schedules for an underground railway system[J]. IEEE Transactions on Automatic Control,1983,25(2): 217-222
[23]程宇,秦作睿.列车运行调整专家系统的研究[J].铁道学报.1992,14(2)：43-51
[24]Dejan Jovanovi , Patrick T. Harker. Tactical Scheduling of Rail Operations:The SCAN I System[J]. Transportation Science,1991,25(1):46-64
[25]曹家明.单线铁路列车运行调整优化模型及算法.铁道学报[J].1994.16(3)：72-78
[26]Ostlund, B.. Computer-Based Planning Systems for the Swedish National Rail Administration[J]. Computer in Railway,1992,2:35-45
[27]Cai X., Goh C. J. A Fast Heuristic for the Train Scheduling Problem[J]. Computer Operations Research,1994,21(5):499-510
[28]赵鹏,胡安洲.高速铁路运行调整弹性研究[J].北方交通大学学报.1995,19：20-24
[29]彭其渊,朱松年,闰海峰.列车运行图可调整度评价系统研究[J].西南交通大学学报.1998,33(4)：367-371
[30]张星臣,杨浩,胡思继等.京沪高速铁路高中速列车共线混行模式下中速列车晚点影响的仿真分析[J].铁道学报,1998,20(5)：1-8
[31]StephenG. Ritehie. A Knowledge-based Decision Support Architecture for Advanced Traffic Management[J]. Transportation Research Part A,1990,24(1):27-37
[32]Araya S., Pukumori K.. ESTRAC Ⅱ:An Expert System for Train Traffic Control in disturbed situations[A]. Proc. of 6th European Con. on Artificial Intelligence[C],1984:23-32
[33]Komaya K. et al.. An Expert System for Train Traffic Control[J]. MITSUBISHI ELECTRIC ADVANCE,1998,43:25-28
[34]Kataoka K., K. Komaya.. Computer-aided railway scheduling systems for high-density train operations[J]. Railway Operations,1994:43-50
[35]Hyoudou M., et al. An expert system for train operation adjustment of SHINKANSEN[J]. IFAC Transporation Systems,1997:1145-1150
[36]Beurrier A, et al. Empty Freight Railcar Assignment by Expert System[J]. IFAC Control, Computers, Communication in Transportation,1989:105-109
[37]Levine P., Pomerol J.Ch.. Railcar Distribution at the French Railways[J]. IEEE Expert,1990, 5(5):61-69
[38]Schaefer H., Pferdmenges S.. An Expert System for Real-time Train Dispatching[J]. Computers in Railway,1994,2:27-33
[39]程宇,孔庆钤.用计算机编制列车运行调整计划的研究[J].铁道学报,1988,10(2),40-50
[40]Yu Cheng. Optimal train traffic rescheduling simulation by a knowledge-based system combined with critical path method[J]. Simulation Practice and Theory,1996,4(6):399-413
[41]Yu Cheng. Hybrid simulation for resolving resource conflicts in train traffic rescheduling[J]. Computers in Industry,1998,35(3):233-246
[42]李鹏,张一军.内部协同式列车运行调整专家系统的研究[J].中国铁道科学,1998,19(3)：1-9
[43]贾利民.模糊控制与决策及其在铁路自动化中的应用[D].铁道部科学研究院博士学位论文,1991
[44]CHANG C.S., and THIA B.S.. Online rescheduling of mass rapid transit systems: fuzzy expert system approach[J]. IEE Proc. Electric Power Applications,1996,143(4):307-316
[45]Alexander, et al. Fuzzy Expert System for Real-time Dispatching of MAGLEV Train Traffic[J]. IFAC Control Computers, Communication in Transportation,1999:681-685
[46]查伟雄,陈治亚,李夏苗.复线列车运行调整理论与方法的研究[J].铁道学报,2000,22(1)：12-16
[47]李平.面向对象遗传算法及其在铁路行车指挥中的应用[D].铁道部科学研究院博士学位论文,2001
[48]董守清,王进勇,闫海峰.双线铁路列车运行调整的禁忌搜索算法[J].中国铁道科学,2005,26(4)：114-119
[49]王进勇.分局调度系统列车运行调整优化模型与算法[D].西南交通大学,2003
[50]孙永福.中国高速铁路的成功之路[J].铁道学报,2009,31(6)：2-3.
[51]钱立新.世界高速铁路的发展水平和中国高速铁路的技术进展[J].铁路采购与物流,2009,9：19-21
[52]铁道部经济规划研究院.世界高速铁路发展趋势[J].铁道经济研究,2006,(01)：35-37
[53]马建军,胡思继,许红等.京沪高速铁路列车运行图编制基本理论的研究[J].北方交通大学学报,2002,26(2)：47-50
[54]金辰虎.高、中速旅客列车混行条件下的行车安全问题[J].中国铁路,1995,2(1)：12-15
[55]汤奇志,时颜,尹红.京沪高速铁路列车运行调整问题的探讨[J].中国铁路,2001,12(1)：37-38
[56]聂磊,张星臣,赵鹏等.高速铁路列车运行调整策略的研究[J].铁道学报,2001,23(4)：1-6
[57]王宏刚,张一军,张琦等.京沪高速铁路列车运行的调整[J].交通运输工程学报,2004,4(1)：67-69
[58]王慧妮.客运专线列车运行调整模型及算法研究[D].西南交通大学,2006
[59]杨浩.铁路运输组织学(第二版)[M].北京：中国铁道出版社,2006,268-285
[60]Caprara, A., Fischetti, M., Toth, P.. Modeling and solving the train timetabling problem[J]. Operations Research,2002,50 (5):851-861.
[61]Caprara, A., Monaci, M., Toth, P., Guida, P.L.. A lagrangian heuristic algorithm for a real-world train timetabling problem[J]. Discrete Applied Mathematics,2006,154(5):738-753.
[62]Ahuja, R.K., Magnanti, T.L., Orlin, J.B.. Network Flows: Theory, Algorithms, and Applications[M]. Prentice Hall, NJ.1993
[63]Matteo Fischetti, Domenico Salvagnin, Arrigo Zanette. Fast Approaches to Improve the Robustness of a Railway Timetable[J]. Transportation Science,2009,43(3): 321-335
[64]M.R. Garey, D.S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness[M]. New York: Freeman,1979
[65]Cai, X., Goh, C.J., Mees, A.I.. Greedy heuristics for rapid scheduling of trains on a single track.[J]. ⅡE Transactions,1998,30 (5):481-493.
[66]http://zhiqiang.org/blog/science/computer-science/preliminary-computer-theory-p-vs-np-an-ove rview-of-the-problem.html理论计算机初步：P vs NP-问题概述
[67]http://zhiqiang.org/blog/science/computer-science/preliminary-computer-theory-p-vs-np-past-pr esent-and-future.html理论计算机初步：P vs NP-历史,现状和未来
[68]Stephen A. Cook. The complexity of theorem proving procedures[A]. Proceedings of the Third Annual ACM Symposium on Theory of Computing[C],1971:151-158.
[69]Pearl, J. Heuristics: Intelligent Search Strategies for Computer Problem Solving[M]. Addsion-Wesley,1984
[70]http://hi.baidu.com/rangemq/blog/item/d55df0fc3c19f2f8fd037f48.html关于P, NP, NPC和NP-hard的通俗解释
[71]http://www.dreamflier.net/log/userl/3/1486.html关于NP-hard NP-complete问题定义典故与解释证明
[72]刑文训,谢金星.现代优化计算机方法(第2版)[M].北京：清华大学出版社,2005：1-50
[73]加里M R,约翰逊D S,张立昂等译.计算机和难解性：NP完全性理论导引[M],北京：科学出版社,1987
[74]Reeves C R (ed). Modern Heuristic Techniques for Combinatorial Problems[M].Oxford: Blackwells Scientific Publication,1993
[75]Polya, G. How to solve it[M]. Princeton: Princeton University Press,1948
[76]Lawler E L. Combinatorial optimization: networks and matroids[M]. USA: Oxford University Press,1976
[77]Papadimitriou C H, Steiglitz K. Combinatorial Optimization: Algorithms and Complexity[M]. New Jersey: Prentice-Hall INC,1982
[78]Klee V, Minty G J. How good is the simplex algorithm?[J]. In Shisha O. ed. Inequalities Ⅲ, New York: Academic Press Inc,1972:159-175.
[79]胡思继.铁路行车组织(高)[M].北京：中国铁道出版社,2007
[80]Wong, W.G, Han, B.M., Ferreira, L., Zhu, X.N., Sun, Q.X.. Evaluation of management strategies for the operation of high speed railways in China[J]. Transportation Research Part A, 2002,36(3),277-289.
[81]Higgins, A., Kozan, E., Ferreira, L.. Optimal scheduling of trains on a single line track[J]. Transportation Research Part B,1996,30 (2),147-161.
[82]Zhou, X. and Zhong, M.. Single-track train timetabling with guaranteed optimality, Branch-and-bound algorithms with enhanced lower bounds[J]. Transportation Research Part B, 2007,41(3):320-341.
[83]Valentina Cacchiani, Alberto Caprara, Paolo Toth. Scheduling extra freight trains on railway networks[J]. Transportation Research Part B:Methodological.2010,44(2):215-231
[84]Lixing Yang, Keping Li, Ziyou Gao, Train timetable problem on a single-line railway with fuzzy passenger demand[J], IEEE Transactions on Fuzzy Systems,2009,17(3):617-629
[85]Yu-Hern Chang, Chung-Hsing Yeh, Ching-Cheng Shen. A multiobjective model for passenger train services planning: application to Taiwan's high-speed rail line[J]. Transportation Research Part B:Methodological,2000,34(2):91-106
[86]Xuesong Zhou, Ming Zhong. Bicriteria train scheduling for high-speed passenger railroad planning applications[J]. European Journal of Operational Research,2005,167(3):752-771