💻 computer science

Assigning and optimising airport ground-handling operations: an rVNS metaheuristic

本文提出了一种用于优化机场餐饮运营中复杂的带时间窗及用餐休息的多趟次容量限制车辆路径与调度问题（MTCVRSPTW-MB）的协同缩减变量邻域搜索（rVNS）元启发式算法，并证明了在旧金山国际机场的实际案例中，该算法相比精确算法具有更优越的效率和里程缩减能力。

原作者： Alexandre Dupaquis, Ronan Guivarch, Sandrine Mouysset, Daniel Ruiz, Vincent Charvillat, Frédéric Bouilhaguet

发布于 2026-07-07

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Alexandre Dupaquis, Ronan Guivarch, Sandrine Mouysset, Daniel Ruiz, Vincent Charvillat, Frédéric Bouilhaguet

原始论文采用 CC BY 4.0 许可（https://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，一个繁忙的机场就像一个巨大的、高风险的拼图游戏。在其中一侧，有数百架正在到达和起飞的飞机，每架飞机都需要装载或卸载食物。在另一侧，有一支由卡车和司机组成的队伍，每位司机都有特定的技能、有限的时间以及严格的午餐休息规则。

目标很简单：按时为每架飞机提供食物，同时使用尽可能少的卡车行驶里程。但其中的数学逻辑极其复杂。如果你试图用标准的计算机程序来解决这个问题，这就像是在沙滩上寻找一颗特定的沙粒，通过逐一检查每一颗沙粒来完成——这太耗时了。

本文介绍了一种更聪明、更快速的方法来解决这个谜题，这种方法被称为 rVNS（简化变邻域搜索法）。以下是其工作原理的拆解，使用了日常概念进行说明：

1. 问题所在：“机场食物版俄罗斯方块”

把机场的地勤团队想象成正在玩一场高速运转的“俄罗斯方块”游戏。

方块： 这些是任务（装载一架飞机、卸载一架飞机）。
槽位： 这些是司机和卡车。
规则： 司机只能驾驶特定的卡车；卡车只能携带一定量的食物；司机必须在开始工作 4 到 5 小时之间进行 30 分钟的午餐休息；且飞机必须在特定的时间窗口内完成喂食。

过去，研究人员尝试过两种解决方法：

“完美”路径（精确算法）： 试图计算每一种可能性以找到绝对最优解。这就像是为了找到最好的故事而试图读完图书馆里的每一本书。它很准确，但太慢了。
“快速”路径（贪婪启发式算法）： 在那一刻做出当前可行的最佳选择。这就像是不看其他书，直接抓起最近的一本书。它很快，但往往导致平庸的结果。

2. 解决方案：“智能洗牌”（rVNS）

新方法 rVNS 就像一位掌握了精髓的拼图高手，他知道有时你必须打破一个好的排列，才能创造出一个更好的排列。

该算法不是从头开始构建完美的拼图，而是从一个还不错的排列开始，然后玩一场**“洗牌与交换”**的游戏。

洗牌（The Shuffle）： 它随机挑选一些任务（方块），将它们从进度表中移除，并放入一个“候补室”。
交换（The Swap）： 然后它尝试将这些任务重新放回，但这一次，它会尝试将它们放入不同的位置，或者与其他任务进行交换，看看整体效果是否更好。

为什么叫“简化”（Reduced）？
通常，这些算法会尝试洗牌巨大的任务块，这非常缓慢。这种新方法通过快速且重复地洗牌较小的任务块来运行。这就像一名厨师在品尝汤的味道并加一点盐，然后再次品尝，而不是每次都试图重写整个食谱。

3. 秘密武器：两种不同的策略

该算法足够聪明，知道何时该专注于什么。它有两种模式：

模式 A（“填充者”）： 它的主要目标是确保没有任何任务被遗漏。它通过洗牌进度表来确保每架飞机都能得到喂食。
模式 B（“里程节省者”）： 一旦大多数任务都被分配完毕，它就会转向专注于节省燃油。它会寻找重新排列卡车的方式，使卡车在飞机之间行驶的里程更少。

