在存在禁飞区的连续空间中，针对电动垂直起降飞机（eVTOL）和无人机配送系统的路径优化：一种强化学习方法

《TRANSPORTATION RESEARCH PART E-LOGISTICS AND TRANSPORTATION REVIEW》：Routing optimization for an eVTOL-and-drone delivery system in continuous space with no-fly zones: A reinforcement learning approach

本文提出了一种混合整数二阶锥规划模型和强化学习方法，用于优化电动垂直起降飞行器与多架无人机的协同配送路径，有效规避禁飞区并减少总配送时间。实验表明，强化学习方法在复杂障碍环境中显著优于基线方法。

　　

刘少军|余一彤|田青云|孙慧军

南洋理工大学土木与环境工程学院，南洋大道50号，639798，新加坡

摘要

电动垂直起降（eVTOL）飞行器与无人机的结合为城市环境中时间敏感的最后一公里配送问题提供了有前景的解决方案。本文研究了一个在连续二维空间中的新型路径优化问题，其中一架eVTOL母机搭载多架无人机进行包裹配送。挑战在于优化母机的飞行轨迹，以高效协调无人机的派遣和回收，同时避开指定的禁飞区——这些禁飞区可能是对大型eVTOL的监管或物理障碍。我们将问题表述为在离散时间和连续空间上的混合整数二阶锥规划（MISOCP）模型，目标是最小化总体配送时间，即所有包裹被送达且所有无人机被回收所需的时间。鉴于求解MISOCP模型的计算负担较大，我们开发了一个强化学习（RL）框架来学习有效的路径策略。由于在最小配送时间内eVTOL的飞行轨迹可能存在多种方案，因此引入了一种基于可视图的后期处理方法，在尊重禁飞区约束的同时优化eVTOL的路径。实验结果表明，所提出的RL方法能够有效协调eVTOL及其无人机，并且在具有复杂障碍物的环境中显著优于基线方法。

引言

近年来，自动化及相关技术的快速发展极大地加速了无人机系统的开发和应用。无人机现已广泛应用于物流、基础设施检查、农业和公共安全等领域（Chung等人，2020年；Otto等人，2018年）。随着市场对基于无人机的物流服务的兴趣日益增长，亚马逊、谷歌、UPS、DHL和SF Express等大型公司都推出了研究项目，探讨使用无人机进行在线订单最后一公里配送的可行性和效率（Huang等人，2024年；Poikonen和Golden，2020年）。由于无人机的飞行范围和载荷能力有限，它们通常与卡车、船舶或航空器等大型运输平台结合使用，共同完成配送任务（Poikonen和Golden，2020年）。

大量研究集中在卡车与无人机协同配送系统上，探讨其运营效率和协调策略（Agatz等人，2018年；Murray和Chu，2015年；Ulmer和Thomas，2018年）。然而，由于卡车受限于道路网络，其性能受到道路基础设施和交通拥堵的影响，这给快速可靠的配送带来了挑战。这一限制促使人们探索更灵活的空中运输平台，如大规模的eVTOL，它们不受地面交通限制。与传统的地面车辆和直升机相比，eVTOL具有多个优势，包括垂直起降能力、低排放的电动推进系统以及在连续空间中机动的能力（Holden和Goel，2016年；Ratei等人，2023年）。这些特性使它们特别适合作为城市环境中协调无人机操作的移动基地。与依赖现有道路连接和节点的卡车与无人机系统不同，eVTOL与无人机系统可以在连续空间中的任意位置进行无人机投放和回收，从而减少行驶距离并提高运营灵活性。这种扩展的空间自由度大大增加了解决方案的空间，为提高效率创造了机会，同时也带来了轨迹规划、同步和合规性方面的新挑战。

最近出现了关于空中母机与无人机协调的正式研究（Amorosi等人，2021年；Amorosi等人，2023年；Poikonen和Golden，2020年），在这些研究中，两种类型的飞行器在连续空间中协同工作，母机负责在灵活的位置投放和回收无人机。然而，这些研究依赖于以事件为中心的建模方法，仅确定了无人机的投放和回收点。实际上，大规模eVTOL在飞行过程中可能会面临各种飞行限制——尤其是在城市环境中，这些限制通常由物理障碍物和监管约束（称为禁飞区）引起（Kamal等人，2023年；Mattei和Blasi，2010年）。由于以事件为中心的模型不优化母机在整个时间内的完整飞行轨迹，它们可能产生无意中穿越限制区域的解决方案。

