学术报告：联合优化列车调度和列车路径选择的问题研究

该研究由以下作者完成：Entai Wang、Lixing Yang、Peiheng Li、Chuntian Zhang 和 Ziyou Gao，分别来自北京交通大学轨道交通控制与安全国家重点实验室以及位于美国亚特兰大的Norfolk Southern Corporation。本研究经过严格的科学审稿，于2023年在《Transportation Research Part C》期刊上发表，文章编号为103994。

一、研究背景与目的

铁路运输以其速度快、容量大、安全高和节能等优点，在中长距离运输中占据重要地位。近年来，中国铁路行业快速发展，截至2020年，全国铁路总里程已达146,000公里，其中包括35,000公里的高速铁路和超过100,000公里的普速铁路。这一庞大的铁路网络已成为国家交通运输的骨干。然而，铁路运输涉及多样化的资源优化问题，例如客运、机车调度和乘务组安排等，这使得铁路运营计划极为复杂。

列车调度（train scheduling）和列车路径选择（train routing）是制定铁路运营计划的两大关键问题。目前，这两个问题往往被分开解决，前者确定列车的站点到发时间，后者负责分配列车的具体行车路径。然而，两者的复杂耦合关系在实际操作中可能导致冲突，使得分离式决策的效率受到限制。因此，本研究试图在一个多分辨率（multi-resolution）的时空网络上，以系统优化为目标，联合解决列车调度和路径选择问题。

研究旨在通过同时优化列车的时刻表和行车路径，在保证列车路径无冲突的基础上，生成一个协调一致的铁路运营方案。

二、研究流程与方法

为实现研究目标，本文提出了一个联合优化模型，并设计了一套创新的求解算法。研究流程包括以下几个主要步骤：

1. 多分辨率时空网络的建模

研究提出了多分辨率时空网络（Multi-Resolution Space-Time Network, MRSN），结合了两种不同分辨率的网络：
（1）宏观时空网络（Macro-Resolution Space-Time Network）：具有较大的时间颗粒度（例如分钟级），用于描述车站及主要线路的整体框架。
（2）微观时空网络（Micro-Resolution Space-Time Network）：具有更精细的时间分辨率（例如秒级），用于描绘车站的具体拓扑结构及详尽的轨道分配情况。

通过结合宏观的列车调度过程与微观的路径分配模型，该框架可以捕捉不同分辨率下列车的运动时空动态。

2. 数学模型的构建

研究构建了一个基于整数线性规划（Integer Linear Programming, ILP）的联合优化模型，用于描述列车的时空轨迹。该模型分为多个模块：
- 时间平衡约束（Flow Balance Constraints）：保证列车在其起点与终点之间有连续的时空路径。
- 列车最小间隔约束（Headway Constraints）：确保列车运行的安全间隔，避免轨道冲突。
- 时空耦合约束（Space-Time Coupling Constraints）：连接宏观与微观网络，使两种方案保持一致性。

3. 求解算法设计

研究设计了一种反馈迭代框架（Feedback Iterative Framework），包括以下步骤： 1. 使用拉格朗日松弛算法（Lagrangian Relaxation, LR）生成初始的列车调度方案。 2. 使用动态规划（Dynamic Programming, DP）方法在微观网络上找到对应冲突最小化的路径。 3. 如果发现冲突，采用分支定界（Branch-and-Bound, BB）算法调整方案，并更新宏观和微观网络中的约束集合。 4. 通过迭代过程优化最终解，直至找到满足所有约束条件的协调解。

三、主要研究结果

1. 验证实验

研究在不同规模的案例上测试了模型与算法，包括小型模拟场景和基于INFORMS RAS 2016数据集的实际铁路场景。实验验证了算法在计算复杂性与解的精度之间的平衡能力。

2. 性能分析

通过实验数据，发现以下几点关键表现：
- 与传统方法相比，该算法无需优化求解器（如CPLEX），可便捷地处理实际中的复杂约束问题。
- 使用嵌入动态规划的拉格朗日松弛算法，大幅改进了解的收敛速度与路径选择的细粒度精确度。

3. 管理洞见

通过对关键参数的敏感性分析，研究还提供了若干改进铁路运力的管理建议，例如：
- 提高线路规划的均衡性（如车次均匀性）。
- 灵活利用车站的轨道资源。
- 加强关键车站区域内的运行协调能力。

四、研究意义与价值

本研究展示了一种系统化地联合优化列车调度与路径选择的创新方法，在列车时刻表与冲突路径分配问题上达到了高度协调。其科学价值主要体现在以下几方面： - 提供了一种可扩展的计算框架，可以推广到更大规模或更复杂的铁路网络。 - 支持铁路行业在繁忙线路中部署更高效的运营策略，提升列车运行的安全性和可靠性。
同时，该研究方法具有较高的应用价值，可以直接辅助铁路规划与调度部门优化资源利用效率。

五、本研究的亮点

• 模型的创新性：首次利用多分辨率耦合网络框架，将宏观和微观调度问题融为一体。
• 算法的灵活性：设计的算法不依赖于特定求解器，可适应多种实际运营环境。
• 理论与实践的结合：在实际数据集上的验证实验表明，该方法具备工程落地的潜力。

这项研究为铁路运营优化领域提供了新思路和新工具，是提升铁路网络运行效率的一项重要突破，也为后续相关研究奠定了重要基础。