大型裝備航空運輸裝載規(guī)劃優(yōu)化方法

趙 燦,吳 磊,張 帥

(1.陸軍工程大學訓練基地, 江蘇 徐州 221004; 2.空軍勤務學院, 江蘇 徐州 221000)

0 引言

在保障搶險救災等緊急任務時需要一次性投送多型號多臺次大型裝備,在裝載前需針對不同運輸投送任務進行裝載方案規(guī)劃,而裝載方案直接影響航空投送效率。為保證貨運飛機飛行安全的前提條件下盡可能提高航空運輸?shù)男?需綜合分析運輸機的載重、重心平衡和空間約束,使得各項參數(shù)處于安全許可范圍內(nèi),保證裝載安全,同時盡可能利用最少架次運輸機完成一次投送任務。

目前,關于航空裝載方案規(guī)劃問題可簡化為帶有約束的裝箱問題[1]或背包問題[2],針對不同應用場景建立一維、二維或三維矩形物體布局模型[3],是典型的NP-hard問題[2],求解方法包括圖論法、模擬退火算法、遺傳算法、禁忌搜索算法[4]、數(shù)學規(guī)劃法[5]等。孟沖等[6]將空間布局約束轉換成0～1整數(shù)線性規(guī)劃,實現(xiàn)對0～1整數(shù)線性規(guī)劃空運裝載問題的求解;Bertsimas等[7]提出了在諸多限制條件下利用混合整數(shù)規(guī)劃模型解決美軍人員和貨物以最小延遲和最大可用飛機利用率交付需求為目標的空運規(guī)劃問題;Roesener 等[4,8]針對貨物裝載在最少數(shù)量的空運飛機問題,提出了禁忌鄰域搜索算法求解混合有效載荷空運裝載問題和動態(tài)空運裝載問題;海軍等[9]以軍用運輸機裝載質(zhì)量最大、空間利用率最高作為優(yōu)化目標建立多目標優(yōu)化模型,利用蟻群算法進行求解;陳丙成等[10]主要將精英選擇策略的精英遺傳算法與輪盤賭的簡單遺傳算法相結合,用于裝箱問題求解;劉勝等[11]提出了一種啟發(fā)式正交二叉樹搜索算法用于三維裝箱問題的求解;李建等[12]針對大規(guī)模同時集散貨物路線問題,提出了一種集成大量鄰域搜索方法的禁忌搜索算法,用于提高求解能力。

目前針對尺寸較小、單體質(zhì)量較輕物體的航空運輸裝載優(yōu)化及優(yōu)化算法本身相關問題研究較多,并取得了很好的研究成果。但大型裝備具有單裝尺寸大、噸位重,同時不同機型貨艙的不同區(qū)域地板的設計承重強度不同[13],裝備裝載位置對于運輸機安全性有直接影響,專門針對大型裝備特點進行的相關研究較少。

前期通過與空軍勤務學院合作開展了關于單臺大型裝備空運適應性的理論研究、虛擬仿真和裝載試驗,該項成果確保了用于裝載優(yōu)化問題研究的大型裝備均可用運輸機進行裝載運輸。為確保運輸機安全,結合大型裝備的特點,在綜合考慮了運輸機裝載大型裝備總重限制、空間限制、平衡制約基礎上,增加了對運輸機地板分區(qū)載重約束的考慮,以完成單次運輸任務所需最少運輸機為優(yōu)化目標,建立了大型裝備軍事航空運輸裝載優(yōu)化模型。航空運輸裝載優(yōu)化屬于NP-hard問題,用啟發(fā)式算法求解該類問題較為合適[4]。

1 裝載優(yōu)化模型建立

現(xiàn)需要使用貨運飛機將一批大型裝備通過航空運輸部署到任務區(qū),待運輸工程裝備型號、數(shù)量及相關運輸性參數(shù)已知。運輸機的貨艙有效長、寬、高,空載重量,空載滿油重心位置,總載重量均已知。另外,如圖1所示,可用于大型裝備裝載的運輸機貨艙有A、B、C、D等4個分區(qū),每個分區(qū)的總載重量、長度已知。

圖1 運輸機貨艙ABCD 4個分區(qū)示意圖

為了便于使用運輸機的重心限制圖進行運輸機重心計算,建立運輸機的貨艙直角坐標系。坐標系原點O位于貨艙前部,沿運輸機縱向中軸線為X軸,由機頭向機尾方向為正方向,沿運輸機的橫軸方向為Y軸,沿運輸機的立軸方向為Z軸。貨艙直角坐標系,如圖2所示。由于裝備的裝載是由內(nèi)向外,先進入貨艙的裝備在內(nèi),后進入貨艙的裝備在外,裝備沿X軸線正方向排列。因此裝備的位置可用該裝備最左端在X軸的位置表示。

圖2 貨艙直角坐標系

1.1 模型假設

基于前期對大型裝備空運適應性研究成果,為了便于模型構建,對不規(guī)則的運輸機貨艙內(nèi)部空間、不規(guī)則的大型裝備外形輪廓進行簡化。

