电力巡检车载无人机协同作业优化

赵 蒙 ,张 博 ,胡祥培 ,黄敏芳

(1.大连理工大学 经济管理学院,辽宁 大连 116024;2.华北电力大学 经济与管理学院,北京 102206)

随着我国用电需求和电网规模的快速增长,电力巡检的工作量也大幅增加[1]。输电设施长期暴露在野外环境中,极易磨损老化,必须定期巡查、检修以确保供电正常。无人机技术的成熟和发展为电力巡检提供了相比人工作业更加安全、经济和高效的解决办法。一方面,无人机电力巡检操作灵活、部署方便,检测精度高,能够消除人工巡检盲区[2];但另一方面,电力巡检无人机的续航能力有限,通常需要保障车为无人机提供放飞回收、转场载运、电池更换和维护保养等服务保障,这就要求无人机和保障车的作业计划充分协调以保证电力巡检任务的顺利执行。

目前较为常用的一辆保障车固定搭配一架无人机的“一对一”模式虽然操作简单,但巡检任务范围较大时该模式的整体运行效率低,对保障车的利用率不足,经济性和时效性较差[3-5]。实际上,车载无人机电力巡检系统(Vehicle-mounted UAV Transmission Inspection System,VUTIS)可由中控平台通过移动互联网技术同时远程控制多架无人机,按照既定的任务方案协同合作,在更短的时间内完成电力巡检任务[6]。如图1所示,作为无人机的可移动保障平台,保障车可以通过更加灵活的作业方式在巡检任务执行期间同时服务更多无人机,即“多对多”模式。在该模式下保障车可沿交通路网穿梭于运维站和各驻车点之间,及时到达指定位置为无人机提供维保和换电等服务;无人机则在放飞之后按计划飞往目标区域进行电力设施巡检,在任务完成或电力不足时前往任意驻车点与保障车汇合进行换电、维保、转场或随车返回运维站。

图1 VUTIS示例

图1右侧所示为VUTIS的部分系统的运行过程。其中,保障车h∈H 由运维站i0出发,车上载有满电状态的无人机d1∈D。保障车h首先到达驻车点i1放飞d1后驶往i2。d1首先飞往电力杆塔i3,之后前往i4,最后前往驻车点i2。与此同时,无人机d2在离开i6后抵达i5进行巡检,之后也前往i2。此时,i1与i2均为电量不足状态,由h回收换电后载回运维站i0。由此例可知,在“多对多”模式中,每辆保障车可以在满足服务能力限制条件下同时服务多架无人机,且无人机和保障车之间没有固定的搭配关系,保障车本质上作为无人机起降和转运的可移动保障平台,而保障车在具体作业场景下同时服务的最大无人机数量则需由优化决策方案确定。

虽然理论上VUTIS能够提升无人机和保障车的利用率,节省运行成本,但也对两者作业方案的时空协同性提出了更高的要求。首先,当无人机有换电或转场需求时,保障车须及时与无人机在驻车点汇合,以保障系统运行效率。此外,在设计无人机和保障车的作业方案时,还要充分考虑无人机的续航限制和气象条件对航行速度的影响,同时关注保障车辆的承载能力和道路交通状态对行驶速度的影响[7]。因此,VUTIS中无人机与保障车的协同作业优化决策不仅要求对两者的时空轨迹精准刻画并构造耦合关联,还要根据系统运行过程中的诸多限制条件对电力巡检作业方案进行调整和约束,最终实现电力巡检成本的最小化。由此可知,VUTIS综合优化问题本质上是无人机和保障车作业计划的协同优化问题(Vehicle-mounted UAV Cooperative Operation Problem,VUCOP)。相比传统的车辆路径问题,该问题更加侧重于实现无人机和保障车在时间和空间上的协同合作,即需要在电力巡检任务的牵引下,综合优化无人机和保障车的作业计划,确保保障车能够在必要时及时与无人机在驻车点相遇并为其提供收放飞,换电和转场等服务,同时还要尽可能地最小化VUTIS 运行总成本。为实现该目标,VUCOP 要求对车辆和无人机作业方案的时间维度和电量状态维度的刻画更加精细,需要在无人机和保障车之间建立更加复杂的时空耦合约束,模型结构更加复杂难解。

