灾后应急救援背景下卡车-无人机协同配送路径规划

摘要：无人机因其具有不受道路条件和交通拥堵影响的特点而被应用于物流配送，因此针对灾后道路损毁严重，卡车无法及时配送救援物资的问题，提出利用“卡车-无人机”协同配送的模式进行救援物资的配送。文章对多辆卡车多架无人机灾后协同配送物资的路径规划问题进行了研究，考虑到受灾群众对救援物资的需求紧迫性，受灾群众满意度会随着救援物资送达时间的延长而降低，因此以最大化受灾群众满意度为目标建立了卡车-无人机协同物资配送模型，并使用了自适应大邻域搜索算法对模型进行求解。最后，通过卡车-无人机协同配送和卡车单独配送两种情况下的对比实验验证了无人机在灾后救援物资配送中的有效性。关键词：无人机；自适应大邻域搜索算法；路径规划；应急救援0

引

言近年来，全球生态环境发生急剧变化，自然灾害频发，因此，做好灾后应急救援，尽最大可能挽救人民群众的生命和财产安全显得尤为重要。以洪涝灾害为例，我国是世界上洪涝灾害多发频发的国家之一，造成过极大的人员伤亡和经济损失。卡车因为具有承载量大、配送范围广的优势，已被广泛应用于灾后救援物资配送过程中，但是由于卡车自身的运输要求，在洪涝灾害等会对道路产生破坏的情况下，道路情况会对卡车配送救援物资产生限制，降低救援效率，因此需要寻找新的技术克服这一难题。随着技术的不断发展，无人机已经被应用于执行救援任务，能够明显缩短救援时间，提高救援效率，尽可能的挽救更多人的生命。2008年汶川地震后，政府派出无人机队伍收集灾区情况，提高搜索效率。2021年郑州洪涝灾害中使用了无人机进行通信指挥为群众运送救援物资[1]。2023年北京汛情中，政府派出无人机给被困群众配送救援物资，以快速响应救援需求，应对复杂的抗洪救灾环境。随着技术不断成熟，无人机的应用领域不断扩大。京东、顺丰、阿里巴巴、亚马逊等公司都已经开通了无人机物流配送业务，美团也将无人机应用在外卖配送服务中，以降低“最后一公里”带来的高昂成本。随着越来越多的企业将无人机应用于实际，很多学者都开始在无人机配送方面展开研究。由于电池容量的限制，无人机一般只能配送距离配送中心较近的节点，当存在距离配送中心较远的节点时，一般采用卡车和无人机协同配送的模式。Murray等[2]首先提出了两个最后一公里交付问题，都只涉及一辆卡车和一架无人机，且目标函数都是最小化卡车或无人机到达仓库的最晚时间。FSTSP为飞行伙伴旅行商问题，当卡车到达客户点时，无人机从卡车上起飞为另一位客户服务，随后在仓库或另一位客户的位置返回卡车；第二个问题为并行无人机调度旅行商问题，这一问题中，卡车和无人机分开进行配送，无人机只能从仓库起飞和降落。Murray等[3]对FSTSP问题进行了扩展，研究了使用一辆卡车和多架无人机进行交付的mFSTSP问题，设定无人机只能从仓库或卡车发射，并且发射和降落节点不能为同一节点，使得卡车或无人机返回仓库的最晚时间最小。Saleu[4]等研究了多无人机多卡车的并行无人机调度问题，问题中使用了多架无人机和多辆卡车为客户提供服务，但限定无人机只能在仓库和客户之间往返，卡车和无人机的配送活动相对独立。Wang等[5]以最小化总成本为目标，提出了多辆卡车和多架无人机的路径优化问题，问题中提出了无人机中转节点用于存放和维护无人机，无人机可以从任意节点起飞，但只能降落在中转节点或仓库，不能在客户节点处降落。Dukkanci等[6]提出了范围受限的最小化能量消耗的无人机交付问题，在该问题中卡车主要起到调度无人机的作用，不对客户提供配送服务，卡车从仓库出发，将无人机和包裹运输到无人机发射点，无人机在客户和发射点之间往返，向客户进行最后一英里的交付，目的是使总成本最小。Dayarian等[7]研究了无人机提供补给的车辆路径问题，问题中无人机不直接对客户提供配送服务，而是被当作一个向卡车补货的工具，以满足顾客最新下达的当天送货上门的订单。Kuo等[8]研究了考虑碳排放的无人机车辆路径问题，通过卡车的行驶距离和无人机的放电过程计算总的碳排放量，通过对配送路线的设计和优化，最小化总的完工时间和碳排放量。Yang等[9]考虑了交通情况不确定性的条件，为了减轻由于交通拥堵不能按计划为客户提供服务的风险，想要找到一条鲁棒路径，使得服务获得的利润最大。在关于应急救援的优化研究方面，许钢焱等[10]研究了单一卡车和无人机的应急响应策略和调度优化，以最小化所有应急需求的响应时间为目标，决策卡车与无人机的调度方案。Liu等[11]考虑了救援行动中的投入和产出因素，引入了DEA模型度量救援效率，并以最大化救援效率为目标对救援路径问题进行了研究。Alinaghian等[12]以最小化到达最后一个临时救援中心的时间为目标，对临时救援中心的选址和救援无人机的路径进行决策。Jiao等[13]将不同的救援任务根据重要性分配权重，以电车为救援车辆，研究了救援车辆如何在能量受限的情况下快速高效地执行多个救援任务，最大化所执行救援任务的总权重。Wang等[14]以未满足需求的总惩罚成本和被满足需求点的等待成本最小为目标，研究了灾后应急资源分配和车辆路径规划问题。基于以上研究发现，研究灾后卡车和无人机协同配送物资的问题较少，并且与应急救援相关研究的优化目标很少考虑到受灾群众对物资送达时间的满意程度，进而很少有问题将节点的满意度最大作为最终的目标。因此本文以洪涝灾害后的应急救援为背景，提出了一个多卡车多无人机的灾后救援物资配送问题。根据道路受损情况和受灾群众对物资需求的紧急程度对卡车和无人机的配送路线进行规划，在给定时间窗口内满足所有受灾群众的需求条件下，使得受灾群众满意度最高。在本文的问题中，随着配送时间的延长，受灾群众的满意度会不断降低，并且由于节点的受灾严重程度不同，不同的节点的满意度降低速度也不同，与Yu等[15]研究中的收益递减模式相似，因此本文参考了Yu等[15]在研究收益递减的鲁棒团队定向问题时提出的随到达时间递减的线性函数，构建满意度递减函数计算每个受灾节点处物资送达时的满意度，通过合理安排卡车和无人机的配送路线，尽快将受灾物资送达各个受灾节点，满足受灾群众的救援物资需求，最大化受灾群众的满意度。1

