邢志偉,劉洪恩,李 彪,2,羅 謙,文 濤,陳肇欣
(1.中國民航大學電子信息與自動化學院,天津 300300;2.中國民航大學航空工程學院,天津 300300;3.中國民用航空局第二研究所,四川 成都 610041)
目前機場運行呈現(xiàn)出大型化和復雜化的趨勢,航班的高密度運行成為常態(tài),機位分配也成為影響現(xiàn)代機場運行效率的瓶頸。航班機位分配問題(flight gate assignment problem,FGAP)作為典型的多輸入多輸出問題是研究難點,如何對機位運行時空演化過程進行精確的定量描述是機位分配問題研究的前提和關鍵。
既有文獻集中于規(guī)劃模型[1-7]、強化學習模型[8]、因果模型[9-10]、網(wǎng)絡流模型[11-15]、圖模型[16-17]、網(wǎng)絡模型[18-21]等。規(guī)劃模型以最小化旅客行走距離、最小機位變動等為目標達到優(yōu)化目的,以機位機型匹配等為約束滿足機場實際需求,產(chǎn)生了線性規(guī)劃模型[1]、整數(shù)規(guī)劃模型[2-5]以及混合整數(shù)規(guī)劃模型[6-7]。但此類方法在模型約束上有不同程度的簡化失真,例如對機場運行過程中來自氣象、管制等外界不可抗因素產(chǎn)生的影響考慮不足。強化學習模型[8]學習效果較好。為改進模型以適應延誤等情況發(fā)生,文獻[9]基于著色Petri網(wǎng)(colored Petri nets,CPN)建立的因果模型對于描述航班延誤在機場運行中的影響傳播以及應對延誤的恢復策略表現(xiàn)較好。但處于連續(xù)變化的航班時刻表使得運行必須對時間窗作動態(tài)調(diào)整,以邏輯相對固定的庫所、變遷為動作的Petri網(wǎng)適用性相對不足。網(wǎng)絡流模型[11-12]可以靈活地描述航班機位變動,在考慮氣象、航班變動等影響時適用于再分配問題,并且通過控制流向可以精確描述機位約束。在此基礎上,文獻[13-15]加入混合整數(shù)規(guī)劃到網(wǎng)絡流模型中,以期同時應對優(yōu)化和再分配問題達到良好效果。但已有研究的問題場景主要為換乘旅客或機位與登機口的再分配,對國內(nèi)機場存在的機位地理情況復雜、影響因素交叉、決策條件模糊等問題分析甚少。文獻[16-17]建立機位圖模型并分別使用圖著色和圖分區(qū)方法以集團劃分得到最小約束沖突,但模型在數(shù)據(jù)規(guī)模增加時依賴復雜求解算法支撐。文獻[18-23]使用時空信息融合模型應用于航空運輸、艦船航跡、鐵路線路分配與自導車輛路由(automated guided vehicles,AGV)等問題,在運行過程刻畫、優(yōu)化問題建模與信息融合數(shù)據(jù)挖掘方面具有優(yōu)越性。文獻[24-27]以經(jīng)典規(guī)劃模型為主,研究聚焦于多目標優(yōu)化、魯棒性增強、算法求解速率及精確度等方面。文獻[28-33]涉及到的模型改進多針對機位容量、旅客行走距離、機位運行時間均衡、航班時刻波動的吸收或其多目標綜合等前設約束方面,并考慮了機位再分配的決策邏輯。與此同時,此類文獻中機位的各類約束及求解目標對建模同樣具有啟發(fā)和指導意義。
綜上,已有研究使用的模型在運行場景變更、數(shù)據(jù)規(guī)模增加以及突發(fā)情況下會產(chǎn)生約束條件失效模型失真等現(xiàn)象,未考慮航班與機位之間的關聯(lián),缺乏對宏觀場景間差異的特征刻畫,導致運行態(tài)勢的辨別缺少支撐。以期對上述問題研究,基于復雜網(wǎng)絡理論研究機場實際機位運行流程宏觀及微觀特征信息,參數(shù)化定量描述模型以及基于模型的特征信息規(guī)律分析方法,并使用歷史數(shù)據(jù)驅(qū)動對模型的有效性進行驗證。
在對機位運行流程分析研究的基礎上,基于圖結構的數(shù)據(jù)挖掘并加入復雜網(wǎng)絡相關概念和分析手段,將離散化的機位運行對象抽象為關系關聯(lián)表達和網(wǎng)絡拓撲結構,并通過將對象特征進行網(wǎng)絡屬性化以實現(xiàn)量化分析。
由飛行區(qū)、航站區(qū)和公共區(qū)構成的機場系統(tǒng)是現(xiàn)代綜合交通系統(tǒng)中連接地側和空側的交通樞紐,如圖1所示,機位相連著空側飛行區(qū)與地測航站區(qū),航空器在機位完成下次飛行前的??炕顒?。
圖1 機場運行功能分區(qū)示意圖Fig.1 Schematic diagram of airport operation function partitioning
機位的使用是機場運行流程的重要環(huán)節(jié),由機場調(diào)度或運行中心為到離港航班分配停機位資源,FGAP包括預分配和實時再分配。其中,機場預分配是指機場在前一天24點之前接收到次日各航空公司的航班計劃后,根據(jù)當前機位的利用狀況、停靠航班等信息,對機場機位進行預分配,并將機位分配計劃傳達到機場相關的保障部門。其余機場資源(如擺渡車輛、值機柜臺、安檢口、登機口等)需要參考機位計劃進行預分配。
實際運行中呈現(xiàn)出多機位并行式的運行狀態(tài),結合網(wǎng)絡化建模需要,機位運行過程時空關聯(lián)網(wǎng)絡建模主要為:以機位運行狀態(tài)描述方法建立靜態(tài)時空關聯(lián)網(wǎng)絡;以機位運行過程描述方法實現(xiàn)時空關聯(lián)網(wǎng)絡演化;以網(wǎng)絡模型結構優(yōu)化方法實現(xiàn)網(wǎng)絡結構的非失真優(yōu)化。
以時空關聯(lián)網(wǎng)絡描述機位運行狀態(tài),V={v1,v2,…,vn}為網(wǎng)絡節(jié)點,表示航班??康綑C位的邏輯關系存在,網(wǎng)絡節(jié)點時間屬性對應航班時刻,空間屬性對應機位地理位置,網(wǎng)絡節(jié)點的時空屬性均使用相對坐標表示??臻g屬性為
(1)
式中,(xi,yi)為第i個機位的絕對坐標,其中i=0,1,…,n,n為機位總量;(x0,y0)為空間零點(初位置)。絕對坐標是在機場建設階段確定的,僅當機場布局變更或運行調(diào)整等特殊情況下變化。時間屬性為
(2)
(3)
節(jié)點的時空屬性可表示為
CG=[IF·SIF·T]
(4)
(5)
網(wǎng)絡邊E={e11,e12,…,e1n,…,en n}存在于任意兩節(jié)點間,也稱作弧,表示任意兩航班間均存在時間空間關系,由此可得到n×n維的邊集合可表示為
(6)
邊的權重W={w11,w12,…,w1n,…,wn n},描述節(jié)點在時空屬性上的關聯(lián)及差異性,以歐氏距離表示對應的邊權重為
(7)
式中,
(8)
(9)
建立節(jié)點位置仿照地理上指狀航站樓外圍機位排布的全連接5節(jié)點網(wǎng)絡圖,如圖2所示。
圖2 仿地理位置排布的全連接5節(jié)點靜態(tài)網(wǎng)絡圖Fig.2 Fully connected five-node static network diagram of imitating geographical location
在將地理位置數(shù)據(jù)加入網(wǎng)絡模型的基礎上,將仿地理位置排布轉化為縱向排布,上述的5節(jié)點全連接網(wǎng)絡模型等效為如圖3的縱向形式。
圖3 縱向排布的全連接5節(jié)點靜態(tài)網(wǎng)絡等效圖Fig.3 Equivalent diagram of vertically arranged fully connected five-node static network
由于網(wǎng)絡模型中節(jié)點會隨著時間t的推移,節(jié)點屬性變量CG包含的時間屬性T會隨之變化,并且邏輯變量IF也存在變化的可能,從而進一步影響網(wǎng)絡中節(jié)點的數(shù)量和屬性,同時網(wǎng)絡結構發(fā)生演化。
(10)
以白色節(jié)點圖示存在節(jié)點,黑色節(jié)點圖示消失節(jié)點。網(wǎng)絡節(jié)點的變化根本上來自于t的變化,網(wǎng)絡演化的來源即是節(jié)點的生成與消失。而通過上述的假設可以找出節(jié)點變化的時間,以此網(wǎng)絡演化模型可表示為一系列的網(wǎng)絡及其連接。依據(jù)不同的時間零點T0定義不同階段,相鄰的時間零點表示相鄰的階段,并于節(jié)點外側設置節(jié)點、階段指示符,變化過程如圖4所示。
圖4 相鄰階段的5節(jié)點網(wǎng)絡離散圖Fig.4 Discrete diagram of five-node network in adjacent stages
其中,階段由時間零點定義,由零點集合中每一個時間零點表示,例如:節(jié)點4和節(jié)點5從第j階段變化到第j+1階段的觸發(fā)條件為
(11)
并且可以得到網(wǎng)絡演化的相鄰節(jié)點集合:
(12)
式中,VP={v1,v2,…,vn1}表示網(wǎng)絡演化中階段較早的節(jié)點集;VL={v1,v2,…,vn2}表示網(wǎng)絡演化中階段較晚的節(jié)點集。
如圖4所示,相鄰兩階段中j表示相鄰的較早階段;j+1表示相鄰的較晚階段;i=4處節(jié)點的消失表示4號機位處航班于j+1階段出港;i=5處節(jié)點的生成表示5號機位處航班于j+1階段進港。以階段更迭表示網(wǎng)絡演化的細分。
圖5 兩階段的5節(jié)點網(wǎng)絡演化圖Fig.5 Evolation diagram of two stage five-node network
圖6 5階段的5節(jié)點時空關聯(lián)網(wǎng)絡演化模型Fig.6 Evolution model of five-node ralational spatio-temporal network with five stages
完整網(wǎng)絡演化模型包括19個節(jié)點、27條內(nèi)邊和12條外邊,可以證明在最復雜情況下,當數(shù)據(jù)維度增加時邊的數(shù)量以指數(shù)增加,在保證信息不丟失前提下對模型的非失真優(yōu)化是必須的。
網(wǎng)絡模型優(yōu)化需保證網(wǎng)絡中關聯(lián)關系和信息不受影響,網(wǎng)絡關聯(lián)關系不變即節(jié)點與邊存在邏輯,也就是網(wǎng)絡主要結構不變;在網(wǎng)絡主要結構不變的前提下,網(wǎng)絡信息不變即是保證節(jié)點時空屬性和節(jié)點連邊權重不變。
模型節(jié)點由節(jié)點存在性性質(zhì)決定,而邊一方面取決于節(jié)點的存在,另一方面取決于節(jié)點的時間屬性。內(nèi)邊的存在依賴于同階段節(jié)點的存在,外邊的存在依賴于不同階段節(jié)點的存在,通過節(jié)點的時間屬性確定而將所有外邊簡化為無向邊。
若兩個相鄰階段的節(jié)點完全相同,則將相鄰階段的節(jié)點合并刪除掉外邊,只需注意決定節(jié)點存在的生成時間零點和消失時間零點即可。邊存在的實質(zhì)是因為節(jié)點在時間維度上發(fā)生了交集,即節(jié)點有相同的時間屬性,最后刪除模型外側的指示符完成優(yōu)化。
圖7為優(yōu)化后的模型,只有7個節(jié)點和15條邊,較之前簡化了12個節(jié)點和24條邊,并且消除了因外邊存在帶來的有向性問題。優(yōu)化后的模型所擁有的15條邊中有6條邊是簡化前模型中存在的,其余的9條邊是經(jīng)過內(nèi)外邊組合變化而得到的。例如,優(yōu)化后的模型中,i=1第1階段的節(jié)點與i=3第4階段的節(jié)點之間的邊,在意義上可看作是優(yōu)化前模型中i=1第1階段至第4階段之間的3條外邊和第4階段i=1與i=3之間的1條內(nèi)邊合并得到。
圖7 5階段的5節(jié)點時空關聯(lián)網(wǎng)絡模型優(yōu)化圖Fig.7 Optimization diagram of five-node ralational spatio-temporal network with five stages
數(shù)據(jù)信息對應模型為:生成時間零點和消失時間零點分別為航班到港時間和離港時間,上述的優(yōu)化操作是將描述同一航班到港離港節(jié)點合并為單一節(jié)點,使用機位的地理位置作為空間屬性,使用實到實飛數(shù)據(jù)作為時間屬性,屬性信息合并而沒有變動或缺失,優(yōu)化操作可行。
在時空關聯(lián)網(wǎng)絡建立的基礎上,加入多維度的網(wǎng)絡特征,以多種定量參數(shù)指標進一步提高模型對場景描述的精確性。
機場運行過程中呈現(xiàn)不同的應用場景和模態(tài)特征,航班密度隨時間推移呈現(xiàn)一定的周期變化、高峰時段進出港航班量增加、氣象和航空管制等不確定因素導致航班非正點情況。根據(jù)對象的描述層次將模態(tài)特征分為宏觀特征(總體特征)和機位特征(微觀特征),共同對運行過程做出參數(shù)化描述。
2.1.1 宏觀特征
描述機場運行所需的宏觀特征矩陣,包括在選定的時間段內(nèi)的所有宏觀特征參數(shù):
UA={Δt,n,M,NA,HA,ρA,γA,RA,DA,AA}
(13)
式中,M為航班總量;NA為機位使用量;HA為高峰小時;ρA為航班密度;γA為航班正點率;RA為非正點情況;DA為航班延誤率;AA為航班平均延誤時間。
2.1.2 機位特征
機位特征是機位的所有微觀特征參數(shù)集合:
UG={CG,BG,OG,RG,DG,AG}
(14)
式中,BG為機位繁忙程度;OG為機位使用率;RG為非正點原因;DG為機位延誤率;AG為機位平均延誤時間。
系統(tǒng)實時運行中,由于不可控的隨機因素(例如發(fā)生流量控制時采取的空中交通管制、惡劣天氣、航空器機械故障等)常造成航班到達機位的時刻(航班到港上輪擋的時間)與計劃時刻(航班時刻表上的時間)不一致,即航班的非正點情況。其中,提早到達情況可通過使航空器適當?shù)谋P旋飛行消除,而延誤情況造成的波及程度相對較大,其影響消除更難。根據(jù)機場實施的《航班正常管理規(guī)定》并綜合考慮機場標準間的差異及研究的需要,此處選定航班實際時刻比計劃時刻延遲15 min以上或航班取消的情況稱為延誤。非正點情況的發(fā)生與機場運行效率和服務質(zhì)量直接相關,尤其當航班發(fā)生延誤傳播情況影響劇烈,一般使用航班密度、機位使用率、延誤率等參數(shù)衡量運行效率和運行質(zhì)量。
圖7的5節(jié)點網(wǎng)絡模型中,由于i=1與i=2的節(jié)點度較高,處于運行的關鍵環(huán)節(jié),在變更此航班的資源分配時會對鄰居節(jié)點產(chǎn)生影響,即需同時考慮其余4個機位的是否隨之調(diào)整。另一方面,集聚化高的網(wǎng)絡中節(jié)點聯(lián)系緊密,形成類似團或群體的局部聚集區(qū)域,區(qū)域內(nèi)節(jié)點發(fā)生變化時對直接相連的相鄰節(jié)點產(chǎn)生影響,但對區(qū)域外的不相鄰節(jié)點影響較小。而集聚程度低的節(jié)點與相鄰節(jié)點并未形成局部區(qū)域,更容易將此節(jié)點發(fā)生變化的影響傳播到更廣范圍的節(jié)點。
圖8為多級網(wǎng)絡系統(tǒng)化建模方法流程,必要步驟包括模型層和信息層,即將機位運行的主要過程描述為網(wǎng)絡模型,在此基礎上加入節(jié)點和全局屬性以及機位運行信息,對模型進行網(wǎng)絡分布、航班動態(tài)信息、機位運行情況等方面的分析。
圖8 建模方法Fig.8 Modeling method
針對國內(nèi)某機場實際運行數(shù)據(jù)建立時空網(wǎng)絡模型,為突出模型對關聯(lián)性較強的航班與機位運行的描述,選取呈現(xiàn)局部團狀的機位運行數(shù)據(jù)進行分析,忽略局部之外的影響和其他次要影響因素,對機場單日(0:00-23:59)南方航空公司(編號為CZ)的運行數(shù)據(jù)過程建立時空網(wǎng)絡模型。
表1 經(jīng)預處理后的機場機位運行數(shù)據(jù)Table 1 Preprocessed operation data of gates operation in airport
表2 機型對應參數(shù)Table 2 Corresponding parameter of aircraft type
表3 機位號對應參數(shù)Table 3 Corresponding parameter of aircraft tag number
預處理后的數(shù)據(jù)可驅(qū)動網(wǎng)絡模型的行為、演化和模型分析,并可得到網(wǎng)絡模型的機位特征和宏觀特征所對應的節(jié)點屬性和全局屬性。依照方法步驟將相同航班實到、實飛的節(jié)點合并為單一節(jié)點,使用機位的地理位置作為空間屬性,使用實到實飛數(shù)據(jù)作為時間屬性T,以序號標注節(jié)點簡化模型表示,并加入求取的其他宏觀微觀特征參數(shù)。模型的節(jié)點集、邊集和模型度矩陣分別為
V={v1,v2,…,v31}
E={e11,e12,…,e3131}
D=diag(1,10,4,8,2,4,7,1,10,4,7,2,9,4,7,5,15,5,
13,13,17,12,18,21,12,12,13,12,16,19,13)
建立時空網(wǎng)絡模型時將節(jié)點1和節(jié)點8剔除,以保證模型是連通圖且分析可靠性較高,依據(jù)數(shù)據(jù)特征計算、狀態(tài)及特征求解,得到如表4~表6所示時空網(wǎng)絡模型的機位特征與宏觀特征以及網(wǎng)絡參數(shù),圖9為數(shù)據(jù)驅(qū)動的網(wǎng)絡節(jié)點生成圖,其中符號L表示當天結束時間為23:59。圖10為優(yōu)化后的時空關聯(lián)網(wǎng)絡模型。
表4 機位特征表Table 4 Features of gates
表5 宏觀特征Table 5 Macro characteristics
表6 網(wǎng)絡參數(shù)Table 6 Network parameters
圖9 數(shù)據(jù)驅(qū)動的網(wǎng)絡節(jié)點生成圖Fig.9 Generated diagram of date-driven network nodes
圖10 實際數(shù)據(jù)驅(qū)動的時空關聯(lián)網(wǎng)絡模型Fig.10 Actual data-driven spatio-temporal relational network model
在確保網(wǎng)絡連通的前提下,剔除對網(wǎng)絡主體特征影響微小的局部節(jié)點,網(wǎng)絡分析是對實際網(wǎng)絡模型的子圖開展。
如圖11(a)所示,若用k表示節(jié)點的度,在相關系數(shù)R2=0.227 2時,擬合曲線為冪律分布P(k)=0.148k-0.421,整體趨勢符合無標度網(wǎng)絡的特點,即少數(shù)節(jié)點占據(jù)了整個網(wǎng)絡中大部分連邊,而多數(shù)節(jié)點的連邊數(shù)量較少。如圖11(b)所示,淺綠色節(jié)點表示度較低的節(jié)點,藍色表示度較高的節(jié)點。
圖11 網(wǎng)絡模型節(jié)點度Fig.11 Node degree of network model
時空網(wǎng)絡模型中,連邊的存在表征了代表航班的節(jié)點之間有時間或空間上的交叉和沖突,其分布規(guī)律說明在機位運行過程中,少數(shù)航班對其他航班存在沖突影響,并有需要變更機位的潛在影響,而多數(shù)航班使用較少的機位資源并對其他航班影響較小,不發(fā)生共用機位的時空資源沖突。如圖12(a)所示,在MAD=0.172 4時,聚類系數(shù)達到0.807 5。圖12(b)中,綠色節(jié)點表示其聚類系數(shù)低于均值,黃色節(jié)點表示其聚類系數(shù)高于均值,紅色節(jié)點表示其聚類系數(shù)為1。節(jié)點的聚類系數(shù)較高,說明航班與機位處于繁忙時空段,且此處發(fā)生變動或調(diào)整時對關聯(lián)節(jié)點影響較大,需要綜合考慮鄰近的所有節(jié)點。宏觀特征和機位特征存在關聯(lián),航班的高峰小時發(fā)生在網(wǎng)絡連邊密集的區(qū)段,58.62%聚集程度較高的節(jié)點對應的機位利用率和繁忙程度較高,結合航班信息可以發(fā)現(xiàn),機場存在將繁忙航空公司的分配優(yōu)先級提高或?qū)㈦`屬于相同航空公司的航班相鄰分配的情況,鄰近區(qū)域符合冪律分布和聚類系數(shù)較高的特點。區(qū)域分配是數(shù)據(jù)呈現(xiàn)的現(xiàn)象,可從系統(tǒng)網(wǎng)絡分析發(fā)現(xiàn)此類模糊規(guī)律。
圖12 網(wǎng)絡模型聚類系數(shù)Fig.12 Clustering coefficient of network model
但實際數(shù)據(jù)驅(qū)動下的模型與標準無標度網(wǎng)絡比較存在誤差,原因主要有兩點。一個是驅(qū)動數(shù)據(jù)為實際運行中隨機影響因素與人工干預疊加作用后的再分配數(shù)據(jù),數(shù)據(jù)內(nèi)部包含了應對干擾的調(diào)整邏輯。另一個是驅(qū)動模型數(shù)據(jù)規(guī)模僅為機場單日局部機位群,存在系統(tǒng)性誤差和隨機性干擾,當數(shù)據(jù)的有效規(guī)模擴大時擬合精度改善。
選取實際運行情況中具有代表性的弱、中、強3種不同規(guī)模復雜度的運行情況,其網(wǎng)絡模型分別如圖13和圖14所示,節(jié)點數(shù)分別為17和58,與圖10中29節(jié)點模型的節(jié)點度分布對比結果如圖15所示,節(jié)點度分布冪律擬合如圖16所示。
圖13 小規(guī)模網(wǎng)絡模型Fig.13 Small-scale network model
圖14 大規(guī)模網(wǎng)絡模型Fig.14 Large-scale network model
圖15 不同規(guī)模網(wǎng)絡節(jié)點度分布對比Fig.15 Comparison of node degree distribution in different scale networks
圖16 不同規(guī)模網(wǎng)絡節(jié)點度分布擬合Fig.16 Node degree distribution fitting of different scale networks
從圖14的擬合效果可以看出,節(jié)點度分布在網(wǎng)絡規(guī)模增大時精度有明顯提升。通過對不同規(guī)模復雜度的網(wǎng)絡對比分析可知,該模型適應于對不同規(guī)模的運行情況進行建模,對時空關聯(lián)網(wǎng)絡模型具有有效性。
本文分析了機場機位運行的規(guī)律,建立時空網(wǎng)絡模型并提出基于時空網(wǎng)絡仿真分析方法,得出以下結論。
(1) 較現(xiàn)有機位運行模型相比,網(wǎng)絡模型基于航班進出港時間、機位地理信息等構成宏觀和微觀特征,提高了描述運行態(tài)勢特征的準確性,并可靈活增刪信息參數(shù)以滿足運行的不同需要。運行過程中,航班與機位產(chǎn)生的關聯(lián)隨著數(shù)據(jù)規(guī)模變化,規(guī)模包含所選時間區(qū)間和所選機位容量以及特征多個維度,而時空網(wǎng)絡模型可對時空關聯(lián)進行精確的唯一描述。
(2) 設計了利用復雜網(wǎng)絡理論對機位運行過程中機位及航班描述的網(wǎng)絡分布分析的方法,可對大規(guī)模運行數(shù)據(jù)中航班延誤、機位繁忙等情況作宏觀微觀分析。
(3) 網(wǎng)絡模型與復雜網(wǎng)絡理論對大規(guī)模數(shù)據(jù)的適應性,在歷史數(shù)據(jù)的模糊規(guī)則挖掘方面具有優(yōu)越性,可利用歷史經(jīng)驗指導未來運行。在后續(xù)研究中需要引入更大規(guī)模的機位運行數(shù)據(jù)、干擾輸入等因素,建立全機場機位運行網(wǎng)絡模型,進一步研究在機場整體層面上的運行模式和信息特征。