民航客機(jī)貨艙自動配平優(yōu)化技術(shù)①

姜昱君,韓 銳

(北京理工大學(xué) 計算機(jī)學(xué)院,北京 100081)

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

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

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

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

1 問題分析

1.1 算法問題分析

算法設(shè)計是配載系統(tǒng)開發(fā)的核心組成部分,該問題從性能方面又可分為執(zhí)行效果和執(zhí)行效率兩部分.

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

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

1.2 系統(tǒng)問題分析

從架構(gòu)方面分析,當(dāng)前配載系統(tǒng)有泛化能力差、模塊化差的問題.

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

模塊化問題指的是部分系統(tǒng)設(shè)計將飛機(jī)配載業(yè)務(wù)過程與算法過程混雜,使得代碼可讀性和擴(kuò)充性差,在航空公司出現(xiàn)新機(jī)型、新需求時,難以調(diào)整,導(dǎo)致算法需要全盤重構(gòu),增加了使用成本.

2 算法設(shè)計

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

2.1 業(yè)務(wù)建模

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

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

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

圖1 受力約束建模

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

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

2.2 相關(guān)參數(shù)

當(dāng)前設(shè)置算法考慮了重量約束、重心約束、裝載順序約束、規(guī)格約束、貨物種類約束等.在業(yè)務(wù)建模中介紹了飛機(jī)運行配平力的概念,飛機(jī)配平力的產(chǎn)生會導(dǎo)致燃油消耗量增大,相同負(fù)載重量情況下,CG 與CGidea相對距離越大,耗油量越高,因此燃油節(jié)約約束轉(zhuǎn)換為最優(yōu)化中心位置[13].

為了能更好地對約束進(jìn)行表達(dá),在當(dāng)前模型下,參數(shù)標(biāo)識方法如表1所示,可得相關(guān)公式.

表1 配載關(guān)鍵參數(shù)表

由上述條件函數(shù)可得目標(biāo)為:

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

公式的使用方法將在第4 節(jié)系統(tǒng)實現(xiàn)中進(jìn)行舉例說明,后續(xù)算法以以上公式為基礎(chǔ),在面臨不同工作環(huán)境時,可以通過增減約束函數(shù)對算法決策分值進(jìn)行適應(yīng)性調(diào)整.

2.3 算法流程

部分傳統(tǒng)算法基于搜索算法,對于效率難以保證,并且由于其算法結(jié)構(gòu),難以進(jìn)行效率優(yōu)化,處理時間隨約束量、配載量上升而急劇增大.

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

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

圖2 算法流程圖

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

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

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

圖3 約束組下方案適應(yīng)度分值計算流程

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

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

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

圖4 調(diào)用流程圖

本文通過調(diào)整遺傳算法決策值計算法法對配載處理方法進(jìn)行優(yōu)化,通過預(yù)處理模塊對數(shù)據(jù)進(jìn)行結(jié)構(gòu)化,確定reward、limit和strategy 等流程數(shù)據(jù)出入接口,通過實現(xiàn)以上接口保證數(shù)據(jù)流完整性和正確性.Load作為調(diào)度器,根據(jù)傳入?yún)?shù)構(gòu)造上述模塊并進(jìn)行組裝調(diào)用,處理輸入模型獲取配載結(jié)果.

3 系統(tǒng)設(shè)計實現(xiàn)

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

3.1 總體架構(gòu)

系統(tǒng)架構(gòu)設(shè)計致力于解決系統(tǒng)完善設(shè)計問題部分,部分飛機(jī)配載系統(tǒng)長期存在的問題僅考慮業(yè)務(wù)問題[1],配載處理泛化能力差,在面對不同機(jī)型需要設(shè)計專屬配載算法,復(fù)用能力差;同時,算法研究常采用單一模型,難以協(xié)調(diào)生產(chǎn)條件下復(fù)雜的應(yīng)用環(huán)境,產(chǎn)學(xué)不匹配,進(jìn)一步加劇系統(tǒng)泛化能力差、可用性低的問題.

本優(yōu)化技術(shù)關(guān)注后端架構(gòu)設(shè)計,可分為交互層、配載邏輯層、實體模型層、配載組件層和數(shù)據(jù)層等,通過交互層為前端調(diào)用提供接口,如圖5所示,本節(jié)對配載系統(tǒng)架構(gòu)進(jìn)行討論.

圖5 總體架構(gòu)圖

3.2 開發(fā)語言框架選擇

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

使用Maven 進(jìn)行版本管理,采用SpringBoot 框架完成系統(tǒng)架構(gòu)搭建.

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

3.3 模塊設(shè)置

除交互層和數(shù)據(jù)持久化層外,本系統(tǒng)從下到上分為實體模型、配載組件和配載邏輯等模塊,本小節(jié)對其實現(xiàn)邏輯和內(nèi)部接口進(jìn)行詳細(xì)介紹.

3.3.1 實體模塊

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

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

圖6 實體結(jié)構(gòu)層次關(guān)系

3.3.2 配載組件模塊

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

表2 模塊內(nèi)部接口設(shè)計表

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

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

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

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

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

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

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

3.3.3 配載邏輯模塊

第3.3.2 節(jié)介紹的3 個模塊通過邏輯接口進(jìn)行信息交互,只要系統(tǒng)設(shè)置了相應(yīng)接口,即使有不同配載需求,只需要通過替換模塊即可完成組合,極大的提高了系統(tǒng)的可擴(kuò)展性和靈活性.

