基于无人机应用的应急救援物质投送网络节点规划问题研究

基于无人机应用的应急救援物质投送网络节点规划问题研究

陈智,吴逢东

陆军勤务学院 重庆市沙坪坝区  400000

摘要：应急救援物资保障时间紧任务重，应充分考虑应急救援的物资需求和无人机配送节点编配，建立以优化网络时效性为目标，以建设资源需求、规模效益等要素为约束条件的应急救援物资无人机投送节点规划数学模型。采用机器学习算法求解模型假设，分析各参数对网络时效性、建设资源需求等指标的影响，验证模型在应急救援物资保障投送节点规划应用中的适用性、可行性、及时性和有效性。

关键词：应急救援；物资投送；遗传算法；无人机

1.引言

应急救援物资保障难度大，运输投送困难，传统的应急救援物资保障主要依靠人力运输和直升机投送，不能适应应急救援快速、高效、精确补给的要求，发展空中补给和实现精确投送是重要突破口。以无人机为平台建立的投送网络具备机动灵活、越障能力强、无人员伤亡、自主操控、成本低廉、载荷比大、全天候等特点，在未来应急救援物资保障投送中具有极大的发展潜力。无人机配送网络节点的选址是决定无人机配送规模效益与时效性好坏的关键，节点选址问题理论研究意义重大。

目前已有大量学者对无人机配送节点选址问题进行了探索研究并广泛应用于生产生活之中，主要形成了竞争模型[1]、限制容量模型[2]、最大区域覆盖模型[3]和P-Center模型[4]4类。如配送领域中，陈义友等[5]研究了考虑顾客选择行为的快递自提点P-中值选址双层规划模型。应急物流领域中，王根基等[6]从成本最小化的目标出发构建混合整数非线性规划数学模型并求解。

在综合考虑无人机网络布局性能要求的前提下，实现了基于遗传算法的无人机投送网络节点选址算法，能够为恶劣环境下无人机投送网络布局提供辅助决策依据。

2.问题描述

无人机投送网络以物资保障建设为依托，将各种配送资源按照一定的要求和原则合理部署而最终形成一个网络化布局投送体系，兼有人工、车辆等传统运送方式无法企及的机动灵活、越障能力强、无人化、智能化、全天候等优点。假设对某一需要无人机服务的救援区域进行无人机配送中心选址规划，前期已经根据现地交通、现场环境、建设条件等因素筛选出一系列候选点，本文要解决的是如何从这一系列候选点中，选择符合目标且满足约束的投送节点建设地址。由于无人机有多种类型，有的可以垂直起降但飞行距离较短，有的可实现远距离运输但需要起降跑道，因此，需要考虑不同类型的投送节点，且不同类型的节点服务半径、服务能力及建设资源需求均不相同。此外，还需考虑建设节点资源需求量，而网络时效性和建设资源需求量与配置点到投送节点的距离直接相关，因此本文模型的目标函数用最小化网络总里程表示，而建设资源需求量和规模效益则作为模型优化的讨论对象。

3.构建模型并求解

3.1符号说明

表示投送节点候选点集合，；

表示配置点集合，,且,,其中表示第类配置点；

表示无人机投送节点类型的集合，；

表示类型为的投送节点的最大服务能力（即服务配置点的最大数量）；

表示类型为的投送节点的最大服务半径；

表示类型为的投送节点的建设成本；

为抗风险能力参数，表示能够服务配置点的设施点的最少个数，配置点类型不同，的取值不同；

表示候选点与配置点之间的距离；

表示建设无人机投送网络的资源需求；

为规模效益参数，表示投送网络所有节点利用率；

为决策变量，取1时表示类型为的候选点服务配置点，否则取0；

为决策变量，取1时表示在候选点建设类型为的投送节点，否则取0。

3.2数学模型

构建无人机投送节点选址模型如下：

                                 （1）

函数式（1）的意义是，在满足约束条件为配置点投送物资至少有个投送网络节点的情况下，使投送网络总里程最小，总里程越小系统的时效性越强。约束条件的意义为配置点抗风险能力，越多其抗风险能力越强，本文中设置三类配置点（一般配置点、中等配置点、加强配置点）。

