Literature Review on Rail Train Timetabling

Abstract

Abstract: The rail train timetabling problem has always been a hot research topic in the field of transportation and operations research due to its wide practical applications and complex computational challenges. As a sub- stage of the hierarchical planning of rail transit operations, the timetable problem can be extended to multiple related areas by integrating the upper- layer line planning problem and the lower- layer rolling stock scheduling problem. The train timetable design is to determine a conflict- free running path for each train in the elaborated space-time network, in which the objectives are the user- based measurements such as the passenger waiting times or the supply- based measurements such as the operating costs. If the overtaking activities are not allowed and the stop-skip pattern is given, the optimization models for train timetables can be formulated by using integer variables. Otherwise, zero-one variables are required to represent the departure orders or skip- stopping decisions of trains at the stations. Generally, the models are typical large-scale, multi-objective and strong-coupled NP-hard problems. It is important and difficult to design effective solution algorithms for this type of problems. For the cases with simple conditions and small scales, one common approach is to properly simplify the original complex problem and/or reasonably revise the intractable formulations, and then solve the updated model using state- of- the- art solution frameworks and commercialoptimization solvers. Two types of direct decomposition algorithms, i.e., branch and bound and dynamic programming are two effective methods. Furthermore, the dual decomposition algorithm, which is represented by Lagrangian relaxation and column generation, is normally the best choice for the complicated and large scale problems. The future research should explore the timetabling problem with the consideration of many practical requirements (i.e., infrastructure maintenance) and time- dependent fares and ticket distributions. In addition, it is an interesting topic to address the train timetabling problem within network-wide applications. Finally, solution algorithms that combine the characteristics of problems and the advanced optimization technologies, and commercial software that is applicable to the actual operations, should be developed in the future.

Key words: railway transportation, train timetable, topic, modeling, algorithm

摘要： 广泛的实践应用和复杂的计算挑战，使得轨道列车时刻表优化问题，多年来一直是交通运输及运筹管理学界的热点研究问题。作为轨道交通运营规划的一个子阶段，列车时刻表向上与线路规划(或开行方案)、向下与动车组调度融合，可以得到多个延伸的研究选题。在特定的时空网络中，列车时刻表设计就是为每个列车确定一条无冲突的运行路径，使基于用户的度量指标如乘客候车时间，或企业的度量指标如运营费用达到最优。对于没有列车越行和停站模式给定的情况，通过整数变量可以完整地刻画列车时刻表模型，但如果考虑列车越行或列车停站决策，则需要引入列车在车站出发顺序或停车决策的0-1变量。一般而言，列车时刻表问题的数学模型是一类典型的大规模、多目标、强耦合的NP完全问题。算法设计是列车时刻表问题最为重要和困难的部分。对于问题较简单或规模较小的情况，常用方法是对原有复杂问题进行适当简化和(或) 对难处理表达式进行合理修改，然后使用先进的计算架构和商用优化软件求解更新后模型。当然，分支定界和动态规划这两类直接分解算法，是求解列车时刻表问题的重要方法。对于问题复杂和规模庞大的情况，以拉格朗日和列生成为代表的对偶分解算法，则是求解列车时刻表问题的最佳选择。未来，探讨列车时刻表与各种现实需要(如设施维修)，以及时变票价和客票分配等因素之间的深度融合，是一个有价值的研究方向；其次，研究网络环境下列车时刻表问题，将是一个非常有意义的研究选题；最后，应进一步设计集成了问题特点与现代优化技术的各类求解算法，开发能够完全应用于实际运营的商用软件。

关键词: 铁路运输, 列车时刻表, 选题, 构模, 算法

CLC Number:

NIU Hui-min. Literature Review on Rail Train Timetabling[J]. Journal of Transportation Systems Engineering and Information Technology, 2021, 21(5): 114-124.

牛惠民. 轨道列车时刻表问题研究综述[J]. 交通运输系统工程与信息, 2021, 21(5): 114-124.

Add to citation manager EndNote|Ris|BibTeX

URL: http://www.tseit.org.cn/EN/abstract/abstract30313.shtml

http://www.tseit.org.cn/EN/Y2021/V21/I5/114

References

[1] 杨浩. 铁路运输组织学(第四版)[M]. 北京: 中国铁道出版社，2017. [YANG H. Railway transport organization (The Fourth Edition) [M]. Beijing: China Railway Publishing House, 2017.]

[2] 毛保华. 城市轨道交通系统运营管理(第二版)[M]. 北京: 人民交通出版社, 2017. [MAO B H. Operations and management for urban rail transit (The Second Edition) [M]. Beijing: China Communications Press, 2017.]

