无人机救灾中的多目标物资装配和投放点定位研究

覃炳发 王东 金焱 蒋俊林

摘   要：文章以2019美国大学生数学建模B题为例，对无人机救灾中的多目标物资装配和投放定位进行了研究。首先，以无人机数量尽可能少、医疗包的数量尽可能多、无人机的飞行距离尽可能远和集装箱利用率尽可能高为目的，建立了多目标整数规划模型。在至少满足波多黎各一个月的医疗包需求以及其他约束条件下，为3个集装箱提供了相应的打包配置。其次，使用空间多层次叠加算法来确定集装箱的最佳投放位置。通过熵值法来给土壤类别、水文、坡度、道路网络、居民分布、医疗中心和重灾地区等影响集装箱投放位置的因素进行赋权。利用ArcGIS软件对各因素进行加权叠加后，筛选出灰度大于6.5的地区，再通过无人机的飞行距离确定集装箱最佳的放置区域。最后，根据道路节点确定3个集装箱的经纬度分别是（18.267 313，﹣65.875 327），（18.279 049，﹣66.141 528），（18.315 155，﹣66.579 81）。

关键词：多目标整数规划;打包配置;空间多层次叠加算法;熵值法;投放位置

1    3个ISO货运集装箱的投放位置

两年前，美国领土波多黎各遭受到了有史以来最严重的飓风袭击，对波多黎各造成了严重的损坏，导致了无数人伤亡。这次飓风伴随着狂风暴雨，几乎摧毁了波多黎各所有的电力系统和通信系统。不仅如此，这次灾害还引起了洪水的泛滥，阻塞和损坏了岛上许多的公路，导致了无法为应急服务车辆规划路线。波多黎各的医疗用品、救生设备以及医疗诊所都十分紧张，非政府组织救援行动也在进一步展开。因此，设计合理的救援物资打包方案以及集装箱投放点对救援行动有着巨大的促进作用。

目前，国内在与救援物资装配问题相似的装箱问题上已经有了大量的研究[1-2]，对于不同情形和条件下的装箱问题，已经有学者研究并给出了许多可行的方案[3-4]。

与单纯研究装箱问题不同的是，本文结合2019年美国大学生数学建模竞赛B题中的场景，在问题中提供的现有无人机类型和数量、医疗包类型和数量以及无人机货舱类型和数量的前提下，以节约成本、满足救援需求为主要目的，建立一个多目标的线性规划模型，为多达3个ISO货运集装箱设计相关的包装配置。此外，为了使得无人机能够进行医疗用品的交付和道路网络的视频侦察，本文充分考虑波多黎各水文、土壤类别、坡度、居民分布、医疗中心、道路网络以及重灾害地区等多个因素，使用空间多层叠加分析算法在ArcGIS软件中综合这些因素对地图信息进行分析，最终得出3个集装箱在波多黎各的最佳投放位置[5]。

2    货运集装箱包装配置模型

2.1  模型假设

结合问题中的实际情况，本文提出如下假设：（1）假设无人机、货舱和医疗包可以在集装箱内任意放置。（2）假设无人机货舱的厚度可以忽略不计，即货舱容量就是货舱的实际大小。（3）假设每一台无人机对应一个货舱。

2.2  符号说明

目标函数式（1）表示实现成本最小化、救援供给量最大化和视频侦察范围最大化要求，权重系数α，β，γ为常数。约束条件式（2）保证了每个集装箱内至少具有一辆具有视频功能的无人机。约束条件式（3）对医疗包总重量需要小于所有无人机的载重量进行约束。约束条件式（4）对集装箱容量进行约束，由于考虑到医疗包和无人机的形状问题，所以约束医疗包、无人机和无人机货舱的总体积不能超过集装箱最大体积的90%，确保医疗包、无人机和无人机货舱能按照某一种摆放方式装入集装箱内。约束条件式（5），（6）和（7）分别对MED1，MED2和MED3医疗包数量进行约束，确保医疗包数量能够满足波多黎各至少一个月的需求量。因为每一天所需3种医疗包的比例为7∶2∶4，所以3个集装箱每一种医疗包的总数量也应该满足7∶2∶4的比例（用约束条件式（8）和（9）表示），目的是使医疗包的利用率达到最高。

2.4  模型求解

针对上述模型，分别取权重系数 α=0.5，β=0.3，γ=0.2，将各项参数带入Matlab中的intlinprog函数，程序运行375 s，求解结果如表1所示。

从表1可以看出，3个集装箱装配飞机的方案基本都是差不多的，都主要偏向于装载B类和C类无人机。B类飞机的飞行速度、最远飞行距离和飞行时间都是最优的，而C类无人机在最大有效负载、速度和飞行时间上的性能都是处于中上水平的，B，C类无人机都可以很大程度地加大援助的效率。此外，每个集装箱还装载了少数几架F型无人机，虽然没有视频功能，但是它的飞行速度是最快的，可以以更快的速度将救援物资送到指定地点。

3    集装箱投放点定位的数学模型

