基于拉格朗日松弛的双线铁路列车运行图优化算法  

An Optimization Algorithm for Double-track Railway Train Timetabling Based on Lagrangian Relaxation

作　　者：廖正文 苗建瑞[1] 孟令云[1] 李海鹰[1] 赵岚[3] 

机构地区：[1]北京交通大学轨道交通控制与安全国家重点实验室,北京100044 [2]北京交通大学交通运输学院,北京100044 [3]西安铁路职业技术学院,陕西西安710014

出　　处：《铁道学报》2016年第9期1-8,共8页Journal of the China Railway Society

基　　金：国家自然科学基金(71571012);轨道交通控制与安全国家重点实验室自主课题(RCS2014ZT25);北京交通大学基本科研业务费(I16JB00080)

摘　　要：针对铁路列车运行图优化模型精确解求解困难的问题,结合累积流变量模型的特点,提出基于累积流变量的列车运行图优化0-1整数规划模型,设计拉格朗日松弛求解算法,将复杂的列车组合优化问题转化为单列车的最短路径问题集合,从而降低求解难度。针对拉格朗日松弛子问题,设计具有状态空间的时空网络,实现车站作业方式的差异化处理。模型与算法以武广高铁为背景进行验证和分析。The research established a cumulative flow variable-based binary programming model for train time-table optimization integrated with the characteristics of cumulative flow variable in order to reduce the difficulty of solving the train timetabling problem. A Lagrangian relaxation algorithm was designed to decrease the difficulty of solving the problem by transforming the complicated schedule problem into a set of time-space shortest path problems of independent trains. In response to the subproblems of Lagrangian relaxation, a time-space network with state space was designed to achieve the differentiated treatment of station operation mode. The model and algorithm were analyzed and verified by a numerical experiment on Wuhan-Guangzhou high speed railway.

关 键 词：列车运行图 累积流变量 整数规划 拉格朗日松弛 

分 类 号：U292.41[交通运输工程—交通运输规划与管理]