[3] 胡思继. 列车运行图编制理论与方法[M]. 北京: 中国铁道出版社, 2013. [HU S J. Theory and method of train scheduling design[M]. Beijing: China Railway Publishing House, 2013.]

[4] 彭其渊, 杨明伦, 聂勋煌. 单线区段实用货物列车运行图的优化模型及算法[J]. 铁道学报, 1995 (3): 15-20. [PENG Q Y, YANG M L, NIE X H. Optimization model and its algorithm for making wagon diagram on singletrack lines[J]. Journal of the China Railway Society, 1995 (3): 15-20.]

[5] 周磊山, 胡思继, 马建军, 等. 计算机编制网状线路列车运行图方法研究[J]. 铁道学报, 1998(5): 15- 21. [ZHOU L S, HU S J, MA J J, et al. Network hierarchy parallel algorithm of automatic train scheduling[J]. Journal of the China Railway Society, 1998(5): 15-21.]

[6] 倪少权, 吕红霞, 杨明伦. 全路列车运行图编制系统设计的研究[J]. 西南交通大学学报, 2003(3): 332-335. [NI S Q, LV H X, YANG M L. Research on design of train diagram-making system of railways in China[J]. Journal of Southwest Jiaotong University, 2003(3): 332- 335.]

[7] 毛保华, 王保山, 徐彬, 等. 我国铁路列车运行计划集成编制方法研究[J]. 交通运输系统工程与信息, 2009, 9(2): 27- 37. [MAO B H, WANG B S, XU B, et al. On integrated train operational scheme drawing-up platform of China[J]. Journal of Transportation Systems Engineering and Information Technology, 2009, 9(2): 27- 37.]

[8] CAPRARA A, TOTH F P. Modeling and solving the train timetabling problem[J]. Operations Research, 2002, 50 (5): 851-861.

[9] BRANNLUND U, LINDBERG P O, NOU A, et al. Railway timetabling using lagrangian relaxation[J]. Transportation Science, 1998, 32(4): 358-369.

[10] TIAN X, NIU H. Optimization of demand- oriented train timetables under overtaking operations: A surrogate-dualvariable column generation for eliminating indivisibility [J]. Transportation Research Part B, 2020, 142: 143-173.

[11] GOOSSENS J, VAN HOESEL S P, KROON L. A branchand-cut approach for solving railway line-planning problems[J]. Transportation Science, 2004, 38(3): 379- 393.

[12] CAPRARA A, MONACI M, TOTH P. A Lagrangian heuristic algorithm for a real-world train timetabling problem[J]. Discrete Applied Mathematics, 2006, 154(5): 738-753.

[13] BURDETT R L, KOZAN E. Techniques for inserting additional trains into existing timetables[J]. Transportation Research Part B, 2009, 43(8/9): 821-836.

[14] CACCHIANI V, CAPRARA A, TOTH P. Scheduling extra freight trains on railway networks[J]. Transportation Research Part B, 2010, 44(2): 215-231.

[15] JIANG F, CACCHIANI V, TOTH P. Train timetabling by skip-stop planning in highly congested lines[J]. Transportation Research Part B, 2017, 104: 149-174.

[16] CORMAN F, DARIANO A, PACCIARELLI D, et al. Evaluation of green wave policy in real-time railway traffic management[J]. Transportation Research Part C, 2009, 17(6): 607-616.

[17] LUSBY R, LARSEN J, EHRGOTT M, et al. A setpacking inspired method for real-time junction train routing[J]. Computers & Operations Research, 2013, 40: 713-724.

[18] MENG L, ZHOU X. Robust single-track train dispatching model under a dynamic and stochastic environment: A scenario based rolling horizon solution approach[J]. Transportation Research Part B, 2011, 45: 1080-1102.

[19] LAMORGESE L, MANNINO C. An exact decomposition approach for the real-time train dispatching problem[J]. Operations Research, 2015, 63(1): 48-64.

[20] YANG L, QI J, LI S, et al. Collaborative optimization for train scheduling and train stop planning on high-speed railways[J]. Omega, 2016, 64: 57-76.

[21] ALTAZIN E, DAUZEREPERES S, RAMOND F, et al. Rescheduling through stop-skipping in dense railway systems[J]. Transportation Research Part C, 2017, 79: 73-84.

[22] SHANG P, LI R, LIU Z, et al. Equity-oriented skipstopping schedule optimization in an oversaturated urban rail transit network[J]. Transportation Research Part C, 2018, 89: 321-343.

