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

主动‑被动车辆协同调度：混合整数规划与自适应大邻域搜索解析

一、研究背景与问题提出

联合国报告指出，每人每年将私车出行转向公共交通可减少约 2.2 吨碳排放（United Nations, 2024）。然而，尽管公共交通在环保方面具有明显优势，其在舒适性、可靠性和换乘便捷性上仍存在不足。为兼顾环保与乘客体验，论文提出模块化舱-基座系统：乘客全程待在“舱体”（pod）内，由“基座”（base，如卡车、地铁列车或船只）承载行进，并在枢纽点完成舱体与不同基座间的无缝转运。该模式避免了乘客自行换乘，并可按需求动态配置运力，从而在乘客满意度与运营效率之间取得平衡。

下图展示了基座携带多个舱体的概念（图1）和未来可能的集散枢纽设计（图2），其中不同的基座（卡车、地铁、船只等）在枢纽装卸舱体，实现无缝换乘。

图1 基座携带多个舱体（取自Fig.1）
图1 基座携带多个舱体（取自Fig.1）
图2 模块化站点设计（取自Fig.2）
图2 模块化站点设计（取自Fig.2）

论文的目标是通过主动‑被动车辆协调解决复杂的门到门多模态调度问题：在给定的多模态网络中，为每名乘客分配舱体和基座并安排行程，使乘客在时窗内尽早到达目的地，同时最小化运营成本。需要同步不同载具的移动和装卸，属于组合优化难题。作者的贡献包括：提出紧凑的混合整数线性规划（MILP）模型；设计自适应大邻域搜索（ALNS）启发式及其聚类扩展；通过大量基准和真实数据实例验证该方法。

二、模型与方法

2.1 POD 问题定义与目标函数（修改版）

论文将该问题称为 POD (active–passive vehicle coordination)，涉及四类元素：顾客集合 、舱体集合 、基座集合  及运输方式集合 。每个基座属于某种运输方式 ，舱体与基座容量分别为  与 。顾客  具有起点 、终点 、时间窗  以及最大行程时长 。

为衡量解决方案的优劣，定义如下加权目标函数：

其中  为所有顾客到达时间总和， 为基座行驶时间之和， 与  分别表示使用的舱体与基座数量。 权重  反映乘客满意度与运营成本的平衡。

注意： 根据论文 Definition 2.5 的说明，基座静止等待时间不计入  ，因为停驻阶段不消耗能量，因此模型只最小化实际行驶时间。

2.2 MILP模型与约束

为求得最优调度，作者建立了离散时间步长  的 MILP 模型。 核心决策变量定义如下：

  • ：时间步  时，舱体  是否位于枢纽 ；
  • ：时间步  时，基座  是否位于枢纽 ；
  • ：时间步  时，舱体  是否被装载在基座  上；
  • ：顾客  是否由舱体  承运；
  • ：顾客  在  时间段内是否在舱体  中； 以及辅助变量 、、 等。

模型约束分为以下几类：

  • 位置与移动约束确保每个时间步中每个舱体与基座仅位于一个枢纽，且移动遵循交通网络：

  • 顾客分配约束每位顾客只能分配给一个舱体：

  • 容量约束舱体载客容量与基座装载容量分别为：

  • 持续时间与同步约束每个离散时间步进一步划分为三个连续阶段：装载/登车、行驶、卸载/下车。 使用连续变量  表示基座  在第  步的开始时间， 分别表示装载/登车与卸载/下车阶段的持续时间。 为衔接离散与连续变量，模型中引入大常数 （big-M）并定义紧凑上界：

该约束保证当所有顾客时间窗结束后，基座不再移动。 通过上述机制，模型确保舱体与基座行驶时间同步。

下图展示了连续时间分解与  取值影响：

  • 图3 展示一个离散时间步内的三阶段结构；
  • 图4 展示  取值对模型可行性的理论下界，由附录 A 命题 3.1 推导，证明在最坏情况下至少需要  个离散步以保证所有同步操作可行。
图3 基座三阶段时间轴（取自 Fig.5）
图3 基座三阶段时间轴（取自 Fig.5）
图4 对可行性的影响（取自Fig.A.20）
图4   对可行性的影响（取自Fig.A.20）

2.3 自适应大邻域搜索（ALNS）

