针对异构监控任务的同步卡车-无人机路线规划及自适应车队调度

《TRANSPORTATION RESEARCH PART E-LOGISTICS AND TRANSPORTATION REVIEW》：Synchronized truck-drone routing with adaptive fleet planning for heterogeneous monitoring tasks

卡车-无人机协同系统通过整合异质化监控任务，优化无人机类型与数量分配及卡车-无人机协同路径规划，建立混合整数规划模型并设计自适应大型邻域搜索算法，有效降低运营成本并提升系统效率。

　　

沈文佳|郑振杰|王正立|周静|杨海

美国纽约大学坦登工程学院土木、城市与环境工程系C2SMART中心，纽约布鲁克林

摘要

卡车-无人机同步系统为各种监测任务提供了一种有前景的解决方案。然而，现有研究通常假设任务特性是均匀的，并采用预定义的卡车-无人机车队配置，其中无人机被固定分配给卡车。这样的假设可能无法准确反映现实世界的情况，在现实世界中，异构监测任务非常普遍，而且往往需要配备特定功能设备的不同类型的无人机。实际上，忽视这种异构性可能会导致冗余的物流操作和系统效率降低。为了解决这一限制，我们开发了一个混合整数规划（MIP）模型，用于卡车-无人机同步系统，该模型考虑了异构监测任务。所提出的模型共同优化了两个关键决策，以最小化总运营成本：决定分配给每辆卡车的无人机类型和数量，以及确定卡车和无人机的路线以完成异构任务。为了高效解决大规模实例，我们开发了一种定制的自适应大邻域搜索（ALNS）算法，并加入了特定于问题的操作符。数值实验表明，所提出的模型不仅有效地适应了任务异构性，而且性能优于基于预定义卡车-无人机车队配置的经典方法。此外，ALNS算法在生成大规模实例的近似最优解方面表现出令人满意的计算效率。

引言

卡车-无人机同步系统在各种监测任务中展示了巨大的潜力（Zhou等人，2023年）。在这种系统中，卡车充当移动仓库，负责携带、发射和回收无人机，并提供电池更换服务（Chung等人，2020年）。无人机则执行专门的监测任务，利用其飞行能力进入目标区域、收集高分辨率数据并在危险环境中操作。此外，无人机可以自主选择直接路线到达目的地，从而降低劳动力成本并提高监测系统的安全性和效率（Momeni等人，2022年；Zeng等人，2022年）。通过结合卡车和无人机的优势，该系统能够在更广泛的地理区域内实现有效监测，同时相比传统方法降低成本。

鉴于实际监测任务的多样性，例如输电线路检查、森林火灾监测、电力设施检查和空气质量监测等，解决任务异构性对于卡车-无人机同步系统至关重要（见图1）。具体来说，任务异构性涉及两个方面。首先，一些任务本质上需要地面检查和人工干预，这是无人机无法独立完成的。例如，室内检查或现场工作人员认证的验证仍然依赖于人类操作员，因为当前的技术限制（Einizinab等人，2023年）。其次，更重要的是，不同的监测任务需要配备特定任务设备的专用无人机（Hassanalian和Abdelkefi，2017年）。例如，用于输电线路检查的无人机通常配备高分辨率摄像头和激光雷达传感器，以检测结构缺陷和监测植被入侵（Rong等人，2020年）。相比之下，用于森林火灾预防的无人机依靠红外传感器和热成像相机来早期发现热量异常和烟雾（De Vivo等人，2021年）。鉴于现实世界应用中异构监测场景的复杂性和普遍性，采用允许卡车部署多种类型无人机的定制策略至关重要。这使得沿单一路线同时执行多样化任务成为可能，从而提高了监测系统的运营灵活性和效率。

尽管异构任务普遍存在，但大多数关于基于无人机的监测的研究都集中在统一的任务设置上（Liu等人，2023年；Luo等人，2019年；Momeni等人，2022年），对不同任务类型带来的多样化需求关注有限。我们根据卡车和无人机的角色，将相关研究大致分为两个流派。在第一种流派中，无人机是监测任务的主要操作单元，而卡车提供支持功能，如长途运输和电池补充。例如，Zeng等人（2022年）研究了单个卡车和无人机的同步，其中无人机执行所有任务。后来，Momeni等人（2023年）将这一框架扩展到多个卡车和无人机，用于难以到达的区域（如森林）的远程监测。然而，这种设置忽略了卡车和无人机之间的潜在任务异构性，导致卡车资源利用不足和系统效率降低。在第二种流派中，虽然卡车和无人机都参与任务执行，但所有无人机任务都被假设为同质的，并由单一类型的无人机处理。这种假设并不能准确反映现实情况，因为多样化的任务需要多种类型的无人机。例如，Tian等人（2022年）提出了一种卡车携带多种相同类型无人机执行复杂军事任务的方案，这些任务不太可能仅由相同的无人机有效完成。同样，建筑工地检查通常需要不同类型的无人机来适应不同的环境条件（Agnisarman等人，2019年）。配备数字相机的无人机适用于光线良好的条件下的危险检测，而配备激光传感器的无人机则对低光环境下的操作至关重要。此外，一些相关研究仅使用无人机执行监测任务（Chowdhury等人，2021年；Sun等人，2022年；Zhou等人，2023年）。例如，Zhou等人（2023年）利用无人机进行城市监测，并同时优化无人机路线和仓库位置，以提高运营效率。