目前,国内外相关领域的研究主要侧重于无人机电力巡检的静态路径规划。Van等[8]通过大数据技术建立无人机巡检路径规划数据库,对追踪到的无人机巡检路径规划数据进行分类存储,从根本上提高了无人机巡检路径规划的效率。朱程雯等[9]针对无人机巡线路径问题,建立无人机巡线作业环境模型,并利用蚁群算法求解,以优化巡线目标的拍摄地点和巡线路径。吴晏芳等[10]将大数据技术应用在无人机巡检路径规划,提出了基于大数据的输电线路无人机巡检路径追踪方法,实现无人机巡检路径规划。有关车辆与无人机协同作业的相关研究主要应用于车载无人机末端配送领域,也即带有无人机的车辆路径问题(Vehicle Routing P roblem with Drone,VRP-D)[11-13]。Wang等[14]研究了基于中转站的车辆和无人机协同配送问题,通过构建该问题的集覆盖模型,采用分支定价算法实现了对该问题的精确求解。杨双鹏等[15]针对“疫情隔离”期间应急物资配送问题,提出一种卡车+无人机联合配送模式,即卡车不参与客户配送,完全充当无人机仓库,无人机可携带多个包裹进行多点配送。何勇等[16]针对“载机平台+无人机”服务模式的载机平台调度问题,在用户需求分散且随时间频繁波动的优化背景下,提出基于两阶段鲁棒优化的载机平台调度模型,并采用L 型算法进行求解。随着车载无人机电力巡检技术的逐渐成熟和推广使用,大部分学者借鉴VRP-D 的优化方法重点研究“一对一”[17]和“一对多”[7]模式的静态路径规划问题,少部分针对“多对多”模式的研究则从空间和时间两个维度上分别构建无人机和车辆调度方案的关联性约束,再建立时间和空间变量之间的耦合关系;若考虑无人机的续航约束和保障车的承载约束,则还要通过引入大量间接变量在时空变量间建立非线性约束。这会导致模型结构极其复杂而难以通过数值型算法快速求解,采用启发式算法又难以保证求解大规模实际问题时的计算精度[18-19]。

针对这一难题,采用时空网络建模方法构建无人机与保障车协同路径优化模型。通过提高变量维度减少变量种类和变量间的复杂耦合约束,能够明显地降低模型结构的复杂度。但另一方面,提高变量维度又会造成网络规模和变量总数的大幅度提高。尤其为精准刻画无人机续航限制对其电力巡检方案的影响,需要在时空网络的基础上构建无人机的时空-状态网络模型,这又会导致变量维度的进一步提高。换言之,通过采用时空网络建模方法,VUCOP可以进一步转化为基于轴福式网络的甩挂运输路径优化问题(Truck and Trailer Routing Problem,TTRP)的衍生变种,而本质上仍然是求解难度很高的NP 难问题。因此,为实现VUCOP 的快速精确求解,本文设计基于拉格朗日松弛和贪心规则的松弛解转换算法(Lagrangian Relaxation and Greedy Rules Algorithm,LR-GR)。首先通过松弛变量间的耦合难约束,将原问题转化为由两组相互独立子问题构成的对偶松弛问题。鉴于每组子问题结构相对简单,可快速求解得到原问题的松弛解。之后,针对VUTIS的轴福式网络结构以及无人机和保障车作业计划的时空关联特性,基于贪心规则对松弛解进行可行化处理,在保证LR-GR 算法单步迭代的计算速度的同时兼顾求解质量,以保证优化算法在求解较大规模实际问题时能够快速收敛,进而在合理时间范围内得到近似最优解。最后,通过一组敏感性分析实验验证了无人机最大载电量对于VUTIS整体运营策略的影响。

1 问题描述和时空网络构建

