|
|
基于拉格朗日松弛算法的列车运行图优化
|
Abstract:
本文主要研究了列车运行图优化问题。在我们所研究的问题当中，根据单线轨道区间的特点，为了使列车保证经济效益同时也要合理地在规定时刻内运行，这就需要我们寻找一个优化的列车运行图。由于在铁路线上运行的列车种类很多导致速度要求也不尽相同，我们主要针对各种速度不同的列车运行图(即非平行运行图)进行展开研究。本文的主要工作是：一是为进一步深入研究该问题，提出了一类基于时–空图构建的列车非平行运行图优化模型；二是针对该模型我们设计相应的启发式拉格朗日松弛算法进行求解；三是通过数值实验对比了标准次梯度法和修正次梯度法的收敛情况。
This paper mainly studies the optimization problem of train working diagram. In the problem we studied, according to the characteristics of the single track segment, in order to ensure the economic benefits of the train while running reasonably within the specified time, we need to find an optimized train working diagram. Because there are many types of trains running on the railway line, which lead to different speed requirements, we mainly study the train working diagrams with different speeds (i.e., non-parallel operation diagrams). The main contributions of this paper are as follows: firstly, in order to further study this problem, a kind of optimization model of non-parallel train operation graph based on time-space graph is proposed; secondly, we design the corresponding heuristic Lagrange relaxation algorithm to solve the model; thirdly, the convergence of the standard sub-gradient method and the modified sub-gradient method is compared by numerical experiments.
| [1] | Lusby, R.M., Larsen, J., Ehrgott, M., et al. (2011) Railway Track Allocation: Models and Methods. OR Spectrum, 33, 843-883. https://doi.org/10.1007/s00291-009-0189-0 |
| [2] | 陈军华. 铁路运输经典问题建模与实现[M]. 北京: 中国铁道出版社有限公司, 2019: 65-89. |
| [3] | Higgins, A., Kozan, E. and Ferreira, L. (1997) Heuristic Techniques for Train Scheduling. Journal of Heuristics, 3, 43-62. https://doi.org/10.1023/A:1009672832658 |
| [4] | Brannlund, U., Lindberg, P.O. and Nou, A. (1998) Railway Timetabling Using Lagrangian Relaxation. Transportation Science, 32, 358-369. https://doi.org/10.1287/trsc.32.4.358 |
| [5] | 周文梁, 史峰, 陈彦, 等. 客运专线网络列车开行方案与运行图综合优化方法[J]. 铁道学报, 2011, 33(2): 1-7. |
| [6] | 刘庆磊, 赵疆昀, 曾小旭, 等. 地铁列车运行图编制系统的设计与实现[J]. 铁路计算机应用, 2017, 26(5): 53-58. |
| [7] | 廖正文, 苗建瑞, 孟令云, 等. 基于拉格朗日松弛的双线铁路列车运行图优化算法[J]. 铁道学报, 2016, 38(9): 1-8. |
| [8] | 高如虎, 牛惠民, 江雨星. 基于多维网络的增开列车条件下高速铁路列车运行图调整[J]. 铁道学报, 2020, 42(5): 1-8. |
| [9] | 孟学雷, 徐杰, 贾利民. 列车运行图稳定性研究综述[J]. 铁道科学与工程学报, 2013, 10(2): 96-102. |
| [10] | Castillo, E., Gallego, I., Urena, J.M., et al. (2011) Timetabling Optimization of a Mixed Doubleand Single-Tracked Railway Network. Applied Mathematical Modelling, 35, 859-878. https://doi.org/10.1016/j.apm.2010.07.041 |
| [11] | Barrena, E., Canca, D., Coelho, L.C., et al. (2014) Single-Line Rail Rapid Transit Timetabling under Dynamic Passenger Demand. Transportation Research Part B: Methodological, 70, 134-150. https://doi.org/10.1016/j.trb.2014.08.013 |
| [12] | Cacchiani, V., Furini, F. and Kidd, M.P. (2016) Approaches to a Real-World Train Timetabling Problem in a Railway Node. Omega, 58, 97-110. https://doi.org/10.1016/j.omega.2015.04.006 |
| [13] | 王凯, 倪少权. 列车运行图计算机编制系统研究与应用综述[J]. 交通运输工程与信息学报, 2016, 14(3): 75-82. |
| [14] | 乐建炜, 宋燕蓉. 铁路列车运行图在线可视化技术探究[J]. 中文科技期刊数据库(全文版)工程技术, 2023(12). |
| [15] | Zhou, X. and Zhong, M. (2007) Single-Track Train Timetabling with Guaranteed Optimality: Branch-and-Bound Algorithms with Enhanced Lower Bounds. Transportation Research Part B: Methodological, 41, 320-341. https://doi.org/10.1016/j.trb.2006.05.003 |
| [16] | Song, M. and Cheng, L. (2022) An Augmented Lagrangian Relaxation Method for the Mean Standard Deviation Based Vehicle Routing Problem. Knowledge-Based Systems, 247, Article ID: 108736. https://doi.org/10.1016/j.knosys.2022.108736 |
| [17] | Hassannayebi, E., Zegordi, S.H. and Yaghini, M. (2016) Train Timetabling for an Urban Rail Transit Line Using a Lagrangian Relaxation Approach. Applied Mathematical Modelling, 40, 9892-9913. https://doi.org/10.1016/j.apm.2016.06.040 |
| [18] | Caprara, A., Fischetti, M. and Toth, P. (2002) Modeling and Solving the Train Timetabling Problem. Operations Research, 50, 851-861. https://doi.org/10.1287/opre.50.5.851.362 |
| [19] | Cacchiani, V. and Toth, P. (2012) Nominal and Robust Train Timetabling Problems. European Journal of Operational Research, 219, 727-737. https://doi.org/10.1016/j.ejor.2011.11.003 |
| [20] | Upadhyay, A. and Bolia, N. (2015) Combined Empty and Loaded Train Scheduling for Dedicated Freight Railway Corridors. Computers & Industrial Engineering, 76, 23-31. https://doi.org/10.1016/j.cie.2014.07.007 |
| [21] | Sing, G., Ernst, A.T., Baxter, M., et al. (2015) Rail Schedule Optimisation in the Hunter Valley Coal Chain. RAIRO-Operations Research-Recherche Opérationnelle, 49, 413-434. https://doi.org/10.1051/ro/2014049 |
| [22] | Fisher, M.L. (1981) The Lagrangian Relaxation Method for Solving Integer Programming Problems. Management Science, 27, 1-18. https://doi.org/10.1287/mnsc.27.1.1 |
| [23] | Kasimbeyli, R., Ustun, O. and Rubinov, A.M. (2009) The Modified Subgradient Algorithm Based on Feasible Values. Optimization, 58, 535-560. https://doi.org/10.1080/02331930902928419 |
| [24] | Gu, H.Y., et al. (2009) Improved Lagrangian Relaxation Based Optimization Procedure for Scheduling with Storage. IFAC-PapersOnLine, 52, 100-105. https://doi.org/10.1016/S0020-7292(09)00113-1 |
