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

王煜清

（四川大學計算機學院，成都　610065）

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

王煜清

（四川大學計算機學院，成都610065）

1　問題的提出

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

首先，對需要解決的問題建立一個數學模型。在建立單機場的地面等待模型時，現做出如下假設：

（1）在時間區間［0，T］內，在目的機場G，著陸的航班出現擁擠，并且機場G是空中交通網絡唯一的容量受限單元。

（3）在時間區間［0，T］內，機場容量c（T）已知。根據c（T）變化，把時間區間［0，T］劃分為n個著陸時間段，每個著陸時間段內有且僅有一架航班著陸。航班Fi的地面等待成本系數已 知。

（4）不考慮航班提前降落，等待時間不超過設定的最大等待時間。

對于單機場地面等待問題而言，在滿足目的機場G容量限制的條件下，求出每個航班的最優地面等待時間，使得總的等待損失最小。因此，可以得到目標函數為：

式中：ti1為航班預計著陸時間；ti2為航班實際著陸時間；gi為航班Fi地面等待時間。

約束條件：

表1

式（3）表示航班不能提前著陸，最大等待時間不超過設定的?個著陸時間段。式（8）表示著陸航班數要滿足該時間段內的容量要求。

2　算法原理

結合實際情況，選取有代表性的10架航班進行算法描述，相關算例數據見表1和表2。

假設各個航班的地面延誤損失系數如表1。

每個航班的基本信息如表2。

表2

假設就是在14:00～14:20這20分鐘內有上述10個航班發生了沖突，根據當時的機場容量，按每兩分鐘一個時隙，共分成10個時隙，并設定每架航班的最大延遲為5個時隙（?=5）。

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

對于上述的10個航班，F1，F2，F3，都在第一個時隙發生沖突，根據貪心策略，選取其中地面延誤損失系數最大的航班F3進行降落，并為每個航班記錄下當前的時延，用變量ɑ表示。F3在時隙1降落，其時延為0，然后把剩下的F1，F2加入到時隙2的隊列中。

對于時隙2的等待隊列，此時共有4個航班（原有的F4，F5，和從時隙1淘汰下來的F1，F2）。然后再按照如同時隙1同樣的處理方式處理時隙2。

其余的時隙也是以此類推，但是有一個問題必須考慮，航班的餓死現象。航班的最大等待延遲是確定的，在對每個航班進行延遲的時候，不能超過最大等待時延。算法對這種情況的處理方法是，當一個航班的當前等待時延ɑ=?時，不在對其進行延遲，而是直接將它分配到當前的時隙中。

3　算法正確性的證明

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

（1）我們發現，在上面建立的數學模型中，所有航班的延遲時隙數量之和β是一定的。因為對于相互沖突的n個航班，選擇其中任何一個航班的降落，其余n-1個航班的ɑ都要加1。β每次加一，對應的就是目標函數值加上相應的航班地面延遲損失系數。所以貪心算法選取地面損失系數最大的降落，其余的航班ɑ加1，在不超出最大等待時延的情況下是可以得到最優解的。

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

4　算法計算結果分析

針對上述的問題實例，用該算法進行計算。最終得到了一個最優解，即航班序列（F3，F5，F6，F8，F2，F1，F4，F7，F10，F9），上面航班對應的延遲時隙數為（0，0，0，0，4，5，5，5，4，5），后面的航班看似延遲很大，其實是由于?條件限制導致的，因為前面拖延下來的航班達到了值，必須要求降落。結合表1進行計算，最后得出的目標函數值（總的等待費用）為11137元。而如果我們按照FCFS進行航班的編排，最后目標函數值為17996元，說明該算法是有效的。該算法的優點是，在滿足限制條件的情況下，它求得的解是最優的。基于人工魚群、遺傳算法、模擬退火等算法求得的是近似值，而非最優解。

5　結語

本文給出了基于貪心算法思想的單機場地面等待策略最優解求解問題，該算法可用于解決實際工作中的一些相關問題，具有一定的實際意義。該算法之所以能求得最優解，因為其只限于這種特定的數學模型，算法的通用性不強，如果是多機場、機場容量動態變化時，本算法并不適用。通用性方面，目前基于搜索的算法優于本算法，但它們的缺點是只能得到近似值，而且計算繁瑣。

［1］王飛，徐肖豪，張靜．基于人工魚群算法的單機場地面等待優化策略［C］，2009.2.

［2］Thomas H.Cormen，Charles E.Leiserson等.算法導論［M］．殷建平，徐云等譯．北京：機械工業出版社，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-），男，山東臨沂人，研究生，研究方向為圖形圖像處理

2015-09-22

2015-10-12

目前大型機場擁塞問題日益嚴重。當擁塞發生時，航班的等待是難免的，如何減少因航班等待引起的開銷，是值得研究的問題。一般來說，飛機的地面等待費用小于在空中等待的費用，所以，將空中等待轉化為地面等待，可以減少等待費用，由此產生了很多地面等待的策略。在現實情況下，由于飛機的機型等因素，使得每個航班單位時間的等待費用也不盡相同，對一個時間段內需要降落的航班進行一個合理的次序編排，可以進一步地縮小由于等待造成的經濟損失。研究單個降落機場在一個時間段內如何有效地解決航班擁塞問題，通過建立相應的數學模型，給出求解該模型的算法，并證明算法的正確性。

空中交通流量管理；地面等待策略；單機場

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.