基于拉格朗日松弛算法的列车运行图优化
Train Working Diagram Optimization Based on Lagrange Relaxation Algorithm
摘要: 本文主要研究了列车运行图优化问题。在我们所研究的问题当中，根据单线轨道区间的特点，为了使列车保证经济效益同时也要合理地在规定时刻内运行，这就需要我们寻找一个优化的列车运行图。由于在铁路线上运行的列车种类很多导致速度要求也不尽相同，我们主要针对各种速度不同的列车运行图(即非平行运行图)进行展开研究。本文的主要工作是：一是为进一步深入研究该问题，提出了一类基于时–空图构建的列车非平行运行图优化模型；二是针对该模型我们设计相应的启发式拉格朗日松弛算法进行求解；三是通过数值实验对比了标准次梯度法和修正次梯度法的收敛情况。
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.
文章引用：高耀辉, 梁东岳. 基于拉格朗日松弛算法的列车运行图优化[J]. 应用数学进展, 2024, 13(5): 2484-2498. https://doi.org/10.12677/aam.2024.135237

参考文献

[1] Lusby, R.M., Larsen, J., Ehrgott, M., et al. (2011) Railway Track Allocation: Models and Methods. OR Spectrum, 33, 843-883. [Google Scholar] [CrossRef] 
[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. [Google Scholar] [CrossRef] 
[4] Brannlund, U., Lindberg, P.O. and Nou, A. (1998) Railway Timetabling Using Lagrangian Relaxation. Transportation Science, 32, 358-369. [Google Scholar] [CrossRef] 
[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. [Google Scholar] [CrossRef] 
[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. [Google Scholar] [CrossRef] 
[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. [Google Scholar] [CrossRef] 
[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. [Google Scholar] [CrossRef] 
[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. [Google Scholar] [CrossRef] 
[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. [Google Scholar] [CrossRef] 
[18] Caprara, A., Fischetti, M. and Toth, P. (2002) Modeling and Solving the Train Timetabling Problem. Operations Research, 50, 851-861. [Google Scholar] [CrossRef] 
[19] Cacchiani, V. and Toth, P. (2012) Nominal and Robust Train Timetabling Problems. European Journal of Operational Research, 219, 727-737. [Google Scholar] [CrossRef] 
[20] Upadhyay, A. and Bolia, N. (2015) Combined Empty and Loaded Train Scheduling for Dedicated Freight Railway Corridors. Computers & Industrial Engineering, 76, 23-31. [Google Scholar] [CrossRef] 
[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. [Google Scholar] [CrossRef] 
[22] Fisher, M.L. (1981) The Lagrangian Relaxation Method for Solving Integer Programming Problems. Management Science, 27, 1-18. [Google Scholar] [CrossRef] 
[23] Kasimbeyli, R., Ustun, O. and Rubinov, A.M. (2009) The Modified Subgradient Algorithm Based on Feasible Values. Optimization, 58, 535-560. [Google Scholar] [CrossRef] 
[24] Gu, H.Y., et al. (2009) Improved Lagrangian Relaxation Based Optimization Procedure for Scheduling with Storage. IFAC-PapersOnLine, 52, 100-105. [Google Scholar] [CrossRef] 

为你推荐