航空器救援調(diào)度模型與算法研究?

胡漢莉 鄧 威（武漢數(shù)字工程研究所武漢430205）

航空器救援調(diào)度模型與算法研究?

胡漢莉 鄧 威
（武漢數(shù)字工程研究所武漢430205）

論文介紹了低空空域下的航空器救援調(diào)度模型及該模型的兩種求解算法，并以汶川地震為背景設(shè)計(jì)算例，比較分析了兩種求解算法的結(jié)果。

航空器救援；遺傳算法

Class Num ber V355

1 引言

航空器救援是指使用航空技術(shù)手段和技術(shù)裝備實(shí)施的一種救援，本文特指重大災(zāi)害下的低空空域的航空應(yīng)急救援，其特性有受災(zāi)范圍廣、人員多，在事故發(fā)生后需動用大批量、多類型航空器執(zhí)行長短距離任務(wù)。

航空器救援具有很高的軍事意義，戰(zhàn)場上航空救援水平的高低對作戰(zhàn)能力的影響是很大的。航空救援水平越高，部隊(duì)?wèi)?zhàn)斗力會越強(qiáng)，人員傷亡數(shù)會越低。因此，提高航空救援的水平是很有必要的。

2 航空器救援調(diào)度模型

2.1 航空器救援調(diào)度問題描述

航空器救援調(diào)度問題可描述為：在一個供求關(guān)系框架下，有若干架航空器、若干個物資配送中心和受災(zāi)點(diǎn)，要求合理的安排航空器的飛行路線和出行時(shí)間，在滿足多種約束條件下，將物資配送中心的物資運(yùn)往受災(zāi)點(diǎn)，并使得相應(yīng)的目標(biāo)函數(shù)最優(yōu)化。

航空器調(diào)度問題主要包括救援物資、航空器、配送中心、受災(zāi)點(diǎn)、運(yùn)輸網(wǎng)絡(luò)、目標(biāo)函數(shù)以及約束條件等要素。

1）救援物資：包含重量和體積、要求送達(dá)時(shí)間和受災(zāi)點(diǎn)、是否允許分批配送等屬性。

2）航空器：其屬性包括航空器類型、單次最大航程、最大裝載量、配送前停靠位置以及完成配送任務(wù)后的停靠位置等。

3）配送中心或出救點(diǎn)：救援物資集散地以及航空器運(yùn)作指揮的中心樞紐，在某次配送調(diào)度任務(wù)中可有單個或多個中心點(diǎn)。

4）受災(zāi)點(diǎn)：其屬性包括物資需求量、需求時(shí)間、需求次數(shù)以及物資滿足率等。

5）運(yùn)輸網(wǎng)絡(luò)：由頂點(diǎn)（受災(zāi)點(diǎn)、配送中心）、無向邊和有向弧構(gòu)成。其中邊和弧的屬性包括方向、權(quán)值（可表示時(shí)間、成本或距離）和交通流量限制等。

6）約束條件：滿足受災(zāi)點(diǎn)對物資類型、規(guī)格和數(shù)量的需求以及對到達(dá)時(shí)間的約束；航空器的實(shí)際裝載量不得超過最大裝載量；航空器單次配送路徑長度不得超過最大航程；不得在配送中心外的其他地點(diǎn)停靠。

7）目標(biāo)函數(shù)：各個受災(zāi)點(diǎn)的物資滿足率最高、配送總里程最短、準(zhǔn)時(shí)性最高、時(shí)間最短等。

2.2 航空器調(diào)度模型相關(guān)概念

假定以下條件：1）調(diào)度過程中航空器滿載直飛，每個架次的救援過程只針對單個受災(zāi)點(diǎn)；2）出救點(diǎn)所能提供的調(diào)度物資總量、各需求點(diǎn)所需的物資總量在調(diào)度周期內(nèi)保持不變；3）航空器可在任一可用出救點(diǎn)裝載物資，在受災(zāi)點(diǎn)投放物資或者降落卸載；4）航空器油量可滿足在任一次出救點(diǎn)-受災(zāi)點(diǎn)-出救點(diǎn)之間的調(diào)度飛行，只能在出救點(diǎn)加油；5）機(jī)組調(diào)度與物資調(diào)度相互獨(dú)立，可不考慮。

