基于遍历算法的无人机救援模型研究

黄敬 王志坚

摘 要：本文研究了救援响应系统的开发需面临装箱问题。将无人机与自身携带的外部货舱、运输集装箱和医疗包组合放入标准ISO集装箱内，采用非线性规划模型，根据三个港口的地理位置采用遍历法找出三个港口到救援地点的最短路径，并给出了无人机的有效载荷包装方案、交付路线和时间表。确立飞行路径最小化目标，根据医疗包数量需求做出相应约束，结合港口与无人机分配情况，使用遍历方法求出救援最佳方案。

关键词：非线性规划；遍历；禁忌；搜索

2017年，史上最严重飓风袭击美国波多黎各领土，使多黎各受到严重破坏，并造成多人因此死亡。非政府组织-HELP，Inc-设计了一种名为“DroneGo”的可移动灾难响应系统，本文则是为该系统提供救援方案来提高其响应能力。同时根据各营救点的需求以及救援路线和侦查路线为HELP，Inc制定营救计划。

针对以上问题，虽然以前的学者都有研究过货物装配问题及配送问题，但本文的背景是救援，因此要综合考虑救援效率以及救援成本的问题，选出合适港口再制定救援路线。鉴于此，本文采用非线性规划、遍历方法、禁忌搜索等方法制定的救援计划，比前人的研究更具有科学性和合理性。

1 问题分析

ISO集装箱停靠港口后，提供无人机的有效载荷包装方案，交付路线和时间表。首先，确立飞行路径最小化的目标，根据各个交货地点对医疗包的数量需求。结合3个港口分配方案，赋予每个方案1-3台无人机，计算每种分配方案的飞行总距离，运用遍历方法求出最佳方案。还要结合当地人口分布，优先配送伤亡人数多的地点。综合考虑波多黎各的多方面因素，提出假设，得出配送路线，无人机的飞行速度，飞行路径和飞行时间。第二步，为了提供无人机飞行计划，使DroneGo车队能够使用车载摄像机评估主要高速公路和道路，从GoogleMap获取波多黎各的主要道路的交叉点，定义这些交叉点为侦察对象，采用禁忌搜索算法得到最佳侦察路线。

2 符号意义

3 模型的建立

3.1 无人机有效载荷包装配置、交付路线和时间表

若某个港口被选择，就为该港口配置一台H Tethered无人机。在考虑最短路径时，还要结合当地人口分布，优先考虑配送伤亡人数多的地点。综合考虑波多黎各的受灾情况和地理因素，得出配送路线。根据所选中的无人机的飞行速度和飞行路径，获得相应的飞行时间。

3.2 评估主要高速公路和道路的搜索模型

为了提供无人机飞行计划，使DroneGo车队能够使用车载摄像机评估主要的高速公路和道路。我们通过网络数据获取波多黎各的主要道路的交叉点，定义这些交叉点为无人机主要的侦察对象。采用禁忌搜索算法：

从一个初始可行解出发，选择一系列的特定搜索方向作为试探，选择实现让特定的目标函数值变化最多的移动。建立Tabu表，对已经优化的过程进行记录和选择，指导下一步的搜索方向，避免陷入局部最优解。

第一步：令禁忌表H=空集，并選定一个初始解xnow；

第二步：满足停止规则时，停止计算，输出结果；否则，在xnow的邻域N（xnow）中选择不受禁忌的候选集Can_N（xnow）；在Can_N（xnow）中选一个评价值最佳的解xnext，xnow=xnext；更新历史记录H，保存f（xnow），重复step2；

第三步：在保存的众多f中，挑选最小（大）值作为解。

4 主要结果

当停靠Arecibo，Fajardo，San Juan这三个港口时，每个港口各配置1架无人机。结合交货地点与港口的距离以及医疗包的需求，得出以下结果：

（1）港口Arecibo配置一台E型无人机，负责的救援点：Hospital Pavia Arecibo，飞行路线是由Arecibo飞到Hospital Pavia Arecibo，飞行时间是5.43分钟（设开始飞行时间为0）。

（2）港口Fajardo配置一台无人机E，负责救援点：Caribbean Medical Center，飞行路线为由Fajardo飞到Caribbean Medical Center，飞行时间2.41分钟。

（3）港口San Juan配置一台无人机B，负责救援点：Hospital HIMA、Hospital Pavia Santurce、Puerto Rico Children's Hospital。考虑到无人机B的配送能力以及为了缩短飞行时间，该无人机的配送方案为：无人机先携带救援点Hospital Pavia Santurce、Puerto Rico Children's Hospital所需的总救援物资，然后先飞往Hospital Pavia Santurce，飞行时间为10.45分钟；再飞往Puerto Rico Children's Hospital，飞行时间为10.91分钟，总飞行时间21.36分钟。在无人机B离开港口的同时，派出一辆营救车带着1个H Tethered平台直接沿着救援点Hospital HIMA的方向驶去。当到达无人机B可以把医疗包带往的救援点Hospital HIMA时，并在能够返回的范围内，等待无人机的到来，再进行充电以及对医疗包进行装配，最后飞往Hospital HIMA，飞行时间为20分钟（重新飞行时，开始飞行时间为0）。通过禁忌搜索算法使用python求得的飞行最短路径结果如下图所示：

5 结语

在保证合理的情况下，运用了遍历算法，在假设条件下考虑了所有可能的情况，减少了误差的产生。在确定最佳飞行路线时，综合考虑了当地人口密集地，海拔和施工地点等因素，增加了模型的可靠性。

参考文献：

[1]王帅.智能轮式机器人在养殖场中路径规划的研究[D].长春大学，2017.

[2]张雪婷，陈英武，王琦，周浩，葛冰峰.整车物流的任务规划模型和算法[J].中国管理科学，2015，23（S1）：624-629.

[3]苏迎迎.果蔬农产品物流运输路径优化研究[D].中国石油大学（华东），2016.

[4]江伟，秦翠兰，康顺光.整车物流运输计划优化模型研究[J].物流工程与管理，2014，36（11）：69-71.

作者简介：黄敬（1996-），男，广东清城人，2016级本科生，研究方向：应用统计学；王志坚（1982-），江西余干人，博士，讲师，研究方向：管理统计方法。