飛機地面除冰運行調度模型研究

張 偉，李 彪

（1.北京首都國際機場股份有限公司，北京 100000；2.中國民航大學電子信息與自動化學院，天津 300300）

飛機地面除冰運行調度模型研究

張 偉1，李 彪2

（1.北京首都國際機場股份有限公司，北京 100000；2.中國民航大學電子信息與自動化學院，天津 300300）

為保證機場冬季航班的正常運行，避免因除冰不及時造成大面積延誤和事故，需對除冰資源進行合理分配使其效用最大化。根據除冰資源條件限制和各參與方的約束條件，提出一種基于博弈分配方案的啟發(fā)式調度模型。博弈分配方案能夠實現資源效率最高，結合啟發(fā)式算法得到整個調度模型的最優(yōu)解。使用北京首都國際機場冬季實際運行數據進行模擬仿真驗證，表明比單一的博弈模型效果更好。

除冰資源；博弈分配方案；啟發(fā)式算法；調度模型；最優(yōu)解

?

對飛機進行全面、有效、準時的除冰成為冬季保證機場正常運行的關鍵。但是機場配備的除冰設備資源有限，如何在機場現有設備條件下發(fā)揮出最大效用，一直是業(yè)界研究的問題。

機場設備的調度和運行保障問題，一直都是民航領域的研究熱點。Voulgarellis等[1]利用Matlab及其他計算機語言對機場各個重要環(huán)節(jié)進行模塊化和系統(tǒng)化的建模，并在平臺對各環(huán)節(jié)進行仿真，探索各個環(huán)節(jié)之間的相互關系；Makhloof等[2]介紹了中轉航班流程的數學模型，設計了實時保障設備的算法，并在實際條件下得到了應用；Sanya等[3]分析了單航班的一系列過站保障服務作業(yè)特性，并使用計算機模擬航班保障服務作業(yè)時的多發(fā)性干擾，分析其對飛機過站的影響能力，從而建立應急保障計劃來應對突發(fā)狀況；徐瑞時[4]提出了一種新的保障評估模型，并將其應用到人員設備的動態(tài)實時調度中。對于除冰雪裝備的調度算法設計和構建，民航領域專家已經做了許多研究：Mao、Mors等[5-7]提出了以飛機為系統(tǒng)主體的Multi-Agent模型，并研究了機場除冰運行調度過程，建立了優(yōu)化算法，但動態(tài)響應不佳；石旭東等[8]利用遺傳算法設計了除冰設備的調度模型，但沒有考慮環(huán)境和資源的限制情況；邢志偉等[9-10]基于博弈論的相關知識，對單除冰坪和多除冰坪資源分配問題做了系統(tǒng)的研究，并取得很好的效果，但需進一步完善。

基于以上分析，結合排隊論和博弈論的相關知識，本文提出一種在動態(tài)博弈資源配置方案基礎上的啟發(fā)式調度算法，利用多航空公司之間的博弈關系，針對有限資源條件下如何實現除冰設備的合理調度和分配，建立了除冰資源的實時調度模型，并與單一的博弈模型進行對比分析。

1 飛機地面除冰流程分析

1.1 飛機除冰調度動態(tài)過程分析

飛機除冰調度問題是一個動態(tài)、耦合性強、實時性的流程控制和資源分配問題[11]。飛機除冰運行流程如圖1所示。

圖1 飛機地面除冰運行圖Fig.1 Aircraftground deicing operation figure

基本過程描述如下：

在航空公司申請除冰到完成所有地面保障服務的期間，存在許多不確定性事件，例如航班延誤出現連鎖反應、由于天氣原因出現的流量控制等，都會造成航班無法照常運行。所以，在除冰資源信息不對稱的情況下如何進行資源的分配，保證航班在除冰資源有限情況下的正常運行，是一個比較重要的問題。對于可控范圍博弈的資源分配模式，在某種程度上還是值得鼓勵和研究的。

1.2 除冰非合作博弈模式分析