车载无人机电力杆塔巡检系统如图1所示,其空间网络表示为有向图GS=(I,L)。其中:集合I=IH∪ID表示空间节点,集合IH包括驻车点和运维站i0所在节点,ID为电力杆塔所在节点集合;L=LH∪LD表示网络中的弧段,LH为驻车点之间以及驻车点与运维站之间的弧段,LD为电力杆塔之间以及电力杆塔与驻车点之间的弧段。在时间维度上,将系统运营周期均匀离散化并生成时间戳集合T={t0,t0+δT,…,t0+MTδT},其中,t0为起始时间,δT为两相邻时间戳之间的时间间隔,集合T中最多包含MT +1个时间戳。通过结合空间网络有向图和时间戳集合,得到车载无人机电力巡检系统的时空网络GT=(N,A)。其中:集合N=NH∪ND表示时空网络中的时空节点,集合NH包括驻车点和i0所对应的时空节点,ND为电力杆塔所对应的时空节点集合;A=AH∪AD表示时空弧段,AH为驻车点之间以及驻车点与运维站之间的时空弧段,AD为电力杆塔之间以及电力杆塔与驻车点之间的时空弧段。考虑到无人机电量限制对电力杆塔巡检任务的影响,本文在刻画无人机作业过程时,在时空网络的基础上进一步拓展电力状态维度。参考时间戳集合,定义无人机电量状态集合E={e0,e0+δE,…,e0+MδE},其中,e0为无人机最低安全电量,δE为两相邻电量等级之间的电量差值,e0+MδE即为无人机最大电量。由此构建时空电网络GE=(V,K),其中,集合V=VH∪VD表示时空电节点,集合VH包括驻车点和i0所对应的时空电节点,VD为电力杆塔所对应的时空电节点集合;K=KH∪KD表示时空电弧段,KH为驻车点之间以及驻车点与运维站之间的时空电弧段,KD为电力杆塔之间以及电力杆塔与驻车点之间的时空电弧段。一队保障车H 各载若干架无人机D 由运维站出发按照既定计划前往指定的驻车点i∈IH执行无人机的放飞和回收任务。无人机在放飞后,根据计划飞往相应的电力杆塔执行巡检任务,之后前往任意驻车点由保障车回收,进行电池更换和维保工作,之后视计划进行再次放飞或由保障车载回运维站。

车载无人机系统电力巡检的过程在时空网络中可由两者的时空轨迹表示。图2所示为时空网络包含19个空间网络节点和38个时间戳。其中:节点1为运维站,由红色标识;节点2～7为驻车点,由蓝色标识;节点8～19为电力杆塔所在节点,由绿色标识。所有无人机和保障车的时空轨迹均由时空弧段构成。例如,保障车h1在时间点0 由运维站1 出发,并在时间点2到达驻车点4,以时空弧可表示为(1,0,4,2)。

图2 VUTIS时空网络表示示例

