基于强化学习的高铁列车运行图编制模型优化方法研究

Optimization Method of Train Working Diagram Compilation Model of High Speed Railways Based on Reinforcement Learning

摘要

针对高铁列车运行图中可能存在的停站时间超出范围、运行时间超出范围、超车和间隔时间不足这4类冲突，基于强化学习理论，实现一个用于调解列车运行图冲突的智能体。通过建立列车运行图编制环境，研究设计用于调解不同冲突的算子集，利用近端策略优化算法在搭建好的环境中训练智能体。为提升算法性能，采用启发式贪心算法采集样本对网络进行监督学习作为前期预训练，利用熵增加算法的探索力度和多策略决策让最终的调解方案更加有效，并使用模型预热让算法网络在每个测试环境中进行参数微调以适应新环境。结果表明，在相同初始环境下，该方法消解所有冲突所需步骤显著少于启发式贪心算法，且100%消解所有冲突的概率远大于启发式贪心算法，该方法为列车运行图编制模型提供了新的参考。

Abstract

To address four types of conflicts that may exist in the train working diagram of high speed railways, such as stop timeout, long-time running, overtaking, and insufficient interval time, this paper implemented an agent to resolve train working diagram conflicts based on reinforcement learning theory. By establishing a train working diagram compilation environment, the research designed an operator set for resolving different conflicts and trained the agent in the constructed environment by using the proximal policy optimization (PPO) algorithm. To enhance algorithm performance, a heuristic greedy algorithm was used to collect samples for supervised learning of networks as initial pre-training. The entropy-increase algorithm was employed to intensify exploration, and multi-policy decision making was utilized to make the final resolution more effective. Model pre-warming was performed to fine-tune the algorithm network parameters in each test environment to adapt to new conditions. The results show that under the same initial conditions, the number of steps required by the proposed method to resolve all conflicts is significantly less than that of steps required by the heuristic greedy algorithm, and the probability of completely resolving all conflicts by the proposed method is much greater than that by the heuristic greedy algorithm. This method provides a new reference for the train working diagram compilation model.

Graphical abstract

关键词

列车运行图 / 强化学习 / PPO算法 / 冲突调解 / 启发式贪心算法

Key words

Train Working Diagram / Reinforcement Learning / PPO Algorithm / Conflict Resolution / Heuristic Greedy Algorithm

0　引言

列车运行图是铁路运输组织的基础，列车运行图的编制质量直接关乎铁路运输的效率。彭其渊等^[1]利用分层优化策略的协同进化蚁群算法求解列车运行图编制问题；许红等^[2]用遗传算法对列车运行图编制问题进行分层叠加铺划求解；史峰等^[3-4]采用时间循环迭代法消解冲突来求解模型；周文梁等^[5-6]采用最小平移时间法则、平移作业时间等方法来消解冲突优化图面；Kaspi等^[7]采用交叉熵元启发式算法对编图问题进行线性规划；王劲等^[8]以最大化通过能力、最小化总停站时间为优化目标，设计了高速铁路列车运行图与车站作业一体化编制模型；夏铭泽等^[9]基于标杆车的编制结果研究了整个列车运行图的框架，并设计了分阶段迭代求解算法。既有文献对列车运行图编制相关问题采用的主流解决方案主要有2种：一种是直接采用Gurobi或Cplex这样的求解器进行求解；另一种是把编图问题分解为运行线编制、车站到发线运用计划编制等一系列子问题，它们都被证明是NP-hard问题。这些求解方法很容易导致模型优化陷入困境，最终给求解带来困难。

随着人工智能技术的快速发展，强化学习方法开始应用到自动驾驶、推荐系统等各个领域。Šemrov等^[10]最早提出将强化学习方法用来调整列车运行时刻表。代学武等^[11]基于强化学习方法提出了用于突发事件下列车群运行调整的模型。韩忻辰等^[12]基于Q-Learning算法研究列车晚点时的调整方法。王荣笙等^[13]提出了一种基于蒙特卡罗树搜索-强化学习的方法，用于实时调整列车在不同车站的发车次序；庞子帅等^[14]基于近端策略优化(Proximal Policy Optimization，PPO)算法在干扰条件下建立列车时刻表调整模型，以最小化列车晚点时间为目标，让智能体与环境交互贪婪地搜索最优策略。这2种不同的算法设计在实际应用中均带来了性能上的提升，但其强化学习方法的动作设计比较单一。郭一唯等^[15]基于强化学习方法针对城际铁路列车运行图的优化调整问题进行建模和求解，该方法模型验证了在解决小规模问题场景中的可行性。Yang等^[16]针对单线铁路列车调度问题，以最小化总优先权加权停留时间为目标，提出了一种深度强化学习算法DRLA-eTGM，通过使用卷积神经网络(Convolutional Neural Networks，CNN)自动从时空容量网格世界模型(TGM)中提取和利用特征，以增强列车调度决策策略。Li等^[17]构建了一个通用的列车调度学习环境，将每个待调度的列车视为一个智能体，提出了一种多智能体深度强化学习(Multiagent Deep Reinforcement Learning，MDRL)方法以实现在与环境交互的过程中学得最佳的合作策略来解决列车调度问题。既有的基于强化学习理论的模型算法在解决列车调度、运行图编制问题方面的实验结果较为可观，但在运算效率和求解效果方面仍有较大的提升空间。

