基于无人机运输的应急物流路径优化研究

摘 要：世界各地无时无刻不在发生着应急事件。在应急事件中，最关键的问题就是物流救援。而在应急物流中，车辆路径问题又是一个棘手问题，因此优化应急物流路径已迫在眉睫。文章以时间最短化为目标，考虑配送中心约束，客户点流量平衡，客户点服务约束，无人机重量约束，无人机航行距离约束，所需无人机数量约束等条件构建数学模型，引入模拟退火算法进行分析，旨在提高应急物流反应速度和运输效率，加强应急响应能力，降低应急物流成本，增强应急物流的安全性，同时探索新型应急物流运输方式，促进应急物流的优化和升级。最后通过案例仿真分析结果，证明文中所建模型及设计的算法对解决该类问题的有效性。

关键词：无人机；路径规划；应急物流；模拟退火算法；车辆路径问题

中图分类号：F252 文献标志码：A DOI：10.13714/j.cnki.1002-3100.2024.18.016

Abstract： The world is constantly experiencing emergency events， and in these situations， the most critical issue is emergency logistics and rescue operations. Within emergency logistics， vehicle routing issues poses a challenging problem， making emergency logistics path optimization an urgent necessity. This article aims to minimize response time， while considering constraints such as distribution center limitations， customer demand balancing， customer service constraints， UAV’s weight limitations， UAV’s flight distance constraints， and the required number of UAVs. A mathematical model is constructed to address these challenges. To achieve the optimization， a simulated annealing algorithm is introduced for analysis. The goal is to enhance the speed and efficiency of emergency logistics response， strengthen emergency response capabilities， reduce logistics costs， improve the safety of emergency logistics， and explore new modes of emergency transport. This research intends to promote the optimization and advancement of emergency logistics. Finally， the effectiveness of the proposed model and algorithm is demonstrated through case-based simulations， affirming their suitability for effectively solving this class of problems.

Key words： UAV; path planning; e1Zy760AIKBcYD191agQ22A==mergency logistics; simulated annealing algorithm; vehicle routing issues

0 引 言

随着社会经济的发展和人口的不断增长，各种自然灾害和突发事件频繁发生，给物流运输带来了巨大的挑战。作为一种全新的物流运输方式，无人机运输在应急物流中的应用受到了广泛的关注。无人机运输具有快速、高效、灵活、机动等优势，可以在短时间内将紧急物资送达受灾区域，有效提高应急物流的效率，减轻灾民的痛苦[1-2]。无人机运输在应急物流中有广泛的应用场景。然而，无人机运输在应急物流中的应用还面临着一系列的问题和挑战。例如无人机运输需要满足快速响应和高效运输的要求，但无人机当前的飞行高度、飞行速度、续航能力等仍有一定的局限。因此，对于无人机运输的应急物流路径规划研究显得尤为重要，它能够为无人机运输提供科学的理论基础和技术支持，使其能够更好地应用于应急物流中，提高救援效率和救援质量，为灾民的生命和财产安全保驾护航[3-4]。本文所构建的模型及算法能有效地解决应急物流下的无人机运输路线问题，并且通过分析了解了最大载重量、最大航行距离以及时间窗惩罚系数对最优解的影响。为应急条件下无人机的运输路径优化问题研究提供了参考方向。本文的主要贡献：相比于传统的VRP问题，本文是基于无人机的运输，在运输条件上增加了无人机的续航这个约束条件以保证整个任务的顺利实施；在应急背景下，优化目标由传统VRP问题的成本最低转变为考虑人民生命财产安全的时间最短，并根据受灾情况的严重程度设置了配送节点的优先级。