1) 大型運輸機貨艙的橫截面并不是規(guī)則的圓形或矩形,為了便于建模計算,將運輸機貨艙的可用裝載空間簡化為長方體,如圖2所示。

2) 大型裝備形態(tài)各異,外形不規(guī)則,將待運大型裝備最大外形輪廓簡化為長方體[13],將不同裝備處于裝載時姿態(tài)的實際重心作為裝備模型重心。

3) 假設所有待裝載大型裝備可以任意裝載在若干架次運載飛機貨艙內(nèi)。

4) 大型裝備由于尺寸較大,難以橫向擺放或橫向擺放后難以轉向。因此,假設待裝載大型裝備只能沿X軸線擺放。

5) 待運大型裝備不可以層疊擺放。

6) 待運大型裝備優(yōu)先裝載在運輸機貨艙的某個分區(qū)中,當大型裝備長度超過某一貨艙分區(qū)長度時,可以占用相鄰2個或3個分區(qū)。

7) 考慮到只有緊湊排列才能使運輸機貨艙被占用長度最小,因此假設同一機艙內(nèi)的所有裝備緊湊排列,任意相鄰2臺裝備系留間距為國軍標[14]規(guī)定的最小間距300 mm。

1.2 優(yōu)化模型

以使用最少數(shù)量的運輸機為優(yōu)化目標,將一批次各型裝備合理地裝到運輸機上,以提高投送效率,約束條件包括:重心位置約束、飛機總載重量約束、空間約束、飛機分區(qū)載重約束[15],以此建立運輸裝載優(yōu)化模型,有

(1)

s.t.Xmin(k)≤Xk≤Xmax(k)

(2)

(3)

(4)

(5)

式(1)—(5)中:βk表示當?shù)趉架次運輸機Fk裝載裝備的決策變量,當裝載時βk=1,否則βk=0;Xk表示第k架次運輸機裝載后的重心坐標,Xmin(k),Xmax(k)分別表示第k架次運輸機最小,最大重心坐標位置;P={Pi|i=1,2,…,N}={pij|pij∈Pi;i=1,2,…,N,J=1,2,…,ni}表示待運裝備集合,其中N為待運裝備的種類數(shù),i為集合中裝備的種類號,ni為第i類裝備的總輛數(shù),j為某類裝備中的件數(shù)號;αijk表示當運輸機Fk裝載裝備pij的決策變量,當裝載時αijk=1,否則為αijk=0;PMi、PLi分別表示第i類裝備的質(zhì)量和長度,i=1,2,…,N;δ1為裝載后相鄰2臺裝備之間的最小距離,δ2為裝載后所運裝備、物資的頂部或四周與飛機內(nèi)部結構之間的最小間隙;Mkmax、Lkmax、Mklmax分別表示第k架運輸機可用于裝載的最大載重量、最大機身長度、第l分區(qū)最大載重量。

2 算法設計

2.1 初始解獲取

通過隨機搜索算法獲取一個初始解。具體步驟如下:

步驟1數(shù)據(jù)初始化:輸入運輸機與待運裝備基本參數(shù)。

步驟2終止條件:迭代N次,且之后某次所用運輸機數(shù)量小于前面計算的各次,則終止,得到一個可行解。否則,繼續(xù)步驟3。

步驟3將所有型號的所有待運裝備編號,隨機排列得到一個裝備編號序列。

步驟4利用貨艙長度、載重約束,分割裝備子序列,得到初步裝機方案。

步驟5利用貨艙長度約束,計算每架運輸機上裝備子序列的重心范圍。

步驟6裝備子序列的重心范圍與運輸機重心可用范圍有交集,則繼續(xù)第7步。否則,終止本次搜索,返回步驟2。

步驟7取交集,得到每架運輸機上裝備子序列的實際重心范圍與裝備首部(最左端)坐標。

步驟8校核運輸機地板分區(qū)最大載重約束,如滿足,則記錄所用裝載方案;否則,終止本次搜索,返回步驟2。

2.2 禁忌搜索算法

禁忌搜索算法可用于解決組合優(yōu)化問題,由于采用類似于人類記憶功能的禁忌策略,容易跳出局部最優(yōu)。當某些搜索策略或搜索區(qū)域適應值較好,可能在沒被禁止到一定周期就解除禁忌,這稱為藐視條件,更容易搜索到全局最優(yōu)。禁忌搜索算法的步驟不再贅述。算法流程如圖3所示。

圖3 算法流程圖

2.3 禁忌搜索算法要素的確定

用禁忌搜索算法求解大型裝備航空運輸裝載優(yōu)化問題,需要確定解的表示、解的評價、鄰域點產(chǎn)生方法、算法終止準則、禁忌對象、禁忌長度及候選集等要素[16]。

采用將待運大型裝備直接排列的表示方法,即將所有類型待運的裝備按照一定的順序直接排列成為一個序列,并對其連續(xù)編號。這個自然數(shù)數(shù)列就構成了一個解,并對應了一種裝載方案。鄰域點產(chǎn)生方法采用兩換位法,產(chǎn)生若干個鄰域點,指定迭代步數(shù)作為算法終止準則,采用解的簡單變化作為禁忌對象,以待運裝備數(shù)量作為禁忌長度,鄰域中隨機選擇若干評價值較好的鄰居作為候選集。