[23] KROON L, PEETERS L, WAGENAAR J, et al. Flexible connections in PESP models for cyclic passenger railway timetabling[J]. Transportation Science, 2014, 48(1): 136- 154.

[24] FONSECA J F, DER HURK E V, ROBERTI R, et al. A matheuristic for transfer synchronization throughintegrated timetabling and vehicle scheduling[J]. Transportation Research Part B, 2018, 109: 128-149.

[25] VEELENTURF L P, KIDD M P, CACCHIANI V, et al. A railway timetable rescheduling approach for handling large-scale disruptions[J]. Transportation Science, 2016, 50(3): 841-862.

[26] NIU H, ZHOU X. Optimizing urban rail timetable under time-dependent demand and oversaturated conditions[J]. Transportation Research Part C, 2013, 36: 212-230.

[27] BARRENA E, CANCA D, COELHO L C, et al. Singleline rail rapid transit timetabling under dynamic passenger demand[J]. Transportation Research Part B, 2014, 70: 134-150.

[28] HASSANNAYEBI E, ZEGORDI S H, YAGHINI M. Train timetabling for an urban rail transit line using a Lagrangian relaxation approach[J]. Applied Mathematical Modelling, 2016, 40(23): 9892-9913.

[29] SHI J, YANG L, YANG J, et al. Service- oriented train timetabling with collaborative passenger flow control on an oversaturated metro line: An integer linear optimization approach[J]. Transportation Research Part B, 2018, 110: 26-59.

[30] LIU L, DESSOUKY M. Stochastic passenger train timetabling using a branch and bound approach[J]. Computers & Industrial Engineering, 2019, 127: 1223- 1240.

[31] SHAFIA M A, AGHAEE M P, SADJADI S J, et al. Robust train timetabling problem: Mathematical model and branch and bound algorithm[J]. IEEE Transactions on Intelligent Transportation Systems, 2012, 13(1): 307- 317.

[32] MENG L, ZHOU X. Simultaneous train rerouting and rescheduling on an N-track network: A model reformulation with network-based cumulative flow variables[J]. Transportation Research Part B, 2014, 67: 208-234.

[33] SHI T, ZHOU X. A mixed integer programming model for optimizing multi-level operations process in railroad yards[J]. Transportation Research Part B, 2015, 80: 19- 39.

[34] CACCHIANI V, CAPRARA A, TOTH P. A column generation approach to train timetabling on a corridor[J]. A Quarterly Journal of Operations Research, 2008, 6(2): 125-142.

[35] FISCHETTI M, MONACI M. Using a general-purpose mixed-integer linear programming solver for the practical solution of real-time train rescheduling[J]. European Journal of Operational Research, 2017, 263(1): 258-264.

[36] GAO R, NIU H. A priority- based ADMM approach for flexible train scheduling problems[J]. Transportation Research Part C, 2021, 123: 102960.

[37] HUANG Y, YANG L, TANG T, et al. Joint train scheduling optimization with service quality and energy efficiency in urban rail transit networks[J]. Energy, 2017, 138: 1124-1147.

[38] YIN J, TANG T, YANG L, et al. Energy- efficient metro train rescheduling with uncertain time-variant passenger demands: An approximate dynamic programming approach[J]. Transportation Research Part B, 2016, 91: 178-210.

[39] YIN J, YANG L, TANG T, et al. Dynamic passenger demand oriented metro train scheduling with energyefficiency and waiting time minimization: Mixed-integer linear programming approaches[J]. Transportation Research Part B, 2017, 97: 182-213.

[40] SPARING D, GOVERDE R M. A cycle time optimization model for generating stable periodic railway timetables [J]. Transportation Research Part B, 2017, 98: 198-223.

[41] NACHTIGALL K, VOGET S. Minimizing waiting times in integrated fixed interval timetables by upgrading railway tracks[J]. European Journal of Operational Research, 1997, 103(3): 610-627.

[42] ROBENEK T, AZADEH S S, MAKNOON Y, et al. Hybrid cyclicity: Combining the benefits of cyclic and non-cyclic timetables[J]. Transportation Research Part C, 2017, 75: 228-253.

[43] NITISIRI K, GEN M, OHWADA H. A parallel multiobjective genetic algorithm with learning based mutation for railway scheduling[J]. Computers & Industrial Engineering, 2019, 130: 381-394.

[44] BARRENA E, CANCA D, COELHO L C, et al. Exact formulations and algorithm for the train timetabling problem with dynamic demand[J]. Computers & Operations Research, 2014, 44: 66-74.

[45] WANG Y, NING B, TANG T, et al. Efficient real- time train scheduling for urban rail transit systems using iterative convex programming[J]. IEEE Transactions on Intelligent Transportation Systems, 2015, 16(6): 3337- 3352.

