多馬爾可夫鏈協同的航班客艙保障過程預測

邢志偉，劉 鵬+，李 彪，羅 謙

(1.中國民航大學 電子信息與自動化學院，天津 300300；2.中國民用航空局第二研究所 工程技術研究中心，四川 成都 610041)

0 引 言

機場作為民航運輸環節的關鍵節點，在保障安全的前提下應盡可能提高機場地面運行的效率和質量。航班在泊入機位后要開展各項客艙保障，其過程預測的準確性很大程度影響了機場推出時隙及保障資源的分配，實現航班客艙保障環節的精確動態預測，為機場運行精細化管理提供決策依據進而提升機場智慧化[1]運營能力。

客艙保障指航班從下客開始到撤輪擋之前以飛機客艙為核心的服務過程，是航班地面保障過程的核心組成部分。目前國內外的研究成果主要集中在地面保障過程的仿真分析[2，3]、流程優化[4，5]以及服務時間估計[6，7]等，而單獨針對客艙保障過程每一節點發生時刻的研究極少涉及。王立文等[8]在充分考慮航班運行屬性的基礎上，基于貝葉斯網絡實現了地面保障關鍵節點的動態預測，但是對于客艙保障過程刻畫不詳細。Q Luo等[9]為實現機場運行協同，提出了基于Petri網的地面保障過程態勢感知方法，但未對保障細節做詳細論證。C Liu等[10]從航班地面服務網絡出發，在滑動窗口變化點檢測的動態網絡模型推理框架的基礎上實現了變化節點檢測。Jenaro Nosedal等[11]通過對機場周轉過程分析，利用因果方法對影響航班保障過程的不同擾動開展了定時評估。邢志偉等[12]考慮了服務流程的復雜性和特殊性，建立了基于深度神經網絡的航班地面保障預測模型，雖能夠較為精確地預測航班保障時間，但無法描述保障過程的細節問題。

對于上述問題，本文從過站航班客艙保障過程分析出發，構建其網絡拓補圖的馬爾可夫模型，設計面向航班客艙保障過程的DBSCAN-SMMC預測方法，基于某機場的歷史保障節點數據仿真驗證，實現客艙保障每一節點的實時預測。

1 航班客艙保障過程分析與建模

1.1 過程分析

客艙保障是航班過站時地面保障過程中的重要環節之一，主要包括航班離港前為保障接續航班正常運行而針對客艙的一系列服務，分為加餐食、客艙清潔、垃圾處理、加清水、排污水5個子過程。在機場，客艙保障過程沒有明確的開始和結束時間，保障環節任一過程最先開始作業，即視為客艙保障過程開始，所有環節作業結束，則該過程結束，客艙保障過程如圖1所示。在實際運行中，配餐作業結束后才會開始排污水作業，而配餐過程和排污水作業均可與加清水作業并行工作，在下客結束后即可開始客艙清潔工作，期間垃圾車作業，在客艙清潔結束后，垃圾車作業隨之完成。為直觀描述客艙保障各個環節之間的約束關系，將航班客艙保障過程刻畫為如圖2所示的甘特圖。整個過程必須嚴格遵守機場的地面運行標準，如果某個航班的某個客艙保障環節出現問題，不僅會影響當前航班的飛行計劃，還有可能造成一系列航班保障不及時引發的機場大面積延誤。綜上，客艙保障過程是一個多條件約束、多資源協同、具有嚴格時間窗的復雜過程。

圖1 過站航班客艙保障過程

圖2 過站航班客艙保障過程甘特圖

針對單個航班客艙保障過程的資源協同預測開展分析與建模，對實際流程做如下理想化處理：

(1)由于始發航班接受保障的時間窗較為寬裕，終到航班不會影響后續航班的執行，且保障過程不完整，因此只考慮過站航班的客艙保障過程。

(2)實際保障過程中，機型大小和執行航線的不同都會影響保障資源的供應量，視為餐食車能一次性提供航班的需求量，清水車、污水車、垃圾車只開展一次作業即可完成本航班的保障，同時不考慮極少數不需要完整保障過程的過站航班。

(3)忽略保障資源的調度對客艙保障過程造成的影響。

(4)實際保障過程中，下客結束和客艙清潔開始兩個節點具有短時連續性和同步性，即下客結束后緊接著就開始客艙清潔，所以將兩個節點視為同一過程。

1.2 航班客艙保障過程馬爾可夫模型

