民航客機貨艙自動配平優化技術①

姜昱君,韓 銳

(北京理工大學 計算機學院,北京 100081)

空中交通作為一種現代化交通方式,在世界各地被廣泛應用,各型號民航客機常包含貨艙部分,由于空中運行的特殊性,為了保障空中交通的安全性,對航空器重心有著嚴格要求,因此航空器配載是飛機運行的關鍵步驟之一.隨著現代化水平提高,國內外對于機場智能化管理已經有了明確的發展方向,引入信息共享系統參與機場管理,該類系統最早由歐洲提出并實施部署,將其命名為airport cooperative decision management system,簡稱為A-CDM,用于完善空管系統內部運行信息通報和協同決策機制,近年來國內正在著手推進機場信息管理系統建設,2017年8月,民航局發布了《關于進一步統籌推進機場協同決策(A-CDM)建設的通知》,要求行業各單位進一步統籌推進A-CDM建設.

配載業務是航空調度的關鍵組成部分,該操作長期以來依靠配載員的經驗手工完成,每個機型有單獨的配載表,學習成本高,配載效果受配載員工作狀態影響大.由飛機負載平衡問題引發的安全事故時有發生,其根源在于飛機的運作性質,配載重心超出前限航空器的前起落架及支撐結構會受到損壞,起飛時難以拉起機頭;落地時會損壞前起落架及支撐結構;配載重心太過靠后,起飛過程中可能發生機尾觸地的“沉尾”安全事故;該類問題還會導致飛機可操作性下降、容錯率降低,在遭遇渦流及強風等惡劣情況時會有失速的危險.隨著機型越來越復雜,航班量越來越大,航空公司對安全、準點的要求越來越高,該項工作已經成為提升配載操作效率的瓶頸,配載業務作為飛機運行關鍵步驟,其智能化、統一化勢在必行.

目前已經有輔助性的配載系統投入使用,但仍不完善,沒有較好地適應民航客機配載的多約束、多變動環境,非常依賴地勤工作人員進行手動調整或者直接進行手動配載操作.有資料指出當前配載過程含義混雜[1],指向多種業務過程,解決方法耦合性高.

本文首先對算法當前存在的問題進行了分析,并根據分析結果將配載業務過程和涉及模型進行了抽象設計,選取遺傳算法作為基礎理論進行針對性優化和模塊化設計,提出約束回報動態計分方法來適應多變、多配載需求的民航貨艙配載算法結構,在不同貨物組合中保持相對穩定的重心優化結果,使得貨物在規格、標簽和經停裝載優先級等約束條件下配載重心接近或達到理論偏移最優值,并達到秒級實時配載計算的目標,取得了較好的測試結果.最后對后續發展方向進行了討論.

1 問題分析

1.1 算法問題分析

算法設計是配載系統開發的核心組成部分,該問題從性能方面又可分為執行效果和執行效率兩部分.

飛機負載平衡問題被認為是一種NP 難箱包裝載(bin packing)問題[2,3]的分支,研究人員對此進行了算法研究.在此基礎上,Kaluzny 等人針對軍事應用[4]提出了一種飛機負載平衡方案,由于在軍用運輸機使用中涉及到的貨物包括軍用裝備、車輛等大型物體,其體積大、重心位置與物品型心位置差距明顯等問題,實現了4 個方向正交旋轉物體進行配平的方法;線性規劃模型常用于最優化計算,Verstichel 等人應用混合整數線性規劃[5]進行配載最優化計算;還有研究人員[6]采用相似的分支定界法來進行配載方案搜索,取得了不錯的配載效果;CLPA 系統設計[7]改進了整數線性規劃方法,從最小化剩余空間而不是最大化裝載空間的角度來進行問題求解,在此基礎上不同類型的貨物劃分為不同優先級來輔助計算.還有研究人員從其他角度[8,9]和特定應用場景[10]對配載問題進行了討論.

