王煜清

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都　610065）

貪心策略求解單元地面等待模型

王煜清

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都610065）

1　問(wèn)題的提出

近年來(lái)，航空業(yè)發(fā)展迅猛，飛行流量的急劇增加也引起了機(jī)場(chǎng)空域和地面的擁擠。在繁忙的大機(jī)場(chǎng)，飛行高峰時(shí)段造成的交通流量飽和，影響了航班的正常運(yùn)行。這不僅造成了旅客時(shí)間上的損失，也對(duì)航空公司造成了大量的人力和財(cái)力浪費(fèi)。目前，空中交通流量管理的解決方法有長(zhǎng)期、中期和短期3種策略。地面等待策略（Ground Holding Policy，GHP）是短期策略中處理交通流量問(wèn)題的一種重要方法。本文研究單機(jī)場(chǎng)地面等待策略如何求解最優(yōu)解的問(wèn)題。

首先，對(duì)需要解決的問(wèn)題建立一個(gè)數(shù)學(xué)模型。在建立單機(jī)場(chǎng)的地面等待模型時(shí)，現(xiàn)做出如下假設(shè)：

（1）在時(shí)間區(qū)間［0，T］內(nèi)，在目的機(jī)場(chǎng)G，著陸的航班出現(xiàn)擁擠，并且機(jī)場(chǎng)G是空中交通網(wǎng)絡(luò)唯一的容量受限單元。

（3）在時(shí)間區(qū)間［0，T］內(nèi)，機(jī)場(chǎng)容量c（T）已知。根據(jù)c（T）變化，把時(shí)間區(qū)間［0，T］劃分為n個(gè)著陸時(shí)間段，每個(gè)著陸時(shí)間段內(nèi)有且僅有一架航班著陸。航班Fi的地面等待成本系數(shù)已 知。

（4）不考慮航班提前降落，等待時(shí)間不超過(guò)設(shè)定的最大等待時(shí)間。

對(duì)于單機(jī)場(chǎng)地面等待問(wèn)題而言，在滿(mǎn)足目的機(jī)場(chǎng)G容量限制的條件下，求出每個(gè)航班的最優(yōu)地面等待時(shí)間，使得總的等待損失最小。因此，可以得到目標(biāo)函數(shù)為：

式中：ti1為航班預(yù)計(jì)著陸時(shí)間；ti2為航班實(shí)際著陸時(shí)間；gi為航班Fi地面等待時(shí)間。

約束條件：

表1

式（3）表示航班不能提前著陸，最大等待時(shí)間不超過(guò)設(shè)定的?個(gè)著陸時(shí)間段。式（8）表示著陸航班數(shù)要滿(mǎn)足該時(shí)間段內(nèi)的容量要求。

2　算法原理

結(jié)合實(shí)際情況，選取有代表性的10架航班進(jìn)行算法描述，相關(guān)算例數(shù)據(jù)見(jiàn)表1和表2。

假設(shè)各個(gè)航班的地面延誤損失系數(shù)如表1。

每個(gè)航班的基本信息如表2。

表2

假設(shè)就是在14:00～14:20這20分鐘內(nèi)有上述10個(gè)航班發(fā)生了沖突，根據(jù)當(dāng)時(shí)的機(jī)場(chǎng)容量，按每?jī)煞昼娨粋€(gè)時(shí)隙，共分成10個(gè)時(shí)隙，并設(shè)定每架航班的最大延遲為5個(gè)時(shí)隙（?=5）。

算法的基本思想是在所有航班不超過(guò)最大延遲的情況下，盡量讓地面延遲損失系數(shù)大的航班延誤的時(shí)隙盡量少，采用的思想是貪心策略的思想，選取當(dāng)前的最優(yōu)解作為全局最優(yōu)解。

