基于模拟退火算法的列车自动调整能力研究

杨 展，张 博，龚 萍

（西南交通大学 信息科学与技术学院，成都 611756）

基于模拟退火算法的列车自动调整能力研究

杨 展，张 博，龚 萍

（西南交通大学 信息科学与技术学院，成都 611756）

列车自动调整（ATR）系统是ATS系统中十分重要的一个环节，对保障行车效率起到了举足轻重的作用。本文首先仔细研究了列车调整多目标多约束的特点，再结合经验性方法对列车调整进行模型建立。然后利用模拟退火算法的收敛于全局最优解的特性对所建模型进行求解，并通过VS2010仿真平台对结论进行验证。

列车自动调整；列车调整模型；模拟退火算法；最优解

城市轨道交通列车由于人为因素或者土建线路因素等干扰条件而产生的偏离运行图计划时刻表运行会导致列车运输能力减少，运输效率下降，总体收益降低，有时甚至会产生严重的影响。通过列车自动调整（ATR，AutomaticTrain Regulation）和人工调整的结合可以很大程度地减少发生运行偏离所引起的损失。传统的人工调整主要应对大面积列车严重偏离时刻表的情况，但会根据操作员经验性知识的不同而产生不同的操作结果，并无统一规范。而列车自动调整通过系统算法与计算机的强大处理能力，在遇到较小范围内（单车晚点，多车晚点等）的运行偏离等情况能得到较好的调整效果。列车自动调整涉及到很多问题的求解优化，是一个多目标多约束的组合优化NP问题，对其采取的解决方法也多种多样。模拟退火方法在处理此类问题中可以避免系统过早收敛陷入局部最优解并且在控制冷却表适度的情况下能以近似概率1收敛于全局最优解。

1 列车调整原理

在运行正常未遇到列车故障或外部干扰的情况下，列车严格依据运行图时刻表运行，但是在实际过程中，难免会因为某些随机发生的事件导致列车偏离计划轨迹行车。故而为了保障列车运行的准点，高效，在发生这些不期望的干扰时能在最短的时间之内恢复按计划图运行，ATR子模块会综合线路参数,列车运行限制以及列车群相互之间的制约关系以发生晚点的时刻向后调整。为了使得调整后的运行图能逼近计划图，需要引入迭代算子将当前时刻的状态与调整后的状态进行加权迭代产生新的状态并用于下一次迭代调整，直到满足系统的需求为止。把这样的计算机演算过程称为预调整，调成完成后会在运行图上生成一条列车运行指导（预测）轨迹线，ATS依据ATR演算的结果给ATO传送停站时间信息与区间运行等级信息从而使得后续列车根据预调整的轨迹线运行。式（1）与图1描述了列车调整过程。

式（1）～（2）中：

G(j)—在j时刻全局的列车晚点状态；

G (0)—列车未发生晚点时的状态；

T—由算法决定的状态转移算子；

Interfere—最初的晚点偏移量。

图1 迭代过程原理

2 调整模型建立

2.1 目标函数

在已知列车发生晚点的情况下，一般有2种调整手段来使列车恢复运行图运行。

（1）停站时间调整：对列车在站内停靠时间（从进站列车速度变为0到出站列车速度＞0）进行调整，但是这里会产生一个客流增加与缩小停站时间的矛盾关系，需要给予充分的考虑。

（2）区间运行时间调整：一般地，计划区间运行时间会留有一部分的时间冗余，利用这部分的冗余时间对列车进行调整。

针对这两个环节对目标函数建模是ATR的重中之重。式（3）给出了总目标函数的表达式：

α—权重因子列向量；

β—子目标因子列向量。

2.1.1 列车总晚点时间

在列车偏离计划后，期望能得到一个能描述全铁路局晚点程度的量，从而能通过调整这个量对目标函数进行优化，列车总晚点时间描述了一个计划内所有的晚点时间加权总和。

式（4）～（5）是一种通用的总晚点时间计算模型，假设一条线路上有m个车站，有n组列车在线路上运行，式中p'di,j表示的是第i辆列车在车站j的实际到达时间， pdi,j表示的是第i辆列车在车站j的计划到达时间，p'fi,j表示的是第i辆列车在车站j的实际出发时间， pfi,j表示的是第i辆列车在车站j的出发时间。由于发生晚点，列车的到站时间将会向后延误，并且假设客流分部是均匀的，那么在延误的这段时间内涌入站内的客流量会与正常计划中的客流发生叠加。当列车到站后，假设上下车客流密度不变的情况下，这时列车屏蔽门开启到关闭的时间是会随着客流增加而增加，这与总晚点时间最小是相矛盾的，所以需要加上一个惩罚因子F。F的设计原则是将列车实际停站时间与计划停站时间偏差进行加权平方，以期望得到的F能尽量地小。