1909年美国成功试飞无人机，一战期间，欧洲部分国家开始在相关技术领域取得突破，20世纪60年代美国开始将无人机用于军事用途，而在民用领域则稍晚一些，1983年，日本首先研发出了农用的喷洒型无人机，到现在经过几十年的发展，日本已在世界上农用无人机领域处于领先地位。2013年，亚马逊创始人提出了无人机物流送货的概念，随后谷歌、Facebook等互联网企业也相继提出无人机物流的发展意向及规划，但是由于美国对航空器领域的政策管控非常严，很多公司的发展方向遭受限制，只能在澳大利亚等国家进行试验。欧洲等一些国家随后相继提出了无人机物流的发展概念，随着时间的推移，目前欧洲在无人机领域也处于领先地位。在无人机运输中，路径规划是最重要的一环，刚开始的路径规划都是由人工完成，但随着环境的变迁和国家政策的逐步正规化，传统的路径规划技术已经满足不了现实情况的需求，计算机算法以及数学建模等热点模式逐渐被国际学者关注，取得了较多的研究性成果。如基于激素的生物启发式无人机路径规划算法研究、分布式多机器人路径规划算法研究等。在协调控制技术研究方面，国外无人机研究人员也取得了不少成果，为多机无人机协同路径规划提供了可靠的技术保障。在视觉计算技术研究领域，国外研究者通过利用基于视觉的无人机路径规划方法，实现了无人机在复杂环境中的智能化操作。其中国外Alraslan 等指出路径规划算法的目标是寻找从源位置到目标位置的最优路径，并提出了一种基于遗传算法的无人机实时路径规划器[5]。此方法不识别障碍物之外或障碍物之间的任何特定点，以解决无形路径的问题。此外，该方法不使用遗传算法中的额外步骤来处理由障碍物内部生成点或与障碍物相交的路径段产生的问题。Zammit等提出了针对复杂室内环境下的3D无人机路径规划问题，比较分析了两种最常用的基于图和基于采样的算法及其变体[6]。该分析的结果概述了方法的可用性，可以帮助未来的无人机路径规划设计者选择与具体应用相关的最佳参数配置的最佳算法。该项工作解决了A*和RRT标准算法的缺点，开发了一种新的A*纹波减少算法，一种新的RRT变体和一个专门设计的平滑算法。

国内的无人机领域研究则起步更晚，从某一方面来说，无人机产业目前在国内的蓬勃发展，与中国制造和中国的现代经济发展有着很大的联系，中国目前的民用无人机规模逐年上升，爆发式增长，尤其是在物流领域的应用，成为无人机的重点发展方向，其中大疆、京东、顺丰等无人机与物流企业走在国内发展前列，而对于无人机路径优化的研究，国内学者也做了许多研究，提出了许多新颖的见解和解决方案[7-9]。如基于M-GA的多无人机协同任务分配问题优化研究、基于强化学习的无人机路径规划算法研究等。在仿真技术领域，我国学者也取得了较大进展，如利用模糊逻辑控制和遗传算法对无人机路径规划进行仿真等。在飞行控制技术研究领域，我国无人机研究人员对飞行控制技术进行了深入研究，为无人机路径规划提供了可靠的技术保障。其中段聪（2022）提出了关于带有取送货的车辆路径问题，通过分析无人机调度的相关研究，结合无人机与卡车各自的特点， 选取了卡车作为无人机着陆和起飞平台的配送模式，探索了医药物流路径优化相关问题[10]。其主要思想是构建一个混合的整数模型，并以最短的配送时间为目标，在这个模型中，作者加入了车辆载量以及客户需求等约束条件，然后设计了无人机回收端邻域搜索算法并进行求解结果。作者还对一般传统的配送模式以及无人机配送模式进行了实验对比， 并且通过设计的模型去验证了算法。最后作者依据实际情况，选用了实际的数据，并选择了最短配送时间的目标参数，运用无人机回收端邻域搜索算法进行验证，实验结果表明，此算法确实有一定可靠性和合理性，为物流企业提供了发展借鉴的方向。鲁熙今（2022）提出的关于卡车-无人机协同配送路径优化问题是不同于传统车辆路径优化问题的一个新问题，它不是简单地着眼于卡车行驶路径，而是如何合理协调两种载运工具，使其实现降本增效的目标[11]。特别是在无人机可以在多个客户点起降、无人机飞行距离受到载重影响的现实条件下， 其复杂程度远远高于仅使用卡车进行物流配送的车辆路径问题。于是建立了以配送时间最短为目标，考虑无人机飞行距离受载重影响的混合整数规划模型，为卡车支持无人机配送问题（Carrier-Vehicle Problem with Drone，CVP-D）设计了以K-Means++聚类算法为基础的三阶段求解算法， 为飞行伙伴旅行商问题（Flying Side-kick Travelling Salesman Problem，FSTSP）设计了两阶段改进模拟退火算法， 利用车辆路径问题标准算例分别进行求解， 通过与单卡车配送进行对比， 验证了模型的有效性。最后，引入真实案例进行仿真实验， 验证两种配送模式在现实生活中的可行性， 定量分析了两种配送模式带来的实际效益，并通过灵敏度分析， 总结了两种配送模式分别适用的物流配送场景，对于提升卡车-无人机协同配送效果具有一定的参考价值。陈存粮（2021）提出在低密度人口地区， 如贫困乡镇或偏远山区，对相关配送问题求解[12]。

