考虑软时间窗的多访问无人机取送货问题研究

本文创新性地研究了带软时间窗的多访问无人机取送货问题（PDmD-sT），针对最后一公里物流提出卡车-无人机协同运作模式。作者建立了混合整数非线性规划模型，采用分段线性化处理无人机非线性悬停功耗，并设计了改进的大邻域搜索算法。结果表明，该协同模式比纯卡车模式平均节省成本超40%，算法求解质量优于基准算法10%以上，为可持续交通系统提供了高效解决方案。

　　

Section snippets

Literature review

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

Problem description

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

Methodology

PDmD-sT涉及一个具有时间弹性的通用场景，这对实际应用非常有价值。这一新问题无法直接用现有的求解方法解决。此外，鉴于车辆路径问题（VRP）的NP难特性，加上多访问无人机、配对服务集成以及软时间窗，PDmD-sT比以往的问题更为复杂。在可行的时间范围内求解大规模问题相对具有挑战性。因此，我们提出了一种新的定制化改进大邻域搜索（ILNS）方法，并结合卡车等待时间优化模型来高效求解。

Numerical experiment

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

Conclusions and future studies

在本研究中，我们评估了一种用于最后一公里物流的新VRPD变体，即考虑软时间窗的多访问无人机取送货问题。在该问题中，多组卡车-无人机对可用于在预定时间范围内协作完成客户的取货和送货服务。此外，我们还考虑了一些配对的客户。每个客户都有一个软时间窗，在时间窗外开始服务将产生惩罚成本。卡车可以在节点等待以减少惩罚，这增加了问题的复杂性，但也提供了更大的调度灵活性。