邢志偉, 王思博, 李 彪, 廉 冠
(1. 中國民航大學(xué) 電子信息與自動化學(xué)院, 天津 300300; 2. 中國民航大學(xué) 航空工程學(xué)院, 天津 300300; 3. 桂林電子科技大學(xué) 建筑與交通工程學(xué)院, 廣西 桂林 541004)
航班地面保障過程是指飛機經(jīng)引導(dǎo)進入機位后開展的一系列針對飛行器、旅客和貨郵的地面處理過程,是提高機場運行效率的核心環(huán)節(jié)之一.在航班推出前合理配置資源利用情況,不但有助于縮減運行時間和運營成本,而且能有效改善延誤、資源閑置浪費等瓶頸問題.目前,機場航班地面保障過程的運行是由多參與方合作開展.然而,整個過程協(xié)同能力差、資源配置不均衡等現(xiàn)象時有發(fā)生.因此,開展以資源均衡優(yōu)化為目標(biāo)的保障過程建模、優(yōu)化方案制定、均衡效果評估將有望緩解上述困境.針對航班地面保障過程建模及優(yōu)化問題,國內(nèi)外研究學(xué)者分別從保障過程核心環(huán)節(jié)[1]、環(huán)節(jié)協(xié)同[2]和保障過程整體[3]出發(fā)建立優(yōu)化模型并驗證其合理性.但這些模型的建立僅側(cè)重于優(yōu)化運行時間,并未考慮過程中資源配置的均衡性.按優(yōu)化對象可將保障過程優(yōu)化問題分為車輛調(diào)度和人員配置優(yōu)化兩類.車輛調(diào)度方面,M. FINK等[4]基于時空網(wǎng)絡(luò)構(gòu)建多保障車輛運行模型,實現(xiàn)對車輛運行路徑的合理優(yōu)化,用以縮短保障過程運行時間.GUO W. A.等[5]針對機場行李運輸車為飛機作業(yè)保障的場景,設(shè)計出一種基于遺傳算法的保障車輛運行優(yōu)化方法,提高了算法的求解能力.人員配置方面,C. MALANDRI等[6]由機場特殊場景出發(fā),分析因人力資源突變導(dǎo)致過站時間增加問題,構(gòu)建相應(yīng)模型求出閾值,作為優(yōu)化機場運行模態(tài)的依據(jù).S.HIEMSTRA-VAN MASTRIGT等[7]采取不同優(yōu)化方案減緩影響因素對旅客登機的干擾,以確保降低航班延誤率.S.PADRN等[8]以西班牙機場實際數(shù)據(jù)為例,建立雙目標(biāo)優(yōu)化模型求出對應(yīng)的Pareto解,為過站航班提供合理優(yōu)化方案.但以上研究僅注重解決某一環(huán)節(jié)的資源優(yōu)化,并未對保障過程整體均衡形成優(yōu)化方案.上述優(yōu)化方法仍無法解決面向多模態(tài)下的保障資源均衡優(yōu)化問題.
文中擬構(gòu)建面向多目標(biāo)的保障過程資源均衡優(yōu)化模型,基于實際數(shù)據(jù)和運行場景展開求解并得出優(yōu)化方案.通過均衡評估指標(biāo)對模型的可行性進行分析驗證,為機場航班地面保障過程的精細化管理提供客觀依據(jù).
結(jié)合過站航班實際運行情況和相關(guān)標(biāo)準(zhǔn)可知,航班地面保障各環(huán)節(jié)不但在時間上具有嚴格的時間窗和優(yōu)先順序約束,還在設(shè)備配置上具有多樣性的特點.由于各環(huán)節(jié)資源需求量存在差異性,進而形成了保障環(huán)節(jié)的多種運行模態(tài).在運行模態(tài)和資源種類的限制下,導(dǎo)致保障過程資源均衡優(yōu)化的實現(xiàn)需考慮多個優(yōu)化目標(biāo).而保障過程的完成不僅需要單一環(huán)節(jié)的優(yōu)化,而且需要多個環(huán)節(jié)協(xié)同運行.因此,還需考慮由多個環(huán)節(jié)構(gòu)成的工作流的運行狀態(tài).如圖1所示,航班地面保障過程可分為飛機、旅客和行李3個工作流,并且每個工作流中存在串行和并行2種形式.
圖1 過站航班地面保障作業(yè)流程圖
總之,航班地面保障過程均衡優(yōu)化問題屬于一類子環(huán)節(jié)多模態(tài)共存、工作流形式復(fù)雜、保障資源種類多樣的多目標(biāo)協(xié)同優(yōu)化問題.
根據(jù)保障環(huán)節(jié)運行特性和機場實際運行數(shù)據(jù),結(jié)合多因素分析法對航班地面保障資源均衡影響要素進行初步分析,并構(gòu)建影響要素拓撲圖,如圖2所示.
圖2 過站航班地面保障作業(yè)影響要素圖
在實際運行過程中,保障資源約束涉及的設(shè)備、人員和物質(zhì)具有多樣性.針對以上資源種類進行合理分類并定義資源類型.
定義1在保障過程推進中,不會因為環(huán)節(jié)的實現(xiàn)而造成消耗、但在規(guī)定時間段內(nèi)有約束的資源稱為可循環(huán)資源.例如,人力、設(shè)備等資源.
定義2隨著保障過程推進,某一環(huán)節(jié)消耗后會造成其他航班需求量無法滿足的資源稱為不可循環(huán)資源.例如,物資、不可再生資源等.
在實際運行過程中,根據(jù)前序環(huán)節(jié)的實際運行狀態(tài)進行實時調(diào)整,以實現(xiàn)保障過程的按時完成.故將運行模態(tài)分為加急模態(tài)、常規(guī)模態(tài)和放緩模態(tài)3類.運行模態(tài)效用是通過對人員和設(shè)備合理配置來實現(xiàn).
除了以上2種關(guān)鍵因素外,影響保障過程資源均衡性的因素還包括機型影響、保障設(shè)備作業(yè)方式、航班密度等.
其他在保障過程資源均衡過程中所涉及的因素可以由空管、機場、航空公司等部門協(xié)同解決,因此文中對這些因素忽略不計.
結(jié)合保障過程中的實際需求,設(shè)定航班地面保障過程資源均衡優(yōu)化中共含有I個保障環(huán)節(jié),各環(huán)節(jié)需要消耗R種資源,有r1種可循環(huán)資源,僅考慮可循環(huán)資源;各環(huán)節(jié)運行模態(tài)為pi(i=1,2,…,I),而pi=1、2、3分別表示加急、常規(guī)、放緩模態(tài);每種運行模態(tài)pi存在對資源的不同需求,包括環(huán)節(jié)開始時間t和可循環(huán)資源YR.環(huán)節(jié)Ti運行模態(tài)可表示為(Tip,YRip1,…,YRipr1).過站航班地面保障資源均衡優(yōu)化問題可描述如下:在滿足保障過程標(biāo)準(zhǔn)完成時間和資源總量的前提下,如何合理安排每個環(huán)節(jié)的實際開始時間和運行模態(tài),使保障過程內(nèi)各類資源的時間消耗量和資源利用量均衡度最大,即保障資源綜合消耗量方差最小.
目標(biāo)如下:① 最小化保障環(huán)節(jié)運行有效偏差,即有效確定保障環(huán)節(jié)是否處于穩(wěn)定狀態(tài),將為保障資源均衡優(yōu)化提供可靠的前提;② 最小化保障環(huán)節(jié)作業(yè)時間,即保障過程結(jié)束的總時間盡可能提前,為機場運行中出現(xiàn)航班延誤現(xiàn)象節(jié)省出更多處理時間,確保其他航班計劃可按時執(zhí)行;③ 最小化保障資源綜合消耗量,即通過合理調(diào)度資源(時間資源和物質(zhì)資源),有效節(jié)約機場實際資源消耗量,緩解機場運行壓力.
文中研究航班地面保障過程資源均衡優(yōu)化調(diào)度問題,需要滿足如下假設(shè):① 保障環(huán)節(jié)一旦開始不產(chǎn)生中斷,運行時間按min來計量;② 保障過程中,各環(huán)節(jié)存在多種運行模態(tài),不同模態(tài)下的資源利用率、運行時間消耗量不同;③ 在航班降落前,已完成對其跑道和機位的預(yù)分配,并不會對其做出臨時調(diào)整;④ 從單個保障環(huán)節(jié)看,在其持續(xù)時間內(nèi),各個時段資源使用量均衡分布.
2.3.1符號變量說明
決策變量包括:Ci=1、0分別表示i需要、不需要特種車輛;pi′=1、0分別表示i取加急、其他模態(tài);zr取值如下:
2.3.2優(yōu)化目標(biāo)
結(jié)合有向圖理論與保障過程實際運行標(biāo)準(zhǔn),將傳統(tǒng)有向圖加以改造,得到保障作業(yè)過程有向圖,如圖3所示.
圖3 過站航班地面保障作業(yè)過程有向圖
設(shè)定上輪擋為基準(zhǔn)環(huán)節(jié),建立保障過程的均衡優(yōu)化模型,此時基準(zhǔn)環(huán)節(jié)的特點為實際開始時間與標(biāo)準(zhǔn)開始時間均為0,資源綜合消耗量為實際和標(biāo)準(zhǔn)值,各環(huán)節(jié)與基準(zhǔn)環(huán)節(jié)的時間間隔可表示為相應(yīng)的時刻.
根據(jù)上述分析,資源均衡優(yōu)化模型的優(yōu)化目標(biāo)如下:最小化保障環(huán)節(jié)運行有效偏差為
(1)
最小化保障環(huán)節(jié)作業(yè)時間為
minf2=min{timax},
(2)
最小化保障資源綜合消耗量為
(3)
2.3.3約束條件
根據(jù)保障過程運行特點可知,針對單個環(huán)節(jié)需滿足時間窗和資源消耗量的約束;同時還需考慮由多個環(huán)節(jié)組成的工作流,即環(huán)節(jié)間優(yōu)先順序和運行模態(tài)的限制.綜上,資源均衡優(yōu)化模型的約束條件如下:
|ti′-ti| (4) |ta-tb′|>0, (5) |tb-ta′|>0, (6) (7) (8) (9) (10) (11) 其中:式(4)表示某一環(huán)節(jié)實際開始時間不得超過標(biāo)準(zhǔn)時間的一個定值,若不滿足視為不均衡,其中N為一個足夠大的常量;式(5)、(6)表示保障環(huán)節(jié)a和b間服務(wù)先后順序的約束;式(7)表示保障過程的實際時間不得超過標(biāo)準(zhǔn)時間的一個范圍,其中N′為一個足夠大的常量,且滿足N′≠20N;式(8)表示每一個環(huán)節(jié)必須分配相應(yīng)的資源完成對其操作;式(9)、(10)表示某一環(huán)節(jié)必須選取一種運行模態(tài)操作中途不許發(fā)生改變,若超過半數(shù)環(huán)節(jié)采用加急模態(tài)視為該過程不具有均衡優(yōu)化意義;式(11)表示同一保障資源不能同時分配給兩個保障環(huán)節(jié). 根據(jù)優(yōu)化目標(biāo)要求,資源均衡優(yōu)化模型需同時實現(xiàn)3個目標(biāo)函數(shù)功能.為了使模型更好與后續(xù)算法結(jié)合,需采用LP-量綱法對目標(biāo)函數(shù)2和3進行量綱一處理. (12) 式中:M2和M3分別為兩個目標(biāo)函數(shù)值;K為權(quán)重系數(shù),由決策者給出.2個目標(biāo)函數(shù)分別為作業(yè)時間最小化f2和資源綜合消耗量最小化f3,所以將式(2)、(3)代入(12),目標(biāo)函數(shù)可轉(zhuǎn)化為 (13) 聯(lián)立式(1)、(4)-(11)、(13),可得出航班地面保障過程均衡優(yōu)化模型. NSGA-Ⅱ算法即帶有精英保留策略的非劣解排序遺傳算法,是對NSGA算法的優(yōu)化,具有魯棒性好、計算效率高等優(yōu)點[9].因此,文中采用一種改進混沌與差分進化的非劣解排序遺傳算法.該算法在NSGA-Ⅱ算法的基礎(chǔ)上,融合了混沌搜索技術(shù)和差分進化思想.其中,混沌迭代公式為 zi+1=μzi(1-zi),i=1,2,…,I,μ∈(0,4, (14) 式中:zi為保障環(huán)節(jié)i的混沌變量;μ為混沌系數(shù)[10].混沌搜索技術(shù)增強了初始種群在最優(yōu)解周圍分布的均勻性,提高算法的求解效率和質(zhì)量. 由于傳統(tǒng)算法對變異算子在總時間范圍內(nèi)只能計算1次,故引入試探向量.根據(jù)差分進化的思想改進基礎(chǔ)向量可有: Yi,d=Xi1,d-1+U(Xi2,d-1-Xi3,d-1), (15) 式中:Y為試探向量;X為基礎(chǔ)向量;U為比例系數(shù),U∈[0,1];d為進化代數(shù).改進后加快了算法的收斂速度[11-12].結(jié)合航班地面保障過程的環(huán)節(jié)運行有效偏差、作業(yè)時間和資源綜合消耗量等計算模型,保障過程均衡優(yōu)化模型的算法流程如圖4所示. 圖4 算法流程圖 依據(jù)改進混沌與差分進化的NSGA-Ⅱ算法所求出的Pareto最優(yōu)解不被Pareto前沿面之外的解(以及Pareto前沿曲線以內(nèi)的其他解)所支配的性質(zhì),Pareto最優(yōu)解只能優(yōu)化Pareto前沿面之外的解.Pareto最優(yōu)解可以為工程項目提供最優(yōu)施工方案,最大限度協(xié)調(diào)各函數(shù)之間的矛盾,實現(xiàn)各目標(biāo)函數(shù)的協(xié)調(diào)優(yōu)化.所以,改進混沌與差分進化的NSGA-Ⅱ算法在求解保障過程均衡優(yōu)化模型上具有一定可行性. 試驗選用國內(nèi)中部某樞紐機場實際運行保障數(shù)據(jù),具體樣例如表1-2所示. 表1 過站航班基本信息實際錄入 表2 過站航班保障過程核心環(huán)節(jié)運行數(shù)據(jù) 預(yù)處理過程如下: 1) 篩選出機型相同、降落時間相近和機位屬性一致的航班,以降低旅客人數(shù)、航班密度和車輛路徑不同對保障過程帶來的間接影響. 2) 考慮到一些保障環(huán)節(jié)數(shù)據(jù)偏差較大,采用數(shù)據(jù)擬合的方式來確定各環(huán)節(jié)服從何種分布. 3)剔除因區(qū)域管制、天氣條件等因素造成延誤的保障運行記錄,保留因保障運行產(chǎn)生延誤的運行記錄. 5) 以保障環(huán)節(jié)i0為基準(zhǔn)環(huán)節(jié),對各環(huán)節(jié)的開始時間和標(biāo)準(zhǔn)時間進行參數(shù)優(yōu)化,以實現(xiàn)時間點對時間間隔的代替. 首先進行模型設(shè)置.為達到保障過程資源配置的均衡性和過站時間同時優(yōu)化的目的,沿用上文簡化后的均衡優(yōu)化模型,在求解時為更具有實際意義形成分層優(yōu)化雙模型:模型1單為目標(biāo)優(yōu)化問題,最小化保障環(huán)節(jié)運行有效偏差,由式(1)、(4)-(7)構(gòu)成;模型2為雙目標(biāo)協(xié)同優(yōu)化問題,同時最小化航班保障資源綜合消耗量和保障環(huán)節(jié)作業(yè)時間,由進行量綱一處理后的式(4)-(11)、(13)構(gòu)成. 其次進行算法參數(shù)設(shè)置.為了有效保證算法性能,先要對算法所用到的所有參數(shù)進行校驗和設(shè)定.改進混沌與差分進化的NSGA-Ⅱ算法有5個運行參數(shù):每級存放的種群規(guī)模popsize∈{120,130,140,150};進化代數(shù)D∈{80,90,100,110};交叉常數(shù)Pc∈{0.7,0.8,0.9,1.0};混沌系數(shù)μ∈{1,2,3,4};比例系數(shù)U∈{0.7,0.8,0.9,1.0}.利用minitab進行田口試驗,計算了16組參數(shù)組合,得出最佳參數(shù)組合為popsize=140,D=100,Pc=0.9,μ=4,U=0.8. 1) 基準(zhǔn)環(huán)節(jié)設(shè)定:首先將上輪擋作為基準(zhǔn)環(huán)節(jié),其標(biāo)準(zhǔn)開始時間和實際開始時間記為0,資源消耗以實際投入為基準(zhǔn). 2) 環(huán)節(jié)狀態(tài)預(yù)判:結(jié)合目標(biāo)函數(shù)1,分別以各環(huán)節(jié)的標(biāo)準(zhǔn)時間和實際時間作為輸入進行對比,確定各環(huán)節(jié)實際運行模態(tài),為后續(xù)環(huán)節(jié)提供新的運行模態(tài). 3) 均衡效果檢驗:結(jié)合所得結(jié)果對保障過程運行總時間和資源消耗總量是否超出標(biāo)準(zhǔn)限制進行檢驗. 4) 均衡效果評估:通過均衡率BP、時間損失系數(shù)ε和資源平滑系數(shù)SI對均衡優(yōu)化模型的優(yōu)化效果進行評估. 為了驗證均衡優(yōu)化模型對航班地面保障過程的優(yōu)化效果,以同一航班在5月的保障過程服務(wù)記錄為例,首先預(yù)判保障過程中各環(huán)節(jié)的均衡狀態(tài),以便于為后續(xù)環(huán)節(jié)配置合適的運行模態(tài).圖5為保障過程中核心環(huán)節(jié)旅客下機的環(huán)節(jié)運行有效偏差優(yōu)化過程適應(yīng)度曲線. 圖5 下客環(huán)節(jié)運行有效偏差優(yōu)化過程 由圖5可見,環(huán)節(jié)運行有效偏差在迭代20次左右就達到了最優(yōu)效果,收斂速度較快.該環(huán)節(jié)運行有效偏差的最優(yōu)解為31. 確定環(huán)節(jié)所處均衡狀態(tài)后,為緊后環(huán)節(jié)匹配合適的運行模態(tài)以達到優(yōu)化目標(biāo).在匹配運行模態(tài)時,還需兼顧總時間和各環(huán)節(jié)資源總量的限制.得到保障過程和資源消耗量的雙目標(biāo)最優(yōu)解,如圖6所示. 圖6 總時間-資源消耗量均衡多目標(biāo)優(yōu)化解集 由圖6可見,保障環(huán)節(jié)作業(yè)時間優(yōu)化在64.073 min,資源消耗量集中在34.86. 為進一步驗證算法的求解速度,將目標(biāo)函數(shù)分層優(yōu)化,得到最終的優(yōu)化解集和各函數(shù)與求解時間關(guān)系圖,證明模型的可行性與算法求解速度,關(guān)系如圖7、8所示. 圖7 過站航班地面保障均衡模型最優(yōu)解集 從圖8可見,隨著種群規(guī)模的逐漸增加,各目標(biāo)函數(shù)遞減,優(yōu)化效果明顯.當(dāng)種群規(guī)模達到70以后,目標(biāo)函數(shù)2逐漸變小,算法優(yōu)化能力逐漸趨于穩(wěn)定.同時種群越大,算法求解的時間越快.當(dāng)總時間達到64 min以后,種群規(guī)模增加,資源消耗量逐漸縮減,說明算法開始優(yōu)化目標(biāo)函數(shù)3,在目標(biāo)函數(shù)2和3確定的情況下,可能存在一種方案.最后將過程的總時間優(yōu)化為64 min,過程資源綜合消耗量限制在34.8,此時過程優(yōu)化效果最佳. 圖8 不同種群規(guī)模下模型最優(yōu)解與求解時間 為了進一步驗證文中所用資源均衡優(yōu)化模型的有效性,將所得結(jié)果分別轉(zhuǎn)化為甘特圖和資源均衡優(yōu)化方案圖2種形式.分析保障過程中各環(huán)節(jié)在時間上優(yōu)化效果和資源上消耗情況,并對比優(yōu)化前后方案,得出各環(huán)節(jié)實際具體優(yōu)化效果,如圖9所示. 圖9 不同調(diào)度方案下環(huán)節(jié)運行時間甘特圖 由圖9可見,在調(diào)整緊后環(huán)節(jié)的運行模式后,各環(huán)節(jié)時間提前量與環(huán)節(jié)優(yōu)化節(jié)省時間具有明顯提升.以環(huán)節(jié)12為例,優(yōu)化前其開始時間為20 min,作業(yè)時間為47 min;優(yōu)化后其開始時間為15 min,作業(yè)時間為42 min.開始時間提前了5 min,過程運行總時間縮短了10.6%,充分驗證模型在過站時間上的有效性. 優(yōu)化前后的各環(huán)節(jié)資源消耗情況如圖10所示,著色區(qū)域為資源閑置總量. 圖10 均衡優(yōu)化前后資源消耗對比圖 由圖10可見:優(yōu)化前,同一時段最大資源消耗量可達18,過程資源閑置總量為33;優(yōu)化后,同一時段最大資源消耗量可達17,過程資源閑置總量為23.最大資源消耗量降低5.6%,資源閑置總量節(jié)約了30.3%. 利用文中模型優(yōu)化國內(nèi)某機場中不同機型的航班地面保障過程.針對機型不同導(dǎo)致各保障環(huán)節(jié)的作業(yè)時間和標(biāo)準(zhǔn)完成時間發(fā)生改變這一現(xiàn)象,首先將機型種類進行劃分,結(jié)果如表3所示. 表3 不同機型最優(yōu)過站時間 為實現(xiàn)對各機型均衡性能驗證,對比分析各機型優(yōu)化前后的運行總時間和資源消耗總量,結(jié)果分析如圖11、12所示. 圖11 優(yōu)化前后各機型運行時間比較 圖12 優(yōu)化前后各機型資源消耗比較 機型不同引起各環(huán)節(jié)在運行時間和資源配置上產(chǎn)生波動,但各環(huán)節(jié)的開始時間與標(biāo)準(zhǔn)時間符合模型要求,輸入相應(yīng)數(shù)據(jù)仍可根據(jù)各環(huán)節(jié)的均衡狀態(tài)求得相應(yīng)的環(huán)節(jié)配置方案.由圖11、12對比可知,所用均衡優(yōu)化模型在運行總時間和資源消耗量上均有良好效果,優(yōu)化了保障過程的運行質(zhì)量,降低航班延誤,提升了機場運行效率. 航班地面保障過程資源均衡評價指標(biāo)包括:均衡率BP表示衡量整個保障過程中各環(huán)節(jié)對時間均衡的利用率;時間損失系數(shù)ε表示衡量保障過程對時間的有效利用程度;資源平滑系數(shù)SI表示衡量保障過程中各環(huán)節(jié)資源負荷的均勻程度[13].這3個指標(biāo)計算式為 (16) BP=1-ε, (17) (18) 式中:T1(Li)、T2(Li)分別為分配給貨郵和客機服務(wù)保障環(huán)節(jié)i的作業(yè)時間;Rhi為各流程需完成保障環(huán)節(jié)資源消耗量的總和;Rhmax為流程中保障環(huán)節(jié)資源消耗量總和的最大值. 根據(jù)模型所得最優(yōu)解,對比保障過程資源均衡優(yōu)化前后2種方案的均衡效果,得到均衡率、時間損失系數(shù)和資源平滑系數(shù)結(jié)果如表4所示. 表4 優(yōu)化前后均衡效果比較 從表4可以看出,與優(yōu)化前的方案1相比較,優(yōu)化后的方案2在航班地面保障過程的均衡率提高了10.7%,時間損失系數(shù)降低了65.7%,資源平滑系數(shù)降低了54.7%. 1) 文中模型能在保證環(huán)節(jié)優(yōu)先關(guān)系、時間和資源約束的條件下,節(jié)約保障過程總時間和資源消耗總量,最大限度滿足各環(huán)節(jié)資源均衡性. 2) 采用改進混沌與差分進化的NSGA-Ⅱ算法求解模型,并將所得方案與原始方案對比,結(jié)果表明取得了優(yōu)良效果. 3) 實現(xiàn)了對保障過程均衡評價指標(biāo)的構(gòu)建,驗證了模型的可行性. 4) 可以進一步考慮多航班下,各環(huán)節(jié)時間和資源配置的均衡優(yōu)化問題,進而提升機場整體運行效率.2.4 模型轉(zhuǎn)化方法
3 基于混沌與差分進化NSGA-Ⅱ算法的模型求解
4 實例分析與討論
4.1 試驗數(shù)據(jù)及其預(yù)處理
4.2 試驗設(shè)置
4.3 試驗過程
4.4 試驗結(jié)果及分析
4.5 均衡優(yōu)化方案對比分析
4.6 保障過程均衡性能評價
5 結(jié) 論