求解思路主要是将人口密度较低的地区划分为若干个配送区域，每个区域内的配送距离相对较短且配送点数量较少，利用无人机进行配送。在这个过程中，他主要采用以下思路：第一，采用多点依次配送策略：将一个配送区域内的多个客户点按照距离远近排序，然后依次使用无人机进行配送。这种策略可以有效地减少每次配送的距离和时间，提高无人机的配送效率。第二，使用混合整数规划模型优化配送路径：针对多点依次配送策略，建立混合整数规划模型，通过对无人机配送路径的优化，进一步降低配送时间和成本。第三，使用无人机-卡车协同配送模式：对于人口密度较低的地区，采用无人机进行配送。而对于周边密度适中的地区，则采用卡车进行中转，实现无人机和卡车的协同配送。这种配送模式可以在提高配送效率的同时，保证配送的及时性和准确性。第四，利用配送网络进行路径优化：建立基于高精度地图的配送网络，通过对网络优化算法的应用，实现无人机路径的优化和配送的实时监控，提高配送效率、准确性和安全性。以上思路的综合应用可以有效地解决低密度人口地区的相关配送问题，提高无人机配送的效率和效益。谢关淑（2021）提出关于应急物流下的无人机与卡车协同配送路径优化问题[13]。

求解思路主要是将无人机和卡车进行协同配送，以提高应急物流的配送效率和应对突发事件。具体思路如下。第一，建立综合配送模型：设计基于混合整数规划的综合配送模型，将无人机与卡车进行协同配送，以最小化总配送成本为目标。第二，采用模拟退火算法进行路径规划：建立无人机和卡车的路径规划模型，并采用模拟退火算法进行路径优化。该算法可以在保证较好解的质量的前提下，避免陷入局部最优解。第三，考虑配送路径的实时变化：在实际应急物流场景下，配送路径会因为不断变化的事件而发生调整。因此，需要在模型中考虑路径的实时变化，以保证路径的稳定性和可靠性。第四，针对不同应急事件制定不同应对方案：在不同应急事件下，无人机和卡车的协同配送方案也需要发生改变。因此需要根据不同的应急事件制定不同的应对方案，以提高应急响应能力。以上思路的应用可以有效提高应急物流配送的效率和效益，同时也可以应对突发事件，提高应急物流的快速响应和迅速解决问题的能力。

1 应急物流路径优化问题数学模型

构建基于无人机运输的应急物流路径优化模型。

1.1 问题描述

在某场突发事件（如地震、山洪、火灾等）发生后，需要尽快将必要的物资和救援队伍送往事故现场进行救援。假设有一批无人机可以用于货运运输，每架无人机拥有相同的货运能力、速度、续航能力等特点。现在需要确定合适的无人机运输路径，保证救援物资和队伍能够在最短的时间内到达事故现场[14]。假设航空交通拥堵和天气等因素不会对无人机运输路径造成太大的影响，现在需要设计一个基于无人机运输的应急物流路径优化问题的模型。要求如下。

确定无人机运输路线，使得时间最短；根据货运能力确定无人机任务分配的策略，使得货物能够得到最大化的使用；保证无人机能够在有限的续航范围内完成运输任务；避免无人机碰撞，以及其他安全问题；保证受灾严重的地区优先得到物资配送。

