基于ADMM方法的新增列车条件下灵活的列车时刻表优化算法研究

Study on Additional Train Timetable Algorithm in Flexible Manner Based on ADMM Approach

以高速铁路走廊为背景,旨在研究新增列车条件下的列车时刻表优化问题。为了获得更加实际和更加灵活的列车时刻表,提出基于小时时段的灵活列车出发时间窗、不固定列车停站方案、停站时间、列车发车顺序、越行时空位置的灵活架构。通过构建时空网络,将列车时刻表问题中的列车安全间隔约束和越行约束表示为列车占用弧段的不相容关系,将灵活构架下的列车时刻表问题刻画为网络多商品流模型。分别利用标准的拉格朗日松弛方法和交替方向乘子法(ADMM)将原问题分解为一系列容易求解的单列车在时空网络中的最短路径问题。最后,以武广高速铁路线路为例,比较两种算法的计算性能。

This paper focuseds on optimizing the train timetables under the condition of additional trains in the case of on the high-speed rail corridor.In order to obtain a more practical and flexible train timetable,a flexible framework was developed which sets flexible departure time window based on hour-period and loosens the train stop pattern and dwelling time,departure sequence and overtaking space-time location.By constructing the space-time network,the train headway and overtaking constraints in the train timetable were transformed into the incompatible relationship between different trains to occupy the space-time arcs.Then,the additional train timetabling problem was developed into the multi-commodity flow model.The standard Lagrangian relaxation method and alternating direction method of multipliers(ADMM)were respectively introduced to decompose the original problem into a series of easy-solved single train shortest path problem in the space-time network.Finally,a real-word example based on Wuhan-Guangzhou high-speed rail corridor was conducted to compare the computational efficiency of the two important algorithms.