中国铁道科学研究院 通信信号研究所 许伟
 
 摘要：针对列车调度指挥系统在开通天津集中台的过程中，出现的列车运行阶段计划调整方案不能满足调度指挥要求的问题，研究天津集中台列车运行阶段计划自动调整方案。天津集中台管辖车站多，车站间环状相连，连接方向多，列车走行径路有300多条。为此，建立以列车优先级别、列车追踪间隔时间、列车区间运行时分、列车起停车附加时分、车站股道接车能力、旅客列车最早发车时间和列车固定停站时间为约束条件，以列车加权晚点总时间最小为目标函数的调整模型。采用动态规化算法进行求解，设计相应的算法步骤，并以天津集中台天津（临时）至下直通场间的车站为例进行验证。计算结果表明：采用上述模型和求解算法进行列车阶段计划调整，能够快速给出列车运行阶段计划的有效调整方案。该方法在天津集中台已经得到了应用。  

 
  关键字： 列车运行；阶段计划；计划调整；列车调度指挥系统

    列车调度指挥系统（Train Dispatching Command System，TDCS）[1]在开通北京铁路局天津集中台的过程中，出现传统列车运行阶段计划调整方案难以满足当前调度指挥的需要。主要原因是,天津集中台管辖方向多，列车径路复杂，集中台在调整时经常会造成多方向的列车冲突,从而造成列车大面积积压，新增列车晚点。本文根据TDCS协同式闭环系统[2]的特点和对以往列车运行计划调整模型[3－5]的研究，针对天津集中台具体情况建立列车运行阶段计划调整模型，采用动态规划算法求解，得到天津集中台有效的列车运行阶段计划调整方案。

     1．模型的建立
 
     1.1 天津集中台概况

    天津集中台管辖3个客运站、10个货运站（场）和7个台间站（两个行调台共同管理的车站，邻台阶段计划传入该车站），车站连接图如图1所示。车站连接方向多，有的甚至超过8个方向，且车站间成环状相连,列车走行径路有300多条。南仓地区下行到达场和下行直通场，客货列车径路交叉严重。天津集中台连接方向多，连接北京方向、京九方向、德州方向、京山方向、北环方向、津蓟支线、港口支线。在这种网状线路情况下，区间和列车径路均严格受到时间和空间的动态限制,移动1条运行线可能会导致一系列的列车运行冲突,紧紧依靠调度员的手工调整不能满足当前的铁路运输要求。本文在对影响列车运行因素分析的基础上，以列车的总晚点时间最小为目标，采用动态规划算法进行优化调整列车运行阶段计划。

                                 
 

                            图1、天津集中台车站连接图

    1.2参数定义

    设天津集中台管辖调度区段内有车站m个，则j＝1,2,…m；运行的列车数为n列, 则i＝1,2,…,n；每个区间线路用具体的编号s表示，s=1,2,…,S；由于两站间的联络线较多，同时,不同参照模式可能导致区间上下行混淆，因此取消区间上下行的概念。

     （1）列车阶段计划运行线为

