基于图神经网络的列生成优化方法：联合乘客出行规划与司机排班调度

原文链接见文末

一、研究背景与问题

伴随人口老龄化与残障群体出行需求增加，欧美各地的“弹性出行（paratransit）”服务压力激增。以美国乔治亚州查塔姆县为例，其公共交通局为老年或行动不便的居民提供预约出行服务，但因需求大、司机排班受限、乘客路径规划复杂，导致大量请求无法满足。现有做法通常将乘客路径规划和司机排班分开优化，无法全局兼顾，且基于列生成（column generation）的大规模路径搜索计算量巨大。为解决该难题，论文提出联合乘客行程规划与司机排班问题（Joint Rider Trip Planning and Crew Shift Scheduling Problem，JRTPCSSP），并设计一种名为 AGGNNI‑CG（Attention & Gated GNN‑Informed Column Generation） 的算法，将列生成与图神经网络相结合，以提升效率和服务质量。

关键挑战

  1. 巨大搜索空间：列生成算法在定价子问题中需要不断寻找具有负化简成本的新路径。当订单多、网路复杂时，路径数量呈指数级增长，导致计算耗时。
  2. 数据异质性：每天的订单数量和分布差异很大，导致构造的图规模可变，传统机器学习模型难以适应。
  3. 排班与行程的耦合：司机的工作时长、换班限制与乘客的时间窗约束耦合紧密，很难通过简单的分解达到全局最优。

二、问题建模

1. 驾驶班次候选集

首先根据司机的允许班次开始时间 、结束时间  以及最大工作时长 ，生成一系列候选班次区间，如下图所示。班次起始时间按照间隔  递增，每个班次长度为 ，形成一组候选班次供后续选择。

图 3. 候选司机班次集示意图
图 3. 候选司机班次集示意图

2. 列生成框架

将联合问题转化为一个受限线性主问题（RLMP）与多个定价子问题。主问题旨在选择最佳的司机班次和车辆路线以最大化完成的乘客数量。令  为乘客请求集合， 为候选班次， 为候选路径集合，决策变量包括是否采用某条路线  以及是否满足乘客请求 。主问题的目标函数为：

主问题限制包括每个请求最多被一条路径服务、班次时间不超时、车辆数受限等。由于候选路径集合  庞大，RLMP初始只取少量列，然后通过迭代解决定价子问题补充新列。

定价子问题本质是寻找具有负化简成本的新的可行路径，可表示为带资源约束的最短路径问题。论文采用动态规划结合剪枝策略：一旦找到几个负化简成本路线就提前终止，避免搜索空间爆炸。

3. 整数求解

由于 RLMP 是线性松弛模型，求出的解可能是分数。论文采用基于路径的分枝策略，对最分数化的变量固定为 1，再次执行列生成直至获得可行整数解。

三、机器学习模型：AGGNNI‑CG

为减少定价子问题的图规模，作者使用**图神经网络（GNN）**预测哪些边更可能出现在高质量路径中，然后仅在这些边构建子图并运行列生成算法。这一框架的训练与推断过程如下图所示。

图 6. AGGNNI‑CG的机器学习框架
图 6. AGGNNI‑CG的机器学习框架
  1. 训练阶段：对历史日期实例执行列生成算法，收集所有出现在最优路径中的边作为标签，并计算每条边的属性（节点特征、边特征）。
  2. 训练模型：使用这些数据训练 GNN。模型输入包括图结构、节点和边特征；输出为每条边属于“有前景”路径的概率。
  3. 预测阶段：对于新实例，利用训练好的 GNN 预测每条边的概率，仅保留概率前  百分位的边构成简化图，然后运行列生成得到近似最优解。

1. 特征编码

  • 节点特征：包括乘客请求的地理坐标、上车时间窗、节点类型（上车点、下车点、车库）。
  • 边特征：包括旅行时间与是否为同一乘客的起终点。

2. GNN架构

GNN由两部分组成：多头图注意力层（GAT）与残差门控图卷积层（Gated GCN）。整体结构如下：

图 7. AGGNNI‑CG 的 GNN架构
图 7. AGGNNI‑CG 的 GNN架构

  • 多头注意力层：对每个节点 ，计算其与邻居  的注意力权重 ，权重由节点和边的特征经过线性变换、LeakyReLU 和 softmax 计算而来。下图展示了注意力机制的计算流程：

    图 10. 注意力机制示意
    图 10. 注意力机制示意

多头机制通过不同的头捕捉不同的关联结构，如下图所示，三头注意力的结果被串联作为输出：

图 11. 三头注意力示意图
图 11. 三头注意力示意图
  • 残差门控 GCN：Gated GCN 通过门控来决定信息流动，使每一层的输出保持稳定。公式表示为：

其中  为 Sigmoid 函数， 为按元素乘法， 为从注意力层计算的门控值。网络通过批归一化、dropout 和 ReLU 激活改进训练稳定性。下图为门控机制示意：

图 12. 门控机制示意图
图 12. 门控机制示意图
  • 解码器：将两个节点的嵌入向量拼接后输入多层感知机（MLP），通过 Sigmoid 输出边为“有前景”的概率。