表1 集合常量表

表2 物資常量表

表3 時(shí)間常量表

表4 二元變量表

航空器調(diào)度模型目標(biāo)函數(shù)及約束條件：

這是一個非線性整數(shù)規(guī)劃模型，目標(biāo)函數(shù)式（1）為使得調(diào)度周期內(nèi)航空器出程飛行架次達(dá)到最大化，從而提高單位時(shí)間內(nèi)的物資調(diào)運(yùn)量；目標(biāo)函數(shù)式（2）為當(dāng)出救架次達(dá)到飽和后，使得參與救援的航空器總的調(diào)度時(shí)間最短，從而降低出救成本。

約束條件式（3）~式（14）有3種，分別為物資約束，時(shí)間約束和航空器位置約束：式（3）保證耐久類物資在調(diào)度周期（k天）開始前k'天內(nèi)完成調(diào)度，同時(shí)滿足受災(zāi)點(diǎn)對快速消耗品的需求；式（4）確保消耗性物資在耐用品調(diào)度完成后的周期內(nèi)，耐用品的總需求架次可以得到保障；式（5）確保調(diào)度周期內(nèi)每天消耗品連續(xù)性需求得到滿足；式（6）確保每天的實(shí)際調(diào)度時(shí)間在允許的調(diào)度時(shí)間之內(nèi)；式（7）和式（8）確保總的出入程飛行架次相同，且航空器只有在上一次執(zhí)行了入程飛行后，方可執(zhí)行本次出程飛行；式（9）和式（10）確保航空器執(zhí)行出程飛行的條件得到滿足；式（11）和式（12）確保航空器執(zhí)行調(diào)度任務(wù)后停靠在出救點(diǎn)的條件得到滿足；式（13）確保每架航空器在執(zhí)行完當(dāng)天的調(diào)度任務(wù)后停靠在一個出救點(diǎn)；式（14）確保所有變量均是二元變量。

3 航空器調(diào)度模型的求解算法

該模型是一類廣義上的運(yùn)輸工具的路徑規(guī)劃和調(diào)度問題，屬于典型的NP難問題，精確求解方法的計(jì)算量會隨著問題規(guī)模的擴(kuò)大呈指數(shù)型增長。本文分別采用傳統(tǒng)遺傳算法和改進(jìn)的爬山遺傳算法對該模型求解，并對兩者的性能進(jìn)行了分析比較。

3.1 基于矩陣編碼的遺傳算法設(shè)計(jì)

基于矩陣編碼的遺傳算法如圖1。矩陣編碼將矩陣整體看作一個遺傳子代個體，不需展開成單列或者單行，從而保存了子代個體基因的完整性。矩陣編碼僅改變了遺傳算法的編碼方式，其核心思想和求解思路并未發(fā)生變化，依然沿襲傳統(tǒng)算法中初始種群的生成、選擇、解的評判和收斂性檢測步驟。

1）種群初始化。本文采用浮點(diǎn)數(shù)矩陣編碼，一個解矩陣代表一條染色體，行代表每架航空器該周期內(nèi)的調(diào)度計(jì)劃，列表示各時(shí)刻航空器所在的位置。具體表達(dá)形式如下：

k為調(diào)度周期，共有k天，f1，f2…，fn為航空器集合，d和c分別為出救點(diǎn)與受災(zāi)點(diǎn)集合。隨機(jī)產(chǎn)生m條該類型的染色體以完成種群的初始化。

