基于效率性和公平性的GDP時隙分配研究

李永慶，田 勇

(南京航空航天大學 民航學院，江蘇 南京 210016)

近幾年來，隨著我國航空運輸業(yè)的迅猛發(fā)展，空中交通量大幅增長，機場擁堵問題越來越突出.地面延誤程序(GDP-Ground Delay Program)是空中交通流量管理中解決機場擁堵問題的一種有效措施.如何有效、合理、公平地分配時隙是GDP中的核心問題.國外對時隙分配已有一定研究，如RBS(Ration-By-Schedule)[1]算法、RBD(Ration-By-Distance)[2]算法等，國內也有學者對時隙分配問題提出了基于公平性或效率性的時隙分配模型，但很少有人提出同時兼顧效率和公平的時隙分配機制與方法[3].

若僅考慮時隙分配的效率性，雖然能減少機場總的延誤成本，但航空公司承擔的延誤成本不能公平地分配，航空公司難以接受時隙分配的結果；若僅考慮時隙分配的公平性，雖然能保證各航空公司的時隙分配的公平性，但不能保證時隙分配的整體效率性.本文對效率性和公平性均衡的時隙分配方法進行了研究，通過建立均衡化數(shù)學模型實現(xiàn)時隙分配的總體最優(yōu)性.

1 時隙分配模型

本文研究的地面等待策略旨在尋找效率性和公平性均衡的時隙分配方案，使時隙分配更趨合理.時隙分配的效率性是指時隙分配能高效的利用時隙資源，減少機場總的延誤成本，公平性是指航空公司之間公平合理地分配時隙資源[4].

數(shù)學模型可表示為：

(1)

約束條件：

(2)

(3)

tj

(4)

(5)

主要參數(shù)說明如下：

F={f1，f2,…,fn}為參與地面等待的航班，f1∈F；S={s1,s2,…,sm}為機場執(zhí)行GDP期間的可用時隙，由GDP執(zhí)行期間機場單位每小時可接受的著陸航班數(shù)量(Arrival Acceptance Rate, AAR)來確定，sj∈S；tj為時隙sj的起始時間；ostai為表示航班fi的時刻表初始計劃著陸的時間；xij為二進制決策變量，當航班fi選擇了時隙sj時為1，否則為0；cij為航班fi分配到時隙sj時所引發(fā)的航班延誤成本.

約束條件主要是對時隙分配的有效性進行約束，式(2)表示每個航班必須分配到一個時隙；式(3)表示一個時隙最多只能被一個航班使用；式(4)表示航班實際的著陸時間不能早于初始時刻表中計劃的著陸時間.

2 公平性約束

時隙分配的公平性問題不能忽略，但公平性與效率性往往互為矛盾，追求公平往往會帶來效率的下降[6].為實現(xiàn)時隙分配在效率和公平性上的均衡，本文在總體目標函數(shù)中引入了公平性指標.

(6)

相關的，同時定義協(xié)作效率函數(shù)Pα(xij)∈[0,1]，同樣也是二進制決策變量xij的線性函數(shù).當dα(xij)=1時，Pα(xij)=1，表示效率性最好；當dα(xij)=dmax時，Pα(xij)=0，表示效率性最差.可以定義協(xié)作效率函數(shù)為：

(7)

(8)

機場總體的公平性指標可以表示為各航空公司協(xié)作公平性指標的線性加權，結合式(8)可得：

(9)

綜上所述，式(1)中的公平性決策目標可以表示為

(10)

(11)

3 遺傳算法求解

上述模型為典型的整數(shù)規(guī)劃模型，遺傳算法是基于空間搜索的算法，適用于大規(guī)模并行計算，并能夠以較大的概率尋找到最優(yōu)解，對本文的整數(shù)模型能夠較快地尋找到最優(yōu)解.算法采用式(12)所示的適應度函數(shù)，式中Tmax為航班的延誤最大估計值，f(x)為模型的目標函數(shù).

(12)

3.1 編碼策略

給每個參與GDP的航班分配時隙，構成染色體個體.航班所分配到的時隙為染色體的基因值，其值根據(jù)航班可用時隙隨機產(chǎn)生，每個時隙只允許被分配一次，這種方式得到的編碼是時隙元素的一個組合排列.

采用賭盤法(基于適應度比例)選擇個體，個體i被選中的概率為：

(13)

其中：Fi為個體的適應度值；N為種群個體數(shù)目.

3.2 交叉