對(duì)于上述的10個(gè)航班，F(xiàn)1，F(xiàn)2，F(xiàn)3，都在第一個(gè)時(shí)隙發(fā)生沖突，根據(jù)貪心策略，選取其中地面延誤損失系數(shù)最大的航班F3進(jìn)行降落，并為每個(gè)航班記錄下當(dāng)前的時(shí)延，用變量ɑ表示。F3在時(shí)隙1降落，其時(shí)延為0，然后把剩下的F1，F(xiàn)2加入到時(shí)隙2的隊(duì)列中。

對(duì)于時(shí)隙2的等待隊(duì)列，此時(shí)共有4個(gè)航班（原有的F4，F(xiàn)5，和從時(shí)隙1淘汰下來(lái)的F1，F(xiàn)2）。然后再按照如同時(shí)隙1同樣的處理方式處理時(shí)隙2。

其余的時(shí)隙也是以此類(lèi)推，但是有一個(gè)問(wèn)題必須考慮，航班的餓死現(xiàn)象。航班的最大等待延遲是確定的，在對(duì)每個(gè)航班進(jìn)行延遲的時(shí)候，不能超過(guò)最大等待時(shí)延。算法對(duì)這種情況的處理方法是，當(dāng)一個(gè)航班的當(dāng)前等待時(shí)延ɑ=?時(shí)，不在對(duì)其進(jìn)行延遲，而是直接將它分配到當(dāng)前的時(shí)隙中。

3　算法正確性的證明

通過(guò)基于貪心策略的航班分配算法，可以求得此航班模型的最優(yōu)解。下面給出算法正確性和有效性的證明。

（1）我們發(fā)現(xiàn)，在上面建立的數(shù)學(xué)模型中，所有航班的延遲時(shí)隙數(shù)量之和β是一定的。因?yàn)閷?duì)于相互沖突的n個(gè)航班，選擇其中任何一個(gè)航班的降落，其余n-1個(gè)航班的ɑ都要加1。β每次加一，對(duì)應(yīng)的就是目標(biāo)函數(shù)值加上相應(yīng)的航班地面延遲損失系數(shù)。所以貪心算法選取地面損失系數(shù)最大的降落，其余的航班ɑ加1，在不超出最大等待時(shí)延的情況下是可以得到最優(yōu)解的。

（2）如果考慮航班達(dá)到最大的等待延遲，即航班的ɑ=β，不能在將此航班延遲，此航班立即降落，這樣仍可保證得到的是最優(yōu)解。反證法：假設(shè)這種情況不是最優(yōu)解，也就是說(shuō)此航班不分配此時(shí)隙時(shí)有最優(yōu)解產(chǎn)生。那么，此航班必須分配到前面的某個(gè)時(shí)隙中，而這樣會(huì)造成前面已分配的航班向后延遲，由于我們按照（1）的方式，是按照地面損失系數(shù)由大到小分配下來(lái)的，并且總的時(shí)隙數(shù)之和β一定，所以這樣分配得到的目標(biāo)函數(shù)值肯定更大。所以，原解為最優(yōu)解。

4　算法計(jì)算結(jié)果分析

針對(duì)上述的問(wèn)題實(shí)例，用該算法進(jìn)行計(jì)算。最終得到了一個(gè)最優(yōu)解，即航班序列（F3，F(xiàn)5，F(xiàn)6，F(xiàn)8，F(xiàn)2，F(xiàn)1，F(xiàn)4，F(xiàn)7，F(xiàn)10，F(xiàn)9），上面航班對(duì)應(yīng)的延遲時(shí)隙數(shù)為（0，0，0，0，4，5，5，5，4，5），后面的航班看似延遲很大，其實(shí)是由于?條件限制導(dǎo)致的，因?yàn)榍懊嫱涎酉聛?lái)的航班達(dá)到了值，必須要求降落。結(jié)合表1進(jìn)行計(jì)算，最后得出的目標(biāo)函數(shù)值（總的等待費(fèi)用）為11137元。而如果我們按照FCFS進(jìn)行航班的編排，最后目標(biāo)函數(shù)值為17996元，說(shuō)明該算法是有效的。該算法的優(yōu)點(diǎn)是，在滿(mǎn)足限制條件的情況下，它求得的解是最優(yōu)的?；谌斯~(yú)群、遺傳算法、模擬退火等算法求得的是近似值，而非最優(yōu)解。