[46] NIU H, ZHOU X, GAO R. Train scheduling for minimizing passenger waiting time with time- dependent demand and skip-stop patterns: Nonlinear integer programming models with linear constraints[J]. Transportation Research Part B, 2015, 76: 117-135.

[47] ZHOU X, ZHONG M. Train scheduling for high-speed passenger railroad planning applications[J]. European Journal of Operational Research, 2005, 167(3): 752-771.

[48] DARIANO A, PACCIARELLI D, PRANZO M. A branch and bound algorithm for scheduling trains in a railway network[J]. European Journal of Operational Research, 2007, 183(2): 643-657.

[49] MANNINO C, MASCIS A. Optimal real-time traffic control in metro stations[J]. Operations Research, 2009, 57(4): 1026-1039.

[50] NIU H, TIAN X, ZHOU X. Demand-driven train schedule synchronization for high-speed rail lines[J]. IEEE Transactions on Intelligent Transportation Systems, 2015, 16(5): 2642-2652.

[51] CHEN Z, LI X, ZHOU X. Operational design for shuttle systems with modular vehicles under oversaturated traffic: Discrete modeling method[J]. Transportation Research Part B, 2019, 122: 1-19.

[52] FISHER M L. The Lagrangian relaxation method for solving integer programming problems[J]. Management Science, 1981, 27(1): 1-18.

[53] CACCHIANI V, CAPRARA A, FISCHETTI M. A Lagrangian heuristic for robustness, with an application to train timetabling[J]. Transportation Science, 2012, 46 (1): 124-133.

[54] ZHOU X, 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.

[55] YANG L, DI Z, DESSOUKY M, et al. Collaborative optimization of last- train timetables with accessibility: A space-time network design based approach[J]. Transportation Research Part C, 2020, 114: 572-597.

[56] MAHMOUDI M, ZHOU X. Finding optimal solutions for vehicle routing problem with pickup and delivery services with time windows: A dynamic programming approach based on state-space-time network representations[J]. Transportation Research Part B, 2016, 89: 19-42.

[57] LU G, ZHOU X, MAHMOUDI M, et al. Optimizing resource recharging location- routing plans: A resourcespace-time network modeling framework for railway locomotive refueling applications[J]. Computers & Industrial Engineering, 2019, 127: 1241-1258.

[58] BARNHART C, HANE C A, VANCE P H. Using branchand-price-and-cut to solve origin-destination integer multicommodity flow problems[J]. Operations Research, 2000, 48(2): 318-326.

[59] 李得伟, 丁世顺, 张琦, 等. 基于客流需求的城际列车时刻表模型改进研究[J]. 交通运输系统工程与信息, 2017, 17(3): 157-164. [LI D W, DING S S, ZHANG Q, et al. Improved dynamic demand oriented timetabling model for intercity railway[J]. Journal of Transportation Systems Engineering and Information Technology, 2017, 17(3): 157-164.]

[60] 江峰, 倪少权, 吕红霞. 基于拉格朗日松弛的高速铁路列车运行图新增运行线局部调整模型[J]. 交通运输系统工程与信息, 2018, 18(4): 163-170. [JIANG F, NI S Q, LV H X. A high-speed railway new-added train timetable partial adjustment model based on Lagrangian relaxation[J]. Journal of Transportation Systems Engineering and Information Technology, 2018, 18(4): 163-170.]

[61] 廖正文, 苗建瑞, 孟令云, 等. 基于拉格朗日松弛的双线铁路列车运行图优化算法[J]. 铁道学报, 2016, 38 (9): 1-8. [LIAO Z W, MIAO J R, MENG L Y, et al. An optimization algorithm for double-track railway train timetabling based on Lagrangian relaxation [J]. Journal of the China Railway Society, 2016, 38(9): 1-8.]

[62] 许红, 马建军, 龙建成. 客运专线列车运行图编制模型及计算方法的研究[J]. 铁道学报, 2007(2): 1-7. [XU H, MA J J, LONG J C. Research on the model and algorithm of the train working diagram of dedicated passenger line [J]. Journal of the China Railway Society, 2007(2): 1-7.]

[63] 朱宇婷, 郭继孚, 余柳, 等. 考虑拥挤的轨道交通网络时刻表协调优化建模[J]. 交通运输系统工程与信息, 2017, 17(6): 175-181. [ZHU Y T, GUO J F, YU L, et al. Congestion-based timetable synchronization optimization model in urban subway network[J]. Journal of Transportation Systems Engineering and Information Technology, 2017, 17(6):175-181.]