李連成?喬迪

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

關(guān)鍵詞 資源有限;短進(jìn)程合作博弈;短進(jì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ù)量在各大機(jī)場都有了大幅度的增長，那么在入冬之后如若遇到除冰坪數(shù)量不夠或除冰所需設(shè)備緊缺的情況下，對有限資源的合理調(diào)度成為影響飛機(jī)航班延誤，乘客滯留的關(guān)鍵問題。目前我國大部分機(jī)場依然使用著先到先服務(wù)的除冰調(diào)度方案。該方案雖然可實(shí)施性最高，但是存在著除冰效率較低，飛機(jī)延誤情況出現(xiàn)較多的問題。所以一些更為優(yōu)化的方案急需被引用。

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

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

1除冰建模

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

表示的飛機(jī)剛進(jìn)入停機(jī)坪的那一時刻，表示的飛機(jī)除冰完成的那一時刻，表示的飛機(jī)的除冰時間。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4結(jié)束語

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

參考文獻(xiàn)

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

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

[3] 邢志偉，喬曉輝.飛機(jī)地面除冰運(yùn)行的非合作博弈研究[J].系統(tǒng)仿真學(xué)報(bào)，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.