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

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

0 引言

現(xiàn)代戰(zhàn)爭中，陸軍作戰(zhàn)區(qū)域不斷擴(kuò)展，使得運(yùn)輸投送能力成為衡量部隊綜合能力的重要因素。相比于其他運(yùn)輸裝備，運(yùn)輸直升機(jī)擁有更強(qiáng)的機(jī)動能力，且可在復(fù)雜環(huán)境遂行精準(zhǔn)運(yùn)輸保障任務(wù)［1］。裝載任務(wù)是運(yùn)輸保障任務(wù)中的重要子任務(wù)。

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

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

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

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

本文首先分析運(yùn)輸直升機(jī)軍事運(yùn)用特點(diǎn)，其次構(gòu)建裝載問題模型，并設(shè)計改進(jìn)層構(gòu)造算法，最后通過仿真試驗，驗證算法的有效性。

1 運(yùn)輸直升機(jī)裝載問題建模

1.1 運(yùn)輸直升機(jī)裝載問題特點(diǎn)

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

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

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

1.2 裝載問題描述

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

運(yùn)輸直升機(jī)裝載問題有以下前提假設(shè)和約束條件。

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

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

1.3 運(yùn)輸直升機(jī)裝載空間和裝載任務(wù)描述

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

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

圖2 運(yùn)輸直升機(jī)艙三維空間

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

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

1.4 裝載問題建模

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

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

運(yùn)輸直升機(jī)裝載模型如下：

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

2 運(yùn)輸直升機(jī)裝載方案生成算法

運(yùn)輸直升機(jī)裝載方案生成算法流程如圖3 所示，首先利用裝載空間構(gòu)造法確定不規(guī)則裝載空間，其次利用基于引導(dǎo)合并策略的層構(gòu)造算法和重心調(diào)整算法生成裝載方案。若調(diào)整后重心不滿足要求，調(diào)整裝載順序后重新生成。

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

2.1 裝載空間構(gòu)造法

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

圖4 直升機(jī)內(nèi)艙空間劃分

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

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

圖5 不規(guī)則空間分割方法和四型規(guī)則空間

2.2 基于引導(dǎo)合并策略的層構(gòu)造算法

每個規(guī)則空間內(nèi)，通過基于引導(dǎo)合并策略的層構(gòu)造算法完成裝載。

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

圖6 XYZ 型三空間劃分法

層構(gòu)造算法中定義了“層”和“塔”兩種空間描述。層是整個裝載空間用平行于YOZ 平面分割成的空間。每個層空間由層內(nèi)第一件裝入物資c 和對應(yīng)的Su和Sr組成，層厚度為c 沿X 軸方向的長度lc，層方向為Y軸方向。一個裝載空間可以有多個層，以及零個或一個空層。每層中的物資可由平行于XOZ面的平面切割成多個部分，稱為塔，如圖7 所示。每個層都可被分為多個塔，以及零個或一個空塔?？諏雍涂账硎緹o物資的空間，可以為調(diào)整重心提供空間。

圖7 層和塔的構(gòu)建方法

層構(gòu)造思想應(yīng)用于直升機(jī)物資裝載問題有兩個優(yōu)勢，一方面與不規(guī)則空間分割方式契合，另一方面有利于以層和塔為單元對物資重心進(jìn)行調(diào)整。

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

經(jīng)典層構(gòu)造算法有可能導(dǎo)致結(jié)果空間利用率低，本文通過增加引導(dǎo)式空間合并策略提高算法空間利用率。為了保留層構(gòu)造的兩大優(yōu)勢，空間合并策略通常只針對層內(nèi)。引導(dǎo)式空間合并策略有兩個核心：

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

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

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

圖8 需求引導(dǎo)式空間合并

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

2.3 重心調(diào)整算法

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

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

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

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

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

2.3.2 Y 軸方向重心調(diào)整

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

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

3 仿真驗證

仿真實驗?zāi)M某型直升機(jī)的8 次裝載任務(wù)。如表1 所示為裝載物資參數(shù)以及8 次裝載任務(wù)的裝載清單，表格左側(cè)表示物資的三維參數(shù)，表格右側(cè)表示每次裝載任務(wù)中物資的數(shù)量。8 次裝載任務(wù)有不同特點(diǎn)，其中任務(wù)I 代表大件物資為主的情況，任務(wù)II 代表小件物資為的情況，任務(wù)III 代表人員較多的情況，任務(wù)IV、V、VI 代表完全物資裝載情況，任務(wù)VII、VIII 代表復(fù)雜裝載情況。

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

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

表1 裝載物資參數(shù)以及8 次裝載任務(wù)的裝載清單

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

圖10 V 號和VIII 號任務(wù)生成的裝載方案

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

4 結(jié)論

本文分析了運(yùn)輸直升機(jī)在遂行運(yùn)輸保障任務(wù)時的軍事運(yùn)用特點(diǎn)，對直升機(jī)裝載空間、裝載任務(wù)、裝載方案進(jìn)行了數(shù)學(xué)描述，建立了以最小裝載重心偏移度為目標(biāo)的運(yùn)輸直升機(jī)裝載多約束模型。在多約束模型的基礎(chǔ)上，提出了一種基于改進(jìn)層構(gòu)造算法的運(yùn)輸直升機(jī)裝載方案生成算法，創(chuàng)新地使用引導(dǎo)合并策略提高每層空間的利用率，同時使用了空間構(gòu)造算法和重心調(diào)整算法，以滿足直升機(jī)對人物混裝和嚴(yán)格重心的要求。

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