通过对现实场景中高铁列车运行图进行深度剖析，针对不同复杂冲突场景设计了多种精细化的动作算子，基于强化学习方法实现了一个性能高效、调图迅速的智能体来消解冲突，并将列车运行图的调整粒度精确到了以秒为基本单位，通过采用PPO算法在训练速度和样本效率方面也带来了很大提升；面对复杂环境的求解收敛速度也得到了改善，全局调解的平均运算时间得以缩短。

1　列车运行图编制优化模型建立

1.1　模型描述

列车运行图刻画了列车在不同车站的到达、出发以及停留时间，同时也体现了不同列车之间的时空关系。列车运行图模型可表示为G=(S，T)，其中S表示车站集合；T表示列车群的集合，列车有2种不同类型，分别为标杆车T_f(旅行速度高、停站次数少、服务于大客流量城市间的高速铁路列车^[9])和非标杆车T_n。

在一张列车运行图中，列车有3种事件类型：Depart，Arrive和Pass，分别表示从某站发车，到达某站和通过某站，默认Depart事件和Arrive事件在车站有停站发生。{\delta }_t^k表示列车t在车站S_k^{}是否有停站(即{\delta }_t^{\mathrm{k}}=\mathrm{1}表示有停站)，若列车t在车站S_k^{}有停站，则记Sto{p}_{t,k}^{}为列车t在车站S_k^{}的停站时间，且停站时间大于等于车站S_k^{}的最短停站时间l{b}_k^{}，同时小于等于其最长停站时间u{b}_k^{}，即停站时间Sto{p}_{t,k}^{}须满足关系式可表示为

{\delta }_t^{k}l{b}_k\le {\delta }_t^{k}Sto{p}_{t,k}\le {\delta }_t^{k}u{b}_k⑴

在相邻2个车站(S_k^{},S_{k+\mathrm{1}})之间，若列车t在车站S_k^{}有停站，则起车附加时间记为A_{\mathrm{d}\mathrm{e}\left(k\right)}^{L_t}；若列车t在车站S_{k+\mathrm{1}}^{}有停站，则停车附加时间记为A_{\mathrm{a}\mathrm{r}\mathrm{r}\left(k+\mathrm{1}\right)}^{L_t}。此外，列车t从车站S_k^{}到车站S_{k+\mathrm{1}}^{}的纯运行时间记为A_{\mathrm{r}\mathrm{u}\mathrm{n}\left(k,k+\mathrm{1}\right)}^{L_t}，则列车t从车站S_k^{}到车站S_{k+\mathrm{1}}^{}的运行时间A_{\mathrm{n}\mathrm{o}\mathrm{r}\mathrm{m}\left(k,k+\mathrm{1}\right)}^{L_t}可表示为

A_{\mathrm{n}\mathrm{o}\mathrm{r}\mathrm{m}\left(k,k+\mathrm{1}\right)}^{L_t}={\delta }_t^k{A}_{\mathrm{d}\mathrm{e}\left(k\right)}^{L_t}+A_{\mathrm{r}\mathrm{u}\mathrm{n}\left(k,k+\mathrm{1}\right)}^{L_t}+{\delta }_t^{k+\mathrm{1}}{A}_{\mathrm{a}\mathrm{r}\mathrm{r}\left(k,k+\mathrm{1}\right)}^{L_t}⑵

除标准运行时间外，还有最大慢行时间A_{\mathrm{s}\mathrm{l}\mathrm{o}\mathrm{w}\left(k,k+\mathrm{1}\right)}^{L_t}，记A_{\left(k,k+\mathrm{1}\right)}^t为列车t的实际运行时间，则列车的实际运行时间A_{\mathrm{n}\mathrm{o}\mathrm{r}\mathrm{m}\left(k,k+\mathrm{1}\right)}^{L_t}须满足关系式可表示为

A_{\mathrm{n}\mathrm{o}\mathrm{r}\mathrm{m}\left(k,k+\mathrm{1}\right)}^{L_t}\le A_{\left(k,k+\mathrm{1}\right)}^t\le A_{\mathrm{n}\mathrm{o}\mathrm{r}\mathrm{m}\left(k,k+\mathrm{1}\right)}^{L_t}+A_{\mathrm{s}\mathrm{l}\mathrm{o}\mathrm{w}\left(k,k+\mathrm{1}\right)}^{L_t}⑶

另外，记D_{t,k}^{}为列车t在车站S_k^{}的发车时间；A_{t,k}^{}为列车t到达车站S_k^{}的时间；P_{t,k}^{}为列车t通过车站S_k^{}的时间；将列车运行图的编制时间周期记为T_{\mathrm{c}\mathrm{y}\mathrm{c}\mathrm{l}\mathrm{e}}^{}(24 h为一周期)，为防止计算时出现负的时间差，这里定义运算符\mathrm{\Theta }，则有

x\mathrm{\Theta }y=(x-y+T_{\mathrm{c}\mathrm{y}\mathrm{c}\mathrm{l}\mathrm{e}})\mathrm{m}\mathrm{o}\mathrm{d}{T}_{\mathrm{c}\mathrm{y}\mathrm{c}\mathrm{l}\mathrm{e}}⑷

1.2　目标函数及约束条件

