基于改進層構造算法的運輸直升機裝載方案設計

李 威，王興亮，王士乾，張志鋒

（北方自動控制技術研究所，太原 030006）

0 引言

現代戰爭中，陸軍作戰區域不斷擴展，使得運輸投送能力成為衡量部隊綜合能力的重要因素。相比于其他運輸裝備，運輸直升機擁有更強的機動能力，且可在復雜環境遂行精準運輸保障任務［1］。裝載任務是運輸保障任務中的重要子任務。

目前運輸直升機裝載方案由人工根據經驗制定。如在美軍中，由空中突擊部隊指揮官和參謀在任務規劃階段制定裝載方案。以這種方式給出的裝載方案不僅受限于人員能力水平，且制定過程耗時長，有極高的不確定性。為了防止人工制定的裝載方案不合理帶來的危險，美軍還在裝載行動中加入物資稱重環節和調整環節，徒增行動時間。

隨著我軍指控系統的信息化發展，在某指控信息系統項目中，急需能自動生成裝載方案的方法。不僅能提高直升機利用率，還能簡化任務規劃流程和指揮參謀人員工作量。同時面對突發狀況時，可快速生成新的裝載方案以適應新任務要求，提高部隊臨機調整能力。

本文為了解決根據直升機裝載任務，生成合適的裝載方案的問題，該問題是一類考慮直升機實際運用特點的三維裝箱問題。

三維裝箱問題屬于NP-hard 問題［2］，主要通過降維法、構造啟發式算法、智能啟發式算法等求解。尚正陽等［4］將三維裝箱問題轉化為帶高度約束的二維裝箱問題，降低了空間分割時的復雜度；George和Robinson［5］提出的“墻”構造思想，成為裝箱問題經典構造法，往后諸多研究都是在該算法基礎上改進的；朱向等［6］提出核心堆思想和對稱極點裝載法實現了裝載方案的平衡約束。近年來，智能算法成為求解NPC 問題的重要方法，Menghani 等［7］將多容器問題分解為單容器問題，使用了兩種改進遺傳算法，同時考慮了實際操作約束；ZHANG 等［8］在使用集成了遺傳算法和模擬退火算法，采用兩段式編碼，解除了物資裝載過程中單一規則的限制，提高了空間利用率。目前國內外研究集中于單純的三維裝箱問題，算法設計時沒有考慮直升機的特殊性，不能應用于直升機領域。

本文首先分析運輸直升機軍事運用特點，其次構建裝載問題模型，并設計改進層構造算法，最后通過仿真試驗，驗證算法的有效性。

1 運輸直升機裝載問題建模

1.1 運輸直升機裝載問題特點

由于直升機操穩特性差，允許的重心變化范圍窄，重心處于極限位置極易造成危險。另外，重心偏移會影響直升機自動傾斜器的傾斜角度，進而影響直升機的機動能力［9］。如圖1 所示，若直升機重心偏后，傾斜器需前傾α 度以平衡重心偏移，導致直升機最大速度減少；若直升機重心偏前，傾斜器需后傾β 度，導致直升機懸停和后退飛行能力受到限制。故直升機對裝載重心有極高要求，一方面裝載重心需嚴格在重心包線區域內以保證飛行安全；另一方面，需盡量減少重心偏移量以保證直升機的機動能力。

圖1 重心偏差對直升機自動傾斜器角度的影響

其次，針對運輸直升機的軍事運用背景和軍事需求，有可能出現人員和物資混裝情況，且裝載物資為軍用物資，有特殊要求。

1.2 裝載問題描述

運輸直升機裝載問題為：針對單架運輸直升機執行裝載任務，生成對應的裝載方案，該裝載方案在滿足裝載任務要求的基礎上，考慮實際約束，使裝載重心盡量靠近直升機旋翼軸投影點。特別地，對于運輸直升機而言，確保飛行安全是關鍵，因此相對于提高空間利用率，減少裝載重心偏移更加重要。

運輸直升機裝載問題有以下前提假設和約束條件。

前提假設：H1 為運輸直升機裝載機艙為近似長方體容器，H2 為待裝物資為規則立方體剛體，且重心與幾何中心重合，H3 為待裝物資擺放方向與直升機朝向平行或正交，H4 為單個乘機人員體重與攜行裝備總重固定，人員坐在座位上時所占體積、重心位置固定。