4. “团队集结”（并行化）

为了让速度更快，研究人员不仅使用了一个计算机大脑，还使用了一个团队。想象一群侦探正在试图破解一起案件。他们没有让一个人检查所有线索，而是分工合作：

侦探团队 1 处理上午班次的进度表。
侦探团队 2 处理下午班次的进度表。
每隔 10 秒，他们就会聚在一起开个小会，分享彼此最好的想法，并将发现的结果结合起来。

这确保了他们不会陷入“死胡同”（局部最优解）——即他们以为找到了最好的方案，但实际上错过了更好的方案。

5. 结果：更快、更好、更顺畅

当他们在旧金山国际机场（SFO）的真实数据上测试这种新方法时：

成功率： 旧方法只能完成约 80–89% 的任务分配。新的 rVNS 方法完成了 99% 到 99.8% 的任务。它几乎从未让飞机处于未喂食状态。
燃油节省： 由于它能更高效地重新排列进度表，卡车的行驶里程比以前减少了约 20% 到 30%。
速度： 它能在不到一分钟的时间内找到这些近乎完美的解决方案，这足以满足实时运营的需求。

总结

简而言之，本文提出了一种新的“智能洗牌”算法，帮助机场管理者将食物配送任务分配给司机和卡车。通过将问题分解为较小的部分，通过随机洗牌来寻找更好的匹配，并利用计算机团队协作，该系统确保了几乎每架飞机都能得到喂食，同时比以往的方法行驶更少的里程。它将一个混乱、看似无法解决的拼图，变成了一个可控且高效的日常流程。

技术摘要：通过 rVNS 进行机场地面代理作业的分配与优化

问题定义
本研究针对机场地面代理作业（特别是餐饮服务）中复杂的组合优化问题进行了探讨。核心问题被建模为带时间窗及用餐休息的多趟次容量受限车辆路径与调度问题 (MTCVRSPTW-MB)，并进行了扩展，以适应具有不同资质和载荷模式的异构卡车车队及驾驶员。

其目标分为两个层面：

首要目标： 最大化分配给可用驾驶员和卡车的餐饮任务（装载/卸载飞机）。
次要目标： 最小化执行这些任务所需的总里程。

该问题受到严格的操作规则约束，包括：

驾驶员约束： 值班表、强制性 30 分钟用餐休息（在值班开始后 4–5 小时发生）以及针对特定机型和航空公司的资质要求。
卡车约束： 容量限制、特定卡车类型（14FT、16FT、22FT）以及每日可用量限制。
任务约束： 执行的时间窗、卡车/驾驶员与特定航班/航空公司的兼容性，以及体积要求。
任务序列（Mission）约束： 管理多任务序列的规则，例如禁止在同一任务序列内进行“国际装载后国内卸载”的操作、确保任务之间有足够的行驶时间，并要求所有任务序列必须在主餐饮单元开始并结束。

本研究利用了 2023 年 3 月旧金山国际机场 (SFO) 的真实数据，涉及约 350 个每日任务、80 名驾驶员和 40 辆卡车。一个关键要求是，解决方案必须在 一分钟内 生成，以具备操作可行性。

方法论
作者提出了一种协作式缩减变量邻域搜索 (cooperative reduced Variable Neighborhood Search, rVNS) 元启发式算法。选择这种方法而非传统的变量邻域搜索 (VNS) 和自适应大邻域搜索 (ALNS)，是为了在计算效率与解质量之间取得平衡。

该方法论的关键组成部分包括：