馬爾可夫鏈(Markov chain)為狀態空間中從一個狀態到另一個狀態的轉換的隨機過程，該過程的特點是無后效性，即下一個狀態的概率分布只能由當前狀態決定。作為描述隨機事件因果關系的重要方法之一，在移動對象軌跡預測、銷量預測、故障預測[13-17]等方面具有廣泛的應用。

航班客艙保障過程預測問題可以表示為：已知某保障過程節點時間的變化軌跡 {T(xk)|k=1，2，3，…xk表示保障節點} 和軌跡預測模型，求解第k+1個節點的時刻T(xk+1)。因每一保障節點的時間只與前一節點有關，因此將此問題視為一個馬爾可夫過程，并由馬爾可夫鏈來表示。選取與客艙保障過程相關聯的節點，將客艙保障過程結構圖等效為如圖3所示的網絡拓補。

圖3 客艙保障過程網絡拓補

其中，x1表示下客開始，x2表示下客結束，x3表示清水車作業開始，x4表示清水車作業結束，x5表示配餐開始，x6表示配餐結束，x7表示污水車作業開始，x8表示污水車作業結束，x9表示客艙清潔開始，x10表示垃圾車作業開始，x11表示客艙清潔結束，x12垃圾車作業結束，x13是一個虛擬的節點，表示客艙保障過程結束。

由于x13是一個虛擬的節點，不影響預測過程，x2與x9具有同步性，在預測過程等效為一個節點，用x9來表示。所以圖3的網絡拓補結構看作3個并行的過程，只要x1發生，3個過程均已開始且互不影響，將其等效為3條馬爾可夫鏈，如圖4所示。

圖4 等效馬爾可夫鏈

定義1 馬爾可夫性：航班客艙保障過程馬爾可夫性可以被定義為

P(Xl+1=tj|X1=t1，X2=t2，…，Xl=ti)=

P(Xl+1=tj|Xl=ti)

(1)

式中：{Xl，l=1，2，…} 為該馬爾可夫鏈的隨機序列，表示航班客艙保障流程中節點的集合，l表示馬爾可夫鏈中xk的位置，k=1，2，…，13；T={t1，t2，…，ti-1，ti，tj…} 為狀態空間，表示保障節點的狀態時刻值的集合。Xl表示當前發生的保障節點，Xl+1表示即將發生的保障節點，ti為當前保障節點的時刻狀態，tj為即將發生的保障節點的時刻狀態預測。

定義2 轉移概率：航班客艙保障過程馬爾可夫鏈為X={X1，X2，…，Xl，…}，隨機變量Xl(l=1，2，…) 的發生時刻定義在狀態空間T={t1，t2，…，ti-1，ti，tj…}，若馬爾可夫鏈在Xl節點處于狀態ti，移動到Xl+1節點時其狀態為tj，將轉移概率記作

pij=P(Xl+1=tj|Xl=ti)

(2)

馬爾可夫鏈中Xl到Xl+1之間所有狀態的轉移概率集合組成的矩陣稱為狀態轉移概率矩陣，其表達式如下

(3)

狀態轉移概率矩陣具有以下兩個性質

pij≥0，i=1，2，…，m；j=1，2，…，n

(4)

(5)

式(1)表示下一個保障節點Xl+1發生的狀態tj僅與當前保障節點Xl的狀態ti相關，與之前已經發生過的保障節點X1，X2，…，Xl-1均無關，但因Xl與Xl-1相關，結合式(2)，可以通過Xl-1預測保障節點Xl的時刻，繼而預測Xl+1的狀態。圖4所示的3條馬爾可夫鏈，只要x1發生，即可預測每一保障節點的時刻值，在前序節點發生時，及時修正預測模型。

2 航班客艙保障過程協同預測方法

2.1 轉移概率矩陣的生成

根據機場航班客艙保障過程的歷史數據得到保障節點的時間分布，然后對其分段與聚類。保障節點的時間序列通常呈現不均衡分布，有些區域時間點分布緊湊，有些區域時間點分布稀疏，而基于密度的聚類方法對此類問題有較好的聚類效果。

DBSCAN是密度聚類的代表性算法，基于一組鄰域 (eps，minPts) 來描述樣本集的緊密程度，其中，eps描述某一樣本的領域距離閾值，minPts描述某一樣本的距離為eps的領域中樣本個數的閾值。可以對任意形狀的稠密數據集聚類，不僅簡化樣本數據，優化預測過程，還能發現數據集中的異常點，具有很強的抗噪性，減少數據波動對預測結果的影響。