各類重心相關算法可分為3 類,第1 類算法只關心基本的配載重心約束,如飛機平衡檢測器內置系統,側重于重心狀態實時監測;第2 類算法在第1 類算法基礎上提升了約束覆蓋面,減輕人工調整工作量,但是泛化能力差,在面對機型變動等特殊情況時不能較好地適應,如前文中介紹的線性規劃計算法,需要針對特定飛機型號推導公式參數;第3 類算法在第2 類算法基礎上,繼續增大約束覆蓋面積,能適應各種特殊情況,在少量人工參與下既能完成配載計算,分支定界搜索法在一定程度上能夠有較好的的可擴展性,但是算法搜索時間較長難以實時配載,不能做到實時響應.

1.2 系統問題分析

從架構方面分析,當前配載系統有泛化能力差、模塊化差的問題.

本文中提到的算法泛化性是指使用一種解決方案能否應對多種機型的配載問題.由于飛機型號對配載過程影響大,部分飛機配載系統出現定制化,系統設計者從單一型號飛機配載方面出發,形成的系統在一類問題上表現較好,但是當飛機機型出現新的需求的時候則需要重新進行公式推導,泛化能力差,不利于飛機信息的系統性管理.例如,有研究人員[3]提出的方案采用2 維建模,且默認貨物不可重疊,當飛機出現雙層貨艙時則需要重新進行理論推導.

模塊化問題指的是部分系統設計將飛機配載業務過程與算法過程混雜,使得代碼可讀性和擴充性差,在航空公司出現新機型、新需求時,難以調整,導致算法需要全盤重構,增加了使用成本.

2 算法設計

為了應對以上問題,提高配載算法的性能和泛化能力,本文實現一種基于遺傳算法的動態分值計算配載算法,抽象解耦約束計算機制,提升應對新需求的能力.

2.1 業務建模

飛機重心[11,12]是影響飛機運行過程的關鍵參數之一,將飛機在機翼常規狀態下平穩運行過程中產生升力的等效點作為理想重心位置,以下用CGidea指代,飛機配載完成后實際重力等效點為實際重心,用CG 指代.理想狀態為CG 與CGidea重合,不需要進行額外力輔助;實際狀態多為CG 與CGidea有相對距離且在飛機運行可接受范圍內,飛機需要通過調整機翼及其他手段產生除正常運行的升力以外的力進行輔助平衡,部分資料將其稱為配平力.將飛機可接受的重心位置集合稱為包線范圍,每架飛機有固定的包線范圍,由飛機硬件決定.

就該目標分析可將影響配載效果的屬性分為固有屬性和可變屬性兩類.模型固有屬性為飛機各項運行指標及其座位、貨艙相關屬性,該類屬性在多次配載過程中,對于同一飛行器不會變動或極少變動;可變屬性為配載過程中旅客及貨品相關參數,包括數量、重量和規格等,在各次配載過程中會發生改變,優化配載過程實際上是優化可變屬性的裝載參數.

根據飛機受力規則,以機頭為縱軸正方向,右翼指向方為橫軸正方向,CGidea為原點進行二維建模,如圖1所示.

圖1 受力約束建模

配載目標主要為貨品,同時乘客力矩也會納入計算以獲得飛機整體力矩,對其建模采用幾何中心作為重心.乘客位置選擇主要受到客艙等級lh和重量wh兩個屬性影響,貨物除了基本的重量限制外,還收到諸如規格、優先級和標簽等屬性影響.

飛機結構中與配載相關組件首先與配載可變屬性對應,包括座位和抽象艙位;其次,油箱、水箱作為飛機液體容器,其屬性在飛機配載過程中有很大影響;最后,飛機本身的整機重量和重心也是其固有屬性的一部分.

2.2 相關參數

當前設置算法考慮了重量約束、重心約束、裝載順序約束、規格約束、貨物種類約束等.在業務建模中介紹了飛機運行配平力的概念,飛機配平力的產生會導致燃油消耗量增大,相同負載重量情況下,CG 與CGidea相對距離越大,耗油量越高,因此燃油節約約束轉換為最優化中心位置[13].

為了能更好地對約束進行表達,在當前模型下,參數標識方法如表1所示,可得相關公式.

表1 配載關鍵參數表

