運(yùn)輸機(jī)群貨物裝載方案生成方法

劉寧君 王立新 潘文俊

（北京航空航天大學(xué) 航空科學(xué)與工程學(xué)院，北京100191）

隨著航空運(yùn)輸?shù)目焖侔l(fā)展以及運(yùn)送物資的大型化與多樣化，空運(yùn)任務(wù)的強(qiáng)度也在不斷增大.對于一個同時使用多種型號運(yùn)輸機(jī)的航空運(yùn)輸機(jī)群，如何合理地安排機(jī)群的貨物裝載方式，有效地利用有限的運(yùn)輸資源并節(jié)約運(yùn)輸成本，成為當(dāng)前迫切需要研究解決的難題.國內(nèi)目前主要采用人工規(guī)劃的方法進(jìn)行裝載，這一方面費(fèi)時費(fèi)力，另一方面也難以得到特定優(yōu)化指標(biāo)下的最佳裝載方案.若采用自動算法來生成機(jī)群的裝載方案，則可極大地提高機(jī)群運(yùn)輸?shù)男?

由于國內(nèi)剛開始關(guān)注這類問題的研究，尚檢索不到相關(guān)的研究成果文獻(xiàn).國外可參考的裝箱算法有“最佳艙段適應(yīng)法”（BFL，Best Fit Level）［1］、“寬度排序試驗(yàn)法”（CLS）［2］以及“雙邊插入法”（FC，F(xiàn)loor－Ceiling）［2］等.但這些參考文獻(xiàn)均未給出上述算法的完整介紹，且方法僅限于單機(jī)貨物的裝載，也未考慮如何進(jìn)行貨物重心位置的調(diào)整，以保證運(yùn)輸機(jī)的飛行穩(wěn)定性與安全性等具體問題.針對現(xiàn)有研究工作中尚存在的這些問題，本文開展了運(yùn)輸機(jī)群貨物的裝載方法研究：首先確定了機(jī)群貨物裝載的順序，其次，生成了各架飛機(jī)貨物裝載的初步方案，然后對貨物的重心位置進(jìn)行了縱向和橫向的調(diào)整，最后按照特定的優(yōu)化指標(biāo)，優(yōu)選出運(yùn)輸機(jī)群的最優(yōu)裝載方案，從而形成了一種較系統(tǒng)的運(yùn)輸機(jī)群貨物裝載方案生成的新方法.

1 機(jī)群貨物裝載方案

為機(jī)群裝載貨物時，需先將貨物分類，再依次為單架運(yùn)輸機(jī)分別進(jìn)行裝載.通過改變機(jī)群的裝載順序，并對不同的裝載順序進(jìn)行預(yù)裝載，可以生成各種不同的裝載預(yù)案.對所有得到的裝載預(yù)案進(jìn)行分析、比較和篩選，可最終優(yōu)選出滿足給定指標(biāo)的運(yùn)輸方案.

1.1 貨物的分類

為了方便闡述，本節(jié)假設(shè)運(yùn)輸機(jī)群由甲型、乙型和丙型3種運(yùn)輸機(jī)組成，且無論從可運(yùn)送貨物的體積還是重量來說，它們的運(yùn)載能力都存在甲型＞乙型＞丙型的關(guān)系.在裝載之前，先按照機(jī)型的運(yùn)載能力，把待運(yùn)的k件貨物歸納到如下幾個集合中：

式中任意一個不等式不滿足，則意味著貨物大小超過貨艙尺寸或者重量超過運(yùn)輸機(jī)載重上限，因此這件貨物不能列入相應(yīng)的集合.

若S所有＝S甲型（即不存在機(jī)群中最大運(yùn)輸機(jī)都無法運(yùn)送的待裝貨物），就可以對貨物進(jìn)行分類，生成貨物集合S1，S2，S3.僅可由機(jī)群中最大的運(yùn)輸機(jī)運(yùn)送的貨物歸入S1中；可以由機(jī)群中最大和第2大（但不能由第3大）運(yùn)輸機(jī)運(yùn)送的貨物歸入S2中；僅可由第3大運(yùn)輸機(jī)運(yùn)送的貨物歸入S3中，即：