2）種群可行化。所謂解的可行化即將染色體的編碼向量映射為滿足全部約束限制的可行解的過程，如圖2。可行化操作只需判定解的時(shí)間和物資約束即可。時(shí)間約束通過引入帶有各點(diǎn)間時(shí)間常數(shù)的矩陣，求和后與每天的作業(yè)時(shí)限比較，若小于時(shí)限要求則轉(zhuǎn)入下一步，若不滿足則需將每天最后一次飛行的受災(zāi)點(diǎn)虛擬化，以消減時(shí)間使之符合要求。物資約束須將原解矩陣分解出一個子矩陣，并統(tǒng)計(jì)原矩陣和新生成的子矩陣中各受災(zāi)點(diǎn)的出現(xiàn)頻率，若達(dá)到頻次要求則可行化操作結(jié)束，若不滿足則需產(chǎn)生新解以維持種群數(shù)量不變，并繼續(xù)執(zhí)行可行化操作，直到所有解均達(dá)到可行化為止。

3）解的個體評價(jià)及適應(yīng)度函數(shù)評估。衡量和評價(jià)某個染色體好壞的準(zhǔn)則即為適應(yīng)度函數(shù)，函數(shù)值越大則該染色體的性能越優(yōu)越，其對應(yīng)的解更接近于最優(yōu)解。在本文的航空器調(diào)度模型中，根據(jù)目標(biāo)函數(shù)的特征，取兩目標(biāo)函數(shù)的加權(quán)和作為本算法的適應(yīng)度函數(shù)，其表達(dá)形式為

根據(jù)不同的算例賦予加權(quán)系數(shù)不同的取值，在此w1與w2分別取1和5000。

4）選擇與復(fù)制。在本問題的求解過程中，應(yīng)用適應(yīng)度函數(shù)計(jì)算出當(dāng)前代中的適應(yīng)度平均值，然后對該代種群中所有染色體按照適應(yīng)度函數(shù)值由高到低進(jìn)行排序，排在榜首的個體性能最為優(yōu)越，將其直接復(fù)制進(jìn)入下一代種群，而其他剩余個體則采用適應(yīng)度比例方法，選擇進(jìn)入下一代，比例Pi為

5）染色體交叉和變異操作。復(fù)制操作不會產(chǎn)生新的個體，交叉操作可產(chǎn)生新的個體，即新的航空器調(diào)度方案。具體實(shí)施過程為：按照一定的比例隨機(jī)選擇若干條染色體進(jìn)行交叉操作，即交換解矩陣中的行或列，同理，選取某條染色體中的隨機(jī)位置點(diǎn)進(jìn)行變異，計(jì)算后的解須進(jìn)行可行化操作。

6）采用指定代數(shù)的終止條件。事先設(shè)置最大遺傳代數(shù)N，達(dá)到N代算法終止，將最優(yōu)染色體對應(yīng)的航空器調(diào)度方案輸出。

3.2 爬山遺傳算法設(shè)計(jì)

基本遺傳算法在局部搜索能力方面暴露出的不足是為人共知的。另外，利用基本遺傳算法求解一些優(yōu)化問題時(shí)還會陷入過早收斂現(xiàn)象或停滯現(xiàn)象，對最終的尋優(yōu)效果和計(jì)算效率產(chǎn)生影響。為了克服基本遺傳算法的不足，通常從三方面著手：引入高級操作策略（如倒位操作）；引入群體策略（如多種群遺傳算法和群體規(guī)模可變遺傳算法）；將基本遺傳算法與其他搜索方法相結(jié)合（如爬山算法）。

航空器調(diào)度的爬山遺傳算法充分利用啟發(fā)式信息，從而有效地提高遺傳算法的局部搜索能力，進(jìn)一步改善其解的品質(zhì)和收斂速度。該算法的特點(diǎn)是對每一代得到的最優(yōu)個體實(shí)施多次爬山操作，然后以通過爬山操作得到的個體取代原個體。算法如下：

1）解的表示方法及初始化同基本遺傳算法。僅對每一代得到的最優(yōu)個體利用兩交換法進(jìn)行爬山操作，采用固定的爬山次數(shù)，并將操作后的個體取代原個體。

2）引入罰函數(shù)思想對約束條件進(jìn)行處理，對不可行解引入懲罰權(quán)重，降低該解的遺傳概率。解的評價(jià)函數(shù)如下：