在同一车站S_k^{}的任意两列车(i,j)要满足一系列间隔时间约束，间隔时间约束与列车类型以及在该站的事件类型有关，用L_i表示列车i的类型(标杆车T_f或者非标杆车T_n)，用E_{L_i}表示类型为L_i列车的某个事件类型，包括D_{L_i}(发车)，A_{L_i}(到达)和P_{L_i}(通过)，最后用间隔时间函数\tau :S\times \left(E\times L,E\times L\right)\to T将在车站S_{}^{}上的事件类型对应映射到约束间隔时间。此时列车对(i,j)须满足的间隔时间约束具体如下。

（1）前车后车均为发车时的间隔时间{\tau }_{(D_{L_i},D_{L_j})}^k须满足约束条件为

D_{j,k}\mathrm{\Theta }{D}_{i,k}\ge {\tau }_{(D_{L_i},D_{L_j})}^k⑸

（2）前车发车后车通过时的间隔时间{\tau }_{(D_{L_i},D_{L_j})}^k须满足约束条件为

P_{j,k}\mathrm{\Theta }{D}_{i,k}\ge {\tau }_{(D_{L_i},D_{L_j})}^k⑹

（3）前车通过后车发车时的间隔时间{\tau }_{(P_{L_i},D_{L_j})}^k须满足约束条件为

D_{j,k}\mathrm{\Theta }{P}_{i,k}\ge {\tau }_{(P_{L_i},D_{L_j})}^k⑺

（4）前车后车均为通过时的间隔时间{\tau }_{(P_{L_i},P_{L_j})}^k须满足约束条件为

P_{j,k}\mathrm{\Theta }{P}_{i,k}\ge {\tau }_{(P_{L_i},P_{L_j})}^k⑻

(5)前车后车均为到达时的间隔时间{\tau }_{(A_{L_i},A_{L_j})}^k须满足约束条件为

A_{j,k}\mathrm{\Theta }{A}_{i,k}\ge {\tau }_{(A_{L_i},A_{L_j})}^k⑼

（6）前车到达后车通过时的间隔时间{\tau }_{(A_{L_i},P_{L_j})}^k须满足约束条件为

P_{j,k}\mathrm{\Theta }{A}_{i,k}\ge {\tau }_{(A_{L_i},P_{L_j})}^k⑽

（7）前车通过后车到达时的间隔时间{\tau }_{(P_{L_i},A_{L_j})}^k须满足约束条件为

A_{j,k}\mathrm{\Theta }{P}_{i,k}\ge {\tau }_{(P_{L_i},A_{L_j})}^k⑾

列车t在车站S_k^{}的到达时间A_{t,k}^{}、发车时间D_{t,k}^{}和停站时间Sto{p}_{t,k}^{}存在着换算关系可表示为

Sto{p}_{t,k}^{}=D_{t,k}^{}-A_{t,k}^{}⑿

对于通过Pass事件({\delta }_k^{\mathrm{t}}=\mathrm{0})，可表示成D_{t,k}^{}=A_{t,k}^{}=P_{t,k}^{}，即Sto{p}_{t,k}^{}=\mathrm{0}。同样地，可用发车时间D_{t,k}^{}和到达时间A_{t,k}^{}表示在区间(S_k^{},S_{k+\mathrm{1}})上的实际运行时间A_{(k,k+\mathrm{1})}^t，其可表示为

A_{(k,k+\mathrm{1})}^t=A_{(k,k+\mathrm{1})}^{}-D_{t,k}⒀

另外，在车站(S_k^{},S_{k+\mathrm{1}})之间，任意两列车(i,j)还必须满足在列车运行图面上没有交点，即须满足的约束条件可表示为

(A_{j,k+\mathrm{1}}^{}-A_{i,k+\mathrm{1}}^{})(D_{j,k}^{}-D_{i,k}^{})\ge \mathrm{0}⒁

由于初始得到的列车运行图是松弛的，图面中存在许多冲突，且冲突包含列车内冲突和列车间冲突，列车内冲突可以分为停站时间超出范围、运行时间超出范围；列车间冲突可以分为间隔时间不足和超车。记C_{\mathrm{s}\mathrm{t}\mathrm{o}\mathrm{p}}^{}，C_{\mathrm{r}\mathrm{u}\mathrm{n}}^{}，C_{\mathrm{i}\mathrm{n}\mathrm{t}\mathrm{e}\mathrm{r}\mathrm{v}\mathrm{a}\mathrm{l}}^{}，C_{\mathrm{o}\mathrm{v}\mathrm{e}\mathrm{r}\mathrm{t}\mathrm{a}\mathrm{k}\mathrm{e}}^{}分别表示图面上停站时间冲突个数，运行时间冲突个数，间隔时间冲突个数和超车冲突个数。将最小化列车运行图面中的冲突个数作为衡量目标，目标函数计算公式为

\mathrm{m}\mathrm{i}\mathrm{n}z=C_{\mathrm{s}\mathrm{t}\mathrm{o}\mathrm{p}}^{}+C_{\mathrm{r}\mathrm{u}\mathrm{n}}^{}+C_{\mathrm{i}\mathrm{n}\mathrm{t}\mathrm{e}\mathrm{r}\mathrm{v}\mathrm{a}\mathrm{l}}^{}+C_{\mathrm{o}\mathrm{v}\mathrm{e}\mathrm{r}\mathrm{t}\mathrm{a}\mathrm{k}\mathrm{e}}^{}⒂

2　强化学习模型和算法设计

2.1　算法介绍

