研究报告

作者和机构信息

这项研究的主要作者是 Marc Goerigk 和 Anita Schöbel，作者所属机构为德国哥廷根大学 (Georg-August-Universität Göttingen) 的数值与应用数学研究所 (Institut für Numerische und Angewandte Mathematik)。此研究发表在 Computers & Operations Research 期刊上，文章的在线发布日期为 2012 年 9 月 8 日。

研究背景

这项研究属于组合优化 (combinatorial optimization) 和大规模优化 (large-scale optimization) 的范畴，重点是周期事件调度问题（Periodic Event Scheduling Problem，PESP）。PESP 是一个离散优化问题，其目的是为一组事件在给定的周期内分配时间，使其符合某些时间跨度约束。此问题在寻求公共交通系统中的周期性时刻表（如铁路或地铁运营计划）方面表现出强大的建模能力。

PESP 的问题复杂度非常高，即使求得可行解本身也是一个 NP-hard 问题 (非确定性多项式复杂问题)。尽管如此，近年来的研究表明，PESP 模型在实际应用中具有很强的可行性。例如，2005 年柏林地铁首次采用数学优化方法生成了全新的时刻表；2006 年，荷兰最大的铁路公司 Nederlandse Spoorwegen 实施了一个新时刻表，预计每年可产生 4000 万欧元的利润。

目前解决 PESP 最常见的方法是混合整数规划技术（Mixed Integer Programming, MIP），但其计算时间往往较长。为处理大规模实例，Nachtigall 和 Opitz（2008 年）提出了一种基于经典网络单纯形（Network Simplex）方法的启发式算法，称为模网络单纯形方法 (Modulo Network Simplex)。本文的研究目标是改进这一方法，以便更高效地解决大规模铁路时刻表优化问题。

研究流程和方法

在研究过程中，作者主要在以下几个方面进行了详细的工作。

周期事件调度问题 (PESP) 建模

研究首先梳理了 PESP 的基本定义。周期性事件可以形式化表达为给定周期内重复发生的事件集 (E)。这些事件通过活动 (activity) (A) 相连接，每个活动具有一个时间跨度约束 ([l{ij}, u{ij}])，表示两事件间的最短时间和最长时间间隔。此外，PESP 可通过线性目标函数扩展，用以优化活动持续时间的特定加权目标，例如最小化乘客的总行程时间。为此，作者引入了事件-活动网络 (Event-Activity Network, EAN)，使用图论工具对问题进行解释。

模网络单纯形方法介绍

Nachtigall 和 Opitz 提出的模网络单纯形方法是一种 NP-hard 问题的启发式解决方案。该方法首先将解编码为跨度树结构（Spanning Tree Structure），通过单纯形方法的变体操作对解进行逐步改进。

在每次迭代中，算法通过交换基本树中的边与非树边来改进目标值，这需要计算相关的单纯形表 (Simplex Tableau)。然而，由于模参数（Modulo Parameter）的存在，这一过程往往引入了复杂性和耗时性。

改进措施

为了克服模网络单纯形方法的计算瓶颈，作者从两方面进行了优化：

1. 提升运行效率（Inner Loop）
   作者提出了两个策略来减少单纯形表内计算的时间需求：

   • *“First Quality” 模式*：优先从具有最少非零条目的列中搜索潜在的改进操作，并动态更新退出标准。
   • *“Percentage” 模式*：仅搜索前 (p\%) 的稀疏列，显著减少计算量。

2. 提高解的质量（Outer Loop）
   为逃离局部最优解，作者引入了多种搜索启发式：

   • *单点切割（Single Node Cuts）*：以单一事件为中心对松弛量进行调整。
   • *小区间边切割（Small Span Edge Cuts）*：优先选择活动时间跨度较小的边进行切割。
   • *随机节点切割（Random Node Cuts）*：不考虑是否在当前迭代中有效，强制让算法重新进行搜索。
   • *多节点切割（Multinode Cuts）*：通过贪婪算法动态扩大切割的节点集来施加改进。

数据分析与测试

作者使用 Lintim 工具箱中的数据集（PESPLIB 数据集）进行了广泛的实验，这些实例覆盖多个场景，规模从区域性铁路系统到德国长距离铁路网络。每个实例均通过约束满足问题（CSP）求得初始可行解，并进一步优化为周期时刻表的最佳解。

实验结果

实验分为三个部分，分别测试新方法在运行效率和解质量两方面的表现。

1. 运行效率改进
   在 100 秒时间限制下，与传统的陡降法 (Steepest Descent) 相比，“First Quality”和“Percentage” 模式能够显著加快运行速度，迭代次数分别增加了约 273% 和 347%，同时降低每次迭代中计算的复杂度。实验表明，新方法的目标值平均优化速度比商业 MIP 求解器 Gurobi 快近两倍。

2. 解质量改进
   在无时间限制的情况下，使用多节点切割的改进方法比传统单节点切割的解质量高出约 9.1%。其中多节点切割多次帮助算法跳出局部最优解，最终能够找到更好的全局解。

3. 综合表现
   将内外层优化结合后，作者方法在所有实例上均明显优于 Gurobi 方法。平均来看，改进后的模网络单纯形方法在一个小时运行时间内将初始解的质量提高了 31.1%，而 Gurobi 仅能提高约 10%。

研究结论

本研究通过改进传统的模网络单纯形方法，不仅显著提升了算法的运行效率，还在大规模周期时刻表优化实验中展现出更优的解质量。这一改进方法运用了一系列启发式策略和图论工具，成功地弥补了原有算法在局部最优点处易陷入停滞的短板。

研究对周期性时刻表优化问题的科学意义和实际应用价值重大，为未来公共交通系统的智能化排班提供了更高效的数学优化工具。同时，这一方法还具备扩展性，可用于求解多周期版本的 PESP，或进一步结合鲁棒性优化技术以应对交通系统中的不确定因素。

研究亮点

1. 提出了一种结合内外层搜索改进的双优化算法框架。
2. 引入了多种切割策略，尤其是多节点切割，有效避免了局部最优解问题。
3. 在大规模铁路时刻表实例方面显著优于 MIP 求解器 Gurobi，具备强大的实际应用潜力。