由于MILP对大规模实例求解困难，作者设计了自适应大邻域搜索（ALNS）。算法框架如图5所示。该算法在 Meisel and Kopfer (2014) 提出的 Active–Passive VRP 启发式基础上扩展而成，针对本问题特有的多模态与同步约束进行了自适应调整。其思想是从初始解出发，在迭代过程中随机选择移除操作和插入操作破坏并修复解空间，并通过轮盘赌选择策略赋予不同操作概率，以利探索和开发。主要特色包括：

  • 初始解构建：使用最便宜插入策略将客户一一插入舱体并调度基座。
  • 移除规则：包含随机移除和最差移除，以多样性或改进解。
  • 插入规则：使用截止时间（due date）或松弛规则（slack）评估插入位置；前者根据顾客最晚可达时间排序，后者估计载具紧迫性。
  • 自适应权重：根据不同操作在迭代中的表现动态调整其选择概率。
  • 接受准则：采用轮盘赌动态调整各规则的选择概率，改进即加分并重算概率。
图5 ALNS框架流程（取自Fig.7）
图5 ALNS框架流程（取自Fig.7）

2.4 聚类与扩展策略

为了应对更大规模场景，论文在ALNS中引入两步聚类：首先使用最近邻方法对客户初步聚类，再按K‑means对客户及枢纽进一步划分个簇，使算法在每一簇内部独立运行，从而降低计算复杂度。为计算多模态网络中的最短换乘时间，作者引入辅助图，通过估计  实现多模态下的可行最短路径计算（如图6所示）。图7比较了直接最近邻与两步聚类的效果，后者能在保持解质量的情况下显著降低CPU时间。

图6 辅助图用于多模态最短路计算（取自Fig.8）
图6 辅助图用于多模态最短路计算（取自Fig.8）
图7 最近邻与两步聚类效果对比（取自Fig.9）
图7 最近邻与两步聚类效果对比（取自Fig.9）

此外，作者提出不同的LNS变体（仅使用due date或slack规则），以及对时间窗参数的敏感性分析，这些将在数值实验部分讨论。

三、数值实验与分析

作者设计了五组随机基准实例（A–E）以及一个真实数据集（慕尼黑地铁 Zone M）。 MILP 模型使用 Gurobi 11.0.2 求解，采用 4 线程上限，时间上限 10 小时。 所有实验在同一随机种子 42 下运行。 解优劣以相对差距  衡量，其中  为当前最优目标值。

3.1 基准集A、B、C：MILP与ALNS对比

基准集 A、B、C 分别包含 5、10、20 名顾客，涵盖单一或多种交通方式。在图8 的不等式评测中固定 ，在小实例集 A 的扩展对比中进一步设置  或 ，均采用 10 小时求解上限。 图8给出了不同有效不等式对MILP的加速效果；组合不等式（45）与（51）–(52) 可以大幅收紧模型，CPU时间显著下降。

图8 不等式对MILP求解时间的影响（取自Fig.10）
图8 不等式对MILP求解时间的影响（取自Fig.10）

图9比较了MILP和ALNS在实例集A–C上的效果。纵轴是相对差距和CPU时间，横轴为A、B、C三组。可以看到，ALNS在几乎所有实例上都以一至三个数量级的速度优势获得近似最优解，而MILP往往无法在限定时间内完美求解较大实例。因此，在满足运行时间约束的情况下，ALNS是更实用的求解器。

图9 基准集A–C的MILP与ALNS比较（取自Fig.11）
图9 基准集A–C的MILP与ALNS比较（取自Fig.11）

3.2 实例集D与E：LNS变体与聚类效果

集D包含 50 名顾客，集E包含 80 名顾客，两者使用不同比例的舱体与基座。 图10对比了仅使用due date规则、仅使用slack规则以及两者结合的ALNS。实验表明，结合规则的ALNS在解质量和稳定性方面优于单一规则，但计算时间略长。

图10 LNS变体性能对比（取自Fig.12）
图10 LNS变体性能对比（取自Fig.12）

图11针对集D展示了使用聚类()和不聚类的差距和CPU时间。结果表明聚类能显著降低计算时间，但会略微降低目标值。因此，当实例规模较大且实时性要求高时，适当的聚类策略非常重要。

图11 集D聚类与否的影响（取自Fig.13）
图11 集D聚类与否的影响（取自Fig.13）

对于集E，作者比较了与两种簇大小（图12）。较小簇可进一步缩短计算时间，但可行解率下降甚至有部分实例无法求解。较大簇能保证可行解但运算时间增长。

图12 集E不同聚类规模下的结果（取自Fig.14）
图12 集E不同聚类规模下的结果（取自Fig.14）

3.3 LNS变体与时间窗敏感性