由上述條件函數可得目標為:

其中,式(1)–式(3)體現配載過程基本的重量約束,式(4)–式(7)用于保證配載重心約束,式(8)–式(12)用于滿足配載其他約束,用于進行性質判別,并通過式(13)計算分值系數輔助決策.

公式的使用方法將在第4 節系統實現中進行舉例說明,后續算法以以上公式為基礎,在面臨不同工作環境時,可以通過增減約束函數對算法決策分值進行適應性調整.

2.3 算法流程

部分傳統算法基于搜索算法,對于效率難以保證,并且由于其算法結構,難以進行效率優化,處理時間隨約束量、配載量上升而急劇增大.

本文算法基于遺傳算法,結合飛機配載建模設計,采用高度模塊化的方法進行分值計算,在遺傳算法基礎上調整回報策略,使用約束系數模塊和回報系數模塊共同完成配載方案分值計算工作,為策略模塊提供決策依據;并且由于該算法高度模塊化的特點,也可用于其他決策過程,大大提高算法使用靈活性,即使在不同工作環境下,也可通過適應性調整調度策略來進行協調.

遺傳算法使用優勝劣汰的思想,在一代代種群更替的過程中,選擇較優的表現型,并將基因向下一代遺傳,最終靠近最優值.其關鍵步驟為:1)編碼;2)初始化種群;3)評估種群個體適應度;4)選擇;5)交叉;6)變異,其中步驟3)–6)持續迭代,達到預定迭代數或表現型.在經前幾小節建模后,上述步驟已經比較清晰,以23 艙位貨艙一種布局為例,如圖2所示.

圖2 算法流程圖

配載問題實際上是裝載物品對裝載空間的占用過程,屬于典型空間資源調度排列問題,因此使用排列編碼,將所有裝載空間抽象為一個數組對象,數組位置為裝載物體,該數組對象則為一個基因個體.

由于沒有使用指導性的公式規范裝載位置,初始化種群時采用隨機放置的方式;需要注意的是,裝載物體數量可能少于裝載空間,為了不對空艙位進行特殊處理,因此虛構空物品補足數量,采用同樣方式編碼.

本文在個體適應度計算方面,針對飛機貨物裝載多約束、可變約束的需求,設計了動態計分的解決方案.由于不同班次的航班在載客、載貨方面都有不同,沒有一個確定的標準,因此采用信號量分值最大化的方式進行優化遺傳.將每一個約束模型的屬性單獨劃分得到一個約束組,每個劃分中維護自己的影響因子計算方法,通過影響因子乘積的方式對個體進行組合打分,如圖3所示.

圖3 約束組下方案適應度分值計算流程

該方案能夠引入選定約束的影響,并且有較好的可擴展性.需要注意的是,由于算法需要保證最終方案的可用性,因此在該過程中加入保障機制,打分過程中同時進行可用性監測,會保留一個分值最高的可用方案.

選擇和變異時,由于飛機配載不是嚴格的最優化問題,并不要求重心絕對小,而對計算效率要求更高,因此不需要過度擔心陷入局部最優解的問題,使用按比例最佳保留和均勻交叉變異的方法進行基因變換,保證快速收斂.

約束(limit)模塊用于處理禁止性質的配載規則,回報(reward)模塊用于處理鼓勵性質的配載規則,首先通過回報模塊獲取基礎分值,然后通過約束模塊增減系數.各模塊的整體調用流程如圖4所示.

圖4 調用流程圖

本文通過調整遺傳算法決策值計算法法對配載處理方法進行優化,通過預處理模塊對數據進行結構化,確定reward、limit和strategy 等流程數據出入接口,通過實現以上接口保證數據流完整性和正確性.Load作為調度器,根據傳入參數構造上述模塊并進行組裝調用,處理輸入模型獲取配載結果.

3 系統設計實現

前文對當前配載過程所面臨的問題進行了梳理,然后針對上述問題提出了相應的解決方案,為了證明上述算法的可用性,本文對該算法和系統進行了實現,本節對實現細節進行介紹.在第3.1 節、第3.2 節中介紹系統結構和開發框架選取,便于讀者了解實現的整體思路,第3.3 節介紹實現算法功能的各模塊,其中第3.3.2 節對公式的使用方法進行了詳細介紹.