在这项研究中，我们开发了一个混合整数规划（MIP）模型，以解决卡车-无人机同步系统中的异构监测任务并最小化总运营成本。具体来说，我们通过为每辆卡车分配适当类型和数量的无人机来确定卡车-无人机车队配置（即自适应车队规划）。此外，还优化了卡车和无人机执行监测任务的路线。这种卡车-无人机车队规划和路线的联合优化提高了系统的整体灵活性和效率。为了考虑任务异构性，我们制定了一组线性约束，以确保每个任务由特定类型的无人机或卡车执行。此外，还包括时间窗口约束和无人机电池限制，以描述运营限制。为了高效解决大规模实例，我们开发了一种定制的自适应大邻域搜索（ALNS）算法，并加入了特定于问题的操作符。通过在不同场景下进行的数值实验评估了所提出模型的有效性。结果证明了纳入任务异构性和联合优化的优势。此外，还进行了敏感性分析，以检查关键模型参数对系统性能的影响。本研究的主要贡献总结如下：

•

据作者所知，这是首次尝试将多种类型的无人机分配到异构监测任务中，将其纳入一个集成的卡车-无人机同步系统中；

•

与将卡车-无人机车队配置视为固定参数的现有研究不同，我们共同优化了自适应卡车-无人机车队规划和路线决策，以执行异构任务；

•

我们将异构监测问题表述为一个MIP模型，并开发了一种定制的ALNS算法来高效解决该模型；

•

在不同场景下进行了数值实验，以证明纳入任务异构性的好处以及所提出的联合优化的有效性。

本文的其余部分组织如下。第2节，我们回顾了基于无人机的监测和卡车-无人机同步系统的相关文献。第3节，我们介绍了模型构建，包括问题描述、目标函数和约束条件。第4节，我们详细介绍了带有特定于问题操作符的定制ALNS算法。第5节，我们进行了数值实验来验证我们的模型。最后，我们在第6节总结了讨论并概述了几个潜在的未来研究方向。

章节片段

文献综述

在本节中，我们分别在第2.1节和第2.2节回顾了基于无人机的监测的路线规划和卡车-无人机同步系统的现有研究。最后，在第2.3节讨论了现有研究的潜在局限性。

模型构建

在本节中，我们首先在第3.1节描述了问题并介绍了本研究中使用的符号。然后，在第3.2节和第3.3节分别详细介绍了我们模型的目标函数和约束条件。

定制的自适应大邻域搜索

在本节中，我们介绍了一种定制的ALNS算法（Sacramento等人，2019年；Zhou等人，2023年），该算法带有特定于问题的操作符，用于解决大规模实例。这些操作符用于激活和回收无人机、管理异构无人机任务匹配以及处理卡车和无人机操作之间的交互。算法1概述了ALNS的流程。算法首先生成一个初始解并初始化操作符权重。在每次迭代中，

数值实验

在本节中，我们首先在第5.1节介绍数据集和参数调整过程。接下来，在第5.2节评估了定制ALNS算法的性能。我们对Gurobi和ALNS获得的结果进行了比较分析，以评估解决方案的质量和计算效率。然后，我们介绍了在单个卡车中整合异构无人机的优势以及联合优化车队规划和路线的好处

结论

在这项研究中，我们提出使用卡车-无人机同步系统来解决异构监测任务，并联合优化车队规划和卡车-无人机路线，这是文献中的新方法。具体来说，我们构建了一个MIP模型，使用二进制决策变量来最小化系统成本。该模型共同优化了两个关键决策：（1）将无人机类型和数量分配给每辆卡车；（2）卡车和无人机的路线规划，以执行异构任务。

CRediT作者贡献声明

沈文佳：撰写——原始草稿、可视化、软件、方法论、调查、形式分析、数据整理。郑振杰：撰写——审稿与编辑、撰写——原始草稿、监督、方法论、调查、形式分析、概念化。王正立：撰写——审稿与编辑、监督、资源管理、方法论、调查、资金获取、概念化。周静：撰写——审稿与编辑、监督、资源管理、项目管理，

利益冲突声明

本手稿尚未在其他地方部分或全部发表，也没有被其他期刊考虑。我们已阅读并理解了您的期刊政策，并相信本手稿和研究内容没有违反任何这些政策。作者声明他们没有已知的利益冲突或个人关系可能影响本文报告的工作。