目前主流的强化学习算法包括：深度Q网络(Deep-Q Network，DQN)算法^[18]，适用于离散动作问题；深度确定性策略梯度(Deep Deterministic Policy Gradient，DDPG)算法^[19]，适用于连续动作问题；置信区域策略优化(Trust Region Policy Optimization，TRPO)算法^[20]和PPO算法^[21]属于策略梯度算法，性能较好；Soft Actor-Critic (SAC)算法^[22]添加熵正则化来增加探索的次数，防止模型过早收敛到局部最优。在Yang等^[16]使用的DRLA-eTGM的方法中，通过使用CNN从eTGM的状态中提取实用特征来有效选择策略，但需要较长的训练时间；Li等^[17]采用MAA2C算法进行训练，但MAA2C对样本效率要求较高，对超参数的选择也相当敏感，尤其在复杂环境中也需要较长的时间进行训练。由于PPO算法效果稳定，在训练过程中不易产生剧烈震荡，相比于其他强化学习算法的学习效率更高且不需要额外花费过多时间进行超参数调整，故采用PPO算法作为优化算法。PPO算法分为自适应KL惩罚系数PPO算法和裁剪目标函数式PPO算法。裁剪目标函数式的PPO算法直接丢弃了KL散度，以避免策略在优化时兼顾优势函数r_t(\theta )A_{{\pi }_{{\theta }_{old}}}(s_t,a_t)和KL散度，从而影响算法梯度下降的优化方向，这可能会偏离最优策略，因而通过对新旧策略比例r_t(\theta )进行裁剪的方式进行替代，其函数表达式为

L^{\mathrm{c}\mathrm{l}\mathrm{i}\mathrm{p}}(\theta )=E_{\tau |{\pi }_{{\theta }_{old}}}\left[\mathrm{m}\mathrm{i}\mathrm{n}(r_t(\theta )A_{{\pi }_{{\theta }_{old}}}(s_t,a_t),\mathrm{c}\mathrm{l}\mathrm{i}\mathrm{p}(r_t(\theta ),\mathrm{1}-\epsilon ,\mathrm{1}+\epsilon )A_{{\pi }_{{\theta }_{old}}}(s_t,a_t))\right]⒃

式中：\epsilon是一个超参数，通常令\epsilon =\mathrm{0.2}，且r_t(\theta )被定义为

r_t(\theta )=\frac{{\pi }_{\theta }(a_t|s_t)}{{\pi }_{{\theta }_{old}}(a_t|s_t)}⒄

对新旧策略比例r_t(\theta )进行裁剪的好处在于，当新旧策略比例r_t(\theta )超出间隔[\mathrm{1}-\epsilon ,\mathrm{1}+\epsilon ]时，直接用\mathrm{1}-\epsilon或\mathrm{1}+\epsilon替换新旧策略比例r_t(\theta )，相当于不对该样本进行梯度回传，防止由于策略相差太大而导致目标函数突然性巨变。另一方面，原函数是在未裁剪的优势函数和裁剪过的优势函数之间取最小，是未裁剪优势函数的一个下界，当模型往好的方向优化时，裁剪项将不起作用，相当于对L^{\mathrm{c}\mathrm{l}\mathrm{i}\mathrm{p}}(\theta )=E_{\tau |{\pi }_{{\theta }_{old}}}进行优化；但当模型往坏的方向梯度下降时，裁剪项会裁掉这对样本，以防止策略效果大幅下降。裁剪目标函数式PPO算法采用Actor-Critic网络结构进行训练。Actor网络用来预测策略，将公式⒃作为优化的目标函数；Critic网络用来预测状态价值函数，采用的损失函数为预测的状态价值函数值V_{\varphi }(s_t)与样本折扣回报{\stackrel{\wedge }{R}}_t的均方误差，其函数表达式为

Los{s}_{\mathrm{c}\mathrm{r}\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{c}}(\varphi )=E_{\tau |{\pi }_{{\theta }_{old}}}\left[{\displaystyle \sum _{t=\mathrm{0}}^T}(V_{\varphi }(s_t)-{\stackrel{\wedge }{R}}_t{)}^{\mathrm{2}}\right]⒅

Critic网络预测当前状态的平均折扣回报，用于将动作价值函数Q_{\pi }(s_t,a_t)归一化，同时也让模型训练得更稳定。

PPO算法采用On-Policy的训练方式，即PPO算法会用最新的随机策略进行探索以及对动作进行采样，并将采集到的动作和概率值存放到经验重放缓冲区中，等样本收集足够后再利用梯度下降算法进行训练。

2.2　基本动作设计

为便于研究，这里仅用4个车站作为研究对象，其中包括6种基本动作，分别是增加列车、取消列车、增加停站、取消停站、向前平移和向后平移某站指定事件之前或之后的所有事件。增加或取消列车是指在原列车运行图中增加或取消1列列车，且列车的始发站、终到站、发车时间和列车类型等均可自由设定。增加停站是指在列车运行图中对已存在的一列列车增加额外停站，停站时间自由设定；取消停站则是取消一列列车在某站的停站事件，若该站是始发站，则列车的新始发站改为原始发站的下一站，若是终到站，则列车的新终到站改为原终到站的上一站。列车在每个车站有Depart，Arrive和Pass 3种事件类型，且列车的事件之间存在着时间的先后关系，列车的事件编号按时间先后顺序排列。例如向前平移某站指定事件之前的所有事件是指按给定的事件编号和相对于这个事件编号的前向标志将列车某段运行线的所有事件都整体向前平移指定的时间单位。