（2）

函数式（2）用于计算无人机投送网络建设的资源需求量。

（3）

函数式（3）式的意义为投送节点投送能力必须小于节点最大能够提供的服务能力。

（4）

函数（4）式的意义为配置点距离超过投送节点的最大服务半径时，不能向该配置点投送物资。

（5）

函数（5）式的意义为无人机投送网络所有节点利用率不低于，以保证投送网络的规模效益。

3.3遗传算法求解

遗传算法模拟了自然界选择和遗传中发生的复制、交叉和变异等现象，从任一初始种群出发，通过随机选择、交叉和变异操作，产生一群更适应环境的个体，使群体进化到搜索空间中越来越好的区域，这样一代一代地不断繁衍进化，最后收敛到一群最适应环境的个体，求得问题的最优解[7]。

遗传算法的一般求解过程如下：

①编码。将解空间中的解数据从数据形式到二进制形式的基因型的映射成为编码。

②生成初始种群。从解空间中随机产生个初始串结构数据，每一个初始串数据称为一个个体，个个体构成一个初始种群，一般取20-100。

③适应度检测评估。适应度函数是用来评价种群中各个个体好坏的指标，是算法演化的驱动力，也是进行自然选择的唯一依据。本文的目标函数是投送网络时效性最优，并满足建设资源、抗风险能力等约束条件。

④遗传操作。遗传操作包括三个基本操作：选择、交叉、变异，群体经过选择、交叉、变异运算后得到下一代群体。

⑤终止条件判断。当运算达到预先设定的代数或测得种群中最优个体性能满足问题约束条件时可终止运算，否则重复步骤②③④直到达到终止条件。

在科学计算、金融工程和人工智能等领域，Python语言得到了广泛应用。Python拥有庞大的标准库和第三方库，可以轻松实现处理各种工作，包括正则表达式、文档生成、单元测试、线程、数据库、网页浏览器、CGI、FTP、电子邮件、XML、XML-RPC、HTML、WAV文件、密码系统、图形用户界面和其他与系统有关的操作。其中SciPy和NumPy等科学函数库实现了函数计算、向量和矩阵操作， Matplotlib绘图工具函数库可以绘制2D、3D图形，也可以处理科学研究中经常使用到的图形。基于此，本文利用使用Python语言实现遗传算法用于无人机投送网络节点规划问题的求解。

4.算例分析

假设救援环境为一正面100公里纵深100公里地域，配置点均匀分布该区域内，在该区域内随机生成200个配置点的坐标（图1）。将其按序号分成3组，且序号1-160为一般配置点命名组，序号161-180为中等配置点命名组，序号181-200为加强配置点命名组。每两点之间的距离用欧氏距离表示，投送节点的候选点集合为，无人机投送节点相关参数见表1（该数据仅用于算法仿真验证）。

图1随机生成的3类配置点分布图

4.1遗传算法实现

图2 用于无人机投送网络节点选址的遗传算法

编码：常用的遗传算法编码有三种形式：二进制编码、实数编码和符号编码，二进制编码对精度要求较高，字符串过长或过短都会影响搜索效率，而且不能直观反应问题特征，因此在实际中较少应用，本文采用实数编码。

种群初始化：随机生成一定数量的初始种群，种群数量过低会使搜索空间受限，容易陷入局部最优，引起早熟；种群数量过多会使搜索迭代次数增加，算法复杂度上升，降低算法效率。本文种群数设置30。

适应度函数：根据以往文献研究发现，适应度函数多由目标函数变换得到，用于衡量解或个体优劣性的指标，其值越高，遗传的可能性越大，适应度值由适应度函数确定。本文以目标函数的倒数作为适应度函数。

选择：将适应度高的个体保存下来，进行交叉、变异或直接作为下一代新个体，形成新的种群，体现了“优胜劣汰、适者生存”的遗传进化法则。本文采用最优保存策略。

交叉：将两条染色体按一定方式交换基因形成新的个体，从而实现种群的进化，常用的交叉操作有单点交叉、多点交叉和均匀交叉。考虑到投送节点染色体较短，本文采用单点交叉。

