1. 文章信息
《单线铁路列车重新调度的强化学习方法》是2016年发表在《交通研究B部分》上的一篇文章。
2. 总结
本文研究如何提前规划实际运营，以实现最佳的铁路网络基础设施和车辆利用率。初始列车时刻表考虑了可能出现的轻微干扰，这些干扰可以在列车时刻表中得到补偿。较大的干扰，如事故、车辆故障、延长乘客登机时间以及限速变化，会导致列车延误并需要重新安排列车时刻表。本文提出了一种基于强化学习或 Q 学习的列车调度方法。提出了列车重新调度的 Q 学习原则，其中包括学习代理及其行为、环境及其状态和奖励。所提出的方法首先应用于单车道轨道的三列火车的简单重新调度问题。在斯洛文尼亚的实际铁路网络上进行了广泛的实验，对该方法进行了评估。实证结果表明，Q 学习导致的重新调度解决方案至少与几种不依赖学习代理的基本重新调度方法相当，而且通常更好。 在合理的计算时间内学习解决方案，这是实时应用的关键因素。
3. 简介
铁路系统的可靠性通常通过列车准时性来评估，准时性是指列车实际到达目的地的时间与列车时刻表上规定的预计到达时间之间的差异。准时性是用户选择交通方式时考虑的最重要的特征之一。
在铁路交通中，由于列车加速/减速曲线、行驶模式和速度曲线的变化而导致的短暂延误是可以理解且不可避免的。因此，在时刻表中引入了运行时间补充和缓冲时间。这些补充只能补偿小干扰，例如由于天气条件导致的速度变化，但不能补偿较大的延误。干扰和意外事件，例如事故、车辆故障、基础设施故障、由于乘客登车而导致的长时间停车以及限速变化，会导致铁路交通出现更大的延误，需要更详细的交通管理和时刻表重新安排。动态列车交通管理是确保列车准时运行和最大限度地减少延误后果的必要条件。调度员在控制中心执行的重新安排动作的反应集必须可行且有效。列车重新安排是一个实时过程，调度员只有几分钟的时间来对延误做出反应。因此，他们无法检查所有可行的解决方案，而是通过经验和直觉做出决策以找到最佳解决方案。
本文提出一种基于强化学习（Q-learning）解决列车调度问题的方法，从以往的研究可以发现强化学习在交通工程中得到了有效的应用。
4.强化学习原理
解决列车重新调度问题时需要考虑许多因素：所有列车的位置和速度、轨道段的长度、车站的布局或基础设施的容量。监督学习方法（代理从重新调度问题的良好解决方案的示例中学习）是不可行的，因为许多环境因素对最优解决方案有很大影响。另一方面，强化学习结合了动态规划和监督学习的原理，并且在解决任何一门学科都无法单独解决的问题方面非常成功，使其特别适合解决列车重新调度问题。
图 1 描述了强化学习的一般设置，其中主动学习代理与被动环境解耦。代理通过观察环境的当前状态并决定其动作来主动与环境交互。执行操作后，环境将其状态更改为 st+1，并向代理发送强化反馈 rt+1。
在列车重新跟踪的特殊情况下，代理对应于对列车运行和轨道信号做出决策的调度员，而环境则是包括所有轨道、列车和相应时刻表的铁路系统。环境是被动的，因为所有关于改变其状态的动作的决策都来自代理，即调度员。环境向代理发送的强化信号与当前列车延误成反比。强化学习方法使用强化信号来学习最佳代理策略或决策函数，这有助于代理在给定一组可用动作和当前系统状态的情况下决定最佳动作。
Q-learning强化学习方法将代理决策策略形式化为效用函数Q(st, at)。其值对应于代理在当前观察到的环境状态st下的行为at的预期效用。一个动作的效用是指它改善环境当前状态的潜力，也就是说，它告诉我们该动作在给定状态下有多好。当面对状态t的决策时，代理会选择效用函数Q(st, at) at的最大值的行为。在有许多效用函数（最大值）相同的动作的情况下，代理会随机选择其中一种。下面的公式描述了学习过程，即在每次训练迭代中给定获得的奖励来更新效用函数Q的过程
5.算法设计
我们通过系统地解释特定设计选择背后的原理，介绍了使用 Q 学习进行列车重新调度的方法。考虑了五个基本组成部分：环境、状态、代理、动作和奖励反馈。考虑了铁路网络的微观视角，其中列车延误是干扰的主要来源。
环境与模拟：影响铁路运营的主要因素有三个。第一个要素是铁路基础设施，第二个要素包括列车，第三个要素规定了铁路运营的安全原则。研究的目的是为调度员找到可行的列车时刻表修改方法（在合理的时间范围内），以便检测延误。第一个假设是信号系统确保运输过程的安全控制和交通管制，以防止事故发生。信号系统使用不同的信号颜色或两种颜色和/或闪光灯的组合来区分一个区域的两种状态——占用或未占用，红色表示“停止”（表示该闭塞区段当前被占用），绿色表示“空闲”（表示该闭塞区段空闲）。第二个假设是假设列车是一个点对象，因此它不会一次占用多个闭塞区段，第三个假设是车站，使用与车站（枢纽）容量相对应的多个并行闭塞区段来模拟每个车站（或枢纽）。 第四个假设是时间是离散的，以匹配列车时刻表的时间分辨率。第五个假设是关于安全原则的。除了防死锁情况外，模拟器和 Q 学习算法是在 Microsoft Access 和 Visual Basic for Application 环境中实现的。环境模拟器的这些基本对象可用于使用 Q 学习算法中的环境状态重新安排列车，该算法设置信号以在每个模拟步骤中采取行动。
状态：在列车重新调度问题中，需要考虑三个这样的属性（即相应的参数）：列车的当前位置、当前基础设施（区段）的可用性和时间。
代理和动作集：在探索阶段，代理以高概率采取随机动作，而在开发阶段，代理的行为遵循效用函数 Q 的值。对于基础设施中的每个信号元素，有两种可能的动作：将其设置为红色（“停止”）或绿色（“前进”）。因此，候选动作的数量取决于信号元素的数量 |E|，等于 2^|E|，但其中许多动作在给定时刻并不适用，动作数量通常远小于上限 2^|T|。
奖励函数：列车重新调度的具体奖励函数：rt+1 = −delay。列车总延误时间越长，奖励越小。
6.实验环境
针对斯洛文尼亚铁路基础设施的简单人工示例和复杂示例对所提出的方法进行了实证评估。简单示例旨在说明该方法的实用性，而真实示例旨在评估其在真实环境中的可用性。
图 2 显示了铁路基础设施布局的示例，其中一条轨道包含三个车站 A、B 和 C，其中 B 站距离 A 站 8.8 公里，C 站距离 B 站 5.8 公里。A 站和 B 站之间的轨道线分为三个区块（注意它们之间边界的信号元素），B 站和 C 站之间的轨道线分为两个区块。每个车站可容纳三列火车。
图 3 描述了我们在实验中使用的三列火车的初始时刻表。铁路布局如图 2 所示，三列火车有两种不同的恒定速度：第一列火车（1.70 公里/小时）比其他两列火车（2 和 3,100 公里/小时）慢。
我们使用参数设置 α = 0.8、γ = 0.2，以及 50 个训练集，ε = 0,5 (1+ e (10 * (n−0)).4 * 50) 50)，其中 n 是当前训练集中的集数。图 4 显示了所选的检测函数，它确保了训练早期的高检测概率。为了避免局部最优，我们逐渐降低 ε 的值，在整个实验过程中留出一些探索空间，直到最终值为 0，这对应于对学习策略的纯粹利用。
每次 Q 学习实验都是一个随机过程，在探索阶段，代理将采取随机行动。为了正确评估 Q 学习的性能，我们在每个 Q 学习实验中使用不同的随机生成器种子进行 10 次运行。
图 5 描绘了使用三个不同随机种子值的三个 Q 学习实验的学习曲线。尽管代理在训练过程中测试了不同的火车出发点，从而经历了不同的延误，但它仍然学习了两个随机种子值的最优策略和第三个种子值的近乎最优的策略。
前两次运行获得的总最终延迟值为 13 分钟，第三次运行获得的总最终延迟值为 15 分钟。
我们可以得出结论，所提出的用于列车重新调度的 Q 学习算法是高效且有效的，因为代理学习了最优策略并提出了可行且最优的重新调度计划，如图 6 所示。
复杂的现实世界示例：我们在斯洛文尼亚的一条现实世界铁路轨道上对大量列车重新调度任务评估了 Q 学习的性能，该铁路轨道由 23 个区块、14 个车站和 26 列火车组成。为了评估 Q 学习在不同设置下的性能，我们对 100 种不同的初始延迟场景进行了实验，其中前 50 种场景是 3 列火车晚点的情况，后 50 种场景是 5 列火车晚点的情况。图 10 绘制了 S3_08 延迟场景的两条学习曲线：标有“QL_avg”的实线绘制了从使用不同随机种子值的 10 次学习运行中获得的 10 条学习曲线的平均值，标有“QL_stDev”的虚线对应于标准偏差，标有“FIFO”的平虚线对应于使用 FIFO 策略部署获得的总延迟。两条学习曲线都表明，重新调度策略随着训练运行次数的增加而稳步改进。
图 11 中的箱线图比较了随机游走、FIFO 和 Q-learning 三种方法在 50 S3 和 50 S5 延迟场景下的平均性能。结果表明，Q-learning 方法明显优于随机游走方法；与 FIFO 方法相比，Q-learning 的平均性能提升较小且统计上不显著，而 QL 获得的中位延迟略优于 FIFO 方法。
然而，FIFO 方法容易出现死锁，而 QL 在所有情况下都能避免死锁。表 1 对所得实证结果进行了进一步的比较分析，结果表明 Q 学习方法在超过一半的初始延迟场景中（平均而言）明显优于 FIFO 和随机游走方法。
与Q-learning重运行10次得到的最小总延迟进行比较，发现它总是小于或等于FIFO得到的延迟，只有三次延迟。在死锁鲁棒性方面，Q-learning明显优于FIFO和随机游走。
7. 结论
Q 学习算法是一种无模型方法，其中代理通过来自环境的动作和反馈进行学习。
因此，所提方法的主要优点是算法能够适应不同的铁路布局、列车数量、变化的奖励函数等。
第二个优势是算法中定义的约束的性质，它可以定义现实世界中铁路交通管理和重新调度中存在的任意数量和类型的限制。可以根据需要更改和添加限制以满足新要求，例如立法变化。
第三个优点是奖励函数的定义，它可以轻松更改，并且算法将根据新目标（例如，不同类型列车、不同乘客数量的优先级或延迟成本的变化）找到不同的最佳解决方案。最后一个但仍然非常重要的优点是学习代理不需要任何预定义的背景知识。建议引入与安全相关的背景知识（例如，只有一列火车可以占用阻塞的路段，防止死锁）以加快学习过程，尽管代理可以从环境反馈中了解到这种行为是不可取的。对所提出方法的评估表明，它明显优于不利用环境奖励信号来随时间改进策略的随机游走方法。所提出的方法还优于列车重新调度的标准先进先出方法：虽然总延迟的改善不大，但对死锁的鲁棒性改善显着，这与该方法在现实环境中的适用性非常相关。
最后，本文重点研究在没有初始知识的情况下进行学习，并针对每个扰动从头开始重新训练。或者，可以重复使用针对一个扰动学习的策略，并在学习其他扰动的策略时评估其效用。评估重复使用学习到的策略是否以及在多大程度上可以加快学习过程超出了本文使用的评估框架的范围，未来可以进一步研究。