为了明确纳入禁飞区约束，本研究开发了一个基于时间的数学框架，该框架同时确定每个时间步长内eVTOL母机的位置和多次无人机派遣的调度，目标是在操作约束下最小化总配送时间。与仅确定无人机投放和回收位置的基于事件的方法不同，所提出的模型能够连续跟踪eVTOL的飞行轨迹，从而精确避开禁飞区。为了模拟eVTOL与无人机之间的协调，我们首先构建了一个离散时间、连续动作的模型，在该模型中，eVTOL的位置由每个时间步长的连续坐标表示。这种表述方式提供了对系统动态的细致和灵活的描述，为现实环境中的轨迹规划提供了高保真的基础。然而，由于连续和高维的决策空间，使用传统优化技术求解该模型在计算上是不可行的。为了缓解这一挑战，我们构建了一个离散时间、离散动作的模型版本，在该模型中，eVTOL的运动由一组有限的动作（例如方向-速度组合）来表示。这种离散化降低了决策空间的复杂性，并为强化学习（RL）奠定了基础。鉴于为这种复杂和动态的环境设计显式优化算法的难度，RL提供了一种数据驱动的替代方案：智能体通过与离散动作模型定义的环境互动，通过试错学习有效的控制策略，特别适合eVTOL与无人机配送问题中固有的顺序决策过程。

本文的其余部分安排如下：第2节详细回顾了相关文献。第3节介绍了所提出的数学模型：离散时间连续空间模型和离散时间离散动作模型。第4节介绍了为解决可扩展性问题而开发的强化学习框架。第5节报告并讨论了计算结果。最后，第6节总结了本文并指出了未来研究的方向。

章节摘录

文献综述

由于无人机辅助系统在物流、监控、应急响应和基础设施检查等广泛应用中的多功能性和适应性，它们吸引了越来越多的研究兴趣（Betti Sorbelli，2024年）。在本节中，我们回顾了相关文献，重点关注两种主要的系统架构。第一种是卡车与无人机系统，其中地面车辆遵循预定义的道路网络并与无人机协调完成任务。第二种是

问题描述

本章介绍了在存在禁飞区限制的城市环境中eVTOL与无人机配送问题。图1展示了所提出的eVTOL与无人机配送系统的架构。eVTOL作为空中母机，从中央仓库出发，遵循预定轨迹飞行，同时避开指定的禁飞区，并充当多架无人机的运输工具和回收平台。当eVTOL接近包裹所在位置时，会释放一架无人机

解决方案

上述优化模型构成了一个混合整数二阶锥规划（MISOCP）问题，因为存在欧几里得范数约束（例如速度限制和无人机飞行范围）以及二进制决策变量（例如配送分配和优先级约束）。特别是，矩形禁飞区通过时间索引的Big-M析取约束来强制执行，确保eVTOL在每个时间步长内始终位于每个限制区域之外。

实验设置

为了评估所提出模型和算法的性能，我们在不同需求规模的方形服务区域内进行了数值实验。小规模实例主要用于验证模型的正确性并比较精确方法和RL方法的解决方案质量，而中等和大规模实例用于检验RL的可扩展性。此外，还引入了一种优先投放的贪婪启发式方法（见算法2）作为基线方法，该方法优先考虑投放

结论

本研究探讨了如何协调eVTOL飞行器与多架无人机进行最后一公里配送的问题，结合了精确优化模型和强化学习（RL）。提出了两种模型：离散时间连续空间模型（DCm）和离散时间离散动作模型（DDm）。虽然DCm提供了理论上的精确表示，但DDm通过离散化速度和方向选择，使得RL的应用成为可能。

数值实验验证了几个关键点

CRediT作者贡献声明

刘少军：撰写——原始草稿、软件、方法论、概念化。余一彤：撰写——审阅与编辑、方法论、形式分析。田青云：撰写——审阅与编辑、方法论、概念化。孙慧军：撰写——审阅与编辑、验证。

利益冲突声明

作者声明他们没有已知的财务利益或个人关系可能影响本文报告的工作。