由图2可知,保障车h1时空轨迹包括时空弧段(1,0,4,2)、(4,2,4,4)、(4,4,7,25)、(7,25,7,29)、(7,29,2,33)和(2,33,2,38),h2时空轨迹包括时空弧段(1,0,5,5)、(5,5,5,7)、(5,7,4,24)、(4,24,4,27)、(4,27,6,31)、(6,31,6,33)和(6,33,4,38)。由于考虑到无人机电池电量对无人机续航能力和巡检任务的影响,因而在时空网络的基础上增加电量状态维度组成时空电网络,并通过时空电轨迹对无人机的电力巡检作业方案进行描述。图2中,无人机d1、d2和d3电池满载电量为8。无人机d1和d2随保障车h1由驻车点1出发到达驻车点4,也即表示为时空电路径(1,0,8,4,2,8)。由此可知,无人机d1的时空电轨迹包括弧段(1,0,8,4,2,8)、(4,2,8,4,4,8)、(4,4,8,14,7,7)、(14,7,7,14,12,6)、(14,12,6,11,16,5)、(11,16,5,11,21,4)、(11,21,4,7,27,2)、(7,27,2,7,29,8)、(7,29,8,12,33,6)和(12,33,6,12,38,5),无人机d2的时空电轨迹包括弧段(1,0,8,4,2,8)、(4,2,8,4,4,8)、(4,4,8,16,7,7)、(16,7,7,16,12,6)、(16,12,6,18,16,5)、(18,16,5,18,20,3)、(18,20,3,4,25,2)、(4,25,2,4,27,8)、(4,27,8,6,31,8)、(6,31,8,6,33,8)、(6,33,8,15,36,7)和(15,36,7,15,38,6),无人机d3的时空电轨迹包括弧段(1,0,8,5,5,8)、(5,5,8,5,7,8)、(5,7,8,17,11,7)、(17,11,7,17,17,6)、(17,17,6,19,20,5)、(19,20,5,19,25,4)、(19,25,4,10,28,3)、(10,28,3,10,32,2)、(10,32,2,2,36,1)和(2,36,1,2,38,8)。由各无人机的时空电轨迹可见,考虑到电力杆塔的体积构造以及需要着重检测的位置不同,无人机实际上需要在不同杆塔处的滞留的时间也有所不同。此外,无人机在执行不同的电力检测任务时通常需要开启不同的传感器和信息通信模块,由此导致能耗速率的差异。例如,图2中,无人机d1在巡检电力杆塔11时滞留时间为5个时间单位,耗电量为1个单位,而无人机d2在巡检电力杆塔18时滞留时间为4个时间单位,耗电量为2个单位。考虑到无人机在各项性能指标具有一致性的情况下,可知相对于电力杆塔18,杆塔11的巡检任务耗时更长,但杆塔18的巡检任务耗电量更多。需要注意的是,上述电力巡检任务的差异性会通过无人机时空电网络的结构特性加以刻画。例如,无人机在到达示例中电力杆塔11后须通过一条长5个时间单位,1个电量单位的等待时空电弧段,而在到达杆塔18后也须通过一条长4个时间单位,1个电量单位的等待时空弧段才能够完成杆塔18的巡检任务。

2 模型建立

2.1 模型假设

本文提出的VUCOP 旨在通过优化协同保障车与无人机的电力巡检作业方案,在保证完成电力巡检任务的前提下尽可能地降低系统运行总成本,同时还要考虑保障车的载重限制,无人机的续航限制,天气对无人机飞行速度的影响和可行的飞行路径等决策要素。鉴于优化问题本身的复杂性,为进一步聚焦研究内容,做出如下假设:

(1) 无人机和保障车均具有一致的性能指标,包括行驶(或飞行)速度和能耗速率等。

(2) 无人机仅在驻车点与各电力杆塔以及各电力杆塔之间飞行,驻车点和运维站之间由保障车运送。

(3) 电力巡检无人机普遍采用快速换电模式,无人机在返回驻车点换电后即可在单位时间段内完成换电和维保。

2.2 符号定义和数学模型

除上文中定义的集合符号,模型中涉及的其他主要参数和变量定义如下:

cD——无人机固定使用成本

cH——保障车固定派遣成本

q——保障车可同时承载和服务的最大无人机数量

mO——保障车虚拟时空起点

mD——保障车虚拟时空终点

uO——无人机虚拟时空电起点

uD——无人机虚拟时空电终点

因此,基于时空电网络建模方法,VUCOP优化模型具体为:

目标函数式(1)表示VUTIS综合作业方案的总成本最小,包括保障车和无人机各自的固定派遣成本以及可变行驶成本。其中和分别为保障车和无人机的派遣成本,分别为两者在执行电力巡检任务过程中的行驶和飞行成本。由目标函数形式可知,VUCOP 优化决策中包括优化无人机和保障车的派遣数量以及无人机和保障车在任务执行过程中的协同作业计划。约束条件式(2)、(3)分别为保障车和无人机的时空(电)轨迹的流平衡约束。其中,α和β分别为式(2)、(3)的流平衡状态参数,即当m=mO时,α=1;当m=mD时,α=-1;当m∈NH时,α=0。当u=uO时,β=1;当u=uD时,β=-1;当u∈V时,β=0。需要注意的是,未派出的无人机和保障车的时空轨迹仅包含由虚拟起点到虚拟终点的时空(电)路径,不会产生相应的派遣和作业成本。式(4)确保每座电力杆塔都接受巡检。其中,集合={(i,t,e)|(i,t,e)∈VD}表示杆塔i∈ID对应的所有时空电节点集合,向量(u,u′)=(i,t,e,j,s,f)∈KD,表示以u=(i,t,e)∈VD为起始节点的对于杆塔i的巡检时空电弧段。式(5)为保障车和无人机作业方案的耦合关联约束,即无人机由保障车承载完成各驻车点及运维站之间的转移,且需要在驻车点处由保障车进行换电。集合