3.1 總體架構

系統架構設計致力于解決系統完善設計問題部分,部分飛機配載系統長期存在的問題僅考慮業務問題[1],配載處理泛化能力差,在面對不同機型需要設計專屬配載算法,復用能力差;同時,算法研究常采用單一模型,難以協調生產條件下復雜的應用環境,產學不匹配,進一步加劇系統泛化能力差、可用性低的問題.

本優化技術關注后端架構設計,可分為交互層、配載邏輯層、實體模型層、配載組件層和數據層等,通過交互層為前端調用提供接口,如圖5所示,本節對配載系統架構進行討論.

圖5 總體架構圖

3.2 開發語言框架選擇

本后端配載優化方法采用Java 語言開發.希望實現一個泛化能力較好的飛機配載組件,Java 語言具有良好的跨平臺性,在所有具有JVM的平臺上都能良好運行,包括目前各種主要的操作系統,如Windows,MacOS和Linux;同時,Java 在多年的發展下,出現了適用于后端開發的規范和設計模式,并且由研究人員提供了強大的后端開發框架.因此認為Java 語言適合進行本系統開發.

使用Maven 進行版本管理,采用SpringBoot 框架完成系統架構搭建.

數據管理方面本系統采用MongoDB和MySQL共同進行數據存儲管理.MongoDB 作為NoSQL 型數據庫,有數據可讀性強、查詢速度快等優點,但是有數據存儲空間難以管理的問題,因此試用其存儲多查詢而少變更的飛機模型數據,保證模型結構化生成效率;對于多變、多增刪的配載貨物和人員信息使用MySQL數據庫進行存取,保證數據存儲空間能夠較好管理.

3.3 模塊設置

除交互層和數據持久化層外,本系統從下到上分為實體模型、配載組件和配載邏輯等模塊,本小節對其實現邏輯和內部接口進行詳細介紹.

3.3.1 實體模塊

實體模塊根據數據建模部分建立,本文認為配載過程中相關實體模型分別是飛機、艙位、座位、油箱、貨物以及乘客,其關系如圖6所示.

圖6中飛機、座位和艙位間有固定層級關系,每個型號的民航客機都包含一組油箱、一組貨物固定位置和一組座位,因此開發者不需要為每一個型號的飛機單獨進行配載實物建模,將幾項實體模型的各項屬性錄入系統,根據航行信息調用不同的飛機實體模型即可,可以對配載模型進行增刪而不是重新建模,來適應變更的機型要求;并且如果在實際應用中有新的組件需要加入,只需要對組件計算規則進行建模即可.

圖6 實體結構層次關系

3.3.2 配載組件模塊

配載組件模塊目前被劃分為3 個小模塊,分別是約束系數模塊、回報系數模塊和策略模塊,它們分別提供如表2所示的操作接口.

表2 模塊內部接口設計表

配載邏輯模塊通過對這3 個模塊的組合,調用其接口完成配載計算工作.

提出約束模塊和回報模塊的目的是通過各個約束公式得到用于遺傳算法或其他基于最大最小值進行決策的最優化方法的分值,實現過程中,根據公式實現多個裝載檢測邏輯類,形成列表進行循環打分.

以式(4)–式(7)為例,其它公式同理,這4 個公式是針對飛機重心位置的不等式,用于飛機裝載CG是否在保險約束范圍內的性質判別,形成一個CGChecker.在機器學習算法中,計算機根據選取更優的策略來進行迭代更新,而不是通過布爾值來進行取舍,因此在該類中需要對公式進行轉化.

由于約束形式多種多樣,數據代表的意義也不相同,難以直接對其進行歸一化處理,為了防止出現各約束在計算過程中涉及數值差距過大導致影響因子難以調整的問題,需要一個類對不同約束進行處理.