客艙保障節點的歷史數據經過聚類算法處理后，由時間點序列轉化為時間簇序列，但是由于時間點分布不均勻，會得到很多尺寸不一樣的簇。構建馬爾可夫鏈來描述客艙保障節點的預測過程，其節點之間的轉移概率用不同序列的簇之間的聯系來描述，所以簇尺寸的選取對預測精度有很大的影響。如果簇的尺寸太小，會使得轉移到該簇的狀態很少，其轉移概率在轉移概率矩陣中不占優勢，從而容易丟失該數據對預測結果的影響；如果簇的尺寸太大，導致預測的范圍太大，會使預測精度降低，不具代表性。對于此問題，對聚類得到的時間簇序列做了進一步處理，通過合并、分割得到合適尺寸的簇作為馬爾可夫鏈的狀態空間。

在提取航班客艙保障節點歷史時刻的分布特征后，將訓練數據的時間點序列轉換為簇序列，通過統計兩個保障節點間訓練數據從一個簇轉移到另一個簇的頻率作為轉移概率，進而構建馬爾可夫鏈的轉移概率矩陣。Thf到Tuv的馬爾可夫鏈轉移概率計算公式為

phu=p(xu=Tuv|xh=Thf)=

(6)

圖5 簇序列轉移

以保障節點x2到節點x3為例，其轉移概率矩陣為

2.2 “馬氏性”檢驗

用 (gij)i∈(1，m)，j∈(1，n)表示轉移頻數矩陣，“邊際概率”為轉移頻數矩陣的各列之和與全部元素之和的比值，用P·j來表示，即

(7)

(8)

表1 馬爾可夫性檢驗結果

2.3 DBSCAN-SMMC預測方法

根據航班客艙保障過程的馬爾可夫鏈模型，設計了一種協同預測方法，具體步驟如下：

步驟1 初始化處理。收集機場一段時間內航班的實際運行保障數據，對數據進行轉換、刪除、分類、清洗等預處理。整理預處理后的數據，經過DBSCAN聚類算法處理后得到馬爾可夫鏈的狀態空間。

步驟2 初始概率的確定。首個節點的預測值可通過歷史先驗信息由極大似然估計法來確定，即

(9)

步驟3 轉移概率矩陣構造。結合式(6)，可得節點之間的轉移概率矩陣。

步驟4 “馬氏性”檢驗。根據轉移概率矩陣檢驗航班客艙保障節點狀態序列的馬爾可夫性。

步驟5 概率計算與推理。根據轉移概率矩陣，以轉移到下一節點的概率最大的時間簇作為初始預測結果，該時間簇的中心點即為保障節點的初始預測值。以保障節點xh轉移到節點xu為例，保障節點xh的狀態為Thf時，轉移概率最大的時間簇Tuq的中心點作為保障節點xu的初始預測值，其表達式為

phu=p(xu=Tuq|xh=Thf)=

max{p(xu=Tu1|xh=Thf)，…，p(xu=Tun|xh=Thf)}

(10)

步驟6 預測更新。隨著客艙保障節點的發生，其預測值被實際值代替，相應保障節點的狀態也發生變化，根據實際值更新后續節點的預測結果，直至航班的客艙保障節點全部完成。

3 實驗與分析

3.1 數據來源及預處理

仿真數據來源于國內某大型機場某季度的實際運行過程，包括進離港航班的所有字段和保障節點信息，具體數據樣例如表2和表3所示。由該機場某季度實際運行的航班客艙保障數據作為樣本，構成馬爾可夫鏈的狀態空間，從而開展客艙保障過程的預測。由于遠機位的數據較少，作為樣本不具有代表性，因此只針對近機位過站航班的客艙保障過程分析。

表2 航班信息數據樣例

表3 客艙保障過程節點時刻數據樣例

由于機型的不同會導致載客量存在差異，從而影響航班客艙保障過程的時間，因此在概率推理時按照客座數將航班機型分為3類，如表4所示。同時，航線性質不同，所需保障資源也有所不同，從而影響保障時間，根據航線性質劃分為國內近程、國內遠程和國際航線3類。考慮以上影響因素，分別構建馬爾可夫鏈轉移概率矩陣。

表4 航班機型分類

3.2 仿真驗證