表示无人机由保障车承载通过时空弧(m,n)∈AH所对应的时空电弧段集合。该约束表示保障车在干线(驻车点间或驻车点与运维站之间)的时空弧段数与载重量的乘积q均不得小于无人机相对应时空电弧段的数量,即可以保证无人机放飞、回收和转场等操作均要求保障车及时到达指定位置并全程提供保障服务。式(6)、(7)分别为变量的完整性约束。

3 模型求解算法

由于采用了时空网络建模方法,VUCOP 本质上可视为基于轴辐式网络的TTRP衍生问题,而后者已被证明是NP-hard问题[21]。在TTRP 的基础上,VUCOP 进一步要求无人机和保障车的协同作业方案在时间上保持协同,同时还需要考虑电力巡检任务执行过程中无人机的电量限制,以及保障车承载无人机的数量限制,因此模型结构更为复杂,求解更难。为了在保证优化方法计算效率的同时尽可能地提高求解精度,本文根据VUCOP 优化模型结构设计基于LR 算法框架的优化求解方法,将原问题拆分为两组结构相对简单、求解效率较高的子问题,得到原问题的松弛解。在此基础上,根据每个松弛子问题包含的优化决策信息设计高效算法得到相应的可行解。最后,通过次梯度算法更新迭代松弛因子,缩小上下界之间的差值直到求得满足实际决策需求的近似最优解甚至最优解。

3.1 基于LR的原问题模型分解

首先,VUCOP为整数线性规划问题且其优化模型结构满足KKT条件[22],适用于LR算法进行求解;其次,通过分析模型的约束条件可知,式(4)、(5)是建立了多组变量间的耦合关联的难约束。因此,通过松弛这两组约束,可以将原问题分解为两组互不关联的子问题,每组子问题结构相对简单,便于求解。

然后得到原问题的对偶问题,即

满足约束条件式(2)、(3)和式(6)、(7)。

由于松弛了约束条件式(4)、(5),解除了变量X、Y之间的耦合关联,因而松弛问题可以拆分为两个相互独立的子问题。其中,问题S1中包含了个独立子问题,以决策每辆保障车的作业方案,即

满足约束式(2)、(6)。

满足约束式(3)、(7)。

由于每组松弛子问题都只包括一组变量及其对应的流平衡约束和完整性约束,结构相对简单且符合全幺模性质,因而可直接将子问题松弛为连续线性规划问题,且以往相关研究中已证明得到的最优解仍然能够保证二元性[23]。即此时约束条件式(6)、(7)可替换为:

线性化之后,每个独立子问题均可采用单纯形法和内点法等连续线性优化算法进行快速求解,且可采用分布式并行计算进一步提高求解效率。

根据LR 的对偶性可知,由此得到的松弛问题目标函数最小值即为原问题目标函数最小值的下界。

3.2 松弛解的可行化方法

由于松弛了原问题模型中的两组关键约束式(4)、(5),在求解中等实际规模问题时得到的协同作业方案大多数不可行,需要根据每组松弛解能够提供的决策信息及其之间的关联性重新构建耦合关联,以得到原问题的可行解。由于松弛解的可行化算法直接关系到最终优化结果的精度和算法整体的求解效率,所以算法需要兼顾每次循环的求解质量和速度,以提高LR-GR 算法整体的收敛效果同时尽可能地减少算法复杂度。由此,本文根据问题特点提出基于贪心规则的两阶段可行化算法。

首先,对未接受巡检的电力杆塔所对应的巡检时空电弧段重新赋予权重,新增派遣无人机完成剩余的巡检任务,之后再根据所有无人机的派遣方案对集合AH内时空弧段的权重进行赋值,逐次增派保障车覆盖相应时空弧段直至完成所有无人机保障任务。需要注意的是,保障车作业方案还需要特别考虑无人机的承载数量限制。具体步骤如下:

步骤1根据松弛解筛选得到仍未接受巡检的电力杆塔集合IR。