配載邏輯模塊起到了調(diào)配小模塊的作用,該對象中包含了3 個模塊對象的工程類,通過傳入?yún)?shù)對子模塊進(jìn)行拼裝,完成配載計算,其結(jié)構(gòu)如圖7所示.

圖7 Load 模塊組成圖

4 測試

在第3 節(jié)中介紹了系統(tǒng)的實現(xiàn)過程,本節(jié)對上述實現(xiàn)進(jìn)行驗證.

針對算法效果方面,由于本系統(tǒng)結(jié)構(gòu)和算法應(yīng)用目標(biāo)與第2 節(jié)中介紹的解決方法有明顯區(qū)別,難以在統(tǒng)一條件下模擬,因此沒有采用相關(guān)工作進(jìn)行對比,轉(zhuǎn)而使用最優(yōu)解對比驗證算法效果.本次測試使用的對比方法為全排列算法,在一定時間內(nèi)必然可以獲得當(dāng)前條件下的最優(yōu)配載方案,因此可以驗證當(dāng)前算法效果.

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

4.1 測試數(shù)據(jù)設(shè)置

根據(jù)上文相關(guān)參數(shù)及實體模型設(shè)計部分介紹,本優(yōu)化方法涉及數(shù)據(jù)主要包括民航客機(jī)機(jī)型參數(shù)和配載相關(guān)測試數(shù)據(jù).

通過資料調(diào)研,發(fā)現(xiàn)美國波音公司生產(chǎn)的民機(jī)產(chǎn)品在我國民航客機(jī)領(lǐng)域有相對廣泛的應(yīng)用,因此選取大型寬體飛機(jī)波音767 作為基礎(chǔ)機(jī)型生成測試模型數(shù)據(jù),內(nèi)置模型包含座位230 個、貨物裝載艙位23 個,采用雙精度浮點型數(shù)據(jù)表示坐標(biāo)位置.

配載貨物以航空用統(tǒng)一裝載單元為基礎(chǔ)結(jié)構(gòu)進(jìn)行重量、規(guī)格、目的地等參數(shù)可用范圍內(nèi)隨機(jī)數(shù)據(jù)生成模擬需要配載的貨物信息,例如Example1 模式下,可以指定組數(shù)隨機(jī)生成貨物,降低人為測試數(shù)據(jù)集設(shè)定帶來的特殊模式匹配問題.

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

4.2 測試結(jié)果分析

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

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

表3 性能對比

表4中使用構(gòu)造模型將默認(rèn)遺傳算法與搜索算法進(jìn)行對比,表明在小量配載時,遺傳算法有很大概率找到當(dāng)前約束參數(shù)下的最優(yōu)解,可靠性較高.驗證了通過公式形成的約束模塊的可用性.

表4 方法CG 對照測試

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

表5 收斂狀態(tài)關(guān)鍵數(shù)據(jù)表

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

表6 format 約束去除對比

4.3 測試小結(jié)

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

其次,該測試還能證明該優(yōu)化方法的泛化性和可擴(kuò)展性.

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

同時本優(yōu)化方法為后續(xù)開發(fā)優(yōu)化提供了接口,測試用的兩種方法均在本方法內(nèi)部框架下實現(xiàn),使用策略設(shè)計模式采用同樣的調(diào)用接口,通過傳遞方法名稱即可控制方法,有較強(qiáng)的的可擴(kuò)展性.

5 總結(jié)與展望

配載算法的主要指標(biāo)為配載效果和效率,本文描述的算法方案基于遺傳算法實現(xiàn),通過構(gòu)建約束系數(shù)表影響決策值狀態(tài),滿足飛機(jī)配載約束.

本文旨在從多方面優(yōu)化飛機(jī)自動配載技術(shù),推動產(chǎn)學(xué)結(jié)合,希望通過優(yōu)化算法和架構(gòu)設(shè)計保證算法在復(fù)雜多變的生產(chǎn)環(huán)境中得到更好的應(yīng)用.基于上述算法實現(xiàn)的系統(tǒng)通過高度結(jié)構(gòu)化的約束模塊設(shè)計,通過確定模塊接口、提供模板類等方式,實現(xiàn)可拆裝的策略、約束和回報方式,在保證算法可用性的情況下,提高系統(tǒng)的可擴(kuò)展性和靈活性.

本文認(rèn)為在該架構(gòu)下進(jìn)行算法針對業(yè)務(wù)環(huán)境的特性優(yōu)化還有一定空間.基于該算法設(shè)計和系統(tǒng)架構(gòu),可以通過實現(xiàn)接口應(yīng)用其他配載策略、改換約束組合等方式對方法結(jié)構(gòu)進(jìn)行業(yè)務(wù)針對性調(diào)整;同時,由于本算法采用約束組合打分的方式,還可以調(diào)整系統(tǒng)策略算法參數(shù)、根據(jù)目標(biāo)調(diào)整回報函數(shù)和根據(jù)配載實際需求調(diào)整約束正負(fù)系數(shù)等方法進(jìn)行優(yōu)化;此外,還可以通過對約束模塊進(jìn)行劃分來優(yōu)化計算過程,如劃分運行時優(yōu)化約束計算、運行前基礎(chǔ)約束檢測和運行后可用性約束檢測等.

后續(xù)會從以上方面進(jìn)行自動配平優(yōu)化,擴(kuò)大應(yīng)用范圍和業(yè)務(wù)覆蓋面,進(jìn)一步減輕人工工作壓力.