(19)國(guó)家知識(shí)產(chǎn)權(quán)局(12)發(fā)明專利公司32200專利代理師胡杰審查員張菁一種基于改進(jìn)分支限界算法的無(wú)人機(jī)路徑本發(fā)明公開了一種基于改進(jìn)分支限界算法平面點(diǎn)集的聚類和局部TSP問題，通過融合K-means聚類與分支限界算法實(shí)現(xiàn)協(xié)同求解；針對(duì)算法以及分支限界算法，本發(fā)明方法在小規(guī)模TSP實(shí)例中可以獲得更優(yōu)解，針對(duì)大規(guī)模任務(wù)場(chǎng)權(quán)重機(jī)制將高優(yōu)先級(jí)任務(wù)節(jié)點(diǎn)的訪問時(shí)序優(yōu)化結(jié)合任務(wù)優(yōu)先級(jí)以最短路徑為目標(biāo)，構(gòu)建無(wú)人機(jī)巡航的最優(yōu)路徑結(jié)合任務(wù)優(yōu)先級(jí)以最短路徑為目標(biāo)，構(gòu)建無(wú)人機(jī)巡航的最優(yōu)路徑目標(biāo)函數(shù)，根據(jù)任務(wù)點(diǎn)分配互斥性、電池容量和任務(wù)點(diǎn)時(shí)序耦合構(gòu)建約束函數(shù)。構(gòu)建系統(tǒng)服務(wù)質(zhì)量評(píng)估模型。輸入任務(wù)點(diǎn)集合與無(wú)人機(jī)基站位置，基于K-means算法進(jìn)行任務(wù)分配，引入方差與離散度評(píng)價(jià)進(jìn)行聚類篩選，輸出n個(gè)互斥子任基于改進(jìn)的分支限界法進(jìn)行航跡規(guī)劃，用貪心策略生成上界，根據(jù)搜索過程中節(jié)點(diǎn)訪問狀態(tài)的三種情況計(jì)算下界，根據(jù)單步和多步回溯情況進(jìn)行動(dòng)態(tài)剪枝。針對(duì)大規(guī)模任務(wù)節(jié)點(diǎn)，提出一種基于空間劃分的近似優(yōu)化策略，結(jié)合貪心算法和分支限界法，通過對(duì)平面上的點(diǎn)進(jìn)行劃分，不斷更新根節(jié)點(diǎn)來減少分支限界法的枝，達(dá)到快速計(jì)算。21.一種基于改進(jìn)分支限界算法的無(wú)人機(jī)路徑優(yōu)化方法，其特征在于：包括以下步驟：S1、構(gòu)建無(wú)人機(jī)巡航系統(tǒng)；結(jié)合任務(wù)優(yōu)先級(jí)以最短路徑為目標(biāo)，構(gòu)建無(wú)人機(jī)巡航的最優(yōu)路徑目標(biāo)函數(shù)，根據(jù)任務(wù)點(diǎn)分配互斥性、電池容量和任務(wù)點(diǎn)時(shí)序耦合構(gòu)建約束函數(shù)；構(gòu)建系統(tǒng)服務(wù)質(zhì)量評(píng)估模型；S2、輸入任務(wù)點(diǎn)集合與無(wú)人機(jī)基站位置，基于K-means算法進(jìn)行任務(wù)分配，引入方差與離散度評(píng)價(jià)進(jìn)行聚類篩選，輸出n個(gè)互斥子任務(wù)集；S3、基于改進(jìn)的分支限界法進(jìn)行航跡規(guī)劃，用貪心策略生成上界，根據(jù)搜索過程中節(jié)點(diǎn)的不同訪問狀態(tài)分別計(jì)算下界，根據(jù)單步和多步回溯情況進(jìn)行動(dòng)態(tài)剪枝；S4、通過基于空間劃分的近似優(yōu)化策略，結(jié)合貪心算法和分支限界法，通過對(duì)平面上的點(diǎn)進(jìn)行劃分，不斷更新節(jié)點(diǎn)來減少分支限界法的枝，完成計(jì)算；步驟S3中，用貪心策略生成上界具體包括以下分步驟：S3.1、從起始節(jié)點(diǎn)開始，選擇距離當(dāng)前節(jié)點(diǎn)最近的未訪問節(jié)點(diǎn)作為下一個(gè)訪問節(jié)點(diǎn)；S3.2、重復(fù)上一步驟，直至所有節(jié)點(diǎn)均被訪S3.4、計(jì)算該回路的總距離作為上界；步驟S3中，根據(jù)搜索過程中節(jié)點(diǎn)的不同訪問狀態(tài)分別計(jì)算下界；若搜索節(jié)點(diǎn)集合S僅包含起始節(jié)點(diǎn)，則考慮每個(gè)節(jié)點(diǎn)的進(jìn)出恰好都是最短距離的情況，下界1b的計(jì)算公式為：其中，D為距離矩陣，min1和min?分別表示矩陣行中的最小值和次小若搜索節(jié)點(diǎn)集合S包含起始節(jié)點(diǎn)和部分中間節(jié)點(diǎn)，則下界1b的計(jì)算公式為：其中，IS|表示已訪問節(jié)點(diǎn)數(shù)，\表示集合差運(yùn)算；表示搜素節(jié)點(diǎn)組中相鄰節(jié)點(diǎn)距離的和，min(D[S[1],:]\S)表示搜索節(jié)點(diǎn)組中的第一個(gè)節(jié)點(diǎn)到搜索節(jié)點(diǎn)組以外的其他節(jié)點(diǎn)的最小值，min(D[S[|S|],:]\S)表示搜索節(jié)點(diǎn)組中的最后一個(gè)節(jié)點(diǎn)到搜索節(jié)點(diǎn)組以外的其他節(jié)點(diǎn)的最小值，表示距離矩陣行中搜索節(jié)點(diǎn)組以外的其他節(jié)點(diǎn)的最小的兩值之和；若搜索節(jié)點(diǎn)集合S中包含所有節(jié)點(diǎn)，則下界1b表示為完整路徑長(zhǎng)度：步驟S3中，對(duì)當(dāng)前節(jié)點(diǎn)是否為末端節(jié)點(diǎn)進(jìn)行判斷，當(dāng)下界大于上界，且當(dāng)前節(jié)點(diǎn)非末端節(jié)點(diǎn)時(shí)，執(zhí)行單步回溯；首先移除最近加入的節(jié)點(diǎn)v,接著選擇下一個(gè)候選節(jié)點(diǎn)vk+1,最后更新搜索路徑[S[1],S[2],..,S[k-1],vk+1];3當(dāng)下界大于上界，且當(dāng)前節(jié)點(diǎn)為末端節(jié)點(diǎn)時(shí)，執(zhí)行多步回溯；首先連續(xù)移除末端節(jié)點(diǎn)，直至遇到非末端節(jié)點(diǎn)v,接著選擇v的下一個(gè)候選節(jié)點(diǎn)vm+1,最后更新搜索路徑為[S[1],S[2],…,S[m-1],vm+1];步驟S4中，基于空間劃分的近似優(yōu)化策略通過構(gòu)建分層求解框架，將全局優(yōu)化問題分解為多個(gè)局部最優(yōu)子問題，具體包括以下分步驟：S4.1、采用貪心算法生成初始可行解，形成閉合路徑P?,計(jì)算其總距離作為基準(zhǔn)上界；S4.2、對(duì)平面上的點(diǎn)進(jìn)行空間區(qū)域劃分：首先，以起始點(diǎn)0為極坐標(biāo)系原點(diǎn)，建立角度劃分準(zhǔn)則；其次，將路徑P覆蓋的平面區(qū)域劃分為k個(gè)扇形子區(qū)域{R?,R?,…,R};最后，在每個(gè)子區(qū)域R?內(nèi)選取節(jié)點(diǎn)集合V?={v?,V?,…,v};S4.3、分層優(yōu)化迭代：首先，在當(dāng)前層級(jí)使用步驟S3中改進(jìn)的分支限界法求解子區(qū)域節(jié)點(diǎn)集合V的最優(yōu)路徑P*;其次，選取P*中前(k-m)個(gè)節(jié)點(diǎn)作為下一層優(yōu)化的基準(zhǔn)節(jié)點(diǎn)集合B={b?,b?,…,Vk-m);最后，將剩余節(jié)點(diǎn)按空間鄰近性原則分配到各基準(zhǔn)節(jié)點(diǎn)鄰域，形成新的候選節(jié)點(diǎn)集V={v?,V?,…,v};S4.4、動(dòng)態(tài)更新機(jī)制：首先，對(duì)每個(gè)候選節(jié)點(diǎn)集V執(zhí)行局部分支限界優(yōu)化；然后，合并各局部最優(yōu)解形成全局近似解P′;2.根據(jù)權(quán)利要求1所述的一種基于改進(jìn)分支限界算法的無(wú)人機(jī)路徑優(yōu)化方法，其特征在于：所述步驟S1中，無(wú)人機(jī)巡航系統(tǒng)包括無(wú)人機(jī)、無(wú)人機(jī)基站以及不同優(yōu)先級(jí)的任務(wù)點(diǎn)，無(wú)人機(jī)基站數(shù)量表示為K={k?,k?,…,k},共有n個(gè)無(wú)人機(jī)基站，每個(gè)基站部署一架同構(gòu)無(wú)人機(jī)；任務(wù)點(diǎn)集合表示為V={V?,V?,…,V},共有m個(gè)巡航任務(wù)點(diǎn)；每個(gè)任務(wù)點(diǎn)有且僅有一架無(wú)人機(jī)服務(wù)，任務(wù)點(diǎn)按照優(yōu)先級(jí)順序被依次巡航。3.根據(jù)權(quán)利要求2所述的一種基于改進(jìn)分支限界算法的無(wú)人機(jī)路徑優(yōu)化方法，其特征在于：所述步驟S1中，將任務(wù)點(diǎn)集合V={V?,V?,…,V}分解為n個(gè)互斥子集u={U?,U?,…,U},無(wú)人機(jī)基站k,服務(wù)的區(qū)域表示為U,,則需要規(guī)劃該無(wú)人機(jī)從其所屬基站出發(fā)，遍歷區(qū)域U;內(nèi)所有的任務(wù)點(diǎn)后返航的最優(yōu)路徑；考慮巡航任務(wù)點(diǎn)的緊急程度不同，故引入任務(wù)節(jié)點(diǎn)優(yōu)先級(jí)因子p?∈{1,2,3},因此，無(wú)人機(jī)巡航的路徑規(guī)劃問題的目標(biāo)函數(shù)表示為：其中，表示無(wú)人機(jī)j從基站k;巡航至子集U,中的首個(gè)任務(wù)點(diǎn)的距離，表示從子集U?中的最后一個(gè)任務(wù)點(diǎn)返回對(duì)應(yīng)巡航無(wú)人機(jī)基站k;的距離，為子集U,中任務(wù)4.根據(jù)權(quán)利要求3所述的一種基于改進(jìn)分支限界算法的無(wú)人機(jī)路徑優(yōu)化方法，其特征在于：所述步驟S1中，考慮任務(wù)點(diǎn)分配互斥性約束、電池容量約束和任務(wù)點(diǎn)時(shí)序耦合約束，對(duì)于任意兩個(gè)無(wú)人機(jī)服務(wù)區(qū)域U?和U,滿足UnU,=對(duì)于子集U,,其巡航規(guī)劃的路徑距離45.根據(jù)權(quán)利要求4所述的一種基于改進(jìn)分支限界算法的無(wú)人機(jī)路徑優(yōu)化方法，其特征其中，任務(wù)優(yōu)先級(jí)得分用來表征無(wú)人機(jī)巡航系統(tǒng)對(duì)不同優(yōu)先級(jí)任務(wù)的響應(yīng)能到達(dá)時(shí)間得分S用于衡量無(wú)人機(jī)對(duì)任務(wù)點(diǎn)的響應(yīng)時(shí)效性，其權(quán)重@反映無(wú)人機(jī)到達(dá)任務(wù)為可用無(wú)人機(jī)的總數(shù)量，其權(quán)重@表征無(wú)人機(jī)集群規(guī)模擴(kuò)張帶來的成本增加；能耗，其權(quán)重@用于衡量無(wú)人機(jī)續(xù)航能力對(duì)任務(wù)可持續(xù)性的硬性限制。6.根據(jù)權(quán)利要求1所述的一種基于改進(jìn)分支限界算法的無(wú)人機(jī)路徑優(yōu)化方法，其特征Dv=max(IC?I,IC?l,...,ICI)-min(IC?I,IC?5CN119937632B其中，|C|表示第i個(gè)簇的階段數(shù)量；根據(jù)實(shí)際需求對(duì)Dv的閾值進(jìn)行調(diào)整，允許的Dv值越大，則所獲得的可行聚類方案越多。6一種基于改進(jìn)分支限界算法的無(wú)人機(jī)路徑優(yōu)化方法技術(shù)領(lǐng)域[0001]本發(fā)明涉及無(wú)人機(jī)路徑規(guī)劃技術(shù)領(lǐng)域，特別是涉及一種基于改進(jìn)分支限界算法的無(wú)人機(jī)路徑優(yōu)化方法。背景技術(shù)[0002]無(wú)人機(jī)系統(tǒng)憑借其緊湊型結(jié)構(gòu)、低成本部署、高機(jī)動(dòng)性、有效載荷適配性及強(qiáng)環(huán)境系統(tǒng)在物流配送、基礎(chǔ)設(shè)施巡檢和應(yīng)急響應(yīng)等場(chǎng)景的應(yīng)用廣度持續(xù)擴(kuò)展。其中，基于無(wú)人機(jī)群的智能巡檢系統(tǒng)通過三維空間作業(yè)能力，相較傳統(tǒng)智能交通系統(tǒng)實(shí)現(xiàn)了監(jiān)測(cè)覆蓋度與時(shí)空分辨率的數(shù)量級(jí)提升，為新型智能交通體系建設(shè)提供關(guān)鍵技術(shù)支撐。[0003]當(dāng)前多無(wú)人機(jī)路徑規(guī)劃領(lǐng)域存在如下三大核心局限：(1)現(xiàn)有研究普遍基于任務(wù)點(diǎn)的需求均等的前提假設(shè)，將任務(wù)需求同質(zhì)化，未能充分考慮實(shí)際場(chǎng)景中任務(wù)點(diǎn)的優(yōu)先級(jí)差異和服務(wù)質(zhì)量(questionofservice,QoS)要求，導(dǎo)致高價(jià)值任務(wù)響應(yīng)延遲與系統(tǒng)效用次優(yōu)問題；(2)盡管分支限界法在節(jié)點(diǎn)數(shù)較少的小規(guī)模場(chǎng)景下表現(xiàn)出良好的性能，但其時(shí)間復(fù)雜度隨問題規(guī)模的增大呈指數(shù)增長(zhǎng)，現(xiàn)有研究中對(duì)分支限界法的改進(jìn)方法如動(dòng)態(tài)規(guī)約矩陣僅實(shí)現(xiàn)線性級(jí)加速，在計(jì)算效率上的提升仍難以滿足實(shí)時(shí)性要求；(3)當(dāng)前大多數(shù)研究通?？紤]單維度指標(biāo)如最短航跡或最短時(shí)間，缺乏對(duì)負(fù)載均衡性、能源效率等多目標(biāo)協(xié)同優(yōu)化，可能導(dǎo)致部分無(wú)人機(jī)過度負(fù)載，而其他無(wú)人機(jī)利用率不足，影響系統(tǒng)整體穩(wěn)定性和可持發(fā)明內(nèi)容[0004]為了解決以上技術(shù)問題，本發(fā)明提供一種基于改進(jìn)分支限界算法的無(wú)人機(jī)路徑優(yōu)[0005]S1、構(gòu)建無(wú)人機(jī)巡航系統(tǒng)；結(jié)合任務(wù)優(yōu)先級(jí)以最短路徑為目標(biāo)，構(gòu)建無(wú)人機(jī)巡航的最優(yōu)路徑目標(biāo)函數(shù)，根據(jù)任務(wù)點(diǎn)分配互斥性、電池容量和任務(wù)點(diǎn)時(shí)序耦合構(gòu)建約束函數(shù)；構(gòu)建系統(tǒng)服務(wù)質(zhì)量評(píng)估模型；[0006]S2、輸入任務(wù)點(diǎn)集合與無(wú)人機(jī)基站位置，基于K-means算法進(jìn)行任務(wù)分配，引入方差與離散度評(píng)價(jià)進(jìn)行聚類篩選，輸出n個(gè)互斥子任務(wù)集；[0007]S3、基于改進(jìn)的分支限界法進(jìn)行航跡規(guī)劃，用貪心策略生成上界，根據(jù)搜索過程中節(jié)點(diǎn)的不同訪問狀態(tài)分別計(jì)算下界，根據(jù)單步和多步回溯情況進(jìn)行動(dòng)態(tài)剪枝；[0008]S4、通過基于空間劃分的近似優(yōu)化策略，結(jié)合貪心算法和分支限界法，通過對(duì)平面上的點(diǎn)進(jìn)行劃分，不斷更新節(jié)點(diǎn)來減少分支限界法的枝，完成計(jì)算。[0009]本發(fā)明進(jìn)一步限定的技術(shù)方案是：[0010]進(jìn)一步的，步驟S1中，無(wú)人機(jī)巡航系統(tǒng)包括無(wú)人機(jī)、無(wú)人機(jī)基站以及不同優(yōu)先級(jí)的任務(wù)點(diǎn)，無(wú)人機(jī)基站數(shù)量表示為K={k?,k?,…,k},共有n個(gè)無(wú)人機(jī)基站，每個(gè)基站部署一架同構(gòu)無(wú)人機(jī)；任務(wù)點(diǎn)集合表示為V={V?,V?,…,V},共有m個(gè)巡航任務(wù)點(diǎn)；每個(gè)任務(wù)點(diǎn)有且僅7務(wù)點(diǎn)集合V={V?,V?,…,V}分解為n個(gè)互斥子集U={U,?U?…U3,無(wú)人機(jī)基站k,服務(wù)的區(qū)域表區(qū)域U和U,滿足U,U,=?對(duì)于子集U,,其巡航規(guī)劃的路徑距離小于無(wú)人機(jī)最遠(yuǎn)飛行距離，任務(wù)節(jié)點(diǎn)v?和v,,若p?<D,,則S(P.<P,)→t,<t。[o017]其中,任務(wù)優(yōu)先級(jí)得分用來表征無(wú)人機(jī)巡航系統(tǒng)對(duì)不同優(yōu)先級(jí)任務(wù)的響先級(jí)分層的敏感性越強(qiáng)；到達(dá)時(shí)間得分S用于衡量無(wú)人機(jī)對(duì)任務(wù)點(diǎn)的響應(yīng)時(shí)效性，其權(quán)重@反映無(wú)人機(jī)到達(dá)8[0021]無(wú)人機(jī)數(shù)量懲罰項(xiàng)用于評(píng)估系統(tǒng)派出的無(wú)人機(jī)數(shù)量，s為以下分步驟：[0026]其中，d表示第i個(gè)簇中心點(diǎn)到對(duì)應(yīng)無(wú)人機(jī)布局點(diǎn)的歐氏距離；通過調(diào)整fd的閾[0029]其中，C,表示第i個(gè)簇的階段數(shù)量；根據(jù)實(shí)際需求對(duì)Dv的閾值進(jìn)行調(diào)整，允許的Dv[0036]若搜索節(jié)點(diǎn)集合S僅包含起始節(jié)點(diǎn)，則考慮每個(gè)節(jié)點(diǎn)的進(jìn)出恰好都是最短距離的9域節(jié)點(diǎn)集合V的最優(yōu)路徑P*;其次，選取P*中前(k-m)個(gè)節(jié)點(diǎn)作為下一層新的候選節(jié)點(diǎn)集V;={v?,v?,…,v+};針對(duì)大規(guī)模任務(wù)場(chǎng)景，該算法以13.59%-37.13%的路徑長(zhǎng)度損失實(shí)現(xiàn)計(jì)算效率82.41%-應(yīng)時(shí)效提升了66.8%,系統(tǒng)綜合QoS提升18.2%-114.7%。附圖說明[0059]圖5為本發(fā)明實(shí)施例中不同閾值下最短路徑長(zhǎng)度和單無(wú)人機(jī)的路徑長(zhǎng)度與任務(wù)點(diǎn)[0063]本實(shí)施例可視為多倉(cāng)庫(kù)多旅行商問題(Multi-DepotMultipleTravelingU={U,U?…U,3,無(wú)人機(jī)基站k;服務(wù)的區(qū)域表示為U,則需要規(guī)劃該無(wú)人機(jī)從其所屬基站出[0064]考慮巡航任務(wù)點(diǎn)的緊急程度不同，故引入任務(wù)節(jié)點(diǎn)優(yōu)先級(jí)因子p?∈{1,2,3},因[o066]其中,表示無(wú)人機(jī)j從基站k;巡航至子集U,中的首個(gè)任務(wù)點(diǎn)的距離個(gè)無(wú)人機(jī)服務(wù)區(qū)域U和U,滿足U,∩U,=?;對(duì)于子集U,其巡航規(guī)劃的路徑距離小于無(wú)人機(jī)[0070]其中，任務(wù)優(yōu)先級(jí)得分用來表征無(wú)人機(jī)巡航系統(tǒng)對(duì)不同優(yōu)先級(jí)任務(wù)的響應(yīng)能力，優(yōu)先級(jí)因子p的數(shù)值越小，表示任務(wù)點(diǎn)的優(yōu)先級(jí)別越高；其權(quán)重w用于量化不同優(yōu)先級(jí)任務(wù)點(diǎn)的服務(wù)順序?qū)Ψ?wù)質(zhì)量的增益效果，其值越大表明系統(tǒng)服務(wù)質(zhì)量評(píng)估模型對(duì)優(yōu)先級(jí)分層的敏感性越強(qiáng)。[0073]其中，無(wú)人機(jī)到達(dá)任務(wù)點(diǎn)v的實(shí)際時(shí)間為t,最晚到達(dá)時(shí)間為期待到達(dá)時(shí)間為到達(dá)時(shí)間得分S用于衡量無(wú)人機(jī)對(duì)任務(wù)點(diǎn)的響應(yīng)時(shí)效性，其權(quán)重@反映無(wú)人機(jī)到達(dá)任務(wù)點(diǎn)的時(shí)效性對(duì)Qos的非線性影響。[0074]無(wú)人機(jī)數(shù)量懲罰項(xiàng)用于評(píng)估系統(tǒng)派出的無(wú)人機(jī)數(shù)量，s為派出無(wú)人機(jī)的數(shù)量，n為可用無(wú)人機(jī)的總數(shù)量，其權(quán)重の。表征無(wú)人機(jī)集群規(guī)模擴(kuò)張帶來的成本增加，其權(quán)重設(shè)計(jì)旨在抑制資源冗余；允許能耗，其權(quán)重@用于衡量無(wú)人機(jī)續(xù)航能力對(duì)任務(wù)可持續(xù)性的硬性限制。[0076]S2、輸入任務(wù)點(diǎn)集合與無(wú)人機(jī)基站位置，基于K-means算法進(jìn)行任務(wù)分配，引入方差與離散度評(píng)價(jià)進(jìn)行聚類篩選，輸出n個(gè)互斥子任務(wù)集。[0077]在本實(shí)施例中，采用融合K-means聚類與分支限界算法實(shí)現(xiàn)協(xié)同求解，算法的具體實(shí)現(xiàn)步驟如下：[0078]1)給定聚類數(shù)目n,并給定待處理的數(shù)據(jù)集M={x?,X?,...,x},其中x∈R“表示維特征空間中的樣本點(diǎn)。給定最大迭代次數(shù)tmax,初始化計(jì)數(shù)t=0;[0079]2)對(duì)每組初始化中心點(diǎn)，記為C={c[0080]3)對(duì)于數(shù)據(jù)集中的每個(gè)樣本x,計(jì)算其與各聚類中心的歐氏距離，并將其分配到距離最近的聚類中心所對(duì)應(yīng)的簇中；[0081]4)基于當(dāng)前簇分配結(jié)果，重新計(jì)算每個(gè)簇的中心點(diǎn)：其中S表示第j個(gè)簇中的樣本數(shù)量；計(jì)算所有簇的誤差平方和；[0082]5)重復(fù)執(zhí)行步驟3)和步驟4),直到滿足以下終止條件之一：1、聚類中心的變化量小于預(yù)設(shè)閾值；ii、達(dá)到最大迭代次數(shù)tmax;iii、所有樣本到聚類中心的距離平方和收斂；[0083]6)最終將數(shù)據(jù)集M分成n個(gè)互不相交的子集，并且得到對(duì)應(yīng)的聚類中心集合。[0084]在K-means聚類算法的實(shí)際應(yīng)用中，聚類結(jié)果往往具有隨機(jī)性和多樣性；為篩選出[0087]其中，d表示第i個(gè)簇中心點(diǎn)到對(duì)應(yīng)無(wú)人機(jī)布局點(diǎn)的歐氏距離；通過調(diào)整fd的閾[0108]1)若搜索節(jié)點(diǎn)集合S僅包含起始節(jié)點(diǎn)，則考慮每個(gè)節(jié)點(diǎn)的進(jìn)出恰好都是最短距離[0111]2)若搜索節(jié)點(diǎn)集合S包含起始節(jié)點(diǎn)和部分中間節(jié)點(diǎn)，則下界1b的計(jì)算公式為：[0113]其中，S表示已訪問節(jié)點(diǎn)數(shù)，\表示集合差運(yùn)算；該情況下1b的計(jì)算公式即可表示為搜索節(jié)點(diǎn)組中相鄰節(jié)點(diǎn)距離的和，與兩邊節(jié)點(diǎn)到其他節(jié)點(diǎn)的最小值(到搜索節(jié)點(diǎn)組中的節(jié)點(diǎn)除外)的一半，與其他節(jié)點(diǎn)距離矩陣行中最小兩值的和的一半。[0114]3)若搜索節(jié)點(diǎn)集合S中包含所有節(jié)點(diǎn)，則下界1b表示為完整路徑長(zhǎng)度：[0116]節(jié)點(diǎn)回溯也是分支限界過程中的關(guān)鍵，本實(shí)施例在節(jié)點(diǎn)回溯策略方面，針對(duì)當(dāng)前節(jié)點(diǎn)是否為末端節(jié)點(diǎn)，采用以下兩種處理機(jī)制：[0117]1)當(dāng)下界大于上界，且當(dāng)前節(jié)點(diǎn)非末端節(jié)點(diǎn)時(shí)，執(zhí)行單步回溯；首先移除最近加入的節(jié)點(diǎn)vk,接著選擇下一個(gè)候選節(jié)點(diǎn)vk+1,最后更新搜索路徑[S[1],S[2],...,S[k-1],[0118]2)當(dāng)下界大于上界，且當(dāng)前節(jié)點(diǎn)為末端節(jié)點(diǎn)時(shí)，執(zhí)行多步回溯；首先連續(xù)移除末端節(jié)點(diǎn)，直至遇到非末端節(jié)點(diǎn)vm,接著選擇v的下一個(gè)候選節(jié)點(diǎn)vm+1,最后更新搜索路徑為[S[0119]S4、通過基于空間劃分的近似優(yōu)化策略，結(jié)合貪心算法和分支限界法，通過對(duì)平面上的點(diǎn)進(jìn)行劃分，不斷更新節(jié)點(diǎn)來減少分支限界法的枝，完成計(jì)算。[0120]針對(duì)大規(guī)模TSP問題求解時(shí)面臨的指數(shù)級(jí)計(jì)算復(fù)雜度挑戰(zhàn)，本實(shí)施例提出一種基于空間劃分的近似優(yōu)化策略，通過可控的精度損失換取計(jì)算效率的顯著提升；該策略通過構(gòu)建分層求解框架，將全局優(yōu)化問題分解為多個(gè)局部最優(yōu)子問題，具體包括以下分步驟：[0121]S4.1、采用貪心算法生成初始可行解，形成閉合路徑P?,計(jì)算其總距離作為基準(zhǔn)上度劃分準(zhǔn)則；其次，將路徑P,覆蓋的平面區(qū)域劃分為k個(gè)扇形子區(qū)域{R?,R?,…,R};最后，在每個(gè)子區(qū)域R內(nèi)選取節(jié)點(diǎn)集合V={v?,V?,...,vm};[0123]S4.3、分層優(yōu)化迭代：首先，在當(dāng)前層級(jí)使用步驟S3中改進(jìn)的分支限界法精確求解子區(qū)域節(jié)點(diǎn)集合V的最優(yōu)路徑P*;其次，選取P*中前(k-m)個(gè)節(jié)點(diǎn)作為下一層優(yōu)化的基準(zhǔn)節(jié)點(diǎn)集合B={b?,b?,...,Vk-m;最后，將剩余節(jié)點(diǎn)按空間鄰近性原則分配到各基準(zhǔn)節(jié)點(diǎn)鄰域，形成新的候選節(jié)點(diǎn)集V={v?,v?,…,v};并各局部最優(yōu)解形成全局近似解P′;[0126]通過對(duì)平面上的點(diǎn)進(jìn)行劃分，不斷更新根節(jié)點(diǎn)來減少分支限界法的枝，達(dá)到快速的計(jì)算，該混合策略結(jié)合了貪心算法的快速性和分支限界法的精確性優(yōu)勢(shì)，適用于節(jié)點(diǎn)規(guī)35},無(wú)人機(jī)系統(tǒng)配置5個(gè)不同地點(diǎn)的基站K={k?,...,k,,….,k?},各個(gè)基站部署一架同構(gòu)隨著節(jié)點(diǎn)數(shù)量的增加呈指數(shù)型上升；因此在節(jié)點(diǎn)數(shù)量較少時(shí)，參數(shù)n.對(duì)運(yùn)行時(shí)間的影響較加5,算法運(yùn)行效率分別提高86.84%和82.41%;當(dāng)節(jié)點(diǎn)數(shù)為35時(shí)，參數(shù)n.每增加5,算法運(yùn)行效率分別提高91.92%和97.63%。度一致；為更明顯地展示參數(shù)n.對(duì)路徑長(zhǎng)度的影響，本實(shí)施例又進(jìn)行了單無(wú)人機(jī)路徑敏感[0134]由圖5可以看出，在小規(guī)模(10-15點(diǎn))任務(wù)階段，na=5時(shí)的路徑長(zhǎng)度僅增加na=15方案增加13.59%,而n=5方案相較于n=10方案進(jìn)一步增加37.13%。[0135]綜合對(duì)仿真數(shù)據(jù)的系統(tǒng)性分析，參數(shù)n.值的優(yōu)化選擇在82.41%,同時(shí)路徑長(zhǎng)度較n=15方案僅增加13.59%。項(xiàng)核心性能指標(biāo)，分別表征路徑規(guī)劃效率、計(jì)算復(fù)雜度[0137]通過仿真結(jié)果揭示出系統(tǒng)性能的權(quán)衡特性：優(yōu)先級(jí)機(jī)制通過引入36.6%-60.3%的路徑長(zhǎng)度代價(jià)，換取18.2%-114.7%的QoS提高，并降低了66.8%的計(jì)算耗時(shí)。融合K-means聚類與分支限界算法實(shí)現(xiàn)協(xié)同求解；針對(duì)大規(guī)模任務(wù)場(chǎng)景中的計(jì)算復(fù)雜度挑對(duì)于傳統(tǒng)的啟發(fā)式算法以及分支限界算法，本發(fā)明方法在小規(guī)模TSP實(shí)例中可以獲得更優(yōu)解，針對(duì)大規(guī)模任務(wù)場(chǎng)景，該算法以13.59%-37.13%的路徑長(zhǎng)度損失實(shí)現(xiàn)計(jì)算效率82.41%-97.6