问题建模1.1

问题描述洪灾发生后，政府派遣卡车和无人机联合进行物资的配送，为多个受灾点提供救援物资配送服务。由于存在道路损毁问题，卡车无法对一些受灾点提供服务，因此需要用无人机进行配送。考虑在灾后救援情况下，最重要的是能够及时将救援物资送达，满足受灾群众对救援物资的需求，因此，本文将优化目标定为寻找最优的卡车和无人机路径规划方案，使得救援物资配送获得的受灾群众满意度最高。问题考虑多辆卡车和多架无人机，包含3种类型的节点：配送中心、卡车配送节点和无人机配送节点。无人机配送节点是由于灾后道路损坏需要由无人机配送物资，卡车配送节点的道路没有被损坏，直接由卡车配送物资。在配送过程中，每辆卡车可以携带多架无人机从整个受灾区域的指挥中心同时出发，当卡车到达某一需求点进行配送时，无人机可以从卡车上起飞进行救援物资的配送，由于存在续航里程的约束，无人机一次只能访问一个受灾点，与此同时，卡车可以沿着配送路径继续对其他受灾节点进行配送。无人机完成物资配送任务后返回同一辆卡车，返回的位置必须是在受灾点处或指挥中心。直至所有受灾点的物资都配送完毕，卡车携带无人机一同返回指挥中心。无人机也可以直接从指挥中心起飞，为一个受灾节点配送物资后再返回指挥中心。卡车-无人机路径示例如图1所示。灾后救援的情况下，受灾点对物资的需求更加紧急，受灾群众的满意度随物资送达时间的延长呈线性递减。设定群众的最大满意度为，为受灾点处的满意度递减率，每个节点的满意度递减率不同，卡车或无人机的物资送达时间为，基于以上设定构建的满意度模型为：fi（ai）=pi-diai，0≤ai≤Di，其中Di表示受灾点的物资最晚送达时间，所有受灾点的物资都必须要在最晚送达时间的区间内送达。问题假设如下。a.卡车和无人机都是同质的；b.每辆卡车的起点和终点相同，都是指挥中心，途中不返回；c.每个受灾点只能由卡车或无人机配送一次；d.考虑到受灾群众必须都要拿到物资，因此所有受灾点的需求都要在给定的时间窗内得到满足；e.每个受灾节点配送物资的重量均满足无人机的载重量约束；f.每辆卡车线路上装载的所有物资的总重量不超过卡车的最大容量；g.无人机飞出和返回卡车的地点均为卡车可配送的受灾点或指挥中心；h.卡车和无人机在受灾节点的服务时间忽略不计；i.各个节点之间的距离采用欧氏距离计算；j.无人机的飞行速度恒定，不受重力等其他因素的影响；k.无人机的最大飞行时间不受外界因素的影响；l.无人机每次起飞执行配送任务均为满电量，并且满足无人机从卡车起飞到返回卡车这段路程需要的电量。1.2