2.1.2 列车总晚点数目

假如把总晚点时间理解成一个连续的晚点描述模型，那么列车总晚点数目则可看作一离散的晚点描述模型，这两者之间有确切的依赖关系但是又相互独立，不能仅仅以一项指标作为优化目标函数的依据。

2.1.3 列车正点率

D—当次计划中所有列车在分别到达所有站点时刻偏离计划运行图的总次数；

A—当次计划内的总到次数。

列车正点率描述了当次计划中所有列车的实际到达时间与计划到达时间的匹配程度。这项指标中只统计每列车在每站到达的准晚点，并不考虑出发准晚点的情况。

2.2 约束条件确立

列车自动调整亦存在多约束限制。为方便理解，可以以晚点产生的位置为首节点把需要调整的列车群想象为一个多节点的弹簧阻尼系统。其首节点发生瞬时位移后，后面的节点会受到拉力作用而向前节点靠拢，同时又拉动后节点共同作用，并且在跨过平衡位置靠近前节点时，会受到前节点的排斥力而保持“安全距离”，最终系统在自适应调节下趋于平衡态。这与ATR调整过程非常相似，处于平衡态两边的拉力和斥力恰好能描述约束的上下界限制，一般情况下，约束条件为：

3 模拟退火算法求解

3.1 SA原理

模拟退火算法（SA ，Simulated Annealing）成形于20世纪80年代初，是一项随机启发式搜索技术。它不同于传统优化算法的随机搜索策略，不仅使用了随机因素还引入物理退火过程的自然机理，能以一定概率接受劣质解，最终使寻解过程能以近似概率1收敛于全局最优解。SA算法的基本思路是从选取的初始解开始，在借助于控制参数t衰减与等温抽样时产生的一系列马尔可夫链中,利用一个新解产生机制和接受原则, 重复进行“生成新解—计算新老目标函数差—判断是否接纳新解—接纳或放弃新解”，不停地对当前解循环迭代，从而使目标函数趋于最优的执行过程。由于固体退火过程必须缓慢降低温度, 才可以使固体在每一温度下都达到热平衡，最终趋于平衡状态。因此控制参数t的值必须缓慢衰减，才能确保模拟退火算法最终趋于优化问题的整体最优解。

3.2 SA求解步骤

（1）设置初始温度t0与马氏链长度，使用状态产生函数在可行解空间范围内随机产生初始解并计算其目标函数值f(x0)，其中，t0应该足够大以满足

