趙 燦,吳 磊,張 帥

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

0 引言

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

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

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

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

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

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

圖1 運(yùn)輸機(jī)貨艙ABCD 4個(gè)分區(qū)示意圖

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

圖2 貨艙直角坐標(biāo)系

1.1 模型假設(shè)

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

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

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

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

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

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

6) 待運(yùn)大型裝備優(yōu)先裝載在運(yùn)輸機(jī)貨艙的某個(gè)分區(qū)中,當(dāng)大型裝備長(zhǎng)度超過(guò)某一貨艙分區(qū)長(zhǎng)度時(shí),可以占用相鄰2個(gè)或3個(gè)分區(qū)。

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

1.2 優(yōu)化模型

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

(1)

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

(2)

(3)

(4)

(5)

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

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

2.1 初始解獲取

通過(guò)隨機(jī)搜索算法獲取一個(gè)初始解。具體步驟如下:

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

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

步驟3將所有型號(hào)的所有待運(yùn)裝備編號(hào),隨機(jī)排列得到一個(gè)裝備編號(hào)序列。

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

步驟5利用貨艙長(zhǎng)度約束,計(jì)算每架運(yùn)輸機(jī)上裝備子序列的重心范圍。

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

步驟7取交集,得到每架運(yùn)輸機(jī)上裝備子序列的實(shí)際重心范圍與裝備首部(最左端)坐標(biāo)。

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

2.2 禁忌搜索算法

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

圖3 算法流程圖

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

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

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

3 數(shù)值計(jì)算

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

某次遠(yuǎn)程投送任務(wù)待裝載的裝備為9型15臺(tái)裝備,型號(hào)用字母代替如表1所示。

表1 待運(yùn)裝備型號(hào)、數(shù)量等相關(guān)參數(shù)

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

表2 待運(yùn)裝備型號(hào)分布

表3 待運(yùn)裝備相對(duì)于貨艙前部X坐標(biāo)

圖4 待運(yùn)裝備的裝載方案圖

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

圖5 各架次運(yùn)輸機(jī)裝備子序列重心可移動(dòng)范圍

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

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

圖6 各架次運(yùn)輸機(jī)分區(qū)載重利用率

圖7 各架次運(yùn)輸機(jī)空間與載重利用率

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

4 結(jié)論

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

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

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

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