5　結(jié)語(yǔ)

本文給出了基于貪心算法思想的單機(jī)場(chǎng)地面等待策略最優(yōu)解求解問(wèn)題，該算法可用于解決實(shí)際工作中的一些相關(guān)問(wèn)題，具有一定的實(shí)際意義。該算法之所以能求得最優(yōu)解，因?yàn)槠渲幌抻谶@種特定的數(shù)學(xué)模型，算法的通用性不強(qiáng)，如果是多機(jī)場(chǎng)、機(jī)場(chǎng)容量動(dòng)態(tài)變化時(shí)，本算法并不適用。通用性方面，目前基于搜索的算法優(yōu)于本算法，但它們的缺點(diǎn)是只能得到近似值，而且計(jì)算繁瑣。

［1］王飛，徐肖豪，張靜．基于人工魚(yú)群算法的單機(jī)場(chǎng)地面等待優(yōu)化策略［C］，2009.2.

［2］Thomas H.Cormen，Charles E.Leiserson等.算法導(dǎo)論［M］．殷建平，徐云等譯．北京：機(jī)械工業(yè)出版社，2013.1.

［3］徐肖豪，李雄．航班地面等待模型中的延誤成本分析與仿真［C］，2006.2.

［4］胡明華，徐肖豪．空中交通流量控制的地面保持策略［C］，1994.11.

Air Traffic Flow Management；Ground Waiting Strategy；Single Airport

Greedy Strategy for Solving Unit Ground Waiting Model

WANG Yu-qing
（College of Computer Science，Sichuan University，Chengdu 610065）

1007-1423（2015）29-0018-03

10.3969/j.issn.1007-1423.2015.29.005

王煜清（1991-），男，山東臨沂人，研究生，研究方向?yàn)閳D形圖像處理

2015-09-22

2015-10-12

目前大型機(jī)場(chǎng)擁塞問(wèn)題日益嚴(yán)重。當(dāng)擁塞發(fā)生時(shí)，航班的等待是難免的，如何減少因航班等待引起的開(kāi)銷(xiāo)，是值得研究的問(wèn)題。一般來(lái)說(shuō)，飛機(jī)的地面等待費(fèi)用小于在空中等待的費(fèi)用，所以，將空中等待轉(zhuǎn)化為地面等待，可以減少等待費(fèi)用，由此產(chǎn)生了很多地面等待的策略。在現(xiàn)實(shí)情況下，由于飛機(jī)的機(jī)型等因素，使得每個(gè)航班單位時(shí)間的等待費(fèi)用也不盡相同，對(duì)一個(gè)時(shí)間段內(nèi)需要降落的航班進(jìn)行一個(gè)合理的次序編排，可以進(jìn)一步地縮小由于等待造成的經(jīng)濟(jì)損失。研究單個(gè)降落機(jī)場(chǎng)在一個(gè)時(shí)間段內(nèi)如何有效地解決航班擁塞問(wèn)題，通過(guò)建立相應(yīng)的數(shù)學(xué)模型，給出求解該模型的算法，并證明算法的正確性。

空中交通流量管理；地面等待策略；單機(jī)場(chǎng)

At present，the problem of large airport congestion is becoming more and more serious.When congestion occurs，the flight waiting is inevitable，how to reduce the overhead caused by flight waiting is a problem worthy of study.Generally speaking，the ground of the aircraft is less than the cost of waiting in the air，so the air will be waiting for the ground to wait，can reduce the cost of waiting，resulting in a lot of ground waiting for the strategy.In reality，due to the aircraft's model and other factors，so that the cost of waiting for each flight unit time is not the same，the need for a period of time to land a reasonable sequence of flight arrangements，can further reduce the economic losses due to waiting.Studies how to solve the problem of flight congestion in a single landing airport，and gives the algorithm of solving the model，and proves the correctness of the algorithm.