3 數(shù)值計算

程序設計利用模塊化思想,對主要功能函數(shù)進行封裝,以便于修改、調(diào)試與調(diào)用。程序主要包括裝備與運輸機運輸性數(shù)據(jù)讀取模塊、運輸機貨艙總長度與總重量約束計算模塊、運輸機重心范圍約束計算模塊、運輸機分區(qū)載重約束計算模塊、禁忌搜索算法模塊以及結果分析呈現(xiàn)模塊。利用MATLAB軟件編程,對裝備航空運輸裝載方案優(yōu)化進行計算,得出最優(yōu)解。

某次遠程投送任務待裝載的裝備為9型15臺裝備,型號用字母代替如表1所示。

表1 待運裝備型號、數(shù)量等相關參數(shù)

利用所建立的優(yōu)化算法可計算得出裝載方案,結果顯示,使用6架次貨運飛機即可完成此次裝備投送裝載任務,6架次貨運飛機裝載的裝備型號分布如表2所示。待運裝備在各架次運輸機的位置,相對于貨艙前部的坐標如表3所示。待運裝備的裝載方案圖如圖4所示。

表2 待運裝備型號分布

表3 待運裝備相對于貨艙前部X坐標

圖4 待運裝備的裝載方案圖

圖4橫坐標為運輸機貨艙中軸線X軸坐標,單位(1 000 mm),縱坐標為運輸機使用數(shù)量。豎直虛線代表運輸機貨艙分區(qū)界線,橫向點劃線代表某一架次運輸機貨艙。粗實線代表某一臺裝備,線上編號代表裝備編號,“△”代表裝備的首部坐標,“★”表示在本架次運輸機上所裝載裝備組成的裝備序列的重心坐標(相對于貨艙前部)。如第1架運輸機,裝載了編號為1和3的裝備,首坐標分別為2 829.2、10 519 mm,由編號為1和3的2臺裝備組成的緊密裝備序列的重心坐標為10 500.0 mm。從圖4中可以看出優(yōu)化后裝載方案,裝備居運輸機中部裝載,符合一般裝載規(guī)律,空間利用合理。各架次運輸機裝備子序列重心可移動范圍如圖5所示。

圖5 各架次運輸機裝備子序列重心可移動范圍

圖5中運輸機可用重心范圍表示某架次運輸機裝載的裝備序列重心還有一定的可調(diào)整范圍。如第1架次運輸機裝載了編號為1和3的2臺裝備組成的裝備序列,這個裝備序列的重心可用范圍為10 500～10 781 mm,實際上運輸機X軸方向裝載重心允許范圍在10 500～13 500 mm。因此這3臺裝備組成的裝備序列首坐標、裝備間的最小間距均可在小范圍內(nèi)調(diào)整,只要重心仍在可用范圍10 500～10 781 mm內(nèi)即可。

圖6為各運輸機分區(qū)載重利用率。圖7為各運輸機空間與總載重量利用率,運輸機總體空間與載重利用率較高。運輸機的空間平均利用率83.8%,而運輸機的載重平均利用率66.8%。因此,大型裝備的長度是制約裝載方案優(yōu)化的主要因素。

圖6 各架次運輸機分區(qū)載重利用率

圖7 各架次運輸機空間與載重利用率

多臺大型裝備跨分區(qū)裝載優(yōu)化問題的算法,不僅可以適用于只使用某一個相同型號運輸機多架次裝載,通過輸入不同型號運輸機的參數(shù),也同樣適用于采用不同型號運輸機裝載優(yōu)化問題,實現(xiàn)不同型號運輸機同時混編運輸?shù)难b載方案規(guī)劃。

4 結論

1) 考慮了運輸機的貨艙總載重量、分區(qū)載重量限制、總長度限制條件,以最少架次運輸機完成航空裝載為目標,首先運用隨機搜索算法獲得初始解,然后利用禁忌搜索算法求解大型裝備航空運輸裝載問題,可生成針對投送任務的裝備裝載優(yōu)化方案,有助于實際裝載方案擬制。

2) 采用運輸機貨艙總長度與總載重量約束作為分割裝備序列的依據(jù),符合大型裝備普遍較長、線重比(重量與長度的比值)較大的特點。計算結果同樣表明,長度是制約大型裝備裝載的主要因素。

3) 為了便于計算,將大型裝備視為質(zhì)量均勻分布的長方體,后續(xù)研究可考慮裝備底盤型式、載重分布的實際情況,按照輪式、履帶式裝備分別校核運輸機貨艙分區(qū)載荷要求,使模型更加貼合裝備實際特征。

4) 為了使裝備重心范圍嚴格約束,采用了運輸機滿載時的重心可用范圍,然而在實際裝載中如果運輸機未滿載,重心可用范圍較滿載時更寬,因此,下一步研究中,可結合運輸機載重,限制重心可用范圍。