学术报告：基于事件柔性的周期性铁路时刻表制定研究

本研究由 Gabrio Caimi, Martin Fuchsberger, Marco Laumanns 和 Kaspar Schüpbach 完成，研究机构为瑞士苏黎世联邦理工学院（ETH Zurich）的比较运筹学研究所（Institute for Operations Research）。本文发表在 Networks 期刊的第57卷第1期，发表于2011年3月24日，由 Wiley Periodicals 出版，DOI为10.1002/net.20379。

学术背景

本文聚焦于铁路调度领域，这是运筹学和交通规划的重要分支。近年来，欧洲铁路运输无论在客运还是货运方面的流量都大幅增长，而城市中心区域新铁轨的建设代价高昂且几乎不可能。因此，优化现有铁路网络的运力成为了一个迫切的任务。随着铁路时刻表密度的增加，列车调度不仅变得更具挑战性，还需要应对延误的传播问题。目前，大多数铁路公司对可以自动生成无冲突时刻表的技术持高度兴趣。这种技术不仅适用于铁路运行的生产阶段，还对规划阶段中多种时刻表方案的评估具有极高价值。

瑞士联邦铁路公司基础设施部门（SBB-I），作为瑞士铁路基础设施的主要运营商，正在投入资源开发高效的时刻表生成方法以及优化其运行管理系统。研究主要集中于周期性铁路时刻表的制定——这是欧洲许多铁路系统（如瑞士、荷兰和德国）普遍采用的调度模式。制定周期性时刻表的核心方法被归纳为“周期性事件调度问题（Periodic Event Scheduling Problem, PESP）”，其建立在强大的图模型与整数线性规划基础之上。

尽管传统的 PESP 模型有助于生成初步的宏观层面时刻表，这些时刻表在微观层面（包括详细的铁路网络节点、精确的安全系统和列车动力学等局部细节）可能会显得过于严格，从而导致下一阶段的时刻表制定不可行。因此，本文提出了“灵活周期事件调度问题（Flexible Periodic Event Scheduling Problem, FPESP）”模型，旨在通过引入时间灵活性扩大解决空间，提升最终微观调度可行性的可能性。

研究方法和详细流程

本文采用双层调度方法，将铁路网络调度划分为宏观和微观两部分。其研究流程可分为以下几大阶段：

1. 宏观层面PESP模型：

传统的 PESP 模型是研究的起点。该模型通过使用事件时间（πi）建模列车的到达与出发时间，核心约束形式为： [ l_{ij} \leq [\pi_j - \pi_i]t \leq u{ij} ]

其中，变量 (\pi_i) 表示事件发生的具体时间，约束用来表示事件之间的最小和最大间隔（例如列车在两个车站之间的行驶时间或站台之间的最短连接时间）。为求解周期性张力和整数周期跳跃值，研究者引入了周期性张力公式（Cycle Periodicity Formulation, CPF），用该方法优化计算效率并简化 PESP 约束。

2. 引入时间灵活性：

为了增强可行性，本文对传统 PESP 模型进行了扩展，引入了事件时间区间的概念。通过离散化出发时间和到达时间区间（([\pi^i, \pi^i + δ_i])），构造了灵活事件调度模型（FPESP）。这需要调整所有相关约束的上下界（例如增加额外变量 (δ_i) 等），从而确保每个可能的时间值仍满足 PESP 的周期性约束。

这种灵活性不仅对密集运行节点（如大型车站区域）特别有益，也在一定程度上提高了延误吸收能力。例如，当某列车实际发车时间未达到最晚可接受时间，剩余时间窗口可以用于微调后续调度。

3. 灵活性目标函数设计：

在 FPESP 模型中，研究者设计并测试了多种目标函数，以在加强灵活性和优化旅客用时之间取得平衡： - 最小化旅客行程时间（MinTravel）：对列车运行时间、停留时间和换乘连接时间加权优化。 - 最大化灵活性（MaxFlex）：优化每一事件时间窗口的灵活性。 - 综合目标（MixFlex）：通过权重 λ 实现灵活性优化和旅客用时优化的折中。 - 限制启发式优化（PostOpt）：利用已生成的基础调度框架进一步优化灵活性，但保持事件排序不变。

4. 数据测试与优化：

研究利用 MATLAB 和商业优化求解器（如 Mosek 和 CPLEX）实现了模型，并对瑞士中部铁路网络（包括 Lucerne, Zug 和 Arth-Goldau 之间区域）以及南部网络（包括 Chiasso, Biasca 和 Locarno）的2007年时刻表进行了验证。算例共涉及48列列车，采用1小时的周期（T=60分钟）并设置2分钟的最小追踪时间间隔。

研究主要结果

1. 性能对比： 在测试数据中，引入灵活性后的 FPESP 模型相比原始 PESP 模型显著提高了解决方案的可行性。例如，在密集车站区域，允许出发与到达之间的灵活时间间隔有助于缓解时刻表不可行性问题。此外，小幅增加计算时间，但显著扩大了解决方案搜索空间。

2. 高效解优化： 研究结果表明，综合目标函数 MixFlex 成为计算性能和优化结果之间的良好折衷，它能够生成更均衡的解。此外，PostOpt 也以极快的速度生成了接近 Pareto 前沿的解。

3. 双目标权衡： 通过绘制有效边界（Efficient Frontier），研究发现旅客用时和总灵活性之间通常呈现线性权衡关系。进一步分析指出，在实际案例中，较小的灵活性增量可能导致群体事件时间调整幅度的放大。

研究结论与意义

本文通过引入事件时间灵活性（Flexible Event Slots）及进一步提出的“Flexbox 模型”，拓展了传统 PESP 在铁路调度领域的适用性与实用性。这些模型不仅能生成为后续微观调度友好的宏观时刻表，还为解决冲突问题提供了更多可能性，进而提升铁路网络的运行可靠性和服务水平。尤其是在瑞士联邦铁路网络的测试中，作者展示了 FPESP 和 Flexbox 的实际应用潜力。

此外，这种新型模型还能有效吸收运行过程中的延迟，从而提高铁路网络的鲁棒性。研究所提出的双目标优化分析为灵活性和客户服务间的平衡提供了实用工具。

研究亮点与创新

1. 灵活事件调度模型（FPESP）的提出：相比传统 PESP 模型，通过灵活时间窗口的引入扩大了求解空间。
2. Flexbox 模型的进一步推广：这一模型利用自然依赖关系（如同一车站的抵达与出发时间）获取额外的调度弹性。
3. 对大规模问题的实际适用性：本文在中型规模的瑞士铁路场景中验证了 FPESP 和 Flexbox 的性能，证明其在实际铁路网络中具有良好效用。
4. 优化方法的多样性：使用多种目标函数和优化策略（如 MixFlex 和 PostOpt）解决理论与实践中的难题。

未来工作展望

未来研究将进一步验证 FPESP 和 Flexbox 在更大规模铁路场景（如覆盖整个瑞士铁路网络）中的适用性。同时，研究未涉及的微观层调度算法应进一步发展，例如针对具有时间灵活性的时刻表设计高效调度引擎。此外，可进一步研究灵活性与铁路生产力提升之间的定量关系，并结合实时优化技术以完善铁路调度框架。