飛機除冰資源的分配方案和實時調度問題一直都是比較典型的帶有強約束條件的參數解優(yōu)化過程。在資源緊張且無法滿足全部供應的情況下，航空公司、地服公司、機場除冰指揮3個相對獨立的利益方為實現各自的利益而選擇的一些策略，符合非合作博弈模式的情況。非合作博弈中，基本主體是希望在除冰過程中以最小支付方式得到最大效用和收益的航空公司和期望除冰資源效率達到最大和獲益最大化的機場除冰公司。實際博弈過程就是選擇各自博弈方的決策變量和優(yōu)化目標函數的過程。

非合作博弈過程可視作調度中心、航空公司和地服公司3個參與博弈過程的組織，每個組織都會從自己的角度考慮問題，有其策略和目標，但三者又存在一定的聯系，其關系如下

其中：Agta為爭奪除冰資源的航空公司集合；AgtDMC為調度中心；AgtGSC為地面服務公司；R為組織中Agent之間的二元關系的集合；Si為申請除冰航班策略集合；Priorityai為分配除冰資源時航空公司的優(yōu)先級；Sk為決策時的策略集；UDMC為決策時的資源效用。

1.3 除冰合作博弈模式分析

飛機除冰調度合作博弈中，假設該除冰資源分配問題的基本前提成立：即存在一些強有力的約束條件，必須保證其能夠強制執(zhí)行，合作要比對抗得到的結果收益大，同時聯盟內部應存在公平有效的分配規(guī)則。

兩個除冰資源申請方所構成的合作博弈是合作博弈的學者們較早研究的一個基本問題。實際上問題研究的本質并不是選擇自己的策略，而是要確定所有的資源分配方案。分配本身就意味著必須對相關利益進行分割和再分配，也是一種相對的除冰資源利益補償機制。在實際處理過程中必須考慮本身是無法達到最終期望目標的，因此要考慮在除冰資源的博弈過程中對于風險的規(guī)避策略和對效用的期望。從另一個角度講，任何協商都會存在破裂的可能性，在破裂后各方也可能得到的利益稱之為“談判破裂點”，通常用d=（d1，d2）表示，其中 di是博弈方 i在談判破裂時可以得到的利益[11]。

定義1兩個除冰資源申請方的合作博弈。

兩個除冰資源申請方的合作博弈問題可表示為一個三元數組，即

其中：S′為除冰資源可行分配集，S′={s1，s2|0≤si≤m}，i=1，2，m 是最大可分配期望支付；u1、u2為兩除冰主體各自的效用函數；ui為除冰主體的期望效用（expected utility），ui∶S′→R，ui=ui（s）=ui（si），即效用是除冰主體自身利益的函數；d為兩個除冰主體的談判破裂點，d=（d1，d2）。

基于對飛機地面除冰流程的分析以及非合作博弈和合作博弈兩種模式的分析，可得出在除冰流程中，既存在合作博弈，又存在非合作博弈，且參與除冰博弈各方追求的目標和策略并不統(tǒng)一，實際上在單一除冰調度模型下的最優(yōu)解由于各種原因并不存在。因此除冰資源的運行調度建模過程中必須考慮到以上兩種博弈模式，這樣才能得出合理的調度模型。

2 除冰運行調度模型

對于飛機地面除冰的實時調度模型，許多研究學者都是基于單一的調度模型來進行優(yōu)化，取得一定的成果，但并不完善[12]。本文提出基于除冰資源博弈方案的運行調度模型，將兩種博弈方案得出的最優(yōu)解進行合并處理，利用啟發(fā)式算法進行再優(yōu)化處理，能夠進一步保證解的優(yōu)化性，實現資源的最優(yōu)配置。

2.1 飛機除冰合作博弈方案

兩個航空公司進行合作博弈實際上是一個約束問題求最優(yōu)解的過程，即

Nash解是解決實際中存在的非線性優(yōu)化過程最優(yōu)解的重要方法之一，其最終目標函數被稱為“Nash積”。由于它是一個比較明顯的凹函數，但最終生成的集合也是一個凸緊集，所以在除冰方案配置中可能存在最優(yōu)的情況。