3.1  问题分析

在分析选址之前，需要对每一种无人机满载时的最短飞行时间进行计算。题目中只给出了空载时的飞行时间，假设无人在满载的时候飞行时间会下降10%，可以得出计算满载时候各种无人机的最短飞行时间的计算公式如下：

Ti=（1-0.1）ti

其中，ti表示第i种无人机空载时的飞行时间，Ti表示第i种无人机满载时的飞行时间。根据此飞行时间可以计算无人机在最坏情况下的飞行距离，从而对集装箱投放点进行约束。

通过查阅美国地质勘探局发布的国家地质图库[6]，再结合題目所给地图，得到了波多黎各的交通、水文、坡度、土壤类别、居民分布和5个医疗中心的栅格数据，并描出重灾区域的大致范围。根据以上基础数据，通过ArcGIS采用空间多层叠加分析算法对地图信息进行分析。

3.2  模型构建与投放点位置标定

结合实际救援情况，选择的集装箱投放点应该满足如下条件：无人机能够在集装箱和医疗点之间往返、远离重灾区和低洼地区以及临近交通网密集地区等。

根据以上要求，在ArcGIS的ModelBuilder里创建了集装箱选址分析模型，模型如图1所示。

首先，通过高程图生成坡度数据。为了得到集装箱安放的位置与因素之间的远近关系，需要提取水文、居民分布、5个医疗中心、道路交通和重灾地区的直线距离数据集。在用欧氏距离提取完距离数据集后，需要根据偏好值、敏感度值、优先级值或者某些类似的条件指定给各因素分等级，方便评价。为坡的坡度平均划分为5个级别，为水文、道路、居民分布、医疗中心、重灾地区的距离平均划分为10个级别。分级等级越高，越适宜安放集装箱。波多黎各在飓风过后，各地出现洪水的情况下，不宜靠近水文，且应远离。因此，到水文的距离越远，分数越高。重灾地区也是一样的，需要远离，避免二次灾害，也是越远越好。坡度的等级划分，也与洪水相关，太平容易漫，太陡不易放，选择偏缓的坡度为最高级。对于医疗中心的距离，考虑到勘探路面的需求，勘探方位应尽可能地大，选择适中的距离为最佳，保证能送达药品的同时，勘察面积可以最大化。道路和居民分布應该选择越近越好，方便物资的运输和救援。对土壤类别进行重分类，删去沼泽、脆弱的土质等地，对其余的土质重新赋值。

为了得到最佳选址区域，需要对每个区域进行叠加。地理信息以矢量或栅格的数据层面存在，可以通过叠加数层，得到新的一个数层，它将拥有原来两层或多层要素所具有的属性。为更直观体现不同要素对选址的影响，选用权重对要素的重要性进行区分，重要的因素赋予较大的权重值。在对数据层面做叠加分析时，在波多黎各选取5个采样点，根据采样的各项指标数据使用熵值法对各因素进行赋权。通过熵值法最终计算各指标权重如表2所示。

在输入权重后，得到了最终的选址图，图层的分值为8。为更好筛选集装箱放置地点，提取灰度大于6.5的栅格数据，并将栅格数据矢量化。导入题目所给的地图作为底图，可以看出地图明显地被划分为3块区域，如图2所示。

通过下载波多黎各的道路网络图，找寻重要的交通结点，选取交通结点附近的地址，作为集装箱放置的主要地点。结合每个集装箱中无人机的飞行距离，最终确定3个集装箱的投放位置，如表3所示。

4    结语

本文波多黎各受到飓风袭击的事件为背景，根据问题中提供的各项数据，建立了多目标整数规划模型，为无人机救灾设计了3个集装箱的打包配置。结合每个集装箱中无人机的配置以及对投放地点的约束，在ArcGIS软件中利用空间多层次叠加分析算法对地图数据进行分析，最终精确地确定了3个集装箱的投放地点。最终确定的集装箱投放地点不仅能够使得正常交付医疗包到医疗点，还能够在交付过程中用视频侦测到更多的道路数据。

[参考文献]

[1]王悦宸，苏醒，贾熹滨，等.应急救援中基于线性规划的多目标多资源分配模型[J].中国科学技术大学学报，2018（6）：458-466.

[2]崔会芬，许佳瑜，朱鸿国，等.基于改进遗传算法的三维单箱装箱问题研究[J].工业工程与管理，2018（1）：86-89.

[3]那日萨，崔雪莲，韩琪玮.基于实际约束的三维装箱问题优化算法[J].工业工程与管理，2017（4）：10-16.

[4]张雅舰，刘勇，谢松江.一种求解装箱问题的改进遗传算法[J].控制工程，2016（3）：327-331.

[5]钟石泉，王雪莲.多箱型三维装箱问题及其优化研究[J].计算机工程与应用，2009（22）：197-199.

[6]美国地质勘探局.国家地质图库[EB/OL].（2018-12-12）[2019-08-20].https：//ngmdb.usgs.gov/Prodesc/proddesc_15561.htm.