其中Pw為懲罰權(quán)重，M為不可行解中不可行路徑數(shù)，為零時(shí)為可行解。

3）選擇交叉策略及終止條件不變，提高變異概率，以消減對最優(yōu)值進(jìn)行爬山操作引起的單峰效應(yīng)，增加種群的多樣性，跳出局部最優(yōu)。

3.3 算例設(shè)計(jì)與結(jié)果分析

本文以汶川地震為背景設(shè)計(jì)算例，德陽、廣漢是具備航空器起降條件的城市，綿陽和成都為出救城市，都江堰、彭州、雅安、江油和汶川縣為受災(zāi)城市。在調(diào)度周期5天內(nèi)對兩類應(yīng)急物資采用3架航空器進(jìn)行調(diào)度，三個出救城市均有兩種物資且存儲量足夠。航空器在調(diào)度周期前停靠在廣漢市，每天最多允許調(diào)度架次為3次，每天的調(diào)度時(shí)間為630min，裝卸載時(shí)間均為20min，加油時(shí)間為40min，αc取值為2，要求在調(diào)度周期前3天完成耐用品的調(diào)度。相應(yīng)的出救點(diǎn)與受災(zāi)點(diǎn)間的飛行時(shí)間以及各個受災(zāi)點(diǎn)兩類物資的需求分別見表5和表6。

表5 出救點(diǎn)到受災(zāi)點(diǎn)所需飛行時(shí)間（m in）

表6 受災(zāi)點(diǎn)物資需求表

針對本問題的特性，編碼遺傳算法中的各類參數(shù)取值如下：種群個數(shù)為20，遺傳代數(shù)為100，交叉概率Pc取0.7，變異概率Pm取0.15。w1、w2則分別取為1和5000。改進(jìn)爬山遺傳算法參數(shù)設(shè)置為：變異概率Pm設(shè)為0.6，Pw取值為2。圖3、圖4和圖5分別表表目標(biāo)函數(shù)值以及適應(yīng)度函數(shù)值變化軌跡。

由圖3可知：基本遺傳算法與改進(jìn)遺傳算法的出救架次目標(biāo)函數(shù)值有較大差異，其中前者由于進(jìn)行了解的可行化操作以及第一目標(biāo)函數(shù)值在適應(yīng)度函數(shù)中權(quán)重較大，其變化軌跡較為平緩且總體為非遞減狀態(tài)，而改進(jìn)的遺傳算法則未對解進(jìn)行可行化操作使得最初階段由于可行解較少，引入的非可行解大多由于缺少時(shí)間限制而使得出救架次值一定程度較高，隨著解的可行化程度的提高，呈現(xiàn)出一個先減后增的過程。

由圖4可知：傳統(tǒng)的遺傳算法適應(yīng)度函數(shù)中對第二目標(biāo)函數(shù)值即出救時(shí)間的優(yōu)化更多體現(xiàn)在第一目標(biāo)函數(shù)值一定的情況下，且隨著第一目標(biāo)函數(shù)值的增加呈現(xiàn)出總體上升而局部減小的趨勢，這與實(shí)際情況的優(yōu)化過程和目標(biāo)函數(shù)值的設(shè)定權(quán)重一致。而改進(jìn)的遺傳算法在對時(shí)間優(yōu)化上差異更為明顯，這也是由于非可行解的原因引起。

由圖5可見：無論是采用基本還是改進(jìn)的遺傳算法，兩者的適應(yīng)度函數(shù)值都是增加的，而改進(jìn)的遺傳算法比基本遺傳算法的適應(yīng)度值變化范圍大，且收斂速度更快，但存在一定小范圍的波動，前者是由于對每代種群的最優(yōu)解進(jìn)行了爬山操作造成，而后者則是由于較大的變異概率引起。但二者均可求得最優(yōu)解，其對應(yīng)總的調(diào)度較次為44架次，調(diào)度時(shí)間為5285min。