假定某機場有100單位的除冰資源，這些資源對兩個航空公司開放使用。第1個航空公司對于風險的規(guī)避是風險定常的，即u1=u1（s1）=s1；而第2個航空公司對于風險的態(tài)度則是以風險遞減為目標，，兩個航空公司最終的談判破裂點在（0，0）。

則該問題用Nash解法轉化為求解下列Nash積的約束優(yōu)化問題，即

根據約束條件可得 u2=（100-u1）a，帶入 Nash積轉化為單變量最優(yōu)化問題，即一階條件為兩邊乘（100-u1*）a得

從以上分析能夠得出，兩個航空公司在進行合作博弈時對于風險規(guī)避的特性會對談判的最終結果產生較大的作用。資源分配結果的不同主要由反映風險偏好大小的系數a所決定，風險規(guī)避的程度越高，資源分配的傾向和結果就可能越差，效用越低。Nash解法是二人合作博弈問題的最重要解法。Nash解法不僅要滿足優(yōu)化目標效用函數的最大解，而且必須滿足各方對于博弈過程中公平和效率的要求。

2.2 飛機除冰非合作博弈方案

非合作博弈是在航空公司沒有達成聯盟而形成的一種對資源爭奪的分配方案，對于這種情況，除冰資源的調度中必須建立好合理的調度規(guī)則，保證資源發(fā)揮最大的效用，減少航班由于除冰不及時而造成的大面積延誤。

具體的資源配置方案如下：首先航空公司進入等待除冰集合，向調度中心發(fā)出申請，等待其回復；調度中心根據航空公司的申請情況和歷史數據，給出每個航空公司的優(yōu)先權，然后根據優(yōu)先權進行排序；根據優(yōu)先權的順序，航空公司確定自己的策略集合，決定其除冰上投入的資源；除冰調度中心根據各航空公司的最終策略，確定除冰服務的先后順序，并將信息傳送給地面保障服務公司。具體流程如圖2所示。

圖2 非合作博弈調度方案生成流程圖Fig.2 Non-cooperative game scheduling scheme

2.3 啟發(fā)式調度優(yōu)化算法

除冰資源的合理調度是一個求動態(tài)最優(yōu)解的過程，而面對合作博弈和非合作博弈方案的解集，需要尋找一個最優(yōu)解。啟發(fā)式算法的主要作用是得出最優(yōu)解，并對當前最優(yōu)解的狀態(tài)進行評價。

本文選擇比較傳統(tǒng)的貪婪算法作為除冰設備資源運行調度的算法，其采用局部搜索技術快速獲取滿意解，算法簡單且易實現。選擇合作博弈和非合作博弈產生的策略方案作為整個除冰資源的調度方案集，以除冰資源設備的效用最大化作為最終目標，且保證場面的航班延誤達到最小，具體的算法流程如圖3所示。

圖3 貪婪算法流程圖Fig.3 Flowchartof greedy algorithm

3 算例分析

3.1 數據仿真

以北京首都國際機場冬季某天上午1小時內的航班計劃為例，假設此時段有國航、南航和東航3個航空公司，對除冰資源實時調度進行仿真模擬。

首先得到合作博弈和非合作博弈配置方案的策略集，其中需要確定航空公司的優(yōu)先權以及他們?yōu)槌冻龅睦?。確定策略集之后以最大效用和除冰資源效益最大化為目標，利用貪婪算法在策略集中尋找最優(yōu)解。根據實際數據利用Matlab進行模擬，結果如圖4所示。

3.2 對比分析

選取相同條件，利用單一合作聯盟博弈模型和非合作博弈模型運行后發(fā)現，基于資源博弈配置方案的啟發(fā)式調度模型在控制延誤率和資源效用最大化方面表現出不俗的效果，如表1所示。且最大程度上避免了單一啟發(fā)式算法進行調度時出現的違約事件。實現機場在冬季冰雪條件下的安全和高效運行。

圖4 模擬仿真實驗結果圖Fig.4 Simulation results

表1 模型表現對比分析表Tab.1 Performance comparison and analyses between models

4 結語

