基于列生成算法的無(wú)人機(jī)任務(wù)分配

李瑞陽(yáng) 王智學(xué) 何紅悅 鄧巧雨

1.陸軍工程大學(xué)指揮控制工程學(xué)院江蘇南京210000

無(wú)人機(jī)是一種無(wú)需人員駕駛的空中飛行器,能夠?qū)崿F(xiàn)自主飛行、獨(dú)立地完成作戰(zhàn)任務(wù),因此,逐步成為執(zhí)行多樣化軍事任務(wù)的最佳選擇[1?2].無(wú)人機(jī)任務(wù)分配問(wèn)題是根據(jù)既定目標(biāo),把需要完成的任務(wù)合理地分配給系統(tǒng)中的成員,達(dá)到高效率執(zhí)行任務(wù),優(yōu)化無(wú)人機(jī)系統(tǒng)的目的[3?4].該問(wèn)題本質(zhì)上可以看作車輛路徑規(guī)劃問(wèn)題,主要從建立數(shù)學(xué)模型和算法求解兩方面入手進(jìn)行研究.

在以往對(duì)于任務(wù)分配問(wèn)題求解算法的研究中,絕大多數(shù)文獻(xiàn)都是采用人工智能算法進(jìn)行求解,這類算法雖然操作簡(jiǎn)單,易于實(shí)現(xiàn),但是很難保證收斂到全局最優(yōu)解[5?9],而列生成算法、拉格朗日松弛算法這類的基于數(shù)學(xué)規(guī)劃的啟發(fā)式算法克服了這些缺點(diǎn),從理論上講,不受規(guī)模限制,能收斂到最優(yōu)解,屬于精確性方法,目前國(guó)內(nèi)外有很多學(xué)者將其應(yīng)用于求解各種條件下的優(yōu)化分配問(wèn)題[10?14],但是考慮時(shí)間窗約束條件下的無(wú)人機(jī)任務(wù)分配調(diào)度問(wèn)題,目前的研究還比較匱乏,本文基于具體的無(wú)人機(jī)運(yùn)輸任務(wù),利用列生成算法建模求解,旨在找到運(yùn)輸任務(wù)分配的最佳方案,為指導(dǎo)作戰(zhàn)實(shí)踐提供參考.

1 問(wèn)題描述

在無(wú)人機(jī)運(yùn)輸任務(wù)分配問(wèn)題中,如圖1所示,敵我雙方的交戰(zhàn)地域S=[0,s]×[0,s]內(nèi),有n支我軍部隊(duì)A={a1,a2,··· ,an}正在等待物資補(bǔ)給,需要從某基地F調(diào)派一定數(shù)量的無(wú)人機(jī)U={U1,U2,··· ,Um}完成所有部隊(duì)的支援任務(wù).

任務(wù)開(kāi)始前,假設(shè)我軍已經(jīng)通過(guò)偵察機(jī)獲取了所有目標(biāo)部隊(duì)以及交戰(zhàn)地域內(nèi)敵人防空陣地的地理坐標(biāo),采用航路規(guī)劃技術(shù)規(guī)劃了任意兩點(diǎn)之間的優(yōu)化路線,準(zhǔn)備為各無(wú)人運(yùn)輸機(jī)進(jìn)行任務(wù)分配.每個(gè)目標(biāo)部隊(duì)所需要的物資重量事先已知,表示為C={C1,C2,··· ,Cn},部隊(duì)ai期望得到補(bǔ)給的時(shí)間范圍表示為(ei,li),每架無(wú)人運(yùn)輸機(jī)的任務(wù)可以表示為一組目標(biāo)部隊(duì)的有序集合,如TaskU1={F→ai→··· →aj→F},規(guī)劃派出無(wú)人機(jī)數(shù)量最少,飛行路程最短的分配方案,完成所有部隊(duì)的任務(wù)需求.

2 數(shù)學(xué)模型

2.1 模型假設(shè)

正如圖1所示,無(wú)人機(jī)運(yùn)輸任務(wù)分配問(wèn)題的基本模型可以看作一個(gè)完全無(wú)向圖G=(V,E),其中V=(a0,a1,··· ,an)是運(yùn)輸網(wǎng)絡(luò)中節(jié)點(diǎn)的集合,a0=F表示出發(fā)基地,其余表示n支等待支援的作戰(zhàn)部隊(duì);E={dij,(i

1) 每架無(wú)人機(jī)從后勤基地出發(fā),沿著某一條飛行路線把所裝載的所有物資補(bǔ)給運(yùn)輸給待支援部隊(duì)后,返回原基地;

2) 每架無(wú)人機(jī)可以為多支部隊(duì)提供補(bǔ)給,但是為了避免多架無(wú)人機(jī)在空中飛行時(shí)發(fā)生碰撞事故,每只目標(biāo)部隊(duì)只安排一架無(wú)人運(yùn)輸機(jī)進(jìn)行支援;