約束條件：C1（載重量約束）為乘機人員與所有待裝物資總重之和需小于直升機的最大載重量，C2（裝載重心約束）為人員和物資總重心（簡稱裝載重心）滿足直升機飛行的重心要求，C3（物資擺放方向約束）為某些物資限制了其擺放方向，如帶引信彈藥需要垂直直升機飛行方向擺放。

1.3 運輸直升機裝載空間和裝載任務描述

為了研究直升機裝載問題，需要對運輸直升機機艙建模，根據H1 假設，將運輸直升機機艙空間簡化為如下頁圖2 所示的長方體空間。

其中，L，W，H 分別表示直升機機艙的長寬高。根據H4 假設定義人員乘坐空間為Lp，Wp，H 的立方體，如圖2 中的空間所示，物資裝載空間為機艙中排除人員乘坐的位置的剩余空間。

圖2 運輸直升機艙三維空間

點G 表示直升機旋翼軸投影點，Dg表示直升機裝載重心包線區域。直升機裝載重心包線是指直升機在飛行過程中允許的裝載重心變化范圍［10］，用于判斷裝載方案是否滿足C2 約束。一般直升機設計的裝載重心包線為包圍點G 的長方形區域，Lg表示Dg距機艙前端的距離，Ldg，Wdg分別表示Dg的長寬。為了保障直升機的飛行安全，一般Wdg較小；為保證直升機的最大飛行速度，趨向讓重心位置靠前，自動傾斜器向后偏斜，即直升機對重心前移的寬容度大于重心后移［9］。另外由Qmax表示運輸直升機最大內載重量。

裝載任務通過裝載清單描述，包括p 名乘機人員和n 件待裝載物資，每件物資給定其質量、長寬高、允許姿態等參數，其中允許姿態需滿足C3 約束。裝載方案包括每件物資的放置位置、姿態等。

1.4 裝載問題建模

由于直升機裝載重心在垂直方向變化對直升機影響小，故忽略重心垂直方向影響，只考慮裝載重心水平方向投影點與重心包線的關系。定義Qt為人員和物資總總重Gt={Gtx，Gty}，為裝載重心投影點，通過式（1）得出裝載重心偏移量ΔGt={ΔGtx，ΔGty}。

由于直升機對重心前移的容忍度大于重心后移，對Y 軸重心偏移容忍度小，在重心偏移量的基礎上通過式（2）定義兩個方向的重心偏移度φ（ΔGt）={φx，φy}，通過式（3）定義總重心偏移度φ，實現對重心偏移的標準化。

運輸直升機裝載模型如下：

其中，式（5）滿足C1 約束，式（6）滿足C2 約束。

2 運輸直升機裝載方案生成算法

運輸直升機裝載方案生成算法流程如圖3 所示，首先利用裝載空間構造法確定不規則裝載空間，其次利用基于引導合并策略的層構造算法和重心調整算法生成裝載方案。若調整后重心不滿足要求，調整裝載順序后重新生成。

圖3 裝載方案生成算法流程

2.1 裝載空間構造法

考慮到運輸直升機裝載的人物混裝情況，在構造物資裝載空間前需排除人員占用空間。為了方便人員乘機和下機，令人員靠近后艙門乘坐如圖4為乘坐7 人后對物資裝載空間的劃分及優先乘坐順序。

圖4 直升機內艙空間劃分

通過分析可得，物資裝載空間可能為規則空間、不規則L 形空間、凸形空間等。

使用平行于YOZ 平面的面將不規則空間切割成多個規則空間，后在每個規則空間內完成裝載。如圖5 所示，不規則空間切割位置為其在X 軸方向的曲折位置，切割后規則空間的寬度區間有3 種情況，由此分為三型空間。1 型空間寬度區間為［0，W］，2 型空間寬度區間為［0，W-Wp］，3 型空間寬度區間為［Wp，W］。不同型空間在重心調整階段有不同策略。

圖5 不規則空間分割方法和四型規則空間

2.2 基于引導合并策略的層構造算法

每個規則空間內，通過基于引導合并策略的層構造算法完成裝載。

