姜昱君,韓 銳

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

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

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

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

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

1 問(wèn)題分析

1.1 算法問(wèn)題分析

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

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

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

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

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

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

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

2 算法設(shè)計(jì)

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

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

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

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

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

圖1 受力約束建模

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

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

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

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

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

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

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

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

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

2.3 算法流程

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

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

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

圖2 算法流程圖

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

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

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

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

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

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

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

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

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

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

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

3.1 總體架構(gòu)

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

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

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

3.2 開(kāi)發(fā)語(yǔ)言框架選擇

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

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

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

3.3 模塊設(shè)置

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

3.3.1 實(shí)體模塊

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

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

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

3.3.2 配載組件模塊

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

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

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

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

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

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

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

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

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

3.3.3 配載邏輯模塊

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

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

圖7 Load 模塊組成圖

4 測(cè)試

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

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

算法效率方面,通過(guò)測(cè)試本系統(tǒng)配載時(shí)間來(lái)驗(yàn)證能否實(shí)時(shí)計(jì)算.

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

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

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

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

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

4.2 測(cè)試結(jié)果分析

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

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

表3 性能對(duì)比

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

表4 方法CG 對(duì)照測(cè)試

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

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

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

表6 format 約束去除對(duì)比

4.3 測(cè)試小結(jié)

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

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

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

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

5 總結(jié)與展望

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

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

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

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