3. 训练与推断策略

训练数据由历史一天的订单实例组成。作者根据列生成得到的最优路径标注哪些边出现在高质量路线上，这些边的标签为 1，其余为 0。采用二元交叉熵损失训练 GNN。推断时只保留预测概率前  百分位的边，构建简化图运行列生成。感性地，这相当于让模型指出“重点道路”，避免枚举不必要的路径。

四、数据集与实验设计

论文基于查塔姆县 2014–2019 年的真实约车数据，每天约几百个订单。图 13 展示了2014–2019 年间每天订单数量随时间的波动：

图 13. 2014–2019 年每天的订单数量
图 13. 2014–2019 年每天的订单数量

为了分析不同日类型，图 14 将 2014 年的工作日与周末的订单量分开。工作日订单普遍高于周末：

图 14. 2014 年工作日与周末的订单量
图 14. 2014 年工作日与周末的订单量

实验分训练和测试两阶段：选择若干天的实例用于训练 GNN 模型，其余用于测试。评价指标包括：

  1. ROC曲线与 AUC 值：衡量模型判断边是否在最佳路径中的准确度。模型在测试集上的 AUC 约为0.95，如图 15所示：
图 15. GNN 在测试集上的 ROC 曲线，AUC≈0.95
图 15. GNN 在测试集上的 ROC 曲线，AUC≈0.95
  1. 平均行程完成率：完成乘客请求数量与总请求数量的比值。
  2. 求解时间：列生成算法求出整数解的总耗时。

五、实验结果与分析

1. 服务质量与效率提升

根据 AIModels 的解读，该方法在真实数据集上显著提高了服务质量与求解效率：机器学习辅助的列生成不仅使求解速度更快，而且得到的司机排班和行程规划也优于基线方法。在查塔姆县数据上，AGGNNI‑CG「在服务质量和求解时间上均比传统列生成方法表现更佳」，能够处理复杂实例并满足不同日期的需求。系统输出的排班更加高效，能够更好地匹配司机和乘客，提高车辆利用率。

2. 敏感性分析

论文进一步探讨了不同训练集和测试集图规模对模型性能的影响。图 16 对比了基线列生成与 AGGNNI‑CG 在不同简化图阈值下的平均完成率与求解时间。蓝色柱代表 AGGNNI‑CG 的完成率，橙色柱代表求解时间；虚线和实线分别表示基线和 ML 方法。

图 16. AGGNNI‑CG 在不同简化图配置下的性能对比
图 16. AGGNNI‑CG 在不同简化图配置下的性能对比

结果表明，随着保留边的比例增加，AGGNNI‑CG 的完成率逐渐上升并趋近基线质量，但求解时间也相应增加。适当选择阈值可在质量与效率之间取得平衡。

3. 模型优点与限制

  • 优点：

    • 缩减搜索空间：GNN 能有效预测重要边，减少定价子问题的规模，显著提高列生成效率。
    • 处理可变规模：多头注意力与门控机制适应不同订单规模的图结构，实现模型泛化。
    • 集成优化与学习：算法在保证解的可行性的同时引入学习，兼具近似最优和计算速度。

  • 限制：

    • 模型效果依赖于历史数据质量，在其他地区或需求模式下可能需要重新训练。
    • 对突发事件（车辆故障、临时取消）缺乏处理机制。
    • 需要一定的计算资源，中小型机构部署可能受限。

六、难点解析与技术创新

  1. 结合列生成与深度学习的复杂性：列生成算法是经典的运筹优化方法，要求严格的可行性；与深度学习模型结合时必须保证预测边的可行性。论文通过保留候选边集合并在简化图上重新运行列生成，确保全局约束仍然满足，从而避免违反可行性约束。

  2. 图大小可变的神经网络设计：不同日期的订单数量可从几十到几百不等，GNN 必须处理不同规模的图。作者采用多头注意力网络和残差门控 GCN，每层通过归一化和门控机制稳定不同尺寸的输入，有效解决可变规模问题。

  3. 训练数据标签稀缺：高质量路径数量有限，模型难以获取充足正样本。作者通过对多个日期实例进行列生成，收集所有出现在最优或近优路径中的边作为正样本，扩大了训练集；同时采用重采样处理类别不平衡。

七、结论与展望

本文详细解析了《Boosting Column Generation with Graph Neural Networks for Joint Rider Trip Planning and Crew Shift Scheduling》一文。论文针对传统弹性出行服务的路径规划和排班难题，提出了 JRTPCSSP 模型，使用列生成求解，并通过引入注意力和门控机制的 GNN 预测重要边以缩减定价子问题的规模。在查塔姆县真实数据集上的实验表明，该方法显著提升了服务完成率并缩短求解时间。敏感性分析进一步证明了简化图阈值对结果的影响，为实际应用提供了参考。

未来研究可考虑：

  • 增加对突发事件或实时信息的处理，使模型能够动态调整计划。
  • 将乘客优先级、满意度等因素纳入目标函数，提高服务公平性。
  • 探索强化学习等自适应方法，在无需大量标注数据的情况下自动学习重要边。

原文链接：https://doi.org/10.1016/j.tre.2025.104281