城市地铁运营的鲁棒优化：基于设施选址模型求解列车运行图编制与车辆周转规划问题

《European Journal of Operational Research》：Robust optimization for urban metro operations: Solving train timetabling and rolling stock circulation planning problems via facility location models

　　

**需求不确定下鲁棒列车运行图编制与车辆周转计划研究**

• 针对需求不确定的鲁棒列车运行图编制与车辆周转计划
• 提出了可求解性良好的确定性模型与鲁棒优化模型
• 设计了渐进最优间隙缩减算法以求解模型
• 通过若干数值实验验证了所提方法的有效性

**引言**

城市轨道交通系统中的乘客需求通常受到众多不确定因素的影响，例如天气和突发事件。图1展示了2023年3月6日至3月10日期间西安地铁工作日乘客需求的分布情况。如图所示，五天的中位数需求在1099至1345人次之间波动。3月10日中位数最高（1345人次），表明需求较高，而3月9日中位数最低（1099人次）。在不同日期同一时段间的乘客偏差方面，最大偏差为619人次，出现在3月8日与3月10日之间。以上发现均表明乘客需求存在短期波动。

乘客需求的这些不确定性对地铁运营构成了挑战：当实际乘客需求高于预期时，可能需要增加列车服务；反之，当乘客需求低于预期时，资源可能被低效利用，造成不必要的成本。因此，本研究提出了新的建模与算法方法，以优化列车运行图和车辆周转计划，确保地铁运营的鲁棒性。具体而言，本研究致力于解决以下问题：

（1）如何刻画动态且不确定的乘客需求（第3节）：地铁系统中的乘客需求由出发站、目的站和时间维度定义，由此形成高维的随机建模空间。挑战在于构建一个既能捕获这些变化又能保持计算可处理性的不确定集。传统方法将不确定性表示为离散场景（如Gong等，2021；Pan等，2024；Wang等，2024），通过将复杂性限制在预设情形中来简化问题。然而，这些表示方式通常无法提供直接控制保守程度的机制，其保守性一般通过场景生成或场景选择进行调整。因此，本研究采用具有可调保守参数的多面体不确定集，提供了一个系统化的参数化框架，用于管理运营成本与服务鲁棒性之间的权衡。

（2）如何在需求不确定的情况下建模列车运行图编制与车辆周转计划的优化问题（第4节）：列车运行图和车辆周转计划在离散时间点上定义，而乘客到达是时变的，通常聚合到时间区间中。因此，对齐这些时间尺度并将乘客分配到列车上极具挑战性。现有研究通常引入大量辅助变量以将乘客分配纳入列车运行图决策，从而增加了计算复杂性，使问题难以求解（如Mo等，2021；Zhao等，2021；Zhou等，2022）。为此，本研究基于容量受限设施选址问题（CFLP）开发了建模框架，并构建了两个模型：用于名义设置的确定性模型和用于不确定需求的鲁棒模型。在该框架中，列车发车被视为设施，乘客候车被视为被服务的需求，从而实现了更为高效的建模。

（3）如何求解所提出的模型（第5节）：鲁棒模型引入了多面体不确定集。若枚举多面体不确定集对应的所有潜在场景，求解大规模问题将极具挑战性。基于Zeng和Zhao（2013）提出的列与约束生成（C&CG）方法，本研究开发了渐进最优间隙缩减算法，以获得大规模问题（如全天实验）的最优解。在该算法中，主问题在逐步递减的最优间隙下求解，以在受限不确定集内快速生成下界；同时，子问题通过迭代纳入额外的乘客信息来细化部分不确定集，并提供上界。

基于北京地铁和西安地铁的真实数据，本研究开展了数值实验以评估所提方法的性能（第6节）。首先，针对基于CFLP的建模方法，早高峰时段实验（[6:00-11:30]）在1小时求解时限内的计算结果表明，我们的模型达到了最优间隙为0.2%的近最优解，而基准模型（如Zhou等，2022）的最优间隙为18.9%。其次，针对鲁棒模型及其关联算法，北京地铁亦庄线全天实验的结果表明，我们的渐进最优间隙缩减算法产生了最优间隙为1.1%的高质量解。相比之下，传统Benders分解方法未能产生可行解，而基准C&CG算法的最优间隙为2.3%。在西安地铁6号线更大规模的实验中，也观察到了类似的性能提升。此外，与确定性模型和随机规划模型相比，鲁棒模型在最坏情形下展现出更强的韧性，同时保持运营成本在可控范围内。

**文献综述**

优化列车运行图和车辆周转计划一直是城市轨道交通运营领域的持续研究课题。本节首先回顾了该领域的前沿研究（第2.1节 需求导向的列车运行图优化、第2.2节 列车运行图与车辆周转计划的联合优化），随后总结了相关的建模方法（第2.3节 列车运行图与车辆周转计划的建模方法）和求解算法。

**问题描述**

本研究聚焦于一条双向地铁线路，如图2所示。运营方向集合表示为 $\mathcal{F}=\{-1,1\}$，其中 $-1$ 和 $1$ 分别表示上行和下行方向。车站按顺序从1编号至 $J$，其中车站1和车站 $J$ 分别为起始站和终点站。一列列车服务（车次）是指一列从起始站运行至终点站的实体列车。列车编组集合表示为 $\mathcal{I}=\{1,2,\ldots,I\}$，其中……

**数学建模**

在第4.1节中，我们首先介绍确定性模型，该模型作为基础与基准。在第4.2节中，将该模型扩展为需求不确定条件下的鲁棒优化模型。

**求解方法**

确定性模型（DM）的改写形式可直接由商业求解器（如CPLEX）求解。而鲁棒优化模型（RO）中的多面体不确定集 $\Theta$ 通常规模很大，枚举所有可能的乘客需求场景非常困难且耗时。列与约束生成（C&CG）算法是处理此类问题的常用方法（Zeng & Zhao, 2013），它将原始模型分解为主问题（MP）和子问题（SP）。主问题是原始问题的可处理松弛，提供……

**数值实验**

本研究基于北京地铁和西安地铁的真实数据，开展了两组数值实验以评估所提方法的性能。模型与算法使用VB.NET编程语言开发，采用CPLEX 22.1.0求解器。所有实验均在配备Intel Core i5-10500 CPU和16GB内存的Windows 10计算机上完成。

**结论与展望**

精心设计的运营方案对于城市轨道交通系统可靠地安排列车和服务乘客至关重要。本研究提出了两个数学模型，以最小化运营成本与乘客候车时间。第一个模型是基于标准CFLP的确定性模型，它优化了起始站的列车发车时间以及多编组列车的接驳关系。该模型包含的变量和约束较少……

**CRediT作者贡献声明**

周厚生：撰写—审阅与编辑，撰写—初稿，软件，调查研究，概念构思。

钱建国：撰写—审阅与编辑，撰写—初稿，方法论，经费获取，概念构思。

杨立兴：撰写—审阅与编辑，撰写—初稿，指导监督，经费获取，概念构思。

王洪阳：撰写—审阅与编辑，软件。

严然：撰写—审阅与编辑，指导监督。

**利益冲突声明**

作者声明不存在任何可能影响本文报告工作的已知竞争性财务利益或个人关系。

**致谢**

本研究得到国家自然科学基金（项目号：72288101、72371015、72431002）、北京市自然科学基金（项目号：9252012）以及教育部基础学科与交叉学科突破计划（项目号：JYB2025XDXM211）的资助。

周厚生 | 钱建国 | 杨立兴 | 王洪阳 | 严然