缩减型 VNS (rVNS) 框架：
- 与改变步长的经典 VNS 不同，rVNS 采用固定的、较小的步长。
- 该算法通过解构与重构循环运行：它从当前解中取消固定数量的任务 ( $n$ )，并尝试随机重新分配这些任务。
- 为了补偿固定步长，算法利用了调度问题的高度对称性。通过探索“等效”解（具有相同评分的不同调度方案）来进行随机交换，从而在无需进行大规模、高计算成本的步长跳转的情况下实现搜索多样化。
算法结构：
- 分解（问题二分法）： 根据驾驶员值班重叠情况，将每日调度分为两个子问题（上午和下午），从而实现并行处理。
- 热启动启发式（Warm-Start Heuristic）： rVNS 使用由贪婪启发式算法生成的解进行初始化，该算法优先考虑任务较少的合格驾驶员和强制性用餐休息，以防止搜索从较差的局部最优解开始。
- 双目标随机化： 算法根据目标收敛情况在两种随机化策略之间切换：
  - 侧重主要目标： 取消具有相似时间位置的任务，以腾出空间给未分配的任务。
  - 侧重次要目标： 取消对总里程贡献最大的任务。
- 排序启发式： 一种快速启发式算法（算法 3）用于检查任务是否可以在不违反约束的情况下插入驾驶员的序列中，这对于保持重构阶段的速度至关重要。
- 协作并行化： 多启动策略在 8 个核心上运行（每个子问题 4 个核心）。每 10 秒，并行单元会共享结果并从当前最优解重新开始，以减少方差并避免陷入局部最优。
目标函数：
总目标函数 $F$ 是一个加权和，优先考虑任务分配，其次是里程削减，最后是任务序列效率：
$F = 10^6 \sum a_i + 10^3 \sum (x_i + y_i) + \sum e_i$
其中 $a_i$ 代表未分配的任务， $x_i$ 和 $y_i$ 代表行驶距离， $e_i$ 计算任务序列的开始次数。

主要结果
研究将所提出的 rVNS 与贪婪启发式算法 (Greedy Heuristic) 以及数学启发式算法 (Matheuristic)（此前在 [1] 中开发）进行了对比，并使用了两个数据集（S1：任务较少且受限；S2：任务众多且约束较少）。

任务分配： rVNS 显著优于以往的方法。虽然贪婪法和数学启发式方法的任务分配率约为 80–89%，但 rVNS 在两个数据集上的分配率均达到了 99.0% 至 99.8%。
里程削减： 与数学启发式算法相比，rVNS 在 S1 数据集上减少了约 30% 的车队总里程，在 S2 数据集上减少了约 20%。
稳定性与收敛性：
- 并行化 rVNS 比顺序版本表现出更高的稳定性，其里程的标准差为 2–3%，而顺序版本的标准差为 4–6%。
- 收敛速度： 对于较小的数据集 (S1)，主要目标（任务计数）收敛迅速（约 1 秒内），而里程优化在长达一分钟的时间内持续改善。对于较大的数据集 (S2)，主要目标需要约 10 秒收敛，且在一分钟后收益递减。
执行时间： 所有解决方案均在要求的一分钟窗口内生成（具体包括开销在内约为 55–60 秒）。

意义与主张
论文声称，rVNS 元启发式算法为机场地面代理提供了一个稳健且灵活的解决方案，超越了以往的精确解和启发式基准。其核心意义在于：

操作可行性： 它能在实时调度所需的一分钟严格时限内，解决高度受限的多目标问题。
双重优化： 它成功平衡了最大化任务完成率与最小化运营成本（里程）之间的关系，这是以往工作中未能充分优化的功能。
灵活性： 作者指出，该算法的结构允许集成新的约束或目标，例如管理电动汽车充电或多仓库作业。
实际应用： 研究表明，该算法处理包含滑动时间窗和异构车队在内的现实世界复杂数据的能力优于以往模型，为地面代理提供了一个能够自动分配数百个每日任务的工具。

作者对绝对最优性保持谦逊，承认虽然算法不能保证获得全局最优解，但它始终能收敛到优于现有方法（在速度和质量方面）的解。他们强调了未来在实时重分配场景中的应用潜力，即在任务延迟时进行动态重新调度。