带软时间窗的多访问无人机取送货问题（PDmD-sT）建模与优化研究

本文提出了一种创新的卡车-无人机协同取送货问题（PDmD-sT），该问题考虑了无人机多站点访问能力（Multi-visit Drones）和软时间窗（Soft Time Windows）。作者建立了混合整数非线性规划（MINLP）模型，采用分段线性化方法处理无人机悬停非线性功耗，并设计了改进的大邻域搜索（ILNS）算法进行求解。数值实验表明，协同模式相比纯卡车模式平均节省成本超过40%，算法性能优于基准算法10%以上，为最后一公里物流提供了高效灵活的解决方案。

　　

Section snippets

Literature review

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

Problem description

PDmD-sT涉及一组同质的车辆对，可用于服务所有具有仅取货、仅送货或一对一取送货需求的客户。所有车辆对最多从单一仓库出发并返回一次。每个客户由卡车或无人机服务恰好一次，而某些客户由于其货物无法由无人机携带（称为重货）必须分配给卡车。此外，每个客户都有一个软时间窗，允许在窗口之外服务，但会产生惩罚成本。

Methodology

PDmD-sT涉及一个具有时间弹性的通用场景，这对实际应用很有价值。这个新问题无法直接用现有的解决方法求解。此外，鉴于车辆路径问题（VRP）的NP难性质，加上多访问无人机、配对服务集成以及软时间窗，PDmD-sT比以往的问题更为复杂。在可行的时间范围内解决大规模问题相对具有挑战性。因此，需要一种新的定制化方法。

Numerical experiment

为了检验我们提出的模型和算法，我们生成了测试算例并进行了一系列数值测试，如本节所述。我们使用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节详细介绍了所有测试算例的最佳结果。

Conclusions and future studies

在本研究中，我们评估了一种用于最后一公里物流的新VRPD变体，即考虑软时间窗的带多访问无人机的取送货问题（PDmD-sT）。在该问题中，多组卡车-无人机对可用于在预定时间段内协作完成客户的取送货服务。此外，还考虑了一些配对的客户。每个客户都有一个软时间窗，在窗口外开始服务将产生惩罚成本。卡车可以在节点等待以优化时间安排。