當(dāng)運(yùn)輸機(jī)群包含的運(yùn)輸機(jī)型號多于3種時，可同理生成S1，S2，S3，…，Sn（n為型號總數(shù)）.

1.2 機(jī)群裝載順序的確定

采用不同的裝載順序，在進(jìn)行預(yù)裝載之后即可產(chǎn)生不同的裝載預(yù)案.在生成裝載順序時，應(yīng)注意以下兩點(diǎn)：

1）不同順序的總數(shù)要合適.數(shù)量過大會使得計(jì)算時間過長，過小會導(dǎo)致最終優(yōu)選出的運(yùn)輸方案不接近實(shí)際最佳方案；

2）不同順序之間不能過于相似，否則生成的不同裝載預(yù)案也會比較相似，不利于比較和優(yōu)選.

一般來說，隨機(jī)生成足夠數(shù)量的裝載順序即可滿足以上要求.生成順序的數(shù)量應(yīng)按計(jì)算能力和機(jī)群組成情況具體分析；運(yùn)輸機(jī)型號和數(shù)量越多，順序數(shù)也應(yīng)越大.

1.3 不同裝載預(yù)案的生成

裝載順序確定后，就可以對每個裝載順序按照如下的方法進(jìn)行程序預(yù)裝載，以生成相應(yīng)的裝載預(yù)案：

1）按照裝載順序選定需裝載的運(yùn)輸機(jī)；

2）從前面生成的S1，S2，…，Sn中選擇其中能裝入當(dāng)前運(yùn)輸機(jī)的所有貨物集合；

3）在2）中選擇的一個或多個集合中，優(yōu)先選擇貨物較大的集合，并裝載其中的貨物.裝載時，應(yīng)將一個集合中的貨物按照長度遞減的順序逐件嘗試地裝入運(yùn)輸機(jī)，每件貨物的具體裝載方法在第2節(jié)詳細(xì)介紹.若此件貨物能被成功裝入，則將它從所屬集合中去除；

4）運(yùn)輸機(jī)裝滿后，需要對機(jī)艙貨物進(jìn)行重心位置的調(diào)整.調(diào)整過程中需要從運(yùn)輸機(jī)貨艙中去除的貨物，應(yīng)將其重新歸入其原屬的集合（即S1，S2，…，Sn其中一個）中（具體調(diào)整方法和步驟在第3節(jié)中介紹）；

5）如果重心位置調(diào)整失敗，則說明該裝載順序不可行，不能產(chǎn)生有效的裝載預(yù)案.這時可以對下一個裝載順序進(jìn)行預(yù)裝載.如果所有貨物都已裝載完畢，則表明這個裝載順序已經(jīng)順利完成，成功產(chǎn)生了一個裝載預(yù)案.

1.4 最終運(yùn)輸方案的生成

生成了不同裝載預(yù)案后，每個預(yù)案中所有飛機(jī)裝載的貨物重量也就隨之確定，這時就可根據(jù)設(shè)定的優(yōu)化指標(biāo)計(jì)算出機(jī)群在執(zhí)行任務(wù)時耗費(fèi)的成本.一般使用機(jī)群的總耗油或總耗時作為優(yōu)化指標(biāo)，二者分別體現(xiàn)了機(jī)群執(zhí)行空運(yùn)任務(wù)中的燃油成本和時間成本.耗油或耗時量指標(biāo)即為機(jī)群中各架運(yùn)輸機(jī)的耗油或耗時量之和，每架運(yùn)輸機(jī)在不同指標(biāo)下的優(yōu)化航跡和飛行成本算法在參考文獻(xiàn)［3］中已詳細(xì)闡述.