3) 每架無(wú)人機(jī)的載重量是有限制的,所運(yùn)載的物資補(bǔ)給總重量不能超過(guò)該范圍.為了簡(jiǎn)化問(wèn)題,假設(shè)所有無(wú)人運(yùn)輸機(jī)型號(hào)相同,擁有相同的載重能力,同時(shí)不考慮物資種類對(duì)飛行的影響;

4)不考慮無(wú)人運(yùn)輸機(jī)在各個(gè)目標(biāo)部隊(duì)位置處的轉(zhuǎn)向角約束,也不考慮無(wú)人運(yùn)輸機(jī)的航程約束;

5) 假設(shè)每支部隊(duì)都會(huì)進(jìn)行戰(zhàn)前預(yù)估,都有接受補(bǔ)給的時(shí)間窗,即部隊(duì)對(duì)于補(bǔ)給物資的到達(dá)時(shí)間要求是在某個(gè)時(shí)間段上的.

2.2 構(gòu)建模型

2.2.1 標(biāo)號(hào)和參數(shù)變量

U表示無(wú)人運(yùn)輸機(jī)的集合;A表示待援部隊(duì)的集合;V表示任務(wù)分配模型網(wǎng)絡(luò)中的節(jié)點(diǎn)集合,由后勤基地與待援部隊(duì)共同組成,將基地拓展為出發(fā)以及接收節(jié)點(diǎn),分別標(biāo)為0 和n+1 號(hào)節(jié)點(diǎn),待援部隊(duì)構(gòu)成了1 到n號(hào)節(jié)點(diǎn);cij表示網(wǎng)絡(luò)中任意兩個(gè)節(jié)點(diǎn)i和j構(gòu)成的弧(i,j)上的飛行路線成本,等價(jià)于兩點(diǎn)之間飛行路線的長(zhǎng)度dij表示;tij表示網(wǎng)絡(luò)中任意兩個(gè)節(jié)點(diǎn)上的飛行時(shí)間;Ci表示部隊(duì)的物資需求;q表示每架無(wú)人機(jī)的最大載重量;[ei,li]表示每個(gè)節(jié)點(diǎn)的服務(wù)時(shí)間窗要求.sik表示無(wú)人運(yùn)輸機(jī)k在節(jié)點(diǎn)i的卸載物資開(kāi)始時(shí)間;xijk表示0 ?1 變量,如果無(wú)人機(jī)k經(jīng)過(guò)弧(i,j),則為1,否則為0.

圖1 無(wú)人機(jī)運(yùn)輸任務(wù)分配示意圖

2.2.2 數(shù)學(xué)模型

無(wú)人機(jī)運(yùn)輸任務(wù)分配的數(shù)學(xué)模型可以表示為:

其中,式(1)是問(wèn)題的優(yōu)化目標(biāo),表示執(zhí)行任務(wù)的總成本最小,式(2)表示無(wú)人機(jī)從起點(diǎn)出發(fā),只能選擇一條路線,每只部隊(duì)只能被一架無(wú)人機(jī)支援; 式(3)表示無(wú)人運(yùn)輸機(jī)的實(shí)際載貨量不能超過(guò)其最大限制容量;式(4)～式(6)共同構(gòu)成網(wǎng)絡(luò)的流約束,表示每架無(wú)人機(jī)從基地出發(fā),經(jīng)過(guò)待援部隊(duì)處不停留,并最終返回基地.式(7)表示如果無(wú)人運(yùn)輸機(jī)經(jīng)過(guò)弧,那么車輛在點(diǎn)開(kāi)始卸載物資的時(shí)間約束.式(8)保證了在每個(gè)點(diǎn)開(kāi)始卸載物資的時(shí)間要滿足該點(diǎn)的時(shí)間窗約束.式(9)是整數(shù)約束.可以看出,其中式(7)是非線性的,引入式(10)替代將其轉(zhuǎn)化為線性約束:

其中,M代表一個(gè)足夠大的數(shù).

3 模型求解

3.1 列生成算法介紹