2.3　冲突算子设计

强化学习的目标是与环境进行互动以取得最大化的期望回报。对强化学习方法中的基本动作进行再加工和封装，得到一系列新的、功能更强大的动作，所有动作被定义成算子，这些算子集即为强化学习方法的动作空间。

2.3.1　停站时间超出范围算子

当列车t在某车站S_k有停站（{\delta }_t^k=\mathrm{1}）但停站时间时，则将该列车的停站时间延长，直至其等于停站时间的最小下界l{b}_k；当列车t在某车站S_k有停站，即（{\delta }_t^k=\mathrm{1}）但停站时间Sto{p}_{t,k}^{}>l{b}_k时，则将该列车的停站时间缩短，直至其等于停站时间的最大上界u{b}_{\mathrm{k}}。停站时间超出范围算子集如图1所示。

2.3.2　运行时间超出范围算子

实际运行时间A_{(k,k+\mathrm{1})}^t违反公式⑶就会造成运行时间超出范围冲突。当列车t从车站S_k^{}到车站S_{k+\mathrm{1}}^{}的实际运行时间时，则将该列车的运行时间延长，直至其等于运行时间的最小下界A_{\mathrm{n}\mathrm{o}\mathrm{r}\mathrm{m}(k,k+\mathrm{1})}^{L_t}；当列车t从车站S_k^{}到车站S_{k+\mathrm{1}}^{}的实际运行时间A_{(k,k+\mathrm{1})}^t>A_{\mathrm{n}\mathrm{o}\mathrm{r}\mathrm{m}(k,k+\mathrm{1})}^{L_t}+A_{\mathrm{s}\mathrm{l}\mathrm{o}\mathrm{w}(k,k+\mathrm{1})}^{L_t}时，则将该列车的运行时间缩短，直至其等于运行时间的最大上界A_{\mathrm{n}\mathrm{o}\mathrm{r}\mathrm{m}(k,k+\mathrm{1})}^{L_t}+A_{\mathrm{s}\mathrm{l}\mathrm{o}\mathrm{w}(k,k+\mathrm{1})}^{L_t}。运行时间超出范围算子集如图2所示。

2.3.3　超车算子

超车是指在车站(S_k^{},S_{k+\mathrm{1}}^{})之间，列车(i,j)的发车顺序(D_{i,k}^{},D_{j,k}^{})与到达顺序(A_{i,k+\mathrm{1}}^{},A_{j,k+\mathrm{1}}^{})发生逆序，即。由于超车冲突关系异常复杂，因此设计了13种超车冲突算子，超车算子集如图3所示。以算子a为例，列车(i,j)在B—C两站间发生冲突，此处采取的策略是前车延长停站时间，推迟列车i在车站B的发车时间，且延迟的停站时间{\delta }_{\mathrm{d}\mathrm{e}\mathrm{l}\mathrm{a}\mathrm{y}}^{}可以计算。算子a、算子b是通过延长前车的停站时间或增加一个新的停站来消解发生在S_k^{}—S_{k+\mathrm{1}}^{}前后两站之间的超车冲突；算子c、算子d通过缩短前车的停站时间或取消原来的停站来消解发生在S_k^{}—S_{k+\mathrm{1}}^{}前后两站之间的超车冲突；算子e、算子f的作用同算子a、算子b一样，只不过算子e、算子f通过缩短后车的停站时间或取消后车的停站来实现，因此必须要求后车有停站；算子g、算子h的作用同算子c、算子d一样，但只对后车进行作业。由于列车慢行的最大时间相对于运行时间而言非常短，算子i通过给后车增加慢行来调解冲突，该算子可以消解距离后站S_{k+\mathrm{1}}^{}比较近的超车冲突，需要注意的是在实际列车运行图中，标杆车一般不允许慢行，若此时后车为标杆车那么该算子无效。算子j—m均属于通过平移来消解冲突，其中算子j、算子k用来消解靠近前站S_k的冲突，算子l、算子m用来消解靠近后站S_{k+\mathrm{1}}^{}的冲突。该系列算子对冲突点的位置没有硬性要求，但为了限制平移的力度，设定最大平移时间距离使得调整前后的列车运行图的差别尽可能缩小。

2.3.4　间隔时间不足算子

在同一车站S_k^{}，任意2列车(i,j)要满足一系列间隔时间约束，即须满足公式⑷至⑽。设计了10种间隔时间不足冲突算子，间隔时间不足算子集如图4所示。间隔时间不足算子和超车算子一样，消解冲突时需要调整的时间为最小调整时间。算子a、算子b用于处理间隔时间不足时前车有停站的情况，算子a通过缩短停站时间消解冲突，而算子b通过直接取消前车停站来消解冲突；算子c、算子d均是将Pass事件转化为Depart事件，算子c是在C站对前车进行操作，算子d是对后车进行操作；算子e通过延长后车停站时间消解“发发”“通发”这类冲突；算子f通过向左延长前车停站时间消解“到到”“到通”这类冲突；算子g通过减少后车停站时间并向右平移C站之前的事件消解“到到”“通到”这类冲突；算子h通过给后车在B—C站增加慢行来消解“到到”“通到”这类冲突；算子i和j则是通过平移拉开距离来消解所有可能出现的间隔时间不足冲突。