根據(jù)以上計(jì)算結(jié)果可知：通過將具備更強(qiáng)局部搜索能力的爬山算法與傳統(tǒng)的遺傳算法相結(jié)合，構(gòu)造出的低空救援航空器調(diào)度問題的爬山遺傳算法，能夠很大程度上彌補(bǔ)傳統(tǒng)遺傳算法在求解該問題過程中局部搜索能力不強(qiáng)收斂性弱的缺陷，也能夠使得爬山算法所表現(xiàn)出的全局搜索能力較弱的特點(diǎn)隱匿起來，從而得到了更為優(yōu)化的計(jì)算結(jié)果，顯示出更為強(qiáng)大的尋優(yōu)能力。

4 結(jié)語

航空器調(diào)度算法實(shí)際上是一個典型的多目標(biāo)規(guī)劃問題，本文提出并設(shè)計(jì)了重大災(zāi)害條件下針對各個出救點(diǎn)與各個受災(zāi)點(diǎn)的航空器調(diào)度算法，該算法能夠在n2的時(shí)間復(fù)雜度內(nèi)求得問題的最優(yōu)解。

［1］Lucia P，Eric M F，Antonio B.Conflict resolution prob?lems for air traffic management systems solved withmixed integer programming［J］.IEEE Transactions on Intelli?gent Transportation System，2002，3（1）：3-11.

［2］Todd A，Donovan.Concept for an Integrated National Sur?veillance and Data Communication Infrastructure［J］. IEEE.AC paper，2005，5：1-14.

［3］James W.Rogers.Term inal Area Surveillance System［C］//InternationalRadar Conference，1995，501-504.

［4］趙勇，徐道奇，費(fèi)錦榮等.基于AHP的飛行安全評估模型的研究與實(shí)現(xiàn)［J］.微計(jì)算機(jī)信息，2009，25（3）：84-85.

［5］Kernighan B.W.and S.Lin.An efficient heuristic proce?dure for partitioning graphs［J］.The Bell System Techni?cal Journal，1997，49：291-307.

［6］楊尚文，戴福青.基于一種免疫遺傳算法的自由非沖突解脫［J］.航空計(jì)算計(jì)算，2007，37（1）：41-43.

［7］戴玲，夏學(xué)知.多Agent技術(shù)在飛行沖突解脫中的應(yīng)用［J］.艦船電子工程，2008，28（3）：62-64.

［8］程麗媛，韓松臣，劉星.采用內(nèi)點(diǎn)約束的最優(yōu)沖突解脫辦法［J］.交通運(yùn)輸工程學(xué)報(bào)，2005，5（2）：80-84.

［9］簡煒，張友兵，吳陽等.基于爬山法和遺傳算法的聯(lián)合搜索算法［J］.湖北汽車工業(yè)學(xué)院學(xué)報(bào).2004，18（2）：47-49.

［10］韓云祥，陳亞青.飛行沖突解決機(jī)制研究［J］.桂林航天工業(yè)高等專科學(xué)校學(xué)報(bào)，2009（3）：29-35.

［11］蔡良偉，雍正飛.求解帶約束函數(shù)優(yōu)化的兩級自適應(yīng)遺傳算法［J］.系統(tǒng)工程與電子技術(shù)，2000，22（2）：84-86.

［12］簡煒，錢積新.約束優(yōu)化問題的多參量遺傳算法［J］.湖北汽車工業(yè)學(xué)院學(xué)報(bào)，2003，17（4）：24-26.

Research on Arithm etic of Aircraft Rescue Scheduling M odule

HU Han li DENGW ei
（Wuhan Digital Engineering Institute，Wuhan 430205）

This papermakes research on themodule and two kinds of arithmetic of low-altitude aircraft rescue scheduling，and takesWenchuan earthquake asan examp le to compare the two kindsofarithmetic。

aircraftrescue，inheritancearithmetic

V355

10.3969/j.issn.1672-9730.2017.05.022

2016年11月7日，

2016年12月22日

胡漢莉，女，碩士，工程師，研究方向：艦載指控系統(tǒng)研制。鄧威，男，碩士，工程師，研究方向：艦載指控系統(tǒng)研制。