式中： ， 分别为s线路中列车i在j站的到达时刻、出发时刻。

     （2)列车基本图运行线为
    

     式中： ， 分别为s线路中列车i在j站的图定到达时刻、图定出发时刻。

    （3) 列车阶段计划调整时间域为(ｔ1,ｔ2]。

     1.3约束条件^[6，7]

     列车运行调整受列车优先级别、列车追踪间隔时间、列车区间运行时分、列车起停车附加时分、车站股道接车能力、旅客列车最早发车时间和列车固定停站时间的约束。

    （1）列车优先级别约束条件[8] 为 
           ⁽¹⁾

    式中：Wij为列车的优先级别； m_ij为列车的权重因子，由专家系统^[9]根据列车运行知识库中的列车等级、晚点度、旅程完成度等重要信息结合调度员的指令产生；P_v 为列车i在j站的列车等级(由高到低的顺序)； L_v为列车的晚点度,由接入本台的晚点时分确定比值； C_v为列车的旅行完成度,等于完成的旅程和总旅程的比值。

     (2）列车追踪间隔时间约束条件为

                                  (2)

       式中： _mmT^j_ijs， 分别为两列车在j站s线路上的最小发车时间间隔、最小接车时间间隔。

    (3）列车区间运行时分约束条件为

    (3)

    式中：（ ）为s线路中列车i在j+1站和j站间的计划运行时分, 为列车i在j+1站和j站间s线路上的最小运行时分；（ ）为s线路中列车i在j+1站和j站间的图定运行时分。

    (4)列车起停车附加时分约束条件为

   (4)

    式中： 为s线路中列车i在j+1站的通过时分； ， 分别为s线路中列车i在后方j站的到达、出发时间； 为s线路中列车i在j站的起动附加时分； 为s线路中i车在j+1站与j站之间的最小运行时分； 为s线路中列车i在j+1站的到达时间； 为s线路中列车i在j+1站的停车附加时分。

     (5)车站股道接车能力约束条件为

   (5)

      其中:   

    式中： 为接车站在时刻t股道s方向的占用总数； 为车站j在s线路方向总的股道数目。

   （6）旅客列车最早发车时间约束条件为

                      (6)

式中： , 分别为列车i在j站的出发时间、图定发车时间。

（7）列车固定停站时分约束条件为

           (7)

式中：（ ）为列车i在j站的停车时间； 为列车i在j站的最小作业时间（如列检、司乘交班等）。

（8）区间可用约束条件为

(8)

式中： 为j站t时刻s方向线路是否可用。

   （9）其他约束条件为：在实际生产中，影响列车运行的因素还有施工天窗、施工慢行、设备故障、设备技改、区间装卸、恶劣天气（暴雪、大风、大雾等）等，在自动调整过程中，根据现场设备的实时信息和调度员输入的控制命令，专家系统将这些因素关联于约束条件（1）－（8），例如，第j站s线路区间“天窗” 施工，专家系统直接将其作为约束条件（8）处理。

     1.4目标函数

    列车运行阶段计划调整的最终目标是：实现列车贴近基本图行车,提高列车的正点率。因此，建立满足式（1）－式

   （8）约束条件的、以列车加权晚点总时间最小为目标函数的调整模型。即

    （9）约束条件为：式（1）－式（8）。

    2．模型求解算法原理及步骤

    2.1 算法原理

     列车运行是一个动态过程, 随着时间的变化，空间也在不断变化（车站各方向的接车能力、咽喉、股道的占用情况在不断变化）。因此，对模型采用动态规划算法[10]求解，将列车运行阶段计划调整分为N个优化阶段（k=1,2…N， N ），该N个阶段无后向性[10]，且每个阶段的状态无后效性[10]，即第k+1阶段的状态只取决于第k阶段的状态。调整过程中，每趟列车从第 k个阶段进入到第 k＋1阶段都有不同的决策，依据列车在第k 阶段的状态和最佳阶段效益[10]（从第 k个阶段到第 k＋1阶段的最小晚点时分），选取本阶段的最优决策。根据每个优化阶段产生的最小晚点时间，式（9）可以转化为如下基于动态规划算法的优化模型，即
   
         （10）

     约束条件仍然是式（1）－式（8）。

     式中： 表示第k阶段调整后的总晚点时分； M为第1个阶段调整后得出的晚点时间； 为第k-1阶段列车的调整决策对本阶段列车调整的影响； 为第k个阶段的状态变量， 为第k个阶段的决策。

     2.2 算法步骤 

     Step1：初始化列车阶段运行计划调整的参数以满足约束条件（1）－（8）。确定调整范围的起止时间、调整范围内的列车数目以及每列车的接入状态。根据列车运行的时间和空间动态变化，确定调整的优化阶段数N。

     Step2：根据上一阶段所采取的全部可能决策，确定本阶段所采取的可能决策 ，记录本次列车本阶段调整方案，根据约束条件（1）－（8），记录下 的集合。

     Step3： 根据上一个阶段取得的总晚点时间 和本阶段所选取的最优决策 ，确定本次列车运行的决策 。

     Step4：根据k是否取到最大值，判断调整是否完毕。若调整完毕，则选取最后一个阶段调整中 最小的方案即列车晚点时间最小，根据此方案确定的到、发时间 铺画调整后的列车运行阶段计划；否则， 返回Step2继续调整。

    3．运行调整实例

    3.1基础数据

     以天津集中台天津（临时）至下直通场间的车站为例，采用上述模型和求解算法进行列车阶段计划调整。包括的车站有天津（临时）（含临时客站、天津四号楼）、二号楼（含天津站一楼、天津站四调、天津站三号楼）、天津北、下直通、上到场。台间站为天津（临时）、下直通、天津西、汉沟镇、北仓北、北仓、上到场作为接收邻台计划的接入站。表1为天津集中台列车在不同线路上规定的运行时分。图2为天津集中台接收邻台计划后未调整的运行图部分截图。

                                表1 天津集中台部分线路列车基本运行数据 
                

                 
                           图2 天津集中台部分线路调整前的列车运行阶段计划

     3.2 列车阶段计划调整过程与结果

    在列车运行阶段计划调整过程中，首先接收邻台传来的阶段计划，确定7个入口列车的接入时刻，然后根据各个入口列车的正晚点情况以及本台内始发列车，进行初始化，即 ，调整阶段计划时间范围为12:00至15:00，经过上述Step1－Step4过程得出调整后的每条运行线的 ，画出调整后的列车运行图，即图3为天津集中台阶段计划调整后的运行图部分截图。

    图2和图3中蓝色圆圈中的数字表示列车的晚点时分。两图比较，调整效果显而易见。图3中交出车站的晚点时分即蓝色圆圈大大减少，达到列车运行阶段计划调整的目的，验证了动态规化算法在列车运行阶段计划调整中的可行性。
 
                  
                           图3：天津集中台部分线路调整后的列车运行阶段计划

     4．结束语

     列车运行阶段计划自动调整是列车调度指挥系统减少列车调度员工作强度的关键之一。本文在详细分析影响列车运行限制条件的基础上，提出用动态优化算法来求解列车优化模型，保证了系统的实时性；同时，避免了影响列车运行的离散事件在动态优化过程中众多事件寻找最小事件的计算量，能够快速的给出列车调整方案。此种方法在北京铁路局天津集中台得到了比较满意的应用。 

     参考文献

[1] 铁道科学研究院通信信号研究所．铁路运输调度指挥信息管理系统说明书(汇编)[z]．北京：铁道科学研究院通信信号研究所,2002。

[2] 傅京孙，蔡自兴，徐光右．人工智能及其应用[M]．北京：清华大学出版社,1995。

[3] 张京波，胡思继。列车运行调整模型的研究[J]．铁路计算机应用,2001，10（7）：9-12。
（ZHANG Jingbo, Hu Siji，Research of Mathematical Model for Train Dispatching and Disposal[J]． Railway Computer Application, 2001，10（7）：9—12。in Chinese）

[4] 王宏刚,张 琦,王建英,等。 基于遗传算法的高速铁路行车调整模型[J]。中国铁道科学,2006,27（3）：97—100
(WANG Honggang, ZHANG Qi, WANG Jianying,et al. GA-Based Model of Train Operation Adjustment for High-Speed Railway[J]. China Railway Science, 2006,27（3）：97-100 in Chinese)

[5] 周磊山，秦作睿。列车运行计划与调整的通用算法及其计算机实现，铁道学报，1994，16（3）：56-65
(ZHOU Leishan，QIN Zuorui. General Algorithm and Its Realization on Computer for the Train Operation Adjustment System[J]．Journal of the China Railway Society, 1994，16（3）：56－65 in Chinese)

[6] 彭其渊，杨名伦，倪少权。单线使用货物列车运行图计算机编制系统[J]。西南交通大学学报,1995，30（5）：536-542。
(PENG Qiyuan, YANG Mingquan, NI Shaoquan. A System of Making Train Working Graph on Single-Track Lines with Computer [J]. Journal of the Southwest Jiaotong University,1995,30（5）：536－542。in Chinese）

[7] 北京铁路局．2007年列车运行图技术资料[Z]。北京：北京铁路局，2007．

[8] 中华人民共和国铁道部。中华人民共和国铁道部铁道运输调度规则[Z]。北京：中国铁道出版社,2007．

[9] 刘 隽，张铭娣，张一军。TDCS系统列车运行阶段计划的处理方法。中国铁道科学，2006，27（4）：97-100。
(LIU Jun, ZHANG Mingdi, ZHANG Yijun. Train Execution Plan Processing Algorithms in TDCS [J]. China Railway Science, 2006,27（4）：97-100 in Chinese)

[10] 陈理荣.数学建模导论[M]。北京：北京邮电大学出版社，1998。