飛機地面除冰運行的短進程優(yōu)化調(diào)度方法綜述

李連成?喬迪

摘 要 在除冰資源有限的條件下，飛機全面有效的除冰對飛機減少延誤與事故有著很大的影響。因小型機的除冰時間短，除冰效率高，且后面分析的得到在總延誤時間中小型機的權(quán)重比例最大，所以將各航空公司的小型機進行優(yōu)先調(diào)度即為短進程優(yōu)先調(diào)度。考慮到航空公司，機場運控中心，地面服務(wù)公司三者之間的利益平衡問題，在優(yōu)先對小型機進行調(diào)度的前提下，使用了短進程優(yōu)化調(diào)度的合作博弈算法與非合作博弈算法，并于先到先服務(wù)的算法進行仿真分析，最終得到短進程優(yōu)先調(diào)度的合作博弈與非合作博弈算法既能減小總延誤時間又能達到三者的利益平衡。

關(guān)鍵詞 資源有限;短進程合作博弈;短進程非合作博弈;調(diào)度模型

Abstract Under the condition of limited de icing resources， the comprehensive and effective De icing of aircraft has a great impact on the reduction of aircraft delay and accidents. Due to the short deicing time and high deicing efficiency of minicomputer， and the weight proportion of minicomputer is the largest in the total delay time， so the priority scheduling of Minicomputer in each airline is short process priority scheduling. Considering the balance of interests among airlines， airport operation control center and ground service company， the cooperative game algorithm and non cooperative game algorithm of short process optimal scheduling are used on the premise of giving priority to the scheduling of small-sized aircrafts， and the simulation analysis of the algorithm of first come first serve is carried out， finally the cooperative game and non cooperative game algorithm of short process priority scheduling are obtained. It can not only reduce the total delay time， but also achieve the balance of interests of the three party.

Key words Limited resources; Short Process Cooperative Game; Short-process non-cooperative game; Scheduling model

引言

隨著我國的民航事業(yè)迅速發(fā)展，航班的起飛降落數(shù)量在各大機場都有了大幅度的增長，那么在入冬之后如若遇到除冰坪數(shù)量不夠或除冰所需設(shè)備緊缺的情況下，對有限資源的合理調(diào)度成為影響飛機航班延誤，乘客滯留的關(guān)鍵問題。目前我國大部分機場依然使用著先到先服務(wù)的除冰調(diào)度方案。該方案雖然可實施性最高，但是存在著除冰效率較低，飛機延誤情況出現(xiàn)較多的問題。所以一些更為優(yōu)化的方案急需被引用。

利用遺傳算法設(shè)計的除冰設(shè)備的調(diào)度模型，以及基于博弈論的相關(guān)知識，是對單除冰坪和多除冰坪資源分配問題做了系統(tǒng)的研究，并且取得很好的效果，但需要進一步完善。也有隊列模型、非合作博弈、合作博弈等一些算法考慮資源的調(diào)度，主要考慮多方的利益均衡，將機場除冰設(shè)備默認為資源充足[1]。那么在考慮到資源短缺，并且滿足利益均衡的條件下，提出了短進程優(yōu)先調(diào)度的合作博弈算法以及非博弈算法。短進程優(yōu)先調(diào)度的方法是以進程的運行時間長度作為優(yōu)先級，進程運行時間越短，優(yōu)先級越高。那么在機場的除冰調(diào)度運行中首先應(yīng)該考慮到飛機中占大多數(shù)的飛機仍然是中小型客機，它們的除冰時間更短，那么短進程優(yōu)先調(diào)度可用在機場除冰運行調(diào)度中[2]。

將短進程優(yōu)先調(diào)度的合作博弈算法以及非博弈算法與先到先服務(wù)的調(diào)度方法三者之間進行相比，短進程優(yōu)先調(diào)度具有更小的延誤時間，且實現(xiàn)了利益均衡。