问题中需要确定以下内容。

解决思路可以采用模拟退火算法对运输路径进行优化设计，通过设定初始参数，调整搜索范围，降低温度等一系列策略，一步步优化无人机的运输路径。同时，还需要考虑无人机的负载均衡问题、货运安全问题以及调度算法的复杂度问题等。

1.2 模型假设

第一，假设使用的载物无人机之间具有相同的最大安全航行距离，并且在整个航行过程中保持速度不变，不考虑气候、国家政策等禁飞约束。 第二，无人机从配送中心出发去服务目标点，配送任务结束后回到起始点。第三，每个客户的包裹只能由一架无人机运送一次完成配送。 第四，无人机可以一次对多个顾客节点进行送货，且每一次飞行都需要满足无人机的载重和最远飞行距离的限制。第五，无人机的使用数量没有限制。 第六，所有无人机的型号一样，不考虑交通堵塞。

1.3 模型中符号和决策变量（见表1）

1.4 模型建立

2 模型求解

本文模型是基于模拟退火算法进行，算法通过一系列的迭代过程来搜索更优的解。在每一次迭代中，根据当前温度和邻域解的差异程度，决定是否接受新的解。这一步是模拟“退火”的过程，随着温度的降低，算法更趋向于接受使目标函数减小的解，但也有可能接受使目标函数增大的解，以避免陷入局部最优解。随着迭代的进行，温度逐渐降低，搜索空间逐渐缩小，最终在一定条件下终止迭代过程。最终得到的解是算法在搜索过程中找到的最优或次优解。

模拟退火算法（Simulated Annealing Algorithm）是一种启发式优化算法，用于寻找非全局最优解的复杂优化问题。它最初由Kirkpatrick、Gelatt和Vecchi在1983年提出，后进行了进一步的研究和改进。模拟退火算法模拟了冶金中物质从高温状态到低温状态的冷却过程，利用随机性和概率接受策略来跳出局部最小值，并最终找到全局最优解[16-17]。图1为退火算法的工作流程图。

3 仿真实验

3.1 实验设计

3.2 影响参数分析

由上述实验可知，模拟退火算法能有效求解模型，且不同参数对于结果的影响较大，下面我们通过对无人机载重量、无人机最大航行距离以及违反最晚时间窗约束的惩罚函数系数来分析不同参数对实验结果的影响。

无人机载重量：保持其他参数不变，设立不同的无人机载重量。结果表明，随着无人机载重量变大，每辆无人机的装载率会显著变小。当无人机的最大载重量小于路径上所有客户需求量总和时，每辆无人机的装载率已经大于100%，说明无人机已经无法完成配送任务，而最终的总成本变化趋势图也表明，总成本没有收敛到最小，优化目标无法完成。而当无人机的最大载重量远大于路径上的所有客户点需求量总和时，大部分无人机的装载率还没到50%，过大的无人机载重量会导致无人机性能的浪费，造成经济效益偏低，实验得到的数据见表4。

无人机最大航行距离：保持其他参数不变，设置不同的无人机最大航行距离。结果表明，随着无人机最大航行距离的变大，无人机的装载率以及航行距离都会受到影响。当无人机最大航行距离小于路径长度时，必须增大一部分无人机的装载量以及路径长度以满足任务需求。而此时部分无人机的实际航行距离已经大于最大航行距离，所以无法完成优化目标。当无人机最大航行距离远大于路径长度时，无人机的装载率以及航行距离基本不受影响，但会浪费无人机性能，造成经济效益偏低。结果见表5。

违反最晚时间窗约束的惩罚函数系数：保持其他参数不变，设置不同的违反最晚时间窗约束的惩罚函数系数。结果表明，当违反最晚时间窗约束的惩罚函数系数小于违反容量和距离约束的惩罚函数系数时，相当于容量和距离约束更重要。其优化目标更偏向于容量和距离约束，最优路径基本变化不大，在实际情况中可能会造成部分受灾严重的灾民无法得到及时的救援。当违反最晚时间窗约束的惩罚函数系数大于违反容量和距离约束的惩罚函数系数时，相当于最晚时间窗约束更重要，优化目标更偏向于时间窗约束，最优路径会更偏向于节点优先级。实验结果如表6所示。

