城市轨道调度优化：多列编组下的车辆与乘务协同

论文题目：Joint Rolling Stock and Crew Scheduling withMulti-train Composition in Urban Rail Networks

第一作者：Entai Wang 北京交通大学系统科学学院博士生，研究方向聚焦于城市轨道交通与铁路运营优化领域，核心围绕列车调度与径路规划、车辆和乘务调度的联合优化、实时列车运行调整等问题展开，运用网络流等方法探索兼顾服务水平与运营成本的轨道交通运营解决方案。

E-mail：etwang@bjtu.edu.cn。

通讯作者：杨立兴 北京交通大学交通系统科学学院院长，研究涉及交通运输规划与管理系统科学、交通运输、运输组织理论与技术、综合交通运输理论与技术、综合交通系统分析与集成、大数据与智能系统等。

E-mail：lxyang@bjtu.edu.cn。

城市轨道调度优化：多列编组下的车辆与乘务协同

论文摘要

城市轨道网络通过线路规划、列车时刻表制定、车辆运用、车辆编组和乘务排班等环节实现运营。这些环节通常分开规划，导致车辆计划确定后难以灵活调整乘务安排。文章针对这一问题，提出在多线城市轨道网络中同时考虑车辆运用和乘务排班，并引入多列车编组（多车厢拼接） 来适应不同时间段的客流需求。作者构建了基于路径的联合调度模型，决策变量包括滚动库存路线、乘务任务序列及其发车时刻，目标是最小化车辆运营成本和乘务成本。模型考虑车辆列车间安全间隔、路段最小频率、车辆最大通过能力等约束。为求解该问题，论文设计了分枝‑定价‑割（BPC）算法：采用 Benders 分解将模型划分为主问题和定价子问题，并在分枝‑定界树的每个节点使用列生成生成滚动库存和乘务路径；同时结合低界提升和启发式规则等加速技术。在北京地铁实例中，联合调度方案显著提高效率：对照顺序调度，跨线运行和多列编组可减少车辆数量并降低乘务成本。本文的创新在于将多列车编组、跨线运营与乘务排班有机结合，并通过高效算法解决大规模实例。

一、研究背景与问题陈述

1.1 城市轨道运营的复杂性

• 多环节规划：城市轨道运营涉及线路规划、列车时刻表、滚动库存运用、车辆编组及乘务排班等多个层次。
• 顺序决策的局限：传统方法先决定车辆运用，再安排乘务，这种顺序化使得乘务调度缺乏灵活性。
• 多列编组需求：为满足不同线段和时段的客流，运营者常将多台车辆编组成“长列车”以提高运输能力。

1.2 研究问题定义

• 目标：在给定城市轨道网络、多条物理线路、若干车辆和乘务成员的条件下，联合确定滚动库存路径、列车发车时刻和乘务任务序列，最小化总运营成本。

• 约束：

• 车辆路径分配：每台车辆只能选择一条完整的路径。
• 安全间隔：相同线段上两列车之间的发车时间必须满足最小安全间隔。
• 路段频率：每个物理区段在不同时间窗内必须满足最小/最大班次要求。
• 乘务需求：乘务员需按任务顺序完成列车驾驶并满足用餐/休息时间。

• 核心挑战：需同时考虑车辆、乘务、跨线运行与多列编组的复杂耦合，问题规模大、约束多，传统模型难以直接求解。

1.3 城市轨道运营流程示意

为了帮助读者理解各环节在整体规划中的位置，下图展示城市轨道运营流程：从线路规划到乘务排班依次递进，每一步都是下一步的基础。

二、建模与方法框架

2.1 模型概述

作者采用基于路径的整数优化模型表示车辆和乘务决策。令  为车辆路径集合， 为乘务任务序列集合，二元变量  表示是否选择车辆路径 ， 表示是否选择乘务序列 。模型目标函数为：

其中  和  分别是车辆路径与乘务序列的成本，第二项包含乘务员使用人数和相关费用。

关键约束

• 车辆分配约束：每辆车  必须且仅能选择一条路径 ，即

• 安全间隔约束：对于同一路段可能冲突的两次列车 ，若列车  在时间  发车，则列车  在区间  不能发车。

• 最小班次约束：在给定场景  的时间窗内，每段物理区段  至少需要  趟车通过。

• 最大同时行车数约束：每个区段在同一时刻最多允许  台车辆。

• 乘务序列平衡：保证选择的乘务任务序列能覆盖所有在服务车辆的行车任务，满足出勤、休息与餐食时间窗。

2.2 多列编组与跨线运行

为适应不均衡客流，模型允许两台或多台车辆在某些时间段耦合运行，形成长列车。图2展示了多列编组及耦合/解耦概念：两辆车在特定车站耦合，合成长列车运行；到达目的地后解耦分开运行。该机制可提升高峰时段运力，也带来额外的调度复杂度。

2.3 路径与任务表示