約束系數模塊提供check 接口,輸入配載映射數組,返回布爾值,用于表示當前配載映射關系是否滿足該約束規則.每一個約束系數對象只負責一個約束規則的檢查工作,由此可見,每一個禁止規則至少需要對應一個約束邏輯對象,因為不滿足禁止規則的配載方案是不能作為最終方案的,即使該方案經計算后能夠得到最高的分值,該判定過程與配載整體數據而不是當前策略模塊返回的數據有關,在進行計算時,需要聯合預處理過程中傳遞的數據進行綜合評判.

除性質檢查外,limit 對象中還維護一個大于1的正項系數和一個0 到1 之間的負向系數,該系數通過乘式的方式影響初始分值,在經約束模塊檢測后可行的方案取正項系數,不可行則取負向系數.根據不同約束在計算過程中檢測規則不同,會被劃分為單一狀態約束和組合狀態約束,在獲取系數時也有所不同,check 接口作為策略模塊的服務接口,傳遞的是約束整體滿足與否,但是在實際計算中存在單一約束的情況,需要對每子配載問題進行狀態劃分,以保證分值的區分度.在上述例子中,重心約束模塊通過式(4)計算出當前配載方案導致的橫向重心偏移值,然后使用式(7)進行重心性質判別,如果符合需求,則返回一個正向系數,否則返回一個負向系數.

使用時,通過計算不同配載方案重心給出分值,該分值影響遺傳算法過程染色體適應度,結合方式如圖3所示,以此影響算法迭代過程.

3.3.3 配載邏輯模塊

第3.3.2 節介紹的3 個模塊通過邏輯接口進行信息交互,只要系統設置了相應接口,即使有不同配載需求,只需要通過替換模塊即可完成組合,極大的提高了系統的可擴展性和靈活性.

配載邏輯模塊起到了調配小模塊的作用,該對象中包含了3 個模塊對象的工程類,通過傳入參數對子模塊進行拼裝,完成配載計算,其結構如圖7所示.

圖7 Load 模塊組成圖

4 測試

在第3 節中介紹了系統的實現過程,本節對上述實現進行驗證.

針對算法效果方面,由于本系統結構和算法應用目標與第2 節中介紹的解決方法有明顯區別,難以在統一條件下模擬,因此沒有采用相關工作進行對比,轉而使用最優解對比驗證算法效果.本次測試使用的對比方法為全排列算法,在一定時間內必然可以獲得當前條件下的最優配載方案,因此可以驗證當前算法效果.

算法效率方面,通過測試本系統配載時間來驗證能否實時計算.

4.1 測試數據設置

根據上文相關參數及實體模型設計部分介紹,本優化方法涉及數據主要包括民航客機機型參數和配載相關測試數據.

通過資料調研,發現美國波音公司生產的民機產品在我國民航客機領域有相對廣泛的應用,因此選取大型寬體飛機波音767 作為基礎機型生成測試模型數據,內置模型包含座位230 個、貨物裝載艙位23 個,采用雙精度浮點型數據表示坐標位置.

配載貨物以航空用統一裝載單元為基礎結構進行重量、規格、目的地等參數可用范圍內隨機數據生成模擬需要配載的貨物信息,例如Example1 模式下,可以指定組數隨機生成貨物,降低人為測試數據集設定帶來的特殊模式匹配問題.

為了測試方法性能,除以上述模型外,分別以8、11和14 艙位構造module2、module3和module4,按照飛機貨艙比例構建測試模型,進行運行時間測試.

4.2 測試結果分析

測試模型編號為使用的飛機建模編號,測試數據編號為使用一個測試數據類型隨機生成多組測試數據進行測試;時間屬性記錄為服務過程中配載算法運行時間,沒有對網絡傳輸延遲時間進行統計;每次配載完成,通過約束模塊進行配載狀態可用性檢測.本次測試通過算法性能對比、重心偏移對比、自身收斂情況測試和約束去除自對照來驗證算法可用性.

表3為性能對比,由于搜索空間隨艙位數變化指數增長,因此搜索算法在不同艙位數下配載方案計算表現差距極大,以搜索為基礎即使對其進行剪枝等優化,也難以從搜索根部直接剪枝,應對艙位數變化的泛化性差;當前方法基于遺傳算法實現,其時間復雜度隨艙位數線性增長,因此可以做到實時配載.