列生成算法是一種基于數(shù)學(xué)規(guī)劃的啟發(fā)式算法,適合于求解大規(guī)模線性規(guī)劃問(wèn)題.算法受Dantzig 和Wolfe 提出的著名的塊對(duì)角結(jié)構(gòu)與Dantzig-Wolfe 分解原理啟發(fā)[15]而設(shè)計(jì)產(chǎn)生的.其基本原理是: 將原始線性規(guī)劃問(wèn)題中分成兩個(gè)部分,即限制性主問(wèn)題(RMP)和子問(wèn)題(SP),其中RMP 中含有m個(gè)決策變量,用于生成基可行解,使用單純形法對(duì)RMP 進(jìn)行求解,得到最優(yōu)解信息,根據(jù)檢驗(yàn)數(shù)式(11)在候選列中選取列加入到主問(wèn)題中,然后重復(fù)上述過(guò)程,直到找不到這種列,說(shuō)明當(dāng)前的限制性主問(wèn)題已經(jīng)無(wú)法改進(jìn),即問(wèn)題最優(yōu)[16].如果原問(wèn)題需要得到的解是整數(shù)解,則再利用分支定界法進(jìn)行求解.

3.2 算法設(shè)計(jì)

首先需要將數(shù)學(xué)模型轉(zhuǎn)化為依靠列的形式,以方便使用列生成算法進(jìn)行求解.滿足所有約束條件的路徑稱為可行路徑,? 為所有路徑的集合,為了建立路徑與決策變量之間的聯(lián)系,本文引入以下兩個(gè)變量:

?ir: 路徑r經(jīng)過(guò)點(diǎn)i則為1,否則為0;

yr: 路徑r被選擇則為1,否則為0.

由此得到模型的主問(wèn)題:

其中,目標(biāo)函數(shù)式(12)表示在集合中找到一個(gè)子集,使總的飛行路程最短.約束條件式(13)表示選擇的路徑集合中僅提供每支部隊(duì)一次支援.約束式(14)表示每個(gè)可行路徑要么不被選擇,要么最多被選擇一次.注意到主問(wèn)題模型中的可行路徑集合包含非常多的元素,因此,本文使用列生成算法不斷產(chǎn)生對(duì)其有改善作用的可行路徑加入到主問(wèn)題中.設(shè)子問(wèn)題中每個(gè)可行路徑對(duì)應(yīng)的檢驗(yàn)數(shù)(削減成本)為,如果存在任何的路徑滿足<0,則將該路徑r作為一列加入到主問(wèn)題中,否則主問(wèn)題的當(dāng)前解為最優(yōu)解.

子問(wèn)題模型表示為:

其中,σi對(duì)應(yīng)約束式(13)的影子價(jià)格,在子問(wèn)題中為常數(shù),其物理意義表示路徑到達(dá)網(wǎng)絡(luò)中每個(gè)客戶節(jié)點(diǎn)的獎(jiǎng)勵(lì).目標(biāo)函數(shù)式(15)表示在網(wǎng)絡(luò)中尋求一條路徑,使該路徑上的總的路徑成本減去收益總和最小.

3.3 子問(wèn)題求解算法

列生成算法子問(wèn)題又稱為定價(jià)問(wèn)題.在本文中,該問(wèn)題實(shí)際上是一種帶資源約束的初等最短路徑問(wèn)題[17].本文參考并改進(jìn)了Desrochers 的標(biāo)簽修正算法[18].該算法的思路為: 在網(wǎng)絡(luò)中的所有可行路徑在其經(jīng)過(guò)的每個(gè)節(jié)點(diǎn)都帶有若干個(gè)臨時(shí)標(biāo)簽,每個(gè)標(biāo)簽對(duì)應(yīng)一種資源約束,每次從一條路徑上的一個(gè)節(jié)點(diǎn)的臨時(shí)標(biāo)簽出發(fā),在其相鄰點(diǎn)生成新的臨時(shí)標(biāo)簽,然后作為出發(fā)點(diǎn)的節(jié)點(diǎn)的臨時(shí)標(biāo)簽轉(zhuǎn)化為永久標(biāo)簽,當(dāng)所有的標(biāo)簽都為永久標(biāo)簽時(shí)該算法結(jié)束.改進(jìn)的標(biāo)簽修正算法可以表示為:

步驟1.初始化: 首先得到每個(gè)bucket 的長(zhǎng)度h=min{tij},?(i,j) ∈E,然后給初始節(jié)點(diǎn)的標(biāo)簽賦值(Tk0,Ck0,Dk0)=(0,0,0),令Pi表示節(jié)點(diǎn)的永久標(biāo)簽集合,令Qi表示節(jié)點(diǎn)的臨時(shí)標(biāo)簽集合,令Bp表示第p個(gè)bucket.使P0={0,0,0},其他賦值空集.