• 车辆路径：一条路径包含出库、多个行车任务、耦合/解耦操作、相邻任务间的连接与末端入库；定义  表示路径  在时间  开始执行行车任务 。
• 乘务任务序列：乘务人员按时间顺序完成一组行车任务和休息/餐食任务。使用二元参数  记录车辆路径  在时间  覆盖区段 。
• 成本结构：车辆路径成本包括行车成本、连接成本、耦合/解耦成本等；乘务成本包括基本工资、超时和餐食补偿。

三、求解算法与加速技术

3.1 分枝‑定价‑割（BPC）框架

由于候选车辆路径与乘务序列数量巨大，文章提出混合 Benders 分解、列生成与分枝‑定界 的 BPC 算法求解模型。

主要步骤：

1. 预处理时间窗：通过计算各行车任务可能的最早/最晚发车时刻，将时间窗收缩为有效区间，减少列生成难度。
2. Benders 分解：将放松后的模型拆分为以车辆路径选择为决策的主问题和以乘务任务选择为决策的子问题。固定车辆选择后，子问题变为纯乘务排班问题，可以单独求解。
3. 列生成：在求解主问题与子问题的线性松弛时，采用 动态列生成，通过寻找最短路径生成新的车辆路径或乘务序列，以降低成本。
4. 分枝‑定界：当线性松弛解存在分数变量时，在变量上进行分枝，形成搜索树；每个节点再次执行 Benders 分解和列生成，直到得到整数最优解。

3.2 加速策略

为了提升算法效率，作者引入了多项加速技术：

• 低界提升不等式（LBL）：通过添加强约束提高Benders主问题的下界，减少迭代次数。
• 优先级启发式规则（PHRs）：在列生成时优先考虑潜在收益大的车辆路径或乘务序列，加快收敛。
• 动态列剪切（DCG）与列继承（CCI）：动态删除无用列并在分枝节点继承有效列，降低模型规模。
• 并行计算：利用多线程并行求解不同分枝节点，提高求解效率。
• 路径剪枝（PC）：限制路径数目，防止搜索树爆炸。

四、实证研究与结果分析

4.1 实验设置

论文在北京地铁实网中进行验证：考虑4条双向线路共76个站、7个车辆存放基地和43列车辆，规划周期为16小时。旅客需求决定了不同线路的最低班次：市中心2号线平均8分钟一趟，1、4、5号线平均10分钟一趟。乘务员分为两组，工作时间窗口为7:00–15:00和15:00–23:00，并设置两段用餐休息时间。

4.2 计算结果

• 小规模算例：对不同规模的实验，BPC算法相较商用求解器 CPLEX 能在较短时间内获得最佳解或极小间隙，大幅缩短计算时间。例如规模为  的算例，BPC求解时间不到220秒，而直接求解需数小时。
• 实网实例：在北京案例中，设置最大分枝层数和限定总计算时间为12小时，算法最终获得下界313,348、上界335,966，差距6.73%。分析发现，跨线调度和多列编组显著提高高峰时段运力，减少车辆调度次数和乘务投入。约12台车辆跨线支援繁忙的2号线，38趟列车使用长编组，以降低运营成本。乘务排班结果显示共安排168名乘务员，各组适度重叠以满足用餐休息要求。

4.3 管理启示

• 联合调度优势明显：与传统的车辆与乘务分开调度相比，联合调度能充分利用车辆和乘务资源，特别是在跨线运营和客流不平衡的情况下，能减少车辆需求和乘务成本。
• 多列编组与跨线运营互补：长列车编组在高峰时段提供更高运力，跨线调度则平衡各线需求，两者结合可以应对中心城区客流集中与郊区车辆空闲的矛盾。
• BPC算法的适用性：通过预处理、分解和加速技术，BPC算法可处理现实规模的城市轨道调度问题，为运营者提供决策支持。

五、创新点与学术贡献

• 融合多环节调度：论文首次在城市轨道网中联合考虑车辆路径、列车编组、跨线运行和乘务排班，实现系统整体优化。
• 多列编组融入路径模型：模型将车辆耦合/解耦操作纳入路径表示，兼顾乘客需求与车辆容量。
• 基于路径的精确模型：通过路径变量表示所有可能车辆运行方案，避免传统时间空间网络模型的巨大规模。
• 高效BPC算法：结合 Benders 分解、列生成和分枝‑定界，并引入低界提升和动态列剪切等技术，使模型求解效率远超现有方法。
• 实网验证与管理启示：在北京地铁案例上证明方法的可行性，提供了跨线调度和多列编组的定量收益分析。

六、结论与展望

文章针对城市轨道运营中车辆与乘务分开调度导致的效率低下问题，提出在多列编组和跨线运行环境下的联合滚动库存与乘务排班模型，并通过精确的BPC算法成功求解大规模实例。实证研究表明，该方法能显著降低运营成本、提高资源利用率，并对城市轨道网络运营提供重要决策支持。未来可进一步研究乘客动态需求、车辆故障或突发事件对联合调度的影响，并探索基于人工智能的启发式算法以应对超大规模网络。

原文链接见文末，或扫下方交流群二维码。群内实时更新推文及原文 pdf，方便专家学者随时获取（若二维码失效，请翻阅扫描最新文章的二维码）。