变异：为进一步提高种群多样性，将染色体编码串上的部分基因进行转变，提高遗传算法的局部搜索能力和全局搜索能力，主要包括内变异和外变异两种方式。考虑投送节点特征，本文采用外变异。

参数：交叉概率和变异概率决定交叉操作和变异操作发生的频率大小。本文中取。

终止条件：在反复迭代求解后，种群趋近于最优解，但很难得到真正最优解，本文终止条件为累计循环次或连续次迭代结果变化百分比小于。

伪代码如图2所示。

4.2计算结果分析

将以上数据导入模型并求解，程序运行得到最优解，最优目标函数值为。该选址结果为小型投送节点个、中型投送节点个、大型投送节点个，消耗资源万，无人机投送网络运行效益为。

图3 目标优化逼近图

从图3中可以看出，算法的求解目标即投送网络总里程在算法前步急速下降，在步降速减缓，直至步后趋于稳定；投送网络规模效益在算法前步急速增加，在步增速减缓，直至步后趋于稳定，呈现出与网络总里程反向的特点；投送网络的建设成本即需求的资源在算法前步急速下降，在步降速减缓，直至步后趋于稳定，呈现出随网络总里程减少趋势同步和上下波动的特点。

因此在总里程增加不大的情况下，可以选取投资成本小的近视最优解，决策者要在预算与网络时效性之间进行权衡。如算法的第18步需要资源最小，其总里程与最终解差距不大。

4.3模型性能分析

为了验证模型对大规模问题的处理能力，在100km×100km的区域内随机生成250、300、350、400个需求点，各类需求点的比例仍是8∶1∶1。不同问题规模下模型的求解结果见表3。由表3可知，随着问题规模的增大，目标函数值逐渐增大，资源需求量随之增大，同时由于单位面积内需求点数量增加，两点之间的距离缩短，单个投送节点能够提供服务数量变多，投送网络规模效益也随之增大。此外，计算时间虽然随着问题规模的增大而增加，但仍在可接受范围内。

算例分析表明：（1）网络时效性与投送网络的规模效益正相关，与资源需求存在效益负相关性；（2）问题规模越大，投送网络规模效益越好；（3）遗传算法随问题规模变大运算时间增幅较小，表明该算法的时间复杂度较低；（4）程序能在可接受的时间范围内求出模型满足抗风险能力要求配置点的最优解，为应急条件下的无人机投送节点选址决策提供辅助支持。

5.结束语

本文结合应急救援无人机物资投送网络节点选址问题，提出一个以网络总里程最小为目标的无人机配送中心选址模型。与一般选址模型的不同之处在于考虑了配置点和投送节点的异质性及网络的抗风险能力（即配置点与投送点的关系不局限于单分配）。此外，还考虑了投送节点的服务半径、服务能力、规模效益和资源需求等因素。算例分析验证了模型和求解方法的可行性和有效性，不同规模条件的实验结果表明，遗传算法在大规模问题求解上的时间复杂度较小。

6.参考文献

[1]Gentile J,Pessoa A A,Poss M,et al.Integer program-ming formulations for three sequential discrete competi-tive location problems with foresight[J].European Jour-nal of Operational Research,2018:265(3):872-881.

[2]Hoff A, Peiró J,Corberán A,et al.Heuristics for the capaci-tated modular hub location problem[J].Computers and Operations Research,2017,86:94-109.

[3]Silva M R,Cunha C B.A tabu search heuristic for the uncapacitated single allocation p-hub maximal covering problem[J].European Journal of Operational Research, 2017, 262(3):954-965.

[4]Golbarg Kazemi Tutunchi,Yahya Fathi. Effective methods for solving the Bi-criteria p-Center and p-Dispersion Problem[J]. Computers and Operations Research,2018.

[5]陈义友,张锦,曾倩,等.基于顾客选择的自提点选址双层规划模型[J].管理学报,2016,13(12):1842-1850.

[6] 王根基,李莉.电商物流配送中心选址布局问题研究[J].物流科技,2019,42(02):27-29.

[7]张文修,梁怡.遗传算法的数学基础[M]. 西安交通大学出版社,2003.

—1—