確定不同裝載預(yù)案各自耗費(fèi)的成本后即可確定成本最低的為最優(yōu)預(yù)案.最優(yōu)預(yù)案的貨物裝載方式和各架運(yùn)輸機(jī)相應(yīng)的航跡可用于確定最終的運(yùn)輸方案.

2 單機(jī)貨物裝載算法

在飛行條件下，運(yùn)輸機(jī)艙內(nèi)的貨物一般不能多層堆疊［2］，但可以在地板上自由排列.這意味著運(yùn)輸機(jī)貨物裝載是一個需要考慮貨物重心位置安排的特殊二維裝箱問題.本文提出的單機(jī)貨物裝載算法是在綜合BFL裝箱算法［2，4］和CLS裝箱算法［2，5］二者優(yōu)點(diǎn)的基礎(chǔ)上加以改進(jìn)而形成的，前者對尺寸相差較大的貨物都適用，后者能通過對貨物按寬度排序而節(jié)約空間.其大致思路為對運(yùn)輸機(jī)貨艙每個艙段使用FC法［2］裝入貨物，并在裝入過程中將貨物按寬度排序，以盡量節(jié)省空間.對一件待裝的貨物（總重應(yīng)小于運(yùn)輸機(jī)的載重上限），具體裝載步驟如下：

1）為裝入貨艙的第1件貨物建立一個艙段，并將其靠在貨艙左邊裝入，見圖1a；

2）將后續(xù)裝入的貨物放置在艙段后方（朝機(jī)尾的方向）已置貨物的右邊，見圖1b.如果空間不夠，就將貨物翻轉(zhuǎn)90°放置在艙段右前角［4－5］，見圖1c.如果右前角已放有貨物，可將要裝入的和右前角已有的貨物按照寬度遞增的順序從左到右排列，如圖1d所示；

圖1 裝載方法示意圖

3）如果步驟2）中還無法裝入貨物，就建立一個新艙段，如圖1e所示，后續(xù)貨物可以往這個新的艙段內(nèi)裝載.如果運(yùn)輸機(jī)貨艙的剩余空間不足以容納新的艙段，即貨艙空間已被用盡，則待裝貨物無法裝入此運(yùn)輸機(jī).

由于傳統(tǒng)的BFL和CLS算法都沒有考慮艙段位置的安排，可能會出現(xiàn)貨物縱向總重心位置大幅度偏離允許范圍的情況，如圖2a所示.這個問題可通過結(jié)合人工裝載中常用的“金字塔裝載法”［6］來解決.具體做法為：在建立第1個艙段時，將其布置在縱向重心最佳位置處，而之后的艙段則在這個艙段前后兩邊交替建立；此外，有新的貨物要裝入時，優(yōu)先考慮將其裝入靠近縱向重心最佳位置處的艙段中；如果不能實(shí)現(xiàn)，再考慮距離稍遠(yuǎn)的艙段.這樣操作之后，生成的艙段安排如圖2b所示.

圖2 不同的裝載算法對艙段生成的影響

3 艙內(nèi)貨物重心位置調(diào)整