圖6 所示，三空間劃分有XYZ 型和YXZ 型。當物資c 放入空間S 中時，使用占角原則，即將物資擺放于空間左后角，之后將裝載空間劃分為上空間Su、前空間Sf和右空間Sr。

圖6 XYZ 型三空間劃分法

層構造算法中定義了“層”和“塔”兩種空間描述。層是整個裝載空間用平行于YOZ 平面分割成的空間。每個層空間由層內第一件裝入物資c 和對應的Su和Sr組成，層厚度為c 沿X 軸方向的長度lc，層方向為Y軸方向。一個裝載空間可以有多個層，以及零個或一個空層。每層中的物資可由平行于XOZ面的平面切割成多個部分，稱為塔，如圖7 所示。每個層都可被分為多個塔，以及零個或一個空塔。空層和空塔表示無物資的空間，可以為調整重心提供空間。

圖7 層和塔的構建方法

層構造思想應用于直升機物資裝載問題有兩個優勢，一方面與不規則空間分割方式契合，另一方面有利于以層和塔為單元對物資重心進行調整。

將物資裝入層中時需確定裝入的先后順序，稱為定序規則，常見的定序規則有體積與重量聚簇排序，按物資優先級排序等。本文定序規則為物資X軸方向長度遞減順序排序，可使每一層物資盡量規整，減少空隙。為了滿足層方向的要求，層構造時使用XYZ 型三空間劃分；層內放置時，由于物資件X軸方向長度差距小，導致前空間很薄，故使用YXZ型三空間劃分，盡量使右空間更大。

經典層構造算法有可能導致結果空間利用率低，本文通過增加引導式空間合并策略提高算法空間利用率。為了保留層構造的兩大優勢，空間合并策略通常只針對層內。引導式空間合并策略有兩個核心：

第五，在文藝思想方面的交流。 士僧交往，習禪之風盛行，必然對士大夫們的文藝思想產生很大的影響，譬如王士禎的“神韻說”。 他在《香祖筆記》中說：“舍筏登岸，禪家以為悟境，詩家以為化境，詩禪一致，等無差別。” 王士禎雖說到“嚴滄浪以禪喻詩，余深契其說，而五言尤為近之”，受到嚴羽“羚羊掛角，無跡可求”、司空圖“不著一字，盡得風流”以及王惟、孟浩然等前輩以禪論詩的影響，但是究其生平，他喜與僧人交往，智樸是交往最密切的一位了，智樸對他文藝思想的影響值得關注。

一是引導同類物資并排放置，使得其上層空間底面同高，可合并為更大的穩定上空間，同時前空間厚度相同，可合并為更長的前空間；

二是由于定序規則導致非同類物資物資X 軸方向長度差距小，由X 軸方向長度小的物資的需求引導前空間的合并，如圖8 所示，lneed表示最小長度需求量，以lneed為引導，大于需求量的兩個前空間Sf2和Sf3進行合并操作，這種主動合并策略可有效利用前空間裝載厚度小的物資，提高空間利用率。

圖8 需求引導式空間合并

基于引導合并策略的層構造算法的核心為操作3 個棧，分別為空間棧、空隙棧、物資棧。算法初始狀態，空間棧為整個裝載空間；待裝物資按定序規則入棧，同件物資的不同姿態認為是不同物資入棧；空隙棧為空棧，用于記錄無法放入物資的空間，用于合并空間。算法的具體流程如下頁圖9 所示。

2.3 重心調整算法

裝載完成后，需調整裝載重心，使裝載重心偏移度φ 最小。重心調整分為對X 軸和Y 軸兩個不相關方向的調整。由于直升機特殊的動力結構，裝載的Z 軸重心范圍變化小且對飛行影響小，可忽略［10］。2.3.1 X 軸方向重心調整

X 軸方向重心調整手段為層間調整，調整目標是φx最小。層間調整操作包括利用空層厚度移動層和交換層排列順序，調整操作限制在同型空間內。X軸方向重心調整策略首先計算各型空間中物資的X軸方向重心范圍，再計算每型空間中重心最佳位置，最后求解每個空間具體層的放置位置。

假設某個空間中有k 個層和一個厚度為d 的空層，每個層重量qli，層厚為dli，層內X 軸方向重心為xli。計算每個層內物資重量沿X 軸方向的分布密度ρli=qli/dli，按ρli由大到小將層排序，以此排序計算每個空間可調整的X 軸方向重心范圍為：