步骤2对于所有时空电弧段(u,v)∈KD,生成权重参数:

式中,M为取值较大的固定参数。

步骤3选取无人机集合中尚未派遣的一架无人机d∈D,求解如下模型,得到相应的可行解,即

步骤5对于无人机集合中尚未派遣的保障车h∈H,求解模型:

步骤6输出最终可行解并将其代入原问题目标函数式(1),求得相应的目标函数值作为最小目标函数值的上界。

3.3 基于次梯度算法的LR乘子迭代方法

考虑到VUCOP优化模型结构的复杂性,在解决实际规模问题时需要通过不断迭代LR 乘子的取值缩小原问题最优解的上下界之间的差值,不断改善可行解的质量,在合理的运算时间内得到满足实际要求精度的可行解甚至是最优解。本文采用的次梯度算法计算复杂度低,在诸多相关领域研究中都能以较高的执行效率迭代LR 乘子的取值快速收敛上下界。算法具体步骤如下:

步骤0初始化。

(1) 迭代次数K0;

(2) 步长因子(τ)0=2;

(3) 最优解上界(UB)0=-∞;

(4)LR 乘子:(λi)0=0,∀i∈ID,(μmn)0=0,∀(m,n)∈AH。

步骤1求解松弛子问题S1和S2,得到松弛解即原问题目标函数最大值的下界(LB)K。

步骤2根据2.2节的两阶段算法将松弛解可行化得到可行解和相应的目标函数值,如果该取值大于下界,则更新上界(UB)K→(UB)K+1。

步骤3如果在一定迭代次数之内可行解没有明显改善,即下界没有明显上升,则更新步长因子(τ)K=(τ)K+1/θ,θ＞1。

步骤4按照下式计算第K+1次迭代的步长:

步骤5按照下式得到第K +1次迭代的LR乘子:

步骤6若满足以下任意条件则停止迭代,并输出最优上界作为最终的目标函数值,相应的可行解以及上下界之间的相对差值;否则,K→K+1,跳转至步骤2。

(1) 最优解上下界的相对差值(即LR-GR 算法的相对误差)小于预设的阈值,即 ((UB)K -(LB)K)/(LB)K≤ε;

(2) 步长因子小于阈值,即(τ)K＜;

(3) 迭代次数达到预设的最大迭代数,即K=。

4 算例分析

为了验证本文优化方法的性能,首先通过一组可变规模的算例比较LR-GR 算法与CPLEX 商用求解器的计算时间和精度,再通过一个较大规模算例进行敏感性实验分析无人机电池最大载电量对于VUTIS在最优作业策略下的影响,进而得到相应的管理学启示。本文的所有算例均用MATLAB编程实现,使用的CPLEX 版本是12.6.3 学术版,并通过Yalmip工具箱做接口调用。算例的运行环境为载有Intel(R)Core(TM)i7-8700 CPU 3.2 GHz处理器和16 GB内存的台式计算机。

为了保证可变规模算例的代表性,VUTIS网络参照图1中的轴辐式网络结构,驻车点间的距离在[1,5]km 内随机生成,电力杆塔之间以及电力杆塔与驻车点之间的距离在[0.4,1]km 内随机生成。设系统运行的时间段内包含60个时间戳,时间间隔为2 min。每辆保障车的固定派遣成本为100 元,单位距离行驶成本为0.5元/km,平均行驶速度为30 km/h,每辆车最多可以同时承载和服务2架无人机。每架无人机的固定使用成本设为30元,单位距离飞行成本为0.1 元/km,平均飞行速度为12 km/h。设无人机电池电量包含15个电量等级,每个电量等级1 000 m Ah。假设无人机每飞行2 min消耗1个电量等级。

在对比试验中CPLEX 的最大计算时间设置为3 000 s,如果在此时间范围内无法找到可行解,则以“NA”表示。LR-GR 和CPLEX 的优化结果和性能对比如表1所示。需要说明的是,表中“规模”项的3组数字分别表示每个算例的驻车点、电力杆塔、保障车以及无人机的数量。