為了保證空運(yùn)飛行的安全，運(yùn)輸機(jī)艙內(nèi)貨物的總重心位置在機(jī)身的縱、橫兩個方向都必須處于限定的范圍之內(nèi)［7－8］.本文采用的重心調(diào)整方法為先調(diào)整機(jī)身縱向（x方向，如圖1左邊所示的坐標(biāo)系中）的重心位置，之后再調(diào)整橫向（y方向，見圖1）的重心位置.這是因?yàn)樵谡{(diào)整縱向重心位置時，有可能需要去除貨艙內(nèi)的某些貨物，這對貨物的總體橫向重心位置會有影響，而調(diào)整橫向重心位置時無需去除貨物，因此不會引起縱向重心位置的改變.

3.1 縱向重心位置調(diào)整方法

如果將所有的艙段前后無間隙排列形成一個“大艙段”（見圖3），通過前后移動“大艙段”就可非常有效地調(diào)整縱向重心的位置.此外，通過卸除部分貨物也可以調(diào)整重心的位置.具體調(diào)整方法如下：

1）使所有艙段前后連在一起，形成一個“大艙段”，然后將大艙段在貨艙內(nèi)前后移動，如圖3所示，直至貨物重心調(diào)整至合適位置；

2）如果上一步操作還不能調(diào)整好重心位置，就選取位于重心位置偏離方向上最末端的艙段，在艙段中逐件卸除重量最小的貨物，直到貨物總重心位置滿足要求為止.

圖3 大艙段前、后移動的情況

3.2 橫向重心位置調(diào)整方法

橫向重心位置的調(diào)整方法是對某些艙段進(jìn)行左右翻轉(zhuǎn)（如圖4所示），這一調(diào)整對縱向重心位置無影響.一個艙段左右翻轉(zhuǎn)后產(chǎn)生的滾轉(zhuǎn)力矩是原來的負(fù)值.通過左右翻轉(zhuǎn)部分艙段，可使得所有艙段產(chǎn)生的滾轉(zhuǎn)力矩之和盡量接近0，從而消除或減小貨物產(chǎn)生的不對稱滾轉(zhuǎn)力矩，以保證飛行的穩(wěn)定性和安全性.

圖4 艙段左右翻轉(zhuǎn)示意圖

消除或減小貨物在貨艙內(nèi)產(chǎn)生的不對稱滾轉(zhuǎn)力矩即是使L取最小值，具體步驟如下：

1）找出所有Lp為負(fù)值的艙段并將其翻轉(zhuǎn)，這樣所有Lp都變?yōu)檎担?/p>

2）將Lp按從大到小的順序交替放入兩個數(shù)列和中，再將｛cn｝倒序接在｛bn｝之后，組成數(shù)列｛dn｝.這樣｛dn｝應(yīng)該有“兩頭大，中間小”的特征；

3）將｛dn｝從中間某位置分成兩個子數(shù)列，使二者包含的滾轉(zhuǎn)力矩元素之和盡量相近，然后將其中任意一個子數(shù)列中元素的對應(yīng)艙段進(jìn)行翻轉(zhuǎn).

通過以上步驟可使L取得最小值，即貨物在

設(shè)待調(diào)整運(yùn)輸機(jī)在裝載時被分成了q個艙段，其中第p個艙段產(chǎn)生的滾轉(zhuǎn)力矩為Lp，其值的正負(fù)代表力矩產(chǎn)生向右或向左滾轉(zhuǎn)運(yùn)動的趨勢.這樣所有艙段產(chǎn)生的滾轉(zhuǎn)力矩之和為貨艙內(nèi)產(chǎn)生的不對稱滾轉(zhuǎn)力矩最小，這樣就完成了橫向重心位置的調(diào)整.

4 算例與分析

本文對一個典型的運(yùn)輸任務(wù)，采用機(jī)群耗油總量作為優(yōu)化指標(biāo)進(jìn)行了計(jì)算分析.任務(wù)中的航程為1 008km，機(jī)群組成為 Y－7，Y－8，IL－76各3架，貨物信息如表1所示.

表1 貨物信息

經(jīng)過試算，算例中一共隨機(jī)生成了115種不同的裝載順序，在此裝載順序數(shù)時計(jì)算效率較高.經(jīng)過比較選出的最優(yōu)方案使用了一架IL－76、兩架Y－8和一架Y－7運(yùn)輸機(jī)，裝載順序?yàn)镮L－76→Y－8→Y－8→Y－7.在裝載每架運(yùn)輸機(jī)時，各貨物的裝載優(yōu)先級別按照其長度遞減排序，即為卡車→貨箱1→小車→貨箱2→貨箱3→貨箱5→貨箱4→散貨.各架運(yùn)輸機(jī)的耗油量和載重量見表2.

表2 運(yùn)輸機(jī)耗油量和載重量