2.3.5　复杂冲突算子

考虑到实际列车运行图中遇到的冲突问题，仅靠前面几种动作算子可能依旧会使得运行图优化陷入局部最优，故又另外设计了5种通用复杂冲突算子，这5种复杂策略主要用于解决超车和间隔时间不足冲突，且调整的幅度都比较大，复杂冲突算子集如图5所示。例如算子a是级联减停站策略，在实际操作时只需给定列车名t，需要减少的停站时间T_{cut}和开始车站S_k^{}，该算子就能从给定车站S_k^{}开始向前遍历，遇到有停站的则将其停站时间减到最小下限l{b}_p^{}(p\le k)，直到总减停站时间大于T_{cut}即可。算子b是级联加停站策略；算子c和算子d是级联平移策略；算子e是远距离调整策略。

2.4　强化学习模型设计

每一轮强化学习训练的开始都会得到一个新的、松弛的列车运行图，其中会随机产生多个冲突。由于单列车的冲突较好调解，且超车冲突和间隔时间不足冲突不会引起新的单列车冲突，因此在强化学习方法中先将初始列车运行图中的单列车冲突通过预处理的方法进行消解，则后续需要消解的冲突只剩下超车冲突和间隔时间不足冲突。经过这一步处理，就得到了用于网络训练的强化学习训练环境。

强化学习方法的动作空间采用设计的冲突算子集，网络结构采用Actor-Critic结构，Actor-Critic网络结构图如图6所示。Actor网络和Critic网络的状态输入均为1个全局信息列表和1个局部列车时刻表矩阵。全局信息列表中涵盖的内容有冲突类型、冲突发生的前站和后站、前车和后车的类型、列车之间的发车时间差和到达时间差、前车和后车发生冲突的事件时间、在冲突发生处之前的所有站和之后所有站的冲突数量等信息。局部列车时刻表矩阵包含的信息为发生冲突的2列车，以及在它们之前和之后的n列列车的每个事件的时间表，实验中设定n=6。

在Actor网络中，将全局信息列表和局部列车时刻表矩阵分别经过1个线性网络层和ReLU激活函数层，然后将全局信息列表和展成一维的局部列车时刻表矩阵拼接在一起，最后再经过一层线性网络以及1个softmax激活函数进行预测输出。Actor网络的Linear1参数设为18×32，Linear2参数设为12×32，Linear3参数设为288×41。Critic网络与Actor网络结构相同，相比只是去除了softmax激活函数层，直接预测状态价值函数值。Critic网络的Linear1参数设为18×32，Linear2参数设为12×32，Linear3参数设为288×1。经过Actor网络预测可预测得到每个可采取的算子在这一轮中取得最高回报的概率，Critic网络预测得到当前状态的状态价值函数V_{\pi }^{}(s_t)。

强化学习方法的回报函数是基于在采用算子后减少的冲突数量，通过对减少的冲突数量采取加权的方式求得最终的单步回报，对于发生冲突的前一站和之前所有站的冲突，给予较大权重，而对于发生冲突的后一站及之后所有站的冲突，给予较小的权重。记r为算子的单步回报，则单步回报r可表示为

r={\alpha }_{\mathrm{1}}\times cut(conflic{t}_{upper})+{\alpha }_{\mathrm{2}}\times cut(conflic{t}_{lower})⒆

式中：{\alpha }_{\mathrm{1}}和{\alpha }_{\mathrm{2}}为加权参数，且{\alpha }_{\mathrm{1}}\ge {\alpha }_{\mathrm{2}}。

但在某些情况下，例如在没有停站的车站采用了减少停站时间或者取消停站的算子，此时算子应是无效的。为尽可能避免无效算子的使用，通过对无效算子进行标记，当识别到这类无效算子时就对它们进行惩罚，且惩罚值为一个绝对值较大的负常数。值得注意的是，这个绝对值须大于观测到的所有动作能采用但单步回报为负值的算子的单步回报绝对值，此时，这类无用算子的单步回报就等于惩罚值。最后根据重放缓冲区采样到的轨迹来计算采用折扣因子的累计回报即可表示为

Q_{\pi }(s_t,a_t)=E_{s_{t+\mathrm{1}},a_{t+\mathrm{1}},...}\left[{\displaystyle \sum _{l=\mathrm{0}}^{\infty }}{\gamma }^{l}r(s_{t+\mathrm{1}},a_{t+\mathrm{1}})\right]⒇

式中：\gamma为折扣因子，此处\gamma =\mathrm{0.99}。

为帮助模型进行训练，使用启发式算法采集样本来对模型进行监督学习作为前期预训练，然后在此基础上再进行强化学习的自探索训练。另一方面，为防止模型过早收敛，对采样时的动作概率增加熵来提高模型的探索力度。在测试时，由于每次初始化的新环境初始图面都差别较大，为帮助模型适应新环境，让训练好的模型先在新环境中进行k轮强化学习的自探索训练，对模型的参数进行微调，这里称之为模型预热，接着再将微调好的模型运用到此环境中进行测试。除模型预热外，还设计了多策略决策方法，在实验中设定了8个策略数量，即在扰动为100，200，…，800的环境下训练出适应各自环境下的策略，组合构成混合专家(Mixture of Expert，MoE)。不同决策之间采用并行的方式同时在相同环境中进行测试，将多个不同难度环境中训练得到的不同策略组合到一起，从最终结果中选取评分最高的一个作为此时该环境的调图方案。强化学习模型结构图如图7所示。