若總重心范圍與重心包線有重疊部分，說明當前裝載方案可以通過調整以滿足裝載重心要求。

空間內層的放置遵循重心為中心的策略。按ρli由大到小的順序，依次排布于重心的兩側，最后用空層的厚度微調即可。

2.3.2 Y 軸方向重心調整

Y 軸方向重心調整手段為層內調整，調整目標是φy最小，使裝載重心盡量落到機艙中線上。層內調整操作包括利用空塔寬度移動物資和對稱放置的層內物資。設某一層調整前Y 軸方向重心位置為y，空塔寬d，若層滿足式（9），即該層可通過層內調整可使層內裝載重心落到機艙中線上，則稱該層為平衡層，反之為不平衡層。

由于1 型和3 型空間關于機艙中線對稱的，其中層大概率為平衡層，而2 型空間相對于中線偏移，其中層大概率為不平衡層。Y 軸方向重心調整策略為，首先對2 型空間內的層預處理，使得其重心盡量靠近機艙中線；之后按先不平衡層后平衡層的方式將層放入，放入時進行層內調整，盡量抵消之前重心的偏移，隨著放入逐漸減少重心偏移。

3 仿真驗證

仿真實驗模擬某型直升機的8 次裝載任務。如表1 所示為裝載物資參數以及8 次裝載任務的裝載清單，表格左側表示物資的三維參數，表格右側表示每次裝載任務中物資的數量。8 次裝載任務有不同特點，其中任務I 代表大件物資為主的情況，任務II 代表小件物資為的情況，任務III 代表人員較多的情況，任務IV、V、VI 代表完全物資裝載情況，任務VII、VIII 代表復雜裝載情況。

使用本文算法和文獻［6］算法分別針對8 個裝載任務生成裝載方案，由于文獻［6］算法沒有討論人物混裝情況，令其使用本文的裝載空間構造法。如下頁圖10（a）為本文算法針對VIII 號任務生成的裝載方案，其中紅色箭頭表示人員和物資的裝載重心線，橙色區域表示該型直升機的重心包線區域，黃色區域為乘員乘坐區域，各種物資由不同顏色的立方體表示，圖10（b）為本文算法針對V 號任務生成的裝載方案。

下頁表2 為本文算法和文獻［6］算法生成的8個裝載方案的重心偏移結果和算法用時，兩個算法都可將物資裝入機艙空間，在用時上接近，皆為毫秒級，并與物資的總件數呈正相關。但文獻［6］算法生成的裝載方案重心偏移度高，8 個裝載方案僅任務V 的方案滿足直升機重心要求，其余無法滿足直升機重心要求中。而本文算法生成的裝載方案重心偏移度低，8 個裝載方案的裝載重心全部落在直升機重心包線內，且有4 個裝載方案的裝載重心完全與直升機旋翼軸線重合，其余4 個裝載方案的裝載重心偏移度很低。

表1 裝載物資參數以及8 次裝載任務的裝載清單

通過仿真實驗可以驗證，相較傳統人工制定裝載方案的方法，本文算法可以實現從任務到方案的快速生成；相較于其他三維裝箱算法，在保證空間利用率的情況下，本文算法不僅可以滿足人物混裝等需求，生成的裝載方案也可以最大程度減少重心偏移。

圖10 V 號和VIII 號任務生成的裝載方案

表2 裝載方案重心偏移結果和算法用時

4 結論

本文分析了運輸直升機在遂行運輸保障任務時的軍事運用特點，對直升機裝載空間、裝載任務、裝載方案進行了數學描述，建立了以最小裝載重心偏移度為目標的運輸直升機裝載多約束模型。在多約束模型的基礎上，提出了一種基于改進層構造算法的運輸直升機裝載方案生成算法，創新地使用引導合并策略提高每層空間的利用率，同時使用了空間構造算法和重心調整算法，以滿足直升機對人物混裝和嚴格重心的要求。

經仿真實驗證明算法可在毫秒級生成重心偏移度低、空間利用率高的裝載方案，可保證直升機飛行安全，最大化直升機裝載能力的利用率。本文成果應用于某指控系統中，對提高部隊執行運輸保障任務能力有一定的現實意義。