運輸機群貨物裝載方案生成方法

劉寧君 王立新 潘文俊

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

隨著航空運輸的快速發展以及運送物資的大型化與多樣化，空運任務的強度也在不斷增大.對于一個同時使用多種型號運輸機的航空運輸機群，如何合理地安排機群的貨物裝載方式，有效地利用有限的運輸資源并節約運輸成本，成為當前迫切需要研究解決的難題.國內目前主要采用人工規劃的方法進行裝載，這一方面費時費力，另一方面也難以得到特定優化指標下的最佳裝載方案.若采用自動算法來生成機群的裝載方案，則可極大地提高機群運輸的效率.

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

1 機群貨物裝載方案

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

1.1 貨物的分類

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

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

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

當運輸機群包含的運輸機型號多于3種時，可同理生成S1，S2，S3，…，Sn（n為型號總數）.

1.2 機群裝載順序的確定

采用不同的裝載順序，在進行預裝載之后即可產生不同的裝載預案.在生成裝載順序時，應注意以下兩點：

1）不同順序的總數要合適.數量過大會使得計算時間過長，過小會導致最終優選出的運輸方案不接近實際最佳方案；

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

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

1.3 不同裝載預案的生成

裝載順序確定后，就可以對每個裝載順序按照如下的方法進行程序預裝載，以生成相應的裝載預案：

1）按照裝載順序選定需裝載的運輸機；

2）從前面生成的S1，S2，…，Sn中選擇其中能裝入當前運輸機的所有貨物集合；

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

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

5）如果重心位置調整失敗，則說明該裝載順序不可行，不能產生有效的裝載預案.這時可以對下一個裝載順序進行預裝載.如果所有貨物都已裝載完畢，則表明這個裝載順序已經順利完成，成功產生了一個裝載預案.

1.4 最終運輸方案的生成

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

確定不同裝載預案各自耗費的成本后即可確定成本最低的為最優預案.最優預案的貨物裝載方式和各架運輸機相應的航跡可用于確定最終的運輸方案.

2 單機貨物裝載算法

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

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

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

圖1 裝載方法示意圖

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

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

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

3 艙內貨物重心位置調整

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

3.1 縱向重心位置調整方法

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

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

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

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

3.2 橫向重心位置調整方法

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

圖4 艙段左右翻轉示意圖

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

1）找出所有Lp為負值的艙段并將其翻轉，這樣所有Lp都變為正值；

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

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

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

設待調整運輸機在裝載時被分成了q個艙段，其中第p個艙段產生的滾轉力矩為Lp，其值的正負代表力矩產生向右或向左滾轉運動的趨勢.這樣所有艙段產生的滾轉力矩之和為貨艙內產生的不對稱滾轉力矩最小，這樣就完成了橫向重心位置的調整.

4 算例與分析

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

表1 貨物信息

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

表2 運輸機耗油量和載重量

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

圖5 最優方案中各運輸機的裝載圖

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

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

5 結 論

本文較系統地提出了一種運輸機群貨物裝載方案生成的新方法，可實現的主要功能有：

1）自動將待運貨物分配到運輸機群的各架飛機內，并按照指定的優化指標（一般為耗油量或者耗時量）生成接近最佳的運輸方案；

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

3）在貨物重心位置處于允許范圍之外時，能夠在縱向及橫向調整貨物重心位置，使其移至允許范圍之內，從而可保證飛機空運飛行的穩定性與安全性.

（

）

［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］周堃，王立新.大型軍用運輸機的飛行航跡優化［J］.北京航空航天大學學報，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