步驟2.選擇bucket: 在所有bucket 中選擇第l個(gè)bucket,滿足如果沒(méi)有滿足條件的l,則算法結(jié)束.

步驟3.選擇臨時(shí)標(biāo)簽: 在Bp中依次選擇一個(gè)標(biāo)簽(Tki,Cki,Dki).如果Bp為空,則轉(zhuǎn)到步驟2.

步驟4.修正標(biāo)簽(Tki,Cki,Dki): 令EEF(Q)表示在標(biāo)簽集合Q中找到所有有效的標(biāo)簽.對(duì)于節(jié)點(diǎn)i的每個(gè)相鄰節(jié)點(diǎn)j,按條件執(zhí)行:

轉(zhuǎn)到步驟3.

3.4 算法流程圖

結(jié)合上述建模分析,列生成算法的總體流程圖如圖2所示.

4 計(jì)算實(shí)驗(yàn)

基于Visual Studio 2012 和Cplex 12.6 平臺(tái)進(jìn)行仿真算例的求解與測(cè)試,CPLEX 提供了靈活的高性能優(yōu)化程序,能夠解決線性規(guī)劃、二次方程規(guī)劃、二次方程約束規(guī)劃和混合整數(shù)規(guī)劃等多種數(shù)學(xué)優(yōu)化問(wèn)題,并且還在不斷地更新改進(jìn),是一款功能強(qiáng)大的軟件,幾乎幫助解決了每個(gè)行業(yè)中的規(guī)劃和計(jì)劃問(wèn)題,許多先進(jìn)的軟件公司也是CPLEX 的用戶.由于沒(méi)有應(yīng)用無(wú)人機(jī)執(zhí)行作戰(zhàn)保障行動(dòng)的真實(shí)案例,本文為了驗(yàn)證列生成算法在求解無(wú)人機(jī)任務(wù)分配問(wèn)題中的有效性,采用Solomon_25 算例求解VRPTW 經(jīng)典問(wèn)題的測(cè)試數(shù)據(jù).

將各個(gè)單位的任務(wù)需求按照時(shí)間窗序列整理劃分,并將運(yùn)輸任務(wù)分配模型修正為適合列生成算法求解的集合劃分模型,利用該算法對(duì)問(wèn)題進(jìn)行求解,得到的任務(wù)分配路線圖如圖3.

為了驗(yàn)證算法的性能,本文采用多種智能算法(遺傳算法、粒子群算法、差分進(jìn)化算法等)來(lái)求解該問(wèn)題,多種算法給出的結(jié)果都不相同,其中差分進(jìn)化算法最終解的目標(biāo)函數(shù)最小,即飛行總成本最低,圖4給出了采用差分進(jìn)化算法得到的任務(wù)分配路線圖.將兩種算法求解結(jié)果的具體分配方案進(jìn)行對(duì)比分析,如表1所示.

表1 無(wú)人機(jī)任務(wù)分配路線方案對(duì)比

圖2 列生成算法流程圖

圖3 無(wú)人機(jī)任務(wù)分配路線圖(列生成算法)

圖4 無(wú)人機(jī)任務(wù)分配路線圖(差分進(jìn)化算法)

通過(guò)標(biāo)準(zhǔn)測(cè)試算例的對(duì)比結(jié)果分析可以看出,兩種算法求解得到的路徑數(shù)量(即需要派出無(wú)人機(jī)的最大數(shù)量)是一致的,都需要但基于列生成算法對(duì)任務(wù)分配問(wèn)題進(jìn)行求解,其算法的精度明顯更高,與差分進(jìn)化算法相比,無(wú)人機(jī)飛行總路程明顯更短,總路線長(zhǎng)度縮短了8.84 %,驗(yàn)證了列生成算法在求解大規(guī)模運(yùn)籌優(yōu)化問(wèn)題方面的優(yōu)勢(shì).

5 結(jié)論

無(wú)人機(jī)任務(wù)分配優(yōu)化問(wèn)題是無(wú)人機(jī)任務(wù)規(guī)劃系統(tǒng)中的核心技術(shù)問(wèn)題,合適的優(yōu)化模型和算法能夠使無(wú)人機(jī)實(shí)現(xiàn)智能決策、自主高效的完成飛行任務(wù).本文采用的列生成算法是一種基于數(shù)學(xué)規(guī)劃的啟發(fā)式算法,非常適合解決大規(guī)模線性問(wèn)題.通過(guò)與常用的人工智能算法進(jìn)行對(duì)比實(shí)驗(yàn),證明了列生成算法具有更高的求解精度,具有更好的應(yīng)用前景.