1除冰建模

飛機除冰主要是由以下環(huán)節(jié)來完成，首先由機場根據(jù)各航空公司的信譽度以及航班數(shù)量等條件進行了除冰排序，各航空公司根據(jù)已知的除冰排序提出除冰申請，申請通過后，乘客進行登機，飛機進入除冰坪，除冰完畢后，飛機進入軌道起飛，分步流程如圖1所示：

表示的飛機剛進入停機坪的那一時刻，表示的飛機除冰完成的那一時刻，表示的飛機的除冰時間。

在飛機的除冰過程中，機場本身希望越多的飛機起飛，這樣可以減少航班的總延誤時間，而航空公司本身則希望自家公司飛機起飛越多越好，希望自己優(yōu)先使用資源而不會考慮其他公司。第三節(jié)所提到的合作博弈和非合作博弈將解決利益的平衡問題。在利益平衡的前提下，達到最小的延誤總時間。最終得到目標方程：

此時還應(yīng)該考慮到飛機除冰液的時效問題，如果除冰在預(yù)計起飛時間前完成，則飛機能夠起飛，否則超過了除冰液的時效會存在飛機二次結(jié)冰的問題，如若遇到這種問題則需要再次除冰，此種情況出現(xiàn)時，會對資源造成浪費，所以需要在除冰模型中需加入約束條件。國內(nèi)普遍使用的除冰液時效為15分鐘。那么該限制條件為：

在此目的模型的約束下，來分析短進程優(yōu)先調(diào)度的合作博弈算法以及非博弈算法。

2短進程優(yōu)先調(diào)度模型

2.1 短進程優(yōu)先調(diào)度的合作博弈算法

為了方便計算，假設(shè)飛機的除冰時刻是從0時刻開始的，這樣就大大簡化了計算的過程。我們假設(shè)是飛機進行到第個進程的時候要除冰的時間。是個進程的完成瞬間。對上一節(jié)的除冰模型進行短進程處理：

不難得到，對總延誤時間的影響最大，擁有最大的權(quán)重系數(shù)。然后依次是，具有次權(quán)重系數(shù)，以此類推，最后一個進程為最小的權(quán)重系數(shù)。在飛機的除冰過程中，小型與中型飛機占飛機總數(shù)的大部分，所以優(yōu)先對小型與中型飛機進行除冰，即小型中型飛機的在除冰進程的前面，權(quán)重系數(shù)影響較大，對總延誤時間的影響最小[3]。

我們選取類似波音737的飛機，假定為A型機為小型機。類似波音747的飛機，假定為B型機為中型機。類似空客A—380的飛機，假定為C型機為大型機。因為除冰坪的大小有限，選取大部分機場所使用的除冰坪大小，可以同時處理兩架A型機或一架B型，C型機。機場數(shù)據(jù)反應(yīng)，A型機的除冰時間7分鐘，B型機的除冰時間10分鐘，C型機的除冰時間15分鐘。一般機場的除冰坪數(shù)量保持不變，以航班的起飛確定，實際起飛前5分鐘已經(jīng)完成所有工作為前提。根據(jù)之前已經(jīng)得到0時刻開始的飛機除冰總延誤時間，當規(guī)定為個進程飛機原定起飛時間，得到更具有實際意義的短進程優(yōu)先調(diào)度的總延誤時間：

綜上，要想總延誤時間最短，當資源有限的時候，對小型機的優(yōu)先除冰，可以得到很好的效果。

在對小型機進行優(yōu)先調(diào)度的同時，還應(yīng)該考慮到航空公司，機場調(diào)度中心，地面服務(wù)公司三者之間的利益平衡問題，我們首先使用合作博弈的方法解決這個問題。在合作博弈中，是以小型機優(yōu)先調(diào)度為前提，合作利益大于單個利益之和，同時在合作方之間的利益分配公平。