表3 性能對比

表4中使用構造模型將默認遺傳算法與搜索算法進行對比,表明在小量配載時,遺傳算法有很大概率找到當前約束參數下的最優解,可靠性較高.驗證了通過公式形成的約束模塊的可用性.

表4 方法CG 對照測試

表5中數據為收斂情況測試,根據性能對比測試可以得知,當前數量級搜索空間過大,因此不適用搜索算法,采用多次運行自對比的方法,使用2 類模型,5 組測試數據進行遺傳算法收斂測試,測試過程中每個測試用例進行20 次運行,由于篇幅關系,選取其中兩次作為關鍵數據.由該數據可得,算法收斂狀況穩定,坐標偏移極小,在厘米甚至毫米級,靠近理論最優值,總能收斂到打分策略最優值;配載時間達到秒級,驗證了strategy 模塊可用性.

表5 收斂狀態關鍵數據表

表6表示將貨物規格約束從約束列表中去除后重心偏移變化,每組測試用例重心偏移均較去除后更小,該測試結果表明約束系數變化能夠有效引導算法方法像預定目標理論最優值靠近,證明了模塊化拆分約束分值的可用性.

表6 format 約束去除對比

4.3 測試小結

當前測試方案通過多組隨機配載數據下進行測試匯總,首先能夠證明優化方案的可用性和功能可靠性.該測試各測試數據組都能保證秒級配載計算速度;通過上文介紹的配載約束系數模塊檢測,方法給出的各配載方案均能夠滿足飛機正常航行的各項約束目標,且重心位置、裝卸信號量通過回報模塊在效率協調狀態下逼近了理論最優值.

其次,該測試還能證明該優化方法的泛化性和可擴展性.

本測試過程中飛機模型構建流程為:利用本框架提供的模式化構建方法選取適用類;根據機型圖紙注入數據值獲得對象;使用數據層服務進行飛機模型持久化.測試中貨物數據通過模式化構建模塊進行數據注入生成,同樣是在進行持久化的狀態下通過查詢完成后續配載流程,因此實際使用中可以通過修改數據庫查詢配置或直接進行數據轉儲的方法導入配載數據,以提供服務的模式進行業務處理.因此該優化方法受機型變動影響小、受原始系統狀態影響小;此外,當業務中有需求變化時,可以通過調整約束組合、重新實現約束計分方案等方法進行針對性優化,有較好的泛化性.

同時本優化方法為后續開發優化提供了接口,測試用的兩種方法均在本方法內部框架下實現,使用策略設計模式采用同樣的調用接口,通過傳遞方法名稱即可控制方法,有較強的的可擴展性.

5 總結與展望

配載算法的主要指標為配載效果和效率,本文描述的算法方案基于遺傳算法實現,通過構建約束系數表影響決策值狀態,滿足飛機配載約束.

本文旨在從多方面優化飛機自動配載技術,推動產學結合,希望通過優化算法和架構設計保證算法在復雜多變的生產環境中得到更好的應用.基于上述算法實現的系統通過高度結構化的約束模塊設計,通過確定模塊接口、提供模板類等方式,實現可拆裝的策略、約束和回報方式,在保證算法可用性的情況下,提高系統的可擴展性和靈活性.

本文認為在該架構下進行算法針對業務環境的特性優化還有一定空間.基于該算法設計和系統架構,可以通過實現接口應用其他配載策略、改換約束組合等方式對方法結構進行業務針對性調整;同時,由于本算法采用約束組合打分的方式,還可以調整系統策略算法參數、根據目標調整回報函數和根據配載實際需求調整約束正負系數等方法進行優化;此外,還可以通過對約束模塊進行劃分來優化計算過程,如劃分運行時優化約束計算、運行前基礎約束檢測和運行后可用性約束檢測等.

后續會從以上方面進行自動配平優化,擴大應用范圍和業務覆蓋面,進一步減輕人工工作壓力.