考虑软时间窗的多访问无人机协同卡车取送货问题研究：模型构建与算法优化

本文创新性地提出了一种考虑软时间窗（sT）的多访问无人机协同卡车取送货问题（PDmD-sT），针对即时零售和外卖配送中的一对一取送服务（one-to-one pickup and delivery），构建了混合整数非线性规划（MINLP）模型。作者采用分段线性法近似无人机悬停非线性功耗，并设计了改进大邻域搜索（ILNS）算法与卡车等待时间优化策略。实验表明，协同模式比纯卡车模式平均节省成本超40%，算法求解质量优于文献基准算法10%以上，为最后一公里物流的节能增效提供了新思路。

　　

章节亮点

文献综述

近年来，卡车-无人机协同路由调度因其在成本节约和效率提升方面的显著优势，受到了学术界的广泛关注。本节我们简要回顾与本研究最密切相关的三个方面的工作：（1）基础车辆路径问题与无人机（VRPD）及其扩展；（2）取送货服务的考量；（3）带时间窗的旅行商问题/车辆路径问题与无人机（TSPD/VRPD）。

问题描述

PDmD-sT问题涉及一组同构的车辆对（卡车-无人机组合），可用于服务所有具有仅取货、仅送货或一对一取送货需求的客户。所有车辆对最多从单一仓库出发并返回一次。每个客户由卡车或无人机服务且仅服务一次，但部分客户因其包裹过重（无法由无人机承运）必须分配给卡车服务。此外，每个客户都有一个软时间窗，允许在时间窗之外服务，但会产生惩罚成本。

方法论

PDmD-sT涉及具有时间弹性的通用场景，这对实际应用具有重要价值。这一新问题无法直接使用现有求解方法解决。加之车辆路径问题（VRP）本身属于NP难问题，再融入多访问无人机、配对服务以及软时间窗等因素，使得PDmD-sT比以往的问题更为复杂。在合理时间内求解大规模实例相对具有挑战性。因此，我们提出了一种新的定制化改进大邻域搜索（ILNS）算法。

数值实验

为检验我们提出的模型和算法，我们生成了测试算例并进行了一系列数值测试，具体内容在本节描述。我们使用Python 3.9.5编写ILNS代码，并调用Gurobi 10.0.2作为求解器。所有计算均在一台配备2.60 GHz Intel (R) Core (TM) i7-10750H处理器、32 GB内存、运行Windows 10操作系统的笔记本电脑上执行。我们首先在第5.1节介绍测试算例和参数；随后，第5.2节详细展示了所有测试算例的最佳结果。

结论与未来研究

在本研究中，我们评估了一种用于最后一公里物流的新VRPD变体，即考虑软时间窗的多访问无人机取送货问题。在该问题中，多组卡车-无人机对可协同工作，在预设时间段内为客户提供取货和送货服务。此外，我们还考虑了一些配对的客户。每位客户拥有一个软时间窗，若服务在时间窗外开始将产生惩罚成本。卡车可以在节点处等待以优化服务时间。