（2）对当前解引入随机干扰，产生当前解的领域解并计算其目标函数值f(x')。

（3）按照Metropolis法则接受新解：如果f(x*)＜f(x) ，则接受解x*为当前状态。否则产生一在[0,1]上服从均匀分布的随机数p,若式式中T为当前温度，k是物理学中的玻耳兹曼常数,则接受新解x*为当前状态，但是对较优解不能直接舍去，而应存储起来以作为一个后备回归解。

（4）当抽样结果趋于稳定或者达到固定的马尔可夫抽样次数，转（5），否则返回（2）。

（5）使用温度衰减函数t*=λt退火冷却系统。

（6）当t达到终止温度或系统满足某个收敛准则，转（7），否则转（2）。

（7）将当前解作为系统最优解输出。SA流程如图2所示。

图2 SA流程图

3.3 ATR设计

3.3.1 解空间

列车在线路运行过程中，当检测到列车运行发生偏离的时刻即根据瞬时偏移量生成解空间,解空间的生成是从晚点时刻开始向后计算结合约束条件确定，但仅靠约束条件还是不严谨的，因为约束条件全是下界约束，并没约束上界，这与优化目标相矛盾，所以要在合情合理的情况下压缩解空间三围，使得寻解过程带有一定的方向性，否则可能会产生等值传播或增强传播的初解，这对于ATR这样一个实时系统而言是不利的，因为这样会加剧全局调整的时间复杂度。

3.3.2 编码方式

列车在运行过程中基本的时间计量单位是秒，所以每个站点的到发时间“HH:MM:SS”可以编码为从当天凌晨零点开始到此刻的秒数S。

将当次计划中所有对应的需要调整的列车依照先后顺序按照式（13）的方式进行编码并排列为列车运行矩阵A：行为车计划，列为站计划。

式（14）～（15）中：

k—需要调整的列车数量；

tji—第j辆车在第i站的到发站时刻。

多车晚点可以看作是i个单车晚点的叠加情况，所以这里只讨论单车晚点的情形。在当次计划中，列车的晚点模式分为接车晚点与发车晚点，但无论描述哪一种情况都需要包括本次计划内以晚点车次为首的后续所有的车次计划，这是因为列车晚点是一个后效过程，晚点列车的前行列车并不会受到后车晚点的影响。这里面还包括2种情形：（1）线路中间晚点，这种情形只针对本次计划的上行或下行列车群进行调整，所有需要调整的列车都在本次计划内；（2）线路终点晚点，这种情况首先会影响到下次计划的正常出发，在折返冗余时间不足够抵消晚点带来的影响时下次发车时间会受到拖延，所以这种情况应该把下次计划也纳入编码范围内，编码长度是第1种情形的2倍。

3.3.3 邻域解产生函数

新解产生是通过原始解与随机干扰的叠加再进行约束检测得到。设ψ方差为1，均值为0的高斯分布矩阵Nk•m，其中每一个元素ξi,j都服从N(0,1)。再对ψ进行定量处理得到ψ*， ψ*中的每个元素表示为定量规则：若则；若则；否则。新解的产生如式（16）所示：

对A*的约束条件进行判定，若满足条件后则将A*作为新解与旧解执行Metropolis判别准则，否则缩小随机干扰比例尺，重新生成新解。

4 实例仿真结果

本论文仿真的实例对象选择的是成都某一运营线路，通过仿真验证算法可行性。该线路建有17个站，全长18.5 km，全线发车间隔为低峰330 s，列车平均速度设为37 km/h。

（1）晚点参数选择

列车号：10403；晚点车站：第4站；晚点时间：240 s。

（2）算法控制参数选择

初始温度：1 000；降温系数：0.95；马氏链长度：50。

图3中，红色线为计划图，蓝色线为实迹预测图，在无运行干扰产生的情况下，蓝线覆盖红线, 发生晚点后计划图与预测图列车运行轨迹发生偏离，触发ATR调动偏离时间，算法收敛时间大约2 s，这对于全铁路局系统的调整来说是可以忽略不计的。通过实验仿真结果，可以看到在从发生晚点的时刻开始通过算法的迭代逐步寻优后经过7个区间站点的调整，每个站点的总晚点时间依次递减并最终变为0，使得晚点列车10403恢复到按计划图运行的目标，说明算法很好地达到了运行轨迹逼近计划轨迹的要求。

5 结束语

SA算法在本文的案例中有着很好的摆脱局部最优的性能，但是若出现系统过于复杂或者状态空间太大的情况，由于模拟退火算法对整个状态空间的情况了解不大，不便于使搜索范围进入到最有希望的搜索区域，使得模拟退火算法的计算效率不高。而当今客流量的增大又对城轨列车运行效率提出了更高的要求，在基于算法的列车调整系统中，模型是复杂且多元的，将来在这方面的研究中，算法也应该规避单一，由多种方法相结合，比如将SA的全局寻优性能结合粒子群算法的快速收敛性能，或是结合遗传算法对模型依赖小的特点等，只有这样才能获得鲁棒性好并且效能高的处理此类问题的方法。

图3 仿真效果图

[1] 张亦南.基于GA的列车自动调整算法在CBTC系统中的应用研究[D]. 北京：北京交通大学， 2008.

[2] 冯玉蓉. 模拟退火算法的研究及其应用[D]. 昆明： 昆明理工大学，2005.

[3] 肖 鹏.城市轨道交通列车自动调整模型算法研究[D].成都： 西南交通大学, 2006.

[4] 张大华. 列车自动调整系统[J]. 地铁与轻轨，1999（3）.

[5] 朱颢东，钟 勇. 一种改进的模拟退火算法[J]. 计算机技术与发展， 2009（6）.

[6] 庞 峰. 模拟退火算法的原理及算法在优化问题上的应用[D]. 长春：吉林大学，2006.

责任编辑 徐侃春

Automatic train regulation capability based on Simulated Annealing Algorithm

YANG Zhan, ZHANG Bo, GONG Ping
( School of Information Science & Technology, Southwest Jiaotong University, Chengdu 611756, China )

Automatic Train Regulation System was a very important part in the ATS System. it played an important role to ensure traffc effciency. The paper carefully considered the multi-objective and multi-constraint characteristics of train automatic regulation, combined with empirical methods to set up the model of train regulation. The Simulated Annealing Algorithm was with the feature of converging to global optimal solution. The model was solved by using this feature. The simulation platform VS2010 was used to validate the conclusions.

ATR; train regulation model; Simulated Annealing Algorithm; optimal solution

U284.48∶TP39

A

1005-8451（2015）09-0006-05

2015-01-09

杨 展，在读硕士研究生；张 博，在读硕士研究生。