根據歷史數據對構建的馬爾可夫鏈的3個初始保障節點開展極大似然估計，得到初始保障節點的先驗概率模型，即下客結束、配餐開始、客艙清潔開始3個節點發生時間的先驗概率模型，如圖6所示。

圖6 初始保障節點先驗概率模型

歷史數據按照機型、航線性質分類后應用DBSCAN聚類算法，設其領域距離閾值eps=1，樣本個數閾值為minPts=30，分別得到各自的馬爾可夫鏈的狀態空間，把此數據作為訓練集，得到節點之間各狀態的轉移概率矩陣，基于得到的轉移概率矩陣開展馬爾可夫鏈中各保障節點的概率推理，以轉移到下一節點的概率最大的狀態作為初始預測結果，以該狀態的中心點作為預測值。選取該機場某日山東航空股份有限公司出港航班號為4752的航班實際的客艙保障流程數據仿真驗證，結果如圖7所示。

圖7 航班到達后的初始預測結果

隨機選取該機場下一季度30個過站航班的客艙保障過程數據，對每一個保障節點做單獨預測，各節點的預測時間均以馬爾可夫鏈模型中上一節點為基準，各航班客艙保障過程的5個關鍵節點預測結果如圖8所示。

圖8 多航班關鍵節點預測結果

3.3 結果分析

為了驗證本文提出的DBSCAN-SMMC預測方法的精密度和準確性，對上述30個航班的客艙保障過程預測結果分析，結合機場實際運行所允許的1 min保障時間置信區間，計算各關鍵保障節點的均方根誤差(RMSE)和平均絕對誤差(MAE)，即

(11)

(12)

上述多航班預測計算結果如表5所列。

表5 多航班預測分析結果

可知，所有節點均方根誤差RMSE的均值為1.1331，表明結果能夠滿足保障過程的預測要求，且有6個節點的RMSE小于1，能夠很好地反映出預測結果的精密度。平均絕對誤差MAE的均值為0.6061，且所有MAE穩定控制在2 min以內，符合機場運行相關標準的要求，有9個節點的MAE在1 min之內，表明預測結果有較高的準確性。同時，本算法的時間復雜度和響應時間可以滿足預測過程的時效性。

3.4 對比分析

為了進一步驗證馬爾可夫預測模型的可行性，選擇與BP神經網絡預測模型作對比。因清水車作業與其它客艙保障過程不沖突，開始時間相對自由，但作業結束時間會影響航班后續計劃；另外，客艙清潔過程與垃圾車作業過程相互制約，客艙清潔結束后垃圾車作業才能結束，為后續航班保障釋放資源，所以選取這兩個關鍵保障節點，直觀比較兩種方法的預測結果，如圖9所示。

同時，計算兩種方法的平均絕對百分誤差(MAPE)來衡量模型預測結果的好壞，MAPE越小表示預測模型越好，當MAPE大于100%時為劣質模型；計算R-平方(R2)來比較兩個模型的擬合優度，R2越接近1，表明回歸擬合程度越好

(13)

(14)

計算結果見表6。可知，兩個關鍵節點的DBSCAN-SMMC預測方法均比BP神經網絡的MAPE低，而且均在15%以下，表明該模型優于BP神經網絡模型，且模型效果較好；DBSCAN-SMMC預測方法的R2值均在0.8以上，遠大于BP神經網絡模型的R2值，擬合效果更好。

表6 預測參數對比

綜上可知，本文提出的DBSCAN-SMMC方法能夠滿足過站航班客艙保障過程預測的基本要求。

4 結束語

針對客艙保障過程多條件約束、多資源協同的問題，構建了其實際運行過程的馬爾可夫模型；針對保障節點數據分布不均衡的問題，改進了DBSCAN對時間序列聚合，提高了聚類的精準度，得到了客艙保障過程的DBSCAN-SMMC預測方法。研究表明，航班機型、航線性質是航班客艙保障過程考慮的首要條件，是確定馬爾可夫模型轉移概率矩陣的關鍵因素；客艙保障節點的時間預測依賴于上一節點的狀態。航班客艙保障過程受多種因素影響，本文只考慮了機位、航班機型、航線性質等首要影響因素，因此尚存在一定不足，下一步將綜合考慮航班執行時段、旅客等因素，細化模型訓練數據；另外可以進一步研究其它狀態劃分方法對馬爾可夫預測模型精度的影響。