我們以合作博弈中的基本問題“二人合作博弈”進行研究。兩個除冰主體任何一個都不能對整體做出策略要求，而是雙方進行合理的分配的方案。那么在兩者之間就會存在著一些諸如利益轉(zhuǎn)讓、分割等問題。所以要考慮雙方的風(fēng)險態(tài)度和主觀效用評價。但是，任何合作都是不牢靠的，當博弈雙方的合作關(guān)系破裂時，雙方依然能夠得到一些利益，這種談判破裂時雙方的利益稱為“談判破裂點”，通常用表示，其中是博弈方在談判破裂時可以得到的利益[4]。

我們假設(shè)，為除冰的資源的分配集合，可以得到，m是最大的可分配期望支付。，每個除冰的主體自身利益的函數(shù)。那么，，為兩個除冰主體各自的利益函數(shù)。我們就可以得到合作博弈三元數(shù)組：

2.2 短進程優(yōu)先調(diào)度的非合作博弈算法

短進程優(yōu)先算法與上一節(jié)一樣。分析非合作博弈算法，非合作博弈與合作博弈相反，在此算法中沒有合作存在，統(tǒng)一對資源進行爭奪。此時必須進行好合理的資源調(diào)度方案。把航空公司，機場調(diào)度中心，地面服務(wù)公司三者看成非合作博弈的三個博弈方，三者之間是相互聯(lián)系的，與合作博弈不同，非合作博弈每個博弈方都有自己的決策函數(shù)[5]。

假設(shè)是航空公司，是機場調(diào)度中心，是地面服務(wù)公司。是航空公司的申請策略集合，是機場調(diào)度中心分配的優(yōu)先級，是機場調(diào)度中心的決策集合。是決策時的資源效用[6]。最終得到非合作博弈算法：

3仿真結(jié)果與分析

以北京首都國際機場的某天的航班數(shù)據(jù)為仿真數(shù)據(jù)，使用python進行仿真。在各大機場中一般除冰坪的數(shù)量是小于等于4的，我們來計算短進程優(yōu)先調(diào)度的合作博弈算法和非合作博算法以及先到先服務(wù)的算法，三者之間進行比較。最終得到仿真結(jié)果如下折線圖：

最終總結(jié)如下表1。

4結(jié)束語

使用了短進程優(yōu)化調(diào)度下的合作博弈算法和非合作博弈算法，發(fā)現(xiàn)短進程優(yōu)先調(diào)度的方法利用了小型機優(yōu)先調(diào)度的時間少的除冰優(yōu)勢，最大限度地將有限資源利用減少總延誤時間，與先到先服務(wù)的方法比較有很大優(yōu)勢。而且在三方利益平衡方面，短進程下的合作博弈算法更有優(yōu)勢，所以可以使用小型機優(yōu)先除冰調(diào)度的方法下的合作博弈算法，將會使延誤時間最小化，利益最均勻化。

參考文獻

[1] 石旭東，王立文，劉勝飛.飛機集中除冰車輛優(yōu)化調(diào)度方法研究[J].計算機工程與應(yīng)用，2009，45（4）：218-220.

[2] 邢志偉，唐廣群，任準.多除冰坪排隊飛機除冰過程調(diào)度非合作博弈[J].信息與控制，2013，42（4）：511-515.

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

[4] XingZhiwei，LiJunhui.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.

[5] Voulgarellis P G，Christodoulou M A，Boutalis Y S. A MATLAB Based Simulation Language for Aircraft Ground Handling Operations at Hub Airports （SLAGOM）[C].Intelligent Control，2005. Proceedings of the 2005 IEEE International Symposium on，Mediterrean Conference on Control and Automation. IEEE，2005：334-339.

[6] MAO XY，MORS AT，ROOS N，et al. Agent-Based Scheduling for Aircraft Deicing[C]. Proceedings of the 18th Belgium-Netherlands Conference on Artificial Intelligence，2007：229-236.