为了深入理解各LNS操作的作用，作者在集B中分别评估五种拆除/插入组合与ALNS总体框架。 图13显示了单独的LNS变体（due date & random、due date & worst等）与ALNS的差距和CPU时间。 ALNS通过轮盘赌动态选择操作，其性能明显优于单一变体。

图13 LNS拆除/插入规则比较（取自Fig.15）
图13 LNS拆除/插入规则比较（取自Fig.15）

图14考察了允许“不可行初始解”与必须“可行初始解”两种策略对求解实例集C的影响。 当时间窗长度较短（）时，两种策略都难以找到可行解； 在其它时间窗长度下，允许不可行初始解的策略能求解更多实例并取得更好结果。

图14 不同初始解策略下求解实例数（取自Fig.16）
图14 不同初始解策略下求解实例数（取自Fig.16）

3.4 现实数据场景：慕尼黑地铁

为了评估方法在真实环境中的适用性，作者以慕尼黑地铁网（Zone M）为基础构造了30个实例。 图15展示了地铁网核心区域，其中六条线路作为不同的运输方式，节点表示主要枢纽。

图15 慕尼黑地铁Zone M网络（取自Fig.17）
图15 慕尼黑地铁Zone M网络（取自Fig.17）

实例包含 50 名顾客、20 个舱体（容量1–4）、18 个基座（10辆卡车、8列地铁）。 舱体和基座位置、顾客起终点随机指定，基座行驶速度基于真实路网时间，地铁平均速度约 34.8 km/h。 作者在此基础上评价“地铁+卡车”两模态与单一“卡车”模式，且测试是否使用聚类（）。 图16显示，在两模态情况下，无论是否聚类，相对差距均显著低于单一模态，并且聚类能将计算时间降至约 100 s。

图16 两模态与单模态在现实数据上的比较（取自Fig.18）
图16 两模态与单模态在现实数据上的比较（取自Fig.18）

进一步地，图17比较了顾客总到达时间与总旅行时间。 在两模态下，相比单模态平均提前 17.06% 到达（聚类情况下为 15.70% ）， 旅行时间降低 26.40% （聚类情况下为 19.53% ）， 基座行驶时间减少 20.94% （聚类情况下为 18.47% ）。 作者指出，这验证了模块化多模态运输在乘客舒适度与可持续性之间实现了双赢， 证明该系统在现实城市交通中具有可行性与应用潜力。由此可见，多模态融合显著提高了乘客体验并降低运营成本。

图17 顾客总到达时间和旅行时间比较（取自Fig.19）
图17 顾客总到达时间和旅行时间比较（取自Fig.19）

四、挑战与策略

该研究面临多重挑战。首先，基座与舱体的同步性导致状态空间维度极高，离散时间建模使模型含有大量二进制变量和大约束，这类同步约束意味着任何单个车辆路径的局部修改都可能破坏整体可行性，正如 Drexl (2012) 所述，这是 VRP with Multiple Synchronization Constraints (VRPMS) 的核心挑战之一。作者通过合理设定和上界以及引入有效不等式减少模型松弛度。其次，大规模实例求解耗时，需要启发式；ALNS结合多种破坏与修复策略，并通过权重自适应提升效率。此外，多模态网络使舱体拆分频繁，聚类策略有效降低了运算量，但过小的簇可能导致不可行或解质量下降，这反映了实践中算法参数选择的权衡。

五、结论与展望

论文首次系统研究了主动‑被动车辆协同调度的门到门多模态运输问题，提出了以紧凑MILP模型与自适应大邻域搜索为核心的求解框架。研究表明：

  • MILP模型在小实例上能得到最优解，但加入有效不等式对提升求解速度和下界质量至关重要；
  • ALNS启发式在中大规模实例上具有显著优势，可在较短时间内得到接近最优的解；
  • 聚类策略和due date/slack规则组合进一步平衡了计算效率和解质量；
  • 在真实的慕尼黑地铁案例中，多模态方式相较单一交通方式能够平均提前乘客到达17.06%，缩短乘客旅行时间26.40%，并减少基座行驶时间20.94%。

未来研究可从以下方面扩展：结合局部搜索或机器学习策略进一步提升算法性能；考虑实时动态请求和随机旅行时间；探索更多交通模式如共享自行车、无人机等；以及深入分析成本与环保收益之间的权衡。通过持续的理论创新与实践应用，该研究为按需、多模态、模块化出行系统的工程实现奠定了方法基础，为未来城市公共交通提供新的发展路径。

文章须知 

推文编辑：单子叶 

责任编辑：弓仪长

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