考虑订单释放时间和无人机补给的多次访问卡车-无人机取送货问题

《European Journal of Operational Research》：Multi-visit truck-drone pickup and delivery problem with release dates and drone resupply

　　

• •
  引入一种集成的卡车 - 无人机路径规划与需求分配问题。
• •
  考虑物品释放时间、时间窗口以及同时取货和送货。
• •
  考虑三种配送模式，并启用补给无人机。
• •
  一种带有多个有效不等式的混合整数双线性规划模型。
• •
  一种具有多项增强措施和能量优化策略的元启发式算法。

引言

电子商务的增长加速了人们对无人机在最后一公里物流中应用的研究兴趣（Kitjacharoenchai 等人，2020；Tamke & Buscher，2023）。亚马逊、UPS、顺丰速运和京东物流已在各种运营场景中进行过无人机配送试验（Jiang 等人，2024）。无人机在成本、速度和环境性能方面可提供优于传统地面车辆的优势（Sacramento 等人，2019），但其有限的续航和载重限制了其使用（Tamke & Buscher，2023）。卡车 - 无人机配送系统通过将卡车的容量和续航与无人机的机动性相结合来解决这些限制（Kitjacharoenchai 等人，2020）。

虽然前景广阔，但此类集成系统必须适应几种现实世界的运营复杂性。这些包括：(1) 同时取货和送货需求，这带来了混合负载挑战和动态负载波动（Jiang 等人，2024）；(2) 客户指定的时间窗口，糟糕的合并可能导致违规并降低服务可靠性（Cattaruzza 等人，2016）；(3) 多样化的配送模式，特别是在 COVID-19 大流行后对快递柜自提偏好的增长（Peng 等人，2023）；以及 (4) 限制调度时间的物品释放日期（Shelbourne 等人，2017）。

为应对这些挑战，我们提出了带有释放日期和无人机补给的多次访问卡车 - 无人机取送货问题（MV-TDPDRD-DR）。该问题结合了同时取送货、物品释放日期、客户时间窗口、快递柜自提和无人机补给。每辆卡车携带一架配送无人机（DD），两种车辆都在各自的时间窗口内服务客户。补给无人机（RD）将新释放的物品从仓库运送到在途卡车上；这些物品随后由卡车或其配对的 DD 进行配送。这些相互关联特征的加入使得 MV-TDPDRD-DR 比现有的集成卡车 - 无人机协作路径规划变体复杂得多。例如，在单个客户或快递柜地点，卡车、DD 和 RD 之间的协调操作可能涉及多达十种不同类型的活动，如图 1 所示。

在物品释放日期和客户时间窗口下协调上述活动使得可行性测试具有挑战性。为说明这一挑战，我们在图 2 中考虑了三种场景，根据补给节点的不同操作类型进行分类。我们假设任意两个节点之间的卡车行驶时间为 5 分钟，而更快的 RD 和 DD 需要 3 分钟。RD 在节点 $i$ 为卡车补充物品 $j$。(1) 在图 2(a) 中，补给节点也作为卡车服务的客户节点。为满足客户 $m$ 的时间窗口，卡车必须在下午 5:35 之前离开节点 $i$。这一强制截止日期迫使其放弃 RD 在节点 $i$ 执行的补给任务。(2) 在图 2(b) 中，补给节点不仅作为卡车的客户节点，还作为 DD 的起飞节点。DD 需要服务由 RD 携带物品的客户。此外，为满足客户 $l$ 的时间窗口，DD 必须在下午 5:35 之前起飞。然而，RD 的补给物品只能在此时间后到达，这使得 DD 无法及时获取物品以完成配送；以及 (3) 在图 2(c) 中，补给节点也作为快递柜。分配给快递柜的物品的释放时间为下午 5:35，RD 最早能对其补给的时间是下午 5:38。然而，为满足客户 $m$ 的时间窗口，卡车必须在下午 5:35 之前离开快递柜。这两个时间之间的小间隔直接导致方案不可行。这些场景表明，空间上合理的路径规划方案在时间上可能仍然不可行。卡车、DD 和 RD 活动的重叠进一步使调度复杂化，这促使制定筛选不可行操作的加速规则以及详细的可行性测试。

在图 1 描述的十种活动中，大多数涉及 DD。特别是，活动 (h) 和 (j) 需要卡车、DD 和 RD 之间的协调操作。在这种复杂情况下，未能最小化 DD 能耗往往会经常导致不可行解。DD 能耗发生在三种场景中：(1) 飞行能耗：鉴于能耗模型既依赖于行驶时间又依赖于负载，同时取送货任务的加入意味着最短路径可能不是能耗最优的。必须设计专门的算法算子来确定处理取送货任务的节能 DD 路线；(2) 客户时间窗口开启前的等待能耗：在 Meng 等人（2024）的工作基础上，本研究进一步设计了一种基于分解的算法对其进行优化；以及 (3) 降落前的悬停能耗：与先前的研究不同，我们允许无人机在有时间窗口的客户地点起降，并纳入了补给操作。这些特征导致 DD 和卡车在起飞节点的出发时间不同步，为优化无人机在起飞节点的等待时间以最小化回收节点的悬停能耗带来了新挑战。