3　实验仿真与分析

用于进行实验仿真的数据集是构建列车运行图编制模型数据的4个excel文件，分别是站名列表、编图基本参数表、停站时间约束表和列车运行时刻表。

由于强化学习方法的每一轮训练环境都是一个新的松弛列车运行图，运行图中随机生成器的生成方式主要是通过调用底层基本动作来实现增加列车、取消列车、增加停站、取消停站、随机扰动运行时间和随机平移这6个动作，这些随机动作均由发生的概率来选择决定。为了让松弛运行图朝着列车数量增加、停站数量增加的方向发展，在实现过程中将这些动作的概率比例设置为0.3∶0.1∶0.3∶0.1∶0.1∶0.1。另外，还为随机生成器设置了一个扰动次数，用来表示利用随机动作对运行图进行作业的次数。实验中采用启发式算法作为强化学习方法的基线。启发式算法将单列列车冲突的调解作为模型的预处理，使运行图中只剩下超车冲突和间隔时间不足冲突，然后采用贪心策略，每一步根据当前的冲突模拟执行解决这类冲突的算子集。启发式算法还会模拟执行复杂冲突算子集，每一个算子执行完的得分和强化学习方法的单步回报一致。针对当前冲突，启发式算法执行对应的算子集后会得到一个评分列表，最后贪心地在这个评分列表中选择这一步中得分最高的算子作为实际的作业算子，以此来迭代地完成整个优化调整过程。

强化学习训练结果分析如图8所示，其中每一轮训练的初始环境设置在扰动次数为800次的松弛列车运行图环境中，从图8a中可以看出大约在8 000步之后回报函数趋于收敛。由于设置的测试环境是在随机生成器随机生成的不同复杂难度的初始松弛运行图上，实验中设定每一轮调试的最大步数为512，即每一轮中采用算子的最大次数。将环境难度设定为16个等级，分别对应随机生成器扰动次数从50到800(50，100，…，800)，在每个等级上测试化解100个不同的初始冲突运行图，并记录下化解每一个初始冲突运行图时两种算法所需的步数。启发式算法是将当前所有可采用的算子模拟一遍，然后挑选出在当前状态下效果最好的算子，但这有可能只是当前最优而不是未来最优；而强化学习方法通过训练让模型逐渐熟练调图的过程，从而使得模型能够对全局环境进行综合考虑，从图8b可以看出强化学习方法在效率和性能上要优于启发式算法。

再从强化学习方法和启发式算法陷入困境的概率和成功消解冲突的概率这两方面来比较算法的效果。这里将环境难度设为8个等级，分别对应随机生成器的扰动次数从100到800，统计强化学习方法和启发式算法在每个难度等级陷入困境的次数以及成功消解冲突的次数，并计算出对应概率。强化学习方法和启发式算法对比分析如图9所示，可以看出在不同难度等级下，强化学习方法陷入困境的概率均小于启发式算法，而成功消解完所有冲突的概率均大于启发式算法。

4　结束语

通过对高铁列车运行图编制环境进行模拟，针对现实场景中可能遇到的4类典型冲突问题，分别设计了消解冲突的强化学习智能体动作算子。设计的强化学习模型框架在8种不同的环境难度下进行测试，最终得到的模型求解速度和100%消解所有冲突的概率均超过了传统方法，表明提出的模型方法有利于实现列车运行图编制中的冲突快速消解，从而提高列车运行图编制和调整的效率。该方法当前主要聚焦于冲突消解算法的实现，下一步研究将对其进一步拓展，同步考虑运行图OD通达度、列车平均旅行时间、停站分布均衡性等因素。

参考文献

[1] 彭其渊，朱松年，王 培.网络列车运行图的数学模型及算法研究[J].铁道学报，2001，(1)：1-8.

[2] PENG Qiyuan， ZHU Songnian， WANG Pei. Study on a general optimization model and its solution for railway network train diagram[J].Journal of the China Railway Society，2001，(1)：1-8.

[3] 许　红，马建军，龙建成. 客运专线列车运行图编制模型及计算方法的研究[J]. 铁道学报，2007，29(2)：1-7.

[4] XU Hong， MA Jianjun， LONG Jiancheng. Research on the Model and Algorithm of the Train Working Diagram of Dedicated Passenger Line[J]. Journal of the China Railway Society，2007，29(2)：1-7.

[5] 史　峰，黎新华，秦　进，等. 单线列车运行调整的最早冲突优化方法[J]. 中国铁道科学，2005，26(1)：106-113.

[6] SHI Feng， LI Xinhua， QIN Jin，et al. The Earliest Conflict Optimal Method for Train Operation Adjustment on Single Track Railway[J]. China Railway Science，2005，26(1)：106-113.

[7] 史　峰，黎新华，秦　进，等. 单线列车运行图铺划的时间循环迭代优化方法[J]. 铁道学报，2005，27(1)：1-5.

[8] SHI Feng， LI Xinhua， QIN Jin，et al. A Timing-Cycle Iterative Optimizing Method for Drawing Single-Track Railway Train Diagrams[J]. Journal of the China Railway Society，2005，27(1)：1-5.