在裝載計(jì)算過程中，對Y－7和IL－76運(yùn)輸機(jī)內(nèi)的貨物進(jìn)行了縱向重心位置調(diào)整，調(diào)整后貨物緊湊地排列在貨艙中部；對所有運(yùn)輸機(jī)都進(jìn)行了貨物橫向重心位置調(diào)整，調(diào)整后各運(yùn)輸機(jī)內(nèi)貨物在橫向分布比較均勻（如圖5所示）.由于使用了金字塔裝載法，每架運(yùn)輸機(jī)中較大、較重的貨物相對更靠近貨艙中部.

圖5 最優(yōu)方案中各運(yùn)輸機(jī)的裝載圖

采用文獻(xiàn)［3］給出的計(jì)算方法，圖6給出了不同裝載預(yù)案飛行用油總量的分布.從圖中可以看出，不同的裝載預(yù)案之間耗油量相差很大，有約55%的預(yù)案的用油量比最優(yōu)方案多近20t，幾乎為最優(yōu)方案用油量的1.5倍.由此可見，本文提出的貨物裝載生成方法能有效地對不同裝載預(yù)案進(jìn)行優(yōu)化，節(jié)省可觀的運(yùn)輸資源，極大地降低運(yùn)輸成本.

圖6 不同裝載預(yù)案飛行用油總量分布

5 結(jié) 論

本文較系統(tǒng)地提出了一種運(yùn)輸機(jī)群貨物裝載方案生成的新方法，可實(shí)現(xiàn)的主要功能有：

1）自動將待運(yùn)貨物分配到運(yùn)輸機(jī)群的各架飛機(jī)內(nèi)，并按照指定的優(yōu)化指標(biāo)（一般為耗油量或者耗時量）生成接近最佳的運(yùn)輸方案；

2）快速、自動地生成貨物在運(yùn)輸機(jī)貨艙內(nèi)的排列方式，生成的排列方式空間利用率較高、貨物重心位置易處于允許范圍內(nèi)；

3）在貨物重心位置處于允許范圍之外時，能夠在縱向及橫向調(diào)整貨物重心位置，使其移至允許范圍之內(nèi)，從而可保證飛機(jī)空運(yùn)飛行的穩(wěn)定性與安全性.

（

）

［1］Mongeau M，Bès C.Optimization of aircraft container loading［J］.IEEE Transactions on Aerospace and Electronic Systems，2003，39（1）：140－150

［2］Heidelberg K R，Parnell G S，James E Ames IV.Automated air load planning［J］.Naval Research Lagistics，1999，45（8）：751－768

［3］周堃，王立新.大型軍用運(yùn)輸機(jī)的飛行航跡優(yōu)化［J］.北京航空航天大學(xué)學(xué)報(bào)，2010，36（9）：654－658 Zhou Kun，Wang Lixin.Vertical flight trajectory optimization of heavy military airlift aircraft［J］.Journal of Beijing University of Aeronautics and Astronautics，2010，36（9）：654－658（in Chinese）

［4］Gehring H，Menschner K，Meyer M.A computer－based heuristic for packing pooled shipment containers［J］.European Journal of Operational Research，1990，44（2）：227－228

［5］Lodi A，Martello S，Vigo D.Neighborhood search algorithm for the guillotine non－oriented two－dimensional bin packing problem ［C］／／Voss S.Meta－Heuristics：Advances and Trends in Local Search Paradigms for Optimization.Boston：Kluwer Academic Publishers，1998：125－139

［6］Lodi A，Martello S，Vigo D.Heuristic and metaheuristic approaches for a class of two－dimensional bin packing problems［J］.Informs J Comput，1999，11（4）：345－357

［7］Kaluzny B L，David Shaw R H A.Optimal aircraft load balancing［J］.International Transactions in Operational Research，2009，16（6）：767－787

［8］Heidelberg K R.A bin packing algorithm for cargo conveyance systems［M］.Virginia：Virginia Commonwealth University，1995