原文概要

作者及发表信息

这篇学术论文的标题为“A column-generation-based matheuristic for periodic and symmetric train timetabling with integrated passenger routing”，作者为Bernardo Martin-Iradi与Stefan Ropke，他们隶属于丹麦技术大学（Technical University of Denmark）的管理学院（DTU Management）。该论文发表于European Journal of Operational Research，卷号为297（2022），页码为511–531，经同行评审后在2021年5月2日正式在线发布。

研究背景与研究目的

本研究聚焦铁路领域，特别是涉及时刻表排定问题（Train Timetabling Problem, TTP）。该问题对铁路公司的规划与运营具有关键影响，尤其在资源管理（如轨道容量）和乘客服务效率（如减少旅途时间）方面。铁路公司的计划通常划分为三大层级：战略（strategic）、战术（tactical）和操作（operational），而本研究的工作位于战术层，主要涉及定期列车时刻表的排定。

铁路运输规划中的TTP具有高度复杂性，需平衡以下因素： 1. 轨道容量限制：确保两列火车不会在同一区间段同时运行，需考虑最小的列车间隔时间（headway）。 2. 旅客满意度：优化接驳时间（transfer time）和旅行时间。 3. 时间表的稳健性与成本效益：稳健的调度通过减少冲突提高效率，但稳健性和高频服务可能增加运营成本。

已有文献中广泛研究了火车调度问题，通常通过建模、图表示法（graph formulation）或算法求解。然而，现有研究很少将乘客路径（passenger routing）直接集成进时刻表生成过程，而这正是本研究力图弥补的空缺。

本研究的目标有两个： 1. 提出一种新的图表示法（graph formulation），支持直接生成非冲突列车调度方案。 2. 开发一种基于Benders分解（Benders decomposition）的建模方案，实现时刻表生成与乘客路径规划的集成。

研究工作流程与方法细节

研究流程包括五大核心步骤：问题建模、测试实例生成、新算法设计和应用、大规模测试和结果分析，以及拟合乘客路径模型并生成Benders优化切割（Benders’ cuts）。

1. 问题建模

   • 作者采用时空图（time-space graph）对问题进行建模，每个节点表示火车到达或离开的时间点，每条边代表火车行驶或停留的时间。
   • 研究特别强调“对称时刻表（symmetric timetable）”，假设列车在同一路线的两方向运行是对称的，并定义对称时间间隔的偏差容错值（symmetry gap）。
   • 模型需确保轨道容量、列车间隔、最短停站时间、单轨处理规则（single-track management）等各方面约束。

2. 开发基于列生成法（Column Generation）的启发式算法

   • 使用列生成法优化求解问题，将TTP转化为一系列最短路径问题（shortest path problem）。
   • 提出了对称线路图（symmetric line graph）模型以替代传统的单列车图模型，显著减少计算复杂度。

3. 乘客路径集成

   • 构建乘客流模型，计算全体乘客的旅行时间，模型中包括时间片分配、转车路径规划、车站半径需求等。
   • 通过Benders分解，将乘客路径规划问题嵌入时刻表生成问题。生成的Benders切割用于迭代优化时刻表，使得乘客路径规划与列车调度相结合。

4. 算例与性能测试

   • 在丹麦锡兰岛（Zealand）的区域和城际铁路线网中进行试验，包括1小时内规划运行的15条线路（其中3条为高峰期线路）。
   • 对多个参数（例如不同的站点最小间隔时间、对称容差时间设置等）构建实例进行敏感性分析并衡量算法表现。

研究结果与数据支持

1. 基于图模型的求解效率

   • 文中将对称线路图模型与传统的单列车图模型做了对比。结果显示，对称线路图模型大大减少了优化问题的变量数量与限制条件数量，因此性能显著提升。在解LP松弛模型的过程中，列生成迭代次数从传统模型的39降低到7，计算时间从27秒减少到3秒。

2. 乘客旅行时间的优化

   • 新算法能够在多种场景中快速生成高质量的时刻表，兼顾列车运行效率和乘客旅行时间。特定场景下，平均客运时间比基线模型减少了10%以上。

3. 规划稳定性

   • 结果表明，即便在高密集排班（例如高峰期）或多种约束下模型仍能保持稳健性。此特性支持在真实复杂场景中应用。

4. 列生成法和分解方法的结合

   • Benders分解显著增强了解松弛模型的质量，方法结合技术简化了计算流程并扩展了约束集成能力。
   • 模型中新提出的大邻域搜索算法（Large Neighborhood Search）通过随机局部摧毁和修复的方法，进一步提高了解决方案的多样性和性能。

研究结论与意义

本研究提出了一种全新的基于数学规划（mathematical programming）方法，用于解决集成了乘客路径的周期性和对称列车时刻表问题。其科学价值和应用价值体现在以下几个方面： 1. 学术价值 - 研究提出的对称线路图（symmetric line graph）有效解决了TTP中列车对称问题和变量冗余问题。 - Benders切割的整合首次实现乘客路径规划与列车排班的直接联合优化。

1. 应用价值
   • 方法适用于实际铁路网络，特别是高峰期调度优化，为铁路公司节约资源并提升旅客乘车体验提供了理论保障。
   • 方法通用性强，不仅仅适用于丹麦线路，也能够推广到其他线网优化场景。

研究亮点

1. 模型创新：首次提出对称线路图模式，大幅简化列车调度建模。
2. 集成优化：采用列生成和Benders分解相结合的方式，直接整合乘客路径优化。
3. 算例完备性：以真实数据为基础，覆盖了多个场景的敏感性分析，具有良好的普适性。

研究不足与未来工作

研究尚未对动态行车间隔配置或外部的非对称乘客流量场景进行扩展，未来可能考虑进一步扩展方法以支持更为复杂的动态环境。同时，研究提出的对称性约束可能限制实际场景中非对称线路的规划灵活性，这也是作者未来希望突破的方向之一。