[9] 周文梁，史　峰，陈　彦. 基于定序优化的客运专线列车运行图铺划方法[J]. 铁道学报，2010，32(1)：1-7.

[10] ZHOU Wenliang， SHI Feng， CHEN Yan. A Method for Drawing Train Diagram of Dedicated Passenger Line Based on Fixed Order Optimization[J]. Journal of the China Railway Society，2010，32(1)：1-7.

[11] 周文梁，屈林影，史　峰，等. 基于定序优化的高速铁路网络列车运行图优化[J]. 铁道科学与工程学报，2018，15(3)：551-558.

[12] ZHOU Wenliang， QU Linying， SHI Feng，et al. Train Scheduling on High Speed Rail Network Based on Fixed Order Optimization[J]. Journal of Railway Science and Engineering，2018，15(3)：551-558.

[13] KASPI M， RAVIV T. Service-Oriented Line Planning and Timetabling for Passenger Trains[J]. Transportation Science，2013，47(3)：295-311.

[14] 王　劲. 高速铁路列车运行图一体化编制问题的快速精细化研究[D]. 北京：北京交通大学，2020.

[15] 夏铭泽，李　博，张　博，等. 基于均衡性和能力利用的高速铁路标杆车运行图编制方法研究[J]. 铁道科学与工程学报，2024，21(6)：2162-2171.

[16] XIA Mingze， LI Bo， ZHANG Bo，et al. Research on Benchmark Train Working Diagram Based on Equilibrium and Capacity Utilization[J]. Journal of Railway Science and Engineering，2024，21(6)：2162-2171.

[17] ŠEMROV D， MARSETIČ R， ŽURA M，et al. Reinforcement Learning Approach for Train Rescheduling on a Single-Track Railway[J]. Transportation Research Part B：Methodological，2016，86：250-267.

[18] 代学武，程丽娟，崔东亮，等. 基于强化学习的高速列车群运行调整方法[J]. 中国科学(信息科学)，2022，52(5)：890-906.

[19] DAI Xuewu， CHENG Lijuan， CUI Dongliang，et al. Rescheduling of High Speed Trains：A Reinforcement Learning Approach[J]. Scientia Sinica (Informationis)，2022，52(5)：890-906.

[20] 韩忻辰，俞胜平，袁志明，等. 基于Q-learning的高速铁路列车动态调度方法[J]. 控制理论与应用，2021，38(10)：1511-1521.

[21] HAN Xinchen， YU Shengping， YUAN Zhiming，et al. High Speed Railway Dynamic Scheduling Based on Q-Learning Method[J]. Control Theory & Applications，2021，38(10)：1511-1521.

[22] 王荣笙，张　琦，张　涛，等. 基于蒙特卡罗树搜索-强化学习的列车运行智能调整方法[J]. 中国铁道科学，2022，43(5)：146-156.

[23] WANG Rongsheng， ZHANG Qi， ZHANG Tao，et al. Intelligent Adjustment Approach for Train Operation Based on Monte Carlo Tree Search-Reinforcement Learning[J]. China Railway Science，2022，43(5)：146-156.

[24] 庞子帅，王丽雯，彭其渊. 基于强化学习的干扰条件下高速铁路时刻表调整研究[J]. 交通运输系统工程与信息，2023，23(5)：279-289.

[25] PANG Zishuai， WANG Liwen， PENG Qiyuan. High Speed Railway Timetable Rescheduling under Random Interruptions Based on Reinforcement Learning[J]. Journal of Transportation Systems Engineering and Information Technology，2023，23(5)：279-289.

[26] 郭一唯，黄艨靼，李　博，等. 考虑均衡性的城际铁路列车运行图智能调整方法研究[J]. 铁道运输与经济，2020，42(9)：20-25.

[27] GUO Yiwei， HUANG Mengda， LI Bo，et al. A Study on Intelligent Adjustment Method for Intercity Train Working Diagram with Consideration of Evenness[J]. Railway Transport and Economy，2020，42(9)：20-25.

[28] YANG F Y， YANG Y H， NI S Q，et al. Single-Track Railway Scheduling with a Novel Gridworld Model and Scalable Deep Reinforcement Learning[J]. Transportation Research Part C：Emerging Technologies，2023，154：104237.

[29] LI W Q， NI S Q. Train Timetabling with the General Learning Environment and Multi-Agent Deep Reinforcement Learning[J]. Transportation Research Part B：Methodological，2022，157：230-251.

[30] MNIH V， KAVUKCUOGLU K， SILVER D，et al. Human-Level Control through Deep Reinforcement Learning[J]. Nature，2015，518(7540)：529-533.

[31] LILLICRAP T P， HUNT J J， PRITZEL A，et al. Continuous Control with Deep Reinforcement Learning[J]. ArXiv e-Prints，2015：arXiv：

[32] SCHULMAN J， LEVINE S， ABBEEL P，et al. Trust Region Policy Optimization[EB/OL]. (2015-02-19)‍[2024-01-31].

[33] SCHULMAN J， WOLSKI F， DHARIWAL P，et al. Proximal Policy Optimization Algorithms[EB/OL]. (2017-07-20)[2024-01-31].

[34] HAARNOJA T， ZHOU A， ABBEEL P，et al. Soft Actor-Critic：Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor[EB/OL]. (2018-01-04) [2024-01-31].

基金资助

中国国家铁路集团有限公司科技研究开发计划课题(P2022X012)