所得的全局最优解表格说明，最终配送路径均满足约束条件，全局最优解总成本变化趋势图说明，本文所设计的算法能有效达到优化目标，降低成本（此成本是指最后一辆无人机回到配送中心时间和违反时间窗所产生的惩罚成本之和），通过对无人机最大载重量、最大航行距离的约束，保证了无人机的载重量以及续航时间，通过对配送节点优先级设置时间窗惩罚成本，保证了受灾严重的地区优先得到配送，且收敛速度较快（整个计算所用时间大约为13.54s），验证了算法的有效性。

4 结 论

本文得到的主要结论如下。

首先，相比于传统的VRP问题，本文是基于无人机的运输，在运输条件上增加了无人机续航这个约束条件以保证整个任务的顺利实施。

其次，在应急背景下，优化目标由传统VRP问题的成本最低转变为考虑人民生命财产安全的时间最短，并根据受灾情况严重程度设置了配送节点的优先级。

最后，设计了仿真实验以验证算法的有效性，有效解决了基于无人机运输的应急物流路径优化问题，并对影响参数进行了研究，分析了最大载重量、最大航行距离以及违反时间窗惩罚成本函数系数对最优解的影响，对实际情况中具体参数的设计以及无人机的实际选择具有一定借鉴意义。

参考文献：

[1] 费毓晗，张洪海，张连东，等．城市物流无人机运输路径规划[J].武汉理工大学学报（交通科学与工程版），2023，47（1）：79-84，89.

[2] 谷金蔚，刘旭．无人机物流分析与应用研究[J]．科技资讯，2018，16（18）：11-123.

[3] 王琳璘．H物流公司车辆路径优化问题研究[D]．广州：广东工业大学，2022.

[4] 孙亚强．H企业物流配送中心选址及路径优化问题研究[D]．济南：山东财经大学，2022.

[5] ALRASLAN M，ALKURDI A H．UAV path planning using genetic algorithm with parallel implementation[J]．InternationalJournal of Computational Science and Information Technology，2022，10（2）：1-15.

[6] ZAMMIT C，VAN KAMPEN E．Comparison between A*and RRT algorithms for 3D UAV path planning[J]．UnmannedSystems，2021，10：129-146.

[7] 陈亮．农村地区无人机配送选址及路径规划研究[D]．北京：北京信息科技大学，2022.

[8] 郭文静．多目标粒子群算法的研究与应用[D]．东莞：东莞理工学院，2022.

[9] 张硕航．基于改进蚁群混合算法的末端物流路径优化研究[D]．呼和浩特：内蒙古师范大学，2022.

[10] 段聪．基于无人机与卡车联合配送的医药物流路径优化研究[D]．沈阳：沈阳工业大学，2022.

[11] 鲁熙今．卡车-无人机协同配送路径优化模型与算法[D]．兰州：兰州交通大学，2022.

[12] 陈存粮．无人机末端物流配送算法研究[D]．西安：西安电子科技大学，2021.

[13] 谢关淑．考虑应急物流需求等级的无人机与卡车协同配送路径优化问题研究[D]．成都：西南交通大学，2021.

[14] 黎聪，谢莉．物流无人机技术在广西农村配送的可行性研究及实际应用[J]．物流工程与管理，2022，44（9）：31-33.

[15] 林巧珍．带时间窗约束的医药协同配送路径优化研究[D]．厦门：厦门理工学院，2022.

[16] 苗苗．具有禁飞区条件的无人机群路径规划研究[D]．西安：长安大学，2021.

[17] 许卫卫．复杂低空物流无人机路径规划技术研究[D]．南京：南京航空航天大学，2020.

[18] 杨沙．考虑动态需求的冷链物流配送路径优化研究[D]．沈阳：沈阳工业大学，2022.

[19] 罗娟．物流末端“车辆-无人机”协同配送路径优化研究[D]．重庆：重庆邮电大学，2022.

[20] 王家杰．基于时间窗的M公司生鲜产品物流配送路径优化研究[D]．上海：东华大学，2022.