李永慶，田 勇

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

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

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

1 時(shí)隙分配模型

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

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

(1)

約束條件：

(2)

(3)

tj

(4)

(5)

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

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

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

2 公平性約束

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

(6)

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

(7)

(8)

機(jī)場(chǎng)總體的公平性指標(biāo)可以表示為各航空公司協(xié)作公平性指標(biāo)的線性加權(quán)，結(jié)合式(8)可得：

(9)

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

(10)

(11)

3 遺傳算法求解

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

(12)

3.1 編碼策略

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

采用賭盤(pán)法(基于適應(yīng)度比例)選擇個(gè)體，個(gè)體i被選中的概率為：

(13)

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

3.2 交叉

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

3.3 變異

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

4 仿真驗(yàn)證

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

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

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

表2 本文方法與RBS算法效率性對(duì)比

本文所研究的時(shí)隙分配方法和RBS算法的公平性指標(biāo)如表3所示.

表3 本文方法與RBS算法公平性指標(biāo)對(duì)比

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

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

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

5 結(jié) 語(yǔ)

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

參考文獻(xiàn)：

[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ī)場(chǎng)時(shí)隙分配[J].人類工效學(xué), 2010,16(3):49-52

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

[5] 徐肖豪，李 雄. 航班地面等待模型中的延誤成本分析與仿真[J].南京航空航天大學(xué)學(xué)報(bào), 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í)目標(biāo)非平衡指派問(wèn)題求解[J].系統(tǒng)工程理論與實(shí)踐, 2004, 8(4): 80-85.