数学模型模型符号定义如表1所示。根据问题描述，建立的卡车-无人机协同物资配送模型如下。目标函数（1）是最大化受灾群众对政府物资配送服务的满意度。约束（2）确保每个受灾点只能被配送一次物资。约束（3）和（4）确保每辆卡车离开、返回指挥中心仅一次。约束（5）和（6）是流量守恒约束，即当卡车或无人机到达一个受灾节点配送物资时，卡车或无人机必须要从这个受灾节点离开。约束（7）和（8）是子环消除约束。约束（9）是卡车容量约束，即装载到一辆卡车的无人机配送物资的重量和卡车配送物资的重量之和不能超过卡车的最大载荷。约束（10）和（11）确保卡车和无人机的初始时间为0。约束（12）是卡车时间约束，计算两个节点之间的卡车行驶时间。约束（13）是无人机时间约束，计算两个节点之间无人机的飞行时间。约束（14）和（15）是卡车和无人机的同步约束，确保在无人机起飞节点和降落节点处，卡车的到达时间不晚于无人机的到达时间，这两个约束针对的是受灾节点处，当卡车和无人机分别返回指挥中心时不需要同步。约束（16）要求无人机起飞节点处的物资必须由装载该无人机的卡车进行配送，即如果卡车上的无人机在节点离开卡车去给受灾节点配送物资，则节点必须由卡车配送物资。约束（17）要求无人机降落节点处的物资必须由装载该无人机的卡车进行配送，即如果卡车上的无人机在给受灾节点配送物资后在节点处返回卡车，则节点必须由卡车配送物资。约束（18）和（19）是时间窗约束，确保每个受灾点的物资在最晚时间前送达。约束（20）和（21）是对变量取值的约束。2

求解算法本文建立的模型是一个NP难问题，很难通过传统优化方法快速有效地求解，并且精确算法在大规模算例中没有明显优势，因此本文采用了启发式算法对问题进行求解。大邻域搜索算法是经典的启发式算法，并且已经被成功地应用于求解多种车辆路径问题。自适应大邻域搜索算法在邻域搜索算法的基础上加入了自适应的机制，能够根据搜索算子的历史表现选择好的邻域搜索算子，从而提高找到质量更高解的概率[16]。本文针对卡车-无人机协同物资配送模型，提出了改进的自适应大邻域搜索算法对其进行求解。算法流程如图2所示。2.1

解的描述和初始解生成卡车-无人机协同物资配送模型的解由卡车路径和无人机路径两部分组成。如图3所示，卡车路径部分，每条卡车路径的起点和终点都是指挥中心，中间从左到右依次为卡车配送的受灾节点；无人机路径部分，每条无人机路径由每辆卡车上每架无人机的路径组合而成，每架无人机的路径都依次包含3个节点：无人机起飞节点、无人机配送节点和无人机降落节点，其中无人机起飞节点和无人机降落节点都是对应卡车路径中的卡车配送节点或指挥中心。针对初始解生成，本文采用了随机生成的方法分两阶段生成初始路径。第一阶段针对由卡车配送物资的受灾点建立卡车路径解决方案；第二阶段在第一阶段生成的卡车路线的基础上，针对由无人机配送物资的受灾节点，确定每架无人机的起飞节点和降落节点，生成无人机路径。2.2

邻域搜索算子本文使用了3个破坏算子和3个修复算子构造邻域解，在每次迭代时使用轮盘赌的方式选择使用的破坏算子和修复算子。2.2.1

随机破坏算子该算子从当前解决方案中随机移除2个卡车节点和2个无人机节点，其中对无人机节点进行移除时，要在无人机路径中同时移除与该无人机节点相关联的起飞节点和降落节点。2.2.2

贪婪破坏算子该算子将当前解决方案路径中的所有受灾节点依次移除、插入，并记录使受灾群众满意度变化最大（即增加最多）的节点。依次找到2个卡车节点和2个无人机节点并移除。对无人机节点进行移除时，要在无人机路径中同时移除与该无人机节点相关联的起飞节点和降落节点。2.2.3

相关性破坏算子该算子首先从当前解决方案中随机选择1个卡车节点移除，之后根据其他受灾节点与该节点的相关性，选择与该节点相关性最强的1个卡车配送节点和2个无人机配送节点移除。对无人机节点进行移除时，要在无人机路径中同时移除与无人机节点相关联的起飞节点和降落节点。2.2.4