交叉操作是指從種群中隨機選擇兩個個體，通過兩個染色體的交換組合，把父個體的優(yōu)秀特征遺傳給子個體，從而產(chǎn)生新的優(yōu)秀個體.為使新個體保留兩個父個體的優(yōu)良模式，本文采用單點、大片斷基因保留、小片斷基因保序的交叉方法[8]，即對于父個體1和2，隨機地選擇一個交叉位置，兩個父體的基因分成了兩部分，較長的一部分基因分別直接遺傳給它們的子個體1和2，父體1中較短一部分基因按照在父個體2中的順序重新排列后，作為子個體1的另一部分基因.同理，父體2中較短一部分基因按照在父個體1中的順序重新排列后，作為子個體2的另一部分基因.此外，為了得到可行的個體，需要判斷新個體是否滿足約束條件，如果不滿足則需重新進行交叉操作.

3.3 變異

變異操作使遺傳算法具有局部的隨機搜索能力，并可以加快算法速度.具體操作是：在染色體基因串中隨機選擇兩個交換變異點，如果兩位置處的時隙均是對應兩航班的可用時隙，則交換它們，否則重新選擇交換位置.

4 仿真驗證

為驗證理論的正確性，本文運用廣州白云國際機場的航班時刻數(shù)據(jù)進行仿真驗證.并將本文提出的時隙分配方法與現(xiàn)有的RBS算法相比較.原始數(shù)據(jù)和RBS算法分配結果如表1所示.

表1 原始數(shù)據(jù)和RBS算法分配結果

在計算航班延誤成本時，延誤成本等于延誤時間與延誤成本系數(shù)的乘積.在計算航班的延誤成本系數(shù)時，重型、中型和輕型航班的單位延誤運營成本分別設定為4 167元/h、2 916元/h和208元/h；國內、國際(要客)航班中每名旅客的平均延誤成本分別為50元/h和100元/h.在用遺傳算法求解時，選取種群規(guī)模為50，世代數(shù)為150，交叉率為0.7，變異率為0.1.見表2.

表2 本文方法與RBS算法效率性對比

本文所研究的時隙分配方法和RBS算法的公平性指標如表3所示.

表3 本文方法與RBS算法公平性指標對比

由表1、2可知，與RBS算法相比，本文所提方法的總延誤時間與RBS算法相同，但總延誤成本減少了10 869.5元，減少了近的33.4%.因此，該時隙交換方法有效的減少機場總延誤成本，體現(xiàn)了優(yōu)越的效率性.

由表3可以看出，本文提出的方法與RBS算法在時隙分配的公平性上有較大的提升，RBS算法總體公平性指標為0.28，而時隙交換后總體公平性指標為0.15，公平性指標越小，時隙分配越公平.

綜合以上數(shù)據(jù)，可以看出本文的時隙分配方法不但減少了機場總延誤成本，而且兼顧航空公司時隙分配的公平性，達到了預期的效果.

5 結 語

本文對地面等待中的效率性和公平性問題分別進行了定量分析，提出了基于效率性和公平性的地面等待數(shù)學模型，所研究的模型可以在減少機場總的延誤成本的同時兼顧航空公司之間時隙分配的公平性.

參考文獻：

[1] HOFFMAN R L, HALL W, BALL M O,etal. Collaborative decision making in air traffic flow management[R]. NEXTER Research Report, RR-99-2, UC Berkeley, 1999.

[2] BALL M O, HOFFMAN R. Ground Delay Program Planning Under Uncertainty Based on the Ration-by-Distance Principle[J]. Transportation Science, 2010, 22(1): 1-14.

[3] 張洪海，胡明華，陳世林. 基于3E均衡的CDM GDP機場時隙分配[J].人類工效學, 2010,16(3):49-52

[4] 徐肖豪，王 飛. 地面等待策略中的時隙分配模型與算法研究[J]. 航空學報，2010，31(10): 1993-2001.

[5] 徐肖豪，李 雄. 航班地面等待模型中的延誤成本分析與仿真[J].南京航空航天大學學報, 2006, 38(1): 115-120.

[6] SHERALI H D, STAATS R W, TRANI A A. An airspace planning and collaborative decision-making model: Part I—Probabilistic conflicts, workload, and equity considerations[J].Transportation Science, 2003, 37(4): 434-456.

[7] SHERALI H D, STAATS R W, TRANI A A. An airspace planning and collaborative decision-making model: Part II—Cost model, data considerations, and computations[J].Transportation Science, 2006, 40(2): 147-164.

[8] 陶世群, 浦保興. 基于遺傳算法的多級目標非平衡指派問題求解[J].系統(tǒng)工程理論與實踐, 2004, 8(4): 80-85.