基于飛機地面除冰的基本流程，分析了合作博弈和非合作博弈下的資源配置方案，根據構成的調度策略集，利用啟發(fā)式算法進行最優(yōu)解的搜索，以實現除冰資源效用和效益的最大化為目標，建立了飛機地面除冰實時調度模型。根據實際數據模擬運行仿真發(fā)現，該方案能在最大程度上滿足航班的需求，減少航班延誤。通過與單一博弈模型進行對比發(fā)現，無論是從延誤率、資源利用率和效率方面，還是從違約情況和機場效益方面均得到了可接受的結果。

[1]VOULGARELLISPG,CHRISTODOULOU M A,BOUTALISY S.A MATLAB Based Simulation Language for Aircraft Ground Handling Operations at Hub Airports(SLAGOM)[C]//Proceedings of the 2005 IEEE International Symposium on,Mediterrean Conference on Control and Automation,IEEE,2005:334-339.

[2]MAKHLOOFM A A,WAHEEDM E,BADAWIE R,et al.Real-time aircraft turnaround operations manager[J].Production Planning&Control, 2014,25(1):2-25.

[3]SANYA A,CHRISTOPHER C.A simulation based approach for contingency planning for aircraft turnaround operation system activities in airlinehubs[J].Journalof Air Transportation,2006,11(1):140-155.

[4]徐瑞時.繁忙機場地面保障容量評估與優(yōu)化[D].南京:南京航空航天大學,2014.

[5]MAO X Y,MORSA T,ROOSN,et al.Agent-Based Scheduling for Aircraft Deicing[C]//Proceedings of the 18th Belgium-Netherlands Conference on Artificial Intelligence,Brussels,2007:229-236.

[6]MAO X Y,MORS A T,ROOS N,et al.Using Neuro-Evolution in Aircraft Deicing Scheduling[C]//ALAMAS 2007 Adaptive and Learning Agents and Multi-Agent Systems,Berlin,2007:138-145.

[7]MORSA T,MAOX Y,ROOSN,et al.Multi-Agent Sycstem Support for Scheduling Aircraft De-icing[C]//Proceeding of ISCRAM 2007-Intelligent Human Computer Systems for Crisis Response and Management,Delft,2007:467-478.

[8]石旭東,王立文,劉勝飛．飛機集中除冰車輛優(yōu)化調度方法研究[J]．計算機工程與應用,2009,45(4):218-220.

[9]邢志偉,唐廣群,任 準.多除冰坪排隊飛機除冰過程調度非合作博弈[J].信息與控制,2013,42(4):511-515.

[10]邢志偉,喬曉輝.飛機地面除冰運行的非合作博弈研究[J].系統(tǒng)仿真學報,2011,23(3):433-437.

[11]XING Zhiwei,LI Junhui．Research of Game-Theoretic Approach for Aircraft Ground Deicing Operation Scheduling[C]//The 2nd International Conference on Mechanic Automation and Control Engineering(MACE 2011),2011:570-574．

[12]李俊輝.飛機地面除冰調度合作博弈研究[D].天津:中國民航大學,2012.

Research on dispatching model of aircraft ground deicing

ZHANG Wei1,LI Biao2
（1.Beijing Capital International Airport,Beijing 100000,China;2.College of Electronic Information and Automation,CAUC,Tianjin 300300,China）

In order to ensure the normal operation of airport’s winter flights,ovoiding large-scale delays and accidents by deicing in time,a reasonable allocation of de-icing resource is required to maximize its utility.According to the deicing resource conditions and constraints of each participant,a heuristic scheduling model based on game allocation scheme is proposed,Which is able to achieve the highest resource efficiency,getting optimal solution of the whole scheduling model combined with the heuristic algorithm.Simulation with real operation data of Beijing Capital International Airport shows that the current model is better than single game model.

deicing resource;game allocation scheme;heuristic algorithm;scheduling model;optimal solution

張偉（1965—），男，北京人，工程師，碩士，研究方向為機場經營管理.

V351.392；O225

A

1674－5590（2017）05－0022－04

2017-08-06；

2017-08-31

?

劉智勇）