随机修复算子对于每一个移除的卡车节点，该算子随机选择一条卡车路线，在满足卡车载荷约束和时间窗约束的条件下，将该移除节点插入此卡车路线中；对于每一个移除的无人机节点，该算子也随机选择一条卡车路线，在满足卡车载荷约束和时间窗约束的条件下，找到并确定与该无人机节点相关联的起飞节点和降落节点，并将起飞节点、受灾节点和降落节点插入到对应的无人机路线中。2.2.5

贪婪修复算子对于每一个移除的卡车节点，该算子将每个移除的卡车节点循环放入卡车路径中的所有位置，并记录使受灾群众满意度变化最好（即增加最多）的位置，最后将移除的卡车节点插入贪婪修复算子计算得到的最好的位置；对于移除的无人机节点，该算子循环将每条卡车路径中无人机能够起飞的节点作为起飞节点，将无人机节点插入，记录使受灾群众满意度减少最小的位置，并确定与该位置相关联的无人机起飞节点和降落节点，最后将移除的无人机节点及相关联的起飞节点和降落节点插入贪婪修复算子计算得到的最好的无人机路径中。2.2.6

后悔修复算子该算子依次循环计算每个移除节点的后悔值，找到卡车配送节点和无人机配送节点一共4个移除节点中后悔值最大的节点，将其插入到路径中，并更新满意度。再重新循环计算剩余移除节点的后悔值，找到后悔值最大的节点并插入。重复该步骤，直至所有的移除节点都被重新插入到路径中为止。2.3

算子选择在算法迭代过程中，采用了轮盘赌的方法选择使用的破坏算子和修复算子。每个算子被选中的概率为该算子的权重占所有算子权重之和的比例，因此在迭代过程中，算法根据算子的表现动态地调整算子的权重，使表现更好的算子占的比重更大，以获得质量更高的解。迭代开始前将每个算子的权重均设为1，在后续迭代过程中，按照如下的规则对算子的权重进行更新：如果选择的破坏算子和修复算子产生的新解好于当前解，则对应破坏算子和修复算子的权重加；如果选择的破坏和修复算子产生的新解好于全局最优解，则对应破坏算子和修复算子的权重再加；如果选择的破坏算子和修复算子产生的新解比当前解差，但根据模拟退火算法的以概率接受准则被接受，则对应破坏算子和修复算子的权重加；否则，对应破环算子和修复算子的权重不变。在每次破坏和修复操作之后，都按照以上的规则计算更新算子的权重。2.4

停止和接受准则为了防止邻域搜索时陷入局部最优，引入了模拟退火算法以概率接受准则。如果在迭代过程中获得的新解比当前解差，则以概率接受，其中表示新解，表示当前解，表示目标函数值，表示当前温度，随着迭代次数的不断增加，以的降温速度不断降低，其中。当算法达到最大迭代次数或者连续迭代Imax次没有得到更好的解时，算法直接结束，接受当前的全局最优解为最优解并输出。3

计算实验由于本文所研究的问题还没有公开的测试算例可用，为了验证本文卡车-无人机协同物资配送模型和自适应大邻域搜索算法的有效性和可行性，本文参考了来自于文献[17]中修改后的Solomon数据集，将其在Solomon数据集中增加的每个节点的收益递减率对应本文中受灾点处的满意度递减率，并根据本文所研究的问题对数据集进行了适当的改编，部分数据示例见表2。本文中提出的算法由Java实现，实验的运行环境为Intel（R）Core（TM）i5-13500H2.60GHz处理器，16.0GB内存。3.1

参数设置本文所使用数据集中受灾节点规模分别为50，75，100，数据类型分为C型和R型两类，C类数据中节点分布比较集中，R类数据中节点分布比较随机。设定每个算例中由卡车配送的受灾节点占80%，由无人机配送的受灾节点占20%。指挥中心使用卡车和无人机作为物资配送工具，其中，卡车容量为200，每个受灾节点需求物资的重量都在无人机的承载范围之内，卡车和无人机的速度分别为30km/h和50km/h。自适应大邻域搜索算法的最大迭代次数为100。3.2

实验结果根据本文使用的改编后的Solomon数据集和设定的卡车、无人机相关参数，结合本文构建的卡车-无人机协同物资配送模型，在卡车-无人机协同配送和卡车单独配送两种情景下，使用改进的自适应大邻域搜索算法进行求解，每个算例求解10次，记录每次的目标函数值并取平均值，结果对比如表3所示。为了验证无人机在应急救援物资配送中的有效性，本文将卡车-无人机协同配送物资和只有卡车配送物资两种模式下求得的受灾群众满意度