这些相互作用使得 MV-TDPDRD-DR 比现有的无人机车辆路径规划问题（VRPD）变体更具挑战性。据我们所知，以往没有研究处理过这种需求的组合。本文做出了三个主要贡献。

首先，从问题公式化和建模的角度，我们提出了带有释放日期和无人机补给的多次访问卡车 - 无人机取送货问题（MV-TDPDRD-DR）。虽然现有的卡车 - 无人机路径规划研究已处理了现实世界特征的子集，如时间窗口、同时取送货或无人机补给，但以往没有工作同时集成所有这些特征以及三种配送模式（无人机、卡车和快递柜自提）以及通过另一种不同类型的无人机进行的途中补给。我们将此问题公式化为一个混合整数双线性规划（MIBLP）模型，该模型捕捉了配送无人机的负载相关能耗以及卡车在运输过程中的负载变化，这两者都受到同时取送货操作以及补给操作的影响。为了加强模型以用于精确求解方法，我们推导了一组问题特定的有效不等式，以收紧线性规划松弛，在小规模实例上将计算时间减少了 37.53%。

其次，从求解方法的角度，我们设计了一种针对 MV-TDPDRD-DR 的定制自适应大邻域搜索（ALNS）算法。与通用的 ALNS 实现不同，我们的算法结合了：(i) 利用释放日期、时间窗口和配送模式之间相互作用来有效修剪不可行插入操作的加速规则；(ii) 验证多种车辆类型时间约束的基于节点的可行性测试；以及 (iii) 最小化配送无人机在客户节点和集合节点悬停能耗的基于分解的等待时间优化机制。这些特征共同使 ALNS 能够获得比三种基准算法（LNS、VNS 和 Pina-Pardo 等人，2024 年的框架）成本低 37.87%、54.75% 和 21.37% 的解，适用于中等和大规模实例。

第三，从实际角度，我们对八个关键参数进行了广泛的敏感性分析，包括无人机单位成本、电池 - 负载权衡、依赖距离的快递柜连接成本因子、快递柜服务范围、时间窗口紧密度、卡车容量和固定 RD 激活成本。这些分析得出了关于无人机机队组成、快递柜部署策略和应急 RD 利用政策的可操作管理见解，这些见解在以往的卡车 - 无人机路径规划文献中尚未得到系统探索。

在下文中，第 2 节回顾相关文献，第 3 节提出所设计的数学模型，第 4 节开发 ALNS 启发式算法，第 5 节展示数值实验和敏感性分析，第 6 节得出结论。

章节片段

文献综述

本节回顾关于 VRPD 以及带有释放日期和无人机补给的路径规划的研究。VRPD 综述重点介绍卡车和无人机都服务客户的系统。Faramarzzadeh 和 Akpinar (2025) 提供了关于 VRPD 变体的更广泛的综述。

问题描述与公式化

3.1 问题描述、3.2 符号说明描述了问题并定义了符号。3.3 节介绍了数学公式，3.4 节介绍了有效不等式。

求解技术

本节介绍了一种针对 MV-TDPDRD-DR 的定制 ALNS。ALNS 是一种已被证明适用于 VRP 变体的元启发式算法（Sacramento 等人，2019）。它迭代地应用破坏算子从当前解中移除某些节点，并应用修复算子将它们重新插入，从而持续改进初始解（Ropke & Pisinger，2006）。虽然标准的 ALNS 框架非常适合路径规划问题，但 MV-TDPDRD-DR 引入了超越

数值实验

本节通过计算实验评估了 MIBLP 模型、有效不等式和 ALNS 算法。算法使用 Python 3.9.7 实现，并在配备 AMD Ryzen 7 5800H 处理器、Radeon 显卡和 16 GB 内存的计算机上运行。数学模型使用 Gurobi 9.5.1 求解。

结论

本研究解决了一个集成的卡车 - 无人机路径规划与需求分配问题，该问题捕捉了包括物品释放日期、时间窗口、同时取送货、三种配送模式以及通过另一种不同类型的无人机进行的途中补给在内的几个关键现实物流复杂性。我们将此问题公式化为一个 MIBLP 模型，并开发了一种具有加速策略、基于节点的可行性测试和等待时间优化的定制 ALNS。数值实验

CRediT 作者贡献声明

梁双：撰写 – 审阅与编辑，撰写 – 原稿撰写，验证，软件，方法，调查，数据整理，概念化。陈雁如：撰写 – 审阅与编辑，撰写 – 原稿撰写，监督，资金获取，概念化。杜博：撰写 – 审阅与编辑，撰写 – 原稿撰写，概念化。

梁双|陈雁如|杜博