通过表1中两种求解方法的计算结果可知,随着问题规模的逐渐扩大,两者的计算时长也都随之增长,且求解精度也逐渐降低。在算例1 中,LRGR 算法的计算时间长于CPLEX,相对误差也要高于CPLEX。可见,在求解较小规模算例时,CPLEX的计算性能要高于LR-GR 算法。随着网络规模的扩大,电力杆塔、驻车点、保障车和无人机的总数逐渐增加,虽然LR-GR 算法性能有所下降,但由于其采用了LR 松弛和独立子问题并行计算等策略提高了算法的计算效率,因而依然能够保证相对较高的性能。相比之下,CPLEX 则劣化更为严重。尤其对于较大规模算例7和8,CPLEX 已经无法在3 000 s内给出可行解,但LR-GR 算法仍然能够保证在实际操作中可接受时间范围内给出较高质量的可行解(最大规模案例8的计算时间不超过2 000 s,计算误差小于14%)。需要注意的是,VUCOP 是涉及多层复杂网络多主体协同优化的运营决策问题,此类问题的复杂度较高。考虑到车载无人机优化调度领域内相似研究中求解方法的性能表现[14,20],由对比实验的结果可见,本文基于LR 框架的算法在解决较大规模问题时具有相对较高的精度和计算效率。

表1 LR与CPLEX优化结果及性能比较

此外,为了充分反映两种求解方法优化得到的任务执行方案的总体效率,优化结果还对比了两者求解得到的总派遣成本和总行驶成本。其中,总派遣成本是指无人机和保障车的固定派遣成本之和,总行驶成本是无人机飞行成本和保障车行驶成本之和。由两组参数的对比结果可知。LR-GR算法得到的无人机和保障车的派遣成本在每组算例中都不大于CPLEX派遣成本。鉴于总派遣成本占总成本的比例较高,因此,LR-GR 算法求解得到的系统总成本也不大于CPLEX。此外,除算例1和2之外的所有可比较算例中,LR-GR算法都能够优化得到更低的总派遣成本,且两者差距也随着问题规模的扩大而不断增加。由总行驶成本的对比结果可知,在算例1中LR-GR 算法与CPLEX的总行驶成本相同,算例2中LR-GR求解得到的总行驶成本小于CPLEX。这说明,在较小算例中总派遣成本相同的情况下,LR-GR 算法求解得到的总行驶成本不高于CPLEX。而在其他规模较大案例中,LR-GR 求解得到的总行驶成本则要略高于CPLEX。这是由于在这些算例中,无人机和保障车派遣数量的增加能够在一定程度上降低两者的运行调度成本,但由于在系统总成本中,总派遣成本占比远高于总行驶成本,可知LR-GR 算法优化得到的系统总成本低于CPLEX。

图3所示为LR-GR 算法求解算例5过程中的相对误差随迭代次数的变化。可见,由于LR-GR算法的松弛解可行化方法的精度较高,迭代初期就能以较快的速度收敛至相对较低的误差(以低于30的迭代次数达到接近10%的相对误差)。因此,管理者可以根据实际的优化决策需求在保障一定求解精度的同时适当减少迭代次数和计算时间。

图3 LR-GR 算法相对误差随迭代次数的变化

为了进一步验证VUCOP 中关键参数的改变对于系统整体运作策略以及相应指标的影响,以算例8的网络为基础,在保持其他参数取值不变的情况下将无人机的电量等级总数由10增长至30,以观察总成本和各部分成本的变化情况,其实验结果如表2所示。需要说明的是,这里假设无人机续航能力(即最大载电量)提高的同时不改变其载重和续航能力等性能。在实际应用中,企业可以通过购买续航能力更高但其他性能维持不变的同系列不同型号的无人机,这也符合相关行业中电力巡检的管理运营需求。

表2 系统运行各指标随无人机电量等级总数的变化

