多目标优化最低代价无人机机巢选址方法研究.pdf
《多目标优化最低代价无人机机巢选址方法研究.pdf》由会员分享,可在线阅读,更多相关《多目标优化最低代价无人机机巢选址方法研究.pdf(9页珍藏版)》请在咨信网上搜索。
1、第 46 卷第 6 期2023 年 6 月重庆大学学报Journal of Chongqing UniversityVol.46 No.6Jun.2023 多目标优化最低代价无人机机巢选址方法研究戴永东1,黄政2,高超3,王茂飞1(1.国网江苏省电力有限公司泰州供电公司,江苏 泰州 225300;2.中南大学 自动化学院,长沙 410083;3.国网江苏省电力有限公司,南京 210000)摘要:无人机巡检作业中,因为功能与续航距离不同,常面临异构无人机协同和机巢选址问题。无人机机巢的最优部署位置策略,可以看作新的选址优化问题,相对于传统设施选址问题,无人机机巢部署问题面临更多新挑战。笔者综合运
2、用地理信息系统、优劣解距离法对候选点位做预筛选后使用贪心算法和拉格朗日松弛优化的 p-中值覆盖问题优化方法,在综合考虑布点原则、飞行任务、飞行半径、功能性冗余等目标因素,提出一种多目标优化最低代价的无人机机巢选址法,将机巢分布问题定义为限制因素预选址前提下的 p-中值最低代价问题,设置原则性约束,实现多目标优化最低代价的机巢布点,从多个角度考虑降低巡检成本。实验结果表明:多目标优化后机巢布点在建造、维护、巡检和综合成本上比传统选点方法有 9.2%以上的成本节约。关键词:无人机巡检;机巢布点;目标优化;最低代价;原则性约束中图分类号:TM755 文献标志码:A 文章编号:1000-582X(20
3、23)06-136-09A UAV nest deployment method with multi-target optimization and minimum costDAI Yongdong1,HUANG Zheng2,GAO Chao3,WANG Maofei1(1.State Grid Taizhou Power Supply Company,Taizhou,Jiangsu 225300,P.R.China;2.School of Automation,Central South University,Changsha 410083,P.R.China;3.State Grid
4、Jiangsu Electric Power Company,Nanjing 210000,P.R.China)Abstract:In the unmanned aerial vehicle(UAV)inspection operation,heterogeneous UAVs often face coordination and nest site selection problems due to their different functions and range capabilities.The optimal deployment strategy of the UAV nest
5、 can be seen as a new type of location optimization problem.Compared with the traditional facility location problem,the deployment of the UAV nest is facing more new challenges.This paper comprehensively uses geographic information systems and TOPSIS method to pre-screen candidate locations,and then
6、 uses a combination of greedy algorithms and Lagrange relaxation optimization of the p-median coverage problem optimization method.After comprehensively considering factors such as node placement principles,flying tasks,flying radius,and functional redundancy,a multi-objective optimization lowest-co
7、st UAV nest location method is proposed.The nest distribution problem is defined as a p-median problem with the lowest doi:10.11835/j.issn.1000.582X.2023.06.013收稿日期:2022-10-11基金项目:湖南省自然科学基金资助项目(2022JJ30742)。Supported by Natural Science Foundation of Hunan Province of China(2022JJ30742).作者简介:戴永东(1969
8、),男,高级工程师,主要从事智慧电网技术、智能运检技术、无人机智慧巡检技术方向研究,(E-mail)。通信作者:王茂飞,男,工程师,(E-mail)。戴永东,等:多目标优化最低代价无人机机巢选址方法研究第 6 期cost under pre-selected restricted factors,and principal constraints are set to achieve multi-objective optimization lowest-cost node placement and reduce inspection costs from multiple perspect
9、ives.The experimental results show that the cost savings of the nested distribution after multi-objective optimization are more than 9.2%compared with those of traditional methods in terms of construction,maintenance,inspection,and comprehensive costs.Keywords:UAV inspection;nest deployment;target o
10、ptimization;minimum cost;principle constraints 随着中国电网规模扩大,无人机自动化电力线路巡检取代人工巡检已成为当下一大趋势。为进一步提升运检输变配送专业精益化管理水平与运维效率,降低运行成本,缓解巡检人员不足和巡检日益精细化矛盾,提升无人机巡检全自主水平,在电力线路巡检范围内设定不同规模的无人机巢点,作为无人机充电、安放的固定场所至关重要。无人机机巢位置固定,且每个机巢覆盖范围有限,需要通过设置不同机巢,实现电力网络全覆盖目标,由此产生机巢位置的最优部署问题。无人机机巢的最优部署位置策略,可看作一类新的选址优化问题。相对于传统的设施选址问题,无人
11、机机巢部署问题面临更多新挑战1。一方面,无人机在三维空间移动时,起飞点和降落点要有一定面积的空旷区域,在飞行途中可能面临避障航迹规划问题2;另一方面,无人机续航能力有限,其电池容量限制有效载荷和持续工作时间,综合考虑飞行距离、服务时间、巡检质量的同时还需要考虑电量消耗问题。无人机机巢的选址方法可部分借鉴通信设施的选址问题,然而相比传统通信设施选址,无人机选址过程存在更加复杂的环境约束和更大的优化空间。在进行无人机选址任务时,需要明确原则性约束,比如无人机机巢必须设置在有人看守且方便维护的地方,这些原则性约束构成机巢选址过程的过滤条件集合,能够高效排除不符合这些条件的点位,显著缩小算法的搜索空间
12、。此外,机巢选点问题不同于传统通信基站选点问题的一个关键因素是优化目标不同,在进行通信基站选点时,只需保证通过设立基站达到信号的全域覆盖即可。而在进行无人机机巢选点时,不仅需要达到搜索范围的全域覆盖,还需要针对一次性投入的基站建设成本、巢维护、巡检成本等长期投入成本进行多目标优化。结合使用地理信息系统、优劣解距离法和优化 p-中值覆盖方法,综合考虑建造成本、维护成本和巡检成本 3种不同成本,基于改进的 p-median算法提出可行的选址方案。1相关研究机巢布点应首先采用布点规划方法进行布点模拟,再通过遗传算法、禁忌搜索3等方法进行优化。笔者对布点规划方法现状进行讨论,分析基于地理信息系统(GI
13、S)和优劣解距离法的机巢选址方法,横向对比不同代价函数的集合覆盖问题在机巢选址中的优劣。1.1基于 GIS的选址方法随着计算机技术的不断发展,地理信息系统(GIS)46已成为因子评估法中的重要辅助决策手段,被广泛应用于机场选址的研究中。GIS可以将自然地理环境因素如地形、地貌等可视化呈现,从而使分析结果更加科学。除了 GIS,还有其他的辅助决策手段,如多准则决策分析法(multi-criteria decision analysis,MCDA)7、模糊综合评价法(fuzzy comprehensive evaluation,FCE)8等,这些方法可以将各种因素进行量化和比较,从而为机场选址提供
14、科学决策依据。机场选址是一个复杂过程,包括 GIS需要大量数据支持,数据的质量直接影响到机场选址结果的准确性和可靠性;GIS需要专业的地理信息系统技术人员进行操作和分析,需要投入大量的人力和物力资源,不是所有机构和企业都能承担这种成本;GIS只能考虑到数据中存在的因素,而不能考虑到数据之外其他因素,如政策和法律等因素,可能会导致机场选址结果并不是最优。1.2基于优劣解距离法的选址方法优劣解距离法又叫技术偏好排序法(technique for order preference by similarity to an ideal solution,137重 庆 大 学 学 报第 46 卷TOPSI
15、S)是一种常用的多准则决策分析方法,基本思想是通过计算每个决策方案与最优解和最劣解之间的相似度来确定方案的优劣程度。陈俊锋等9利用自然条件、水域条件和交通条件 3个方面构建了 EWM-TOPSIS 模型,用于水上机场选址。同时,种小雷等10对障碍物净空条件的影响程度和范围进行了量化研究,为选址阶段场址之间净空条件的优劣判定提供了新的思路和方法。付蔷等11根据对候鸟迁徙规律研究以及对大连现有和迁建机场周边候鸟的调查数据,比较研究了不同机场建设选址方案对候鸟迁徙的影响。TOPSIS 方法的优点是简单易用,不需要事先确定权重,能处理多个评价指标,同时具有较高可解释性。缺点是对标准化处理要求较高,正负
16、样本标注过程较为繁琐,容易受到评价指标的数量和范围等因素影响,需进行灵敏度分析。1.3最优集合覆盖问题集合覆盖问题12(SCP)是运筹学研究中典型的组合优化问题之一,工业领域里的许多实际问题都可建模为集合覆盖问题,如资源选择问题、设施选址问题(移动基站选址、物流中心选址)等13。SCP一般是在确保覆盖范围的前提下,建立最少的服务设施点以覆盖所有需求点14,其优化目标为总体费用,覆盖范围为约束条件。集合覆盖问题已被证明是一个 NP完全问题,没有多项式时间精确算法,因此实际应用中,往往采用一些近似算法,如贪婪算法;或元启发式算法,如蚁群算法15、遗传算法16等来求得近似最优解。基于 SCP的无人机
17、基站部署问题是在满足规定覆盖比例前提下,融合无人机基站相关约束,优化所需无人机数量及部署位置17。Mozaffari等18假设无人机基站具有相同发射功率和高度,研究了覆盖半径为 R的圆形区域所需的最少无人机数量。Lagum 等19研究了地面网络存在下无人机基站部署的集覆盖问题。在应用时根据具体场景,代价计算模型又分为 p-中值模型和 p-中心模型20。其中,p-中值模型使各任务点到机巢的加权平均距离最小,而 p-中心模型要求使各任务点到机巢的最远距离最小,在无人机巡检语境下,前者可以使单次巡检总路径长度(二阶范数)相对较小,而后者主要使无人机最大响应时间(无穷范数)最小(横向对比如表 1所示)
18、。2基于多目标优化的无人机机巢布点规划无人机机巢为无人机起降提供平台和运输导航系统,也为无人机自主巡检提供完善的路线规划和安全保障21。设置机巢能有效帮助无人机及时完成充电,更好实现飞行巡检任务。2.1可用机巢类型无人机机巢根据存放无人机类型不同划分为 3种,即大型多旋翼机巢、中型多旋翼机巢和小型多旋翼机巢。在该设计中,3种机巢之间的差异集中体现在覆盖半径和可承担巡检任务上,其中大型无人机巢有效覆盖半径为 7 km,中型无人机巢有效覆盖半径为 5 km,小型无人机巢有效覆盖半径仅为 3 km。因 3 种类型的无人机巢实际承担的巡检任务要求互不相同,因此考虑将 3种不同类型的无人机巢部署视为 3
19、次机巢选址过程,分别使用所述机巢选址方法进行独立规划。所述选址方法以小型机巢选址为例,大、中型机巢选址过程同理。表 1代价横向对比Table 1Horizontal comparison of costs策略名称SCPp-medianp-center原理在全覆盖的情况下,优化所需无人机数量及位置使各任务点到机巢的加权平均距离最小使各任务点到机巢的最远距离最小优点以全覆盖为目标,尽量减少成本,方便进行方案调整主要考虑整体的覆盖水平,覆盖效率较高能够满足在应急条件下,距离较远的任务也可以以可控的成本完成缺点不同任务执行频次不同,需要进行人工调整不能考虑距离较远的任务点,不能适应应急场景整体的覆盖水
20、平较差138戴永东,等:多目标优化最低代价无人机机巢选址方法研究第 6 期2.2基于地理信息系统的初步位置筛选无人机固定机巢选址原则主要考虑机巢部署区域不受到外界因素干扰,同时满足机巢供电需求及网络资源需求。为便于管理,部署区域一般定于供电所和本地运维管辖的变电站内。基于这些原则并结合电网地图信息、地形数据和禁飞区信息综合研判可初步筛选获得满足全部硬性要求的候选点位集合。具体来说,这些原则要求可部署固定机巢的位置包括:变电站生活区、供电所空旷区及办公楼楼顶、提供供电及网络区域、无禁飞限制区域等。除原则性要求外,还需要考虑无人机覆盖半径约束对机巢选址的影响。对每个机巢而言,其只需负责其覆盖半径内
21、的巡检目标。该约束可用欧氏距离表示为|(d,u)|r;d D,u U,(1)式中:D为源点集,即本研究中的机巢位置;U为目标点集,即本研究中的任务点位置;r为无人机的覆盖半径,在该例中为 3 km;该式限制机巢与其负责的目标点构成矢量模应小于等于机巢覆盖半径。根据该约束信息可得到机巢点-目标点二部图,进而得到小类集合S,表示为算法 1:小类集合生成输入输入:原点集D;目标点集U;覆盖半径r;输出输出:小类集合S1)Initialize list S,s;2)for d in D;3)清空 s;4)for u in U;5)if distance(d,u)r;6)S.append(u);7)S.
22、append(s);8)return S;在集合覆盖问题语境下,小类集合S中的每一项(小类)中元素的交集应等于总集U,才可实现覆盖。在实现集合覆盖的前提下,又需要考虑实现覆盖所需要的成本或代价。基于地理信息系统的初步位置筛选步骤如图 1。图 1基于地理信息系统的初步位置筛选流程图Fig.1Preliminary Location Screening Flowchart Based on Geographic Information System139重 庆 大 学 学 报第 46 卷使用 ArcGIS 对原则要求绘制单一图层,针对每一个原则,人为判断是否是适宜区。使用 ArcGIS Toolb
23、ox将适宜区赋值为 1,不适宜区赋值为 0,得到变电站生活区图层、供电所空旷区及楼顶图层、可提供供电及网络区域图层和无禁飞区域图层。叠加评估。为了得到综合评估结果,通过对以上 4个图层设置平均权重,进行叠加,根据叠加后综合图层的值进行判断,设置阈值,重新划分 0,1。聚类分析。使用基于欧氏距离的 K-means算法,以半径距离为 3 km 能够覆盖为前提,确定 K个聚类中心。获得初选区域。根据聚类结果在 GIS图上得到实际地点坐标。2.3基于多目标优化的机巢选址机巢选址问题因其应用特殊性,不能简单归结为集合覆盖问题。在使用最少基站数量做到全域覆盖的前提下,还需要考虑实际应用场景下的优化问题。在
24、做多目标优化时,需要考虑多种目标之间的权衡关系,该关系通常使用权重 进行控制,并利用拉格朗日乘子法等优化方法,使最终目标达到帕累托最优,但在本问题中存在区别于传统优化方法的特点,即机巢位置一旦确定下来,便难以更改。因此,在选址时需要确定几个目标之间的权重关系,即针对一个特定实施方案,几个目标之间的权重总是静态的。因此针对机巢选址场景,多目标优化实质上被转化为同质化的代价数值优化,在此基础上,确定可量化的代价数值就成为了优化过程的关键。在本方案中着重考虑 3种类型的代价:机巢建设代价、机巢维护代价和巡检代价。2.3.1机巢建设代价机巢建设作为一个系统性工程项目,不同实施难度会直接造成建设成本有所
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 多目标 优化 最低 代价 无人机 选址 方法 研究
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。