由表2可见,在无人机电池最大载电量由10增长至20的过程中,总成本和其他各部分成本总体上呈下降趋势。随着无人机电池最大载电量的提升,无人机的飞行成本则由7.34元波动式下降至4.24元。尤其当无人机使用成本减少时,无人机飞行成本会出现先增后减的情况。如算例1～3中,无人机使用成本由240元下降至210元,而无人机飞行成本先由7.34 元增长至8.28 元又下降至5.48 元。这说明,在最优作业计划下无人机续航能力的提高确实能够以更少的无人机和保障车完成电力巡检任务,但相对地需要每架无人机承担更多的电力巡检任务,增加所有无人机的总飞行距离;同时,也需要保障车载无人机更加频繁地往返于各驻车点,进而增加保障车的总行驶距离,最终产生更多的无人机飞行成本和保障车行驶成本。但也注意到,随着无人机最大载电量的不断提升,系统效率提升的幅度也在逐渐降低,直至无人机最大载电量提升至24之后,无人机和保障车的派遣成本均维持不变,且总成本的下降幅度也相对较小。由此可见,提高无人机最大载电量所带来的边际收益也随之减少。

5 结论

针对目前“一对一”模式下车载无人机电力巡检系统对无人机和保障车利用率低的问题,结合电力巡检任务范围大,任务点分布稀疏的特点,以提升系统运行效率、灵活性和经济性为目标,提出基于时空网络的“多对多”车载无人机协同作业优化决策方法。研究成果为解决轴辐式双层网络下多主体协同优化决策问题提供了新方法,从无人机与车辆协同作业研究方向上进一步拓展了VRP-D的相关研究,对于车载无人机系统在电力巡检中的进一步推广和提升电力巡检的自动化和智能化水平具有实践指导意义。研究成果的创新之处可具体归纳为:

(1) 根据无人机电力巡检的相关技术背景,通过调研相关行业目前在无人机电力巡检实际运作中遇到的问题和关键需求,提出了车载无人机电力巡检系统的作业模式,为未来的无人机电力巡检的实践管理提供理论支撑。

(2) 针对车载无人机电力巡检协同作业优化问题,提出基于时空网络的无人机与保障车协同路径优化方法,将电力巡检过程中的天气和交通状态等决策要素整合到时空网络构建和时空路径生成机制中,简化了模型的形式。

(3) 为精准刻画无人机巡航能力限制对系统决策的影响,在时空网络的基础上增加了无人机电量维度,避免在构建电量限制约束时出现非线性结构,进一步提高模型的可解性。

(4) 根据VUTIS中保障车和无人机作业方案的时空关联特性,在LR 算法框架的基础上提出LR-GR 算法,以兼顾单步迭代的计算效率和求解质量,并通过与CPLEX 求解器的对比验证了优化算法在解决实际规模问题上的有效性。

此外,本文还通过敏感性分析实验研究了无人机电池总载电量对于VUTIS运作策略和运行成本的影响,并得到了一些重要的管理启示。例如,虽然无人机电池最大载电量的提高能够节省无人机和保障车的派遣数量,降低固定成本,但又会提高每架无人机和每辆保障车的使用效率而在一定程度上提高行驶成本。由于无人机和保障车的行驶成本均远小于各自的固定派遣成本,所以总成本仍然会下降。但这种下降趋势也会随着最大载电量的不断增加而趋于平稳。由此可知,在系统建设和设备采购阶段可以通过选择续航能力更强的无人机而适当减少无人机的采购数量,但过度追求长续航的无人机必然会提高单架无人机的采购成本,最终导致系统运营总成本过高。

本文提出的时空状态网络模型加LR 松弛算法的优化方法理论框架,为研究车载无人机电力巡检系统设计和运营调度各类问题拓展研究思路。例如,考虑到无人机电力巡检的实际操作过程中面临的诸多不确定因素,在之后的研究中将更加关注VUTIS在运行过程中受到的外界环境干扰而出现的随机场景,并针对这一问题将尝试采用随机规划的方法对无人机电力巡检系统的资源配置和网络布局进行可靠性设计。为提高无人机电力巡检的作业效率,在部分作业场景下会将电力杆塔和电缆的巡检任务同步进行,由此产生车载无人机综合电力巡检作业优化问题也将是未来研究的关注方向。最后,在求解结构更加复杂的优化问题时,还需要基于现有的LR 优化方法框架进一步提高单步计算的求解质量,加速收敛过程,以期在解决实际规模问题时能够以合理的计算时间得到更高精度的近似最优解。