基于CDM機(jī)制下不同航空公司的時(shí)隙分配研究

張虹 熊靜 黃曉丹 徐露 李洋 高佩

摘 要：研究了航空公司基于CDM機(jī)制下對(duì)時(shí)隙進(jìn)行二次指派的問(wèn)題。首先運(yùn)用RBS算法對(duì)航班進(jìn)行初次分配，之后結(jié)合Compression算法和固定優(yōu)先權(quán)TTC算法提出了一種新的算法對(duì)時(shí)隙進(jìn)行二次分配，并利用此算法和遺傳算法同時(shí)對(duì)模型進(jìn)行求解。最后應(yīng)用國(guó)內(nèi)某機(jī)場(chǎng)的實(shí)際數(shù)據(jù)進(jìn)行仿真驗(yàn)證，結(jié)果表明，所提算法在對(duì)時(shí)隙的分配中相比RBS算法和遺傳算法不僅可以使得延誤成本減少，而且可以均衡不同航空公司的平均延誤成本。

關(guān)鍵詞：航空運(yùn)輸;Compression算法;固定優(yōu)先權(quán)TTC算法;時(shí)隙交換;CDM

中圖分類號(hào)：U8? ? ? 文獻(xiàn)標(biāo)志碼：A? ? ? 文章編號(hào)：1673-291X（2019）02-0184-03

引言

如今，隨著人們生活水平的日益提高，人們出行對(duì)于舒適度和快速度的需求日益增長(zhǎng)，以至于在伴隨著民航運(yùn)輸業(yè)快速發(fā)展的同時(shí)，空域機(jī)場(chǎng)容量供給并不足以充分提供。尤其在發(fā)生惡劣天氣的情況下，機(jī)場(chǎng)容量大幅度下降，時(shí)隙資源緊張，多數(shù)航班不能按時(shí)降落，只能在空中盤旋等待，不僅增加了危險(xiǎn)性還消耗了巨大成本。如今解決這一問(wèn)題的主要方法是利用地面等待程序（GDP）[1]讓沒(méi)有起飛的航班在機(jī)場(chǎng)等待，因?yàn)榈孛娴却杀具h(yuǎn)低于空中等待，而且采取地面等待代替空中等待這一策略在減少成本的同時(shí)還降低危險(xiǎn)系數(shù)。通過(guò)地面等待策略改變飛機(jī)的起飛時(shí)間，從而避開(kāi)擁堵的時(shí)間段，這關(guān)系到時(shí)隙的分配問(wèn)題。時(shí)隙的分配通常由空管部門決定，這實(shí)際上忽視了航空公司的實(shí)際決策目標(biāo)。本文主要研究基于CDM（協(xié)同決策機(jī)制）下航空公司根據(jù)各自的決策目標(biāo)和空管局共同決策時(shí)隙的二次分配問(wèn)題，從而提高時(shí)隙的利用率。

基于CDM機(jī)制下時(shí)隙研究的國(guó)內(nèi)外文獻(xiàn)主要有，T Vossen等[2]主要研究了航空公司自主支配時(shí)隙資源和與別的航空公司相互交換時(shí)隙資源，將時(shí)隙交換看做易貨流程，并且將優(yōu)化問(wèn)題與當(dāng)前交換時(shí)隙資源程序進(jìn)行比較，討論航空公司提高決策能力的可能性。TWM Vossen等[3]研究了FAA與航空公司之間的數(shù)據(jù)交換策略，允許航空公司之間的交換航班時(shí)刻，并開(kāi)發(fā)了一套整數(shù)規(guī)劃模型，有助于優(yōu)化其內(nèi)部成本函數(shù)。張榮等[4]研究了CDM GDP機(jī)場(chǎng)資源的公平分配問(wèn)題，提出了基于延誤成本公平分配的新的協(xié)同地面等待優(yōu)化模型，并利用遺傳算法對(duì)模型進(jìn)行求解并與RBS算法作了對(duì)比。JW Bono 等[5]研究了GDP期間分配到的時(shí)隙的可能性，利用預(yù)測(cè)博弈論進(jìn)行分析，對(duì)個(gè)航空公司的空余時(shí)隙進(jìn)行拍賣。

綜上可知，如今基于CDM機(jī)制下對(duì)時(shí)隙的研究主要集中在兩方面，一方面是對(duì)時(shí)隙交換的研究，另一方面是對(duì)時(shí)隙拍賣的研究。但是在時(shí)隙交換的研究上少有對(duì)不同航空公司時(shí)隙交換所帶來(lái)的公平性進(jìn)行研究。本文主要研究基于CDM機(jī)制下對(duì)時(shí)隙進(jìn)行二次分配，并提出新的算法對(duì)模型求解降低延誤成本的同時(shí)均衡各航空公司航班的公平性。

一、算法介紹

（一）RBS算法

RBS算法用于初次分配機(jī)場(chǎng)進(jìn)場(chǎng)的時(shí)隙資源，主要流程如下：

（1）首先按免除航班、執(zhí)行過(guò)地面等待程序的航班、其他航班分為三類;

（2）對(duì)每一類航班按最初的時(shí)刻表順序排序;

（3）將所有的可用時(shí)隙進(jìn)行升序排列，然后依次排給航班隊(duì)列中的每一個(gè)航班。

（二）Compression算法+TTC算法

本文所提出的算法主要是針對(duì)各航空公司具有相同目的且不需要取消航班，從而也可達(dá)到延誤成本公平化目標(biāo)所設(shè)計(jì)的。本文提出的算法借用了TTC算法中的根據(jù)決策目標(biāo)確定時(shí)隙優(yōu)先級(jí)的思想，并且借用了Compression算法某航空公司取消航班后該航空公司其余航班具有優(yōu)先級(jí)的思想，并且考慮到多個(gè)航空公司的延誤成本（決策目標(biāo)而定）相對(duì)公平。本文采用輪換優(yōu)先級(jí)使得多個(gè)航空公司公司輪換進(jìn)行選擇時(shí)隙，從而可以達(dá)到選擇時(shí)隙的公平性。

具體算法步驟如下所示：

（1）首先將所有的航班按照目標(biāo)時(shí)隙的升序排列得到了p，將a航空公司的航班排序記為p、將b航空公司的航班排序記為p，假設(shè)航空公司多的話以此類推。

（2）將時(shí)隙航班表初次排列記為S。

（3）首先從RBS算法對(duì)航班進(jìn)行的初次分配中給第一個(gè)航班賦予最高優(yōu)先級(jí)，讓第一個(gè)航班自由選擇一個(gè)期望的時(shí)隙。

（4）判斷第一個(gè)航班是屬于哪個(gè)航空公司的，假如是屬于a航空公司的，則在升序排列的p中找到排列在后面且機(jī)型是輕機(jī)型的飛機(jī)，若沒(méi)有輕機(jī)型的飛機(jī)則選擇中機(jī)型的飛機(jī);依此類推，若有好幾個(gè)相似的機(jī)型則根據(jù)升序排列的p中那幾個(gè)相似機(jī)型中選擇排列最后面的航班，讓這個(gè)航班去執(zhí)行時(shí)隙航班表S中最后的一個(gè)時(shí)隙。

（5）a航空公司執(zhí)行完之后，輪換到b航空公司執(zhí)行。在p中首先尋找機(jī)型是H的航班首先執(zhí)行，其次執(zhí)行機(jī)型是M的航班最后執(zhí)行機(jī)型是L的航班，若有好幾班相似的機(jī)型則選擇p中排序相對(duì)最上的一個(gè)航班。首先讓其選擇一個(gè)期望時(shí)隙，緊接著在p中選擇相對(duì)排列在后且是輕機(jī)型的飛機(jī)，若沒(méi)有輕機(jī)型則選擇中機(jī)型;依此類推，若有好幾個(gè)相似的機(jī)型則根據(jù)升序排列的p中相似機(jī)型中排列最后的航班，讓這個(gè)航班選擇S時(shí)隙中倒數(shù)第二個(gè)時(shí)隙。依此類推，重復(fù)執(zhí)行步驟（4）和步驟（5）直至所有航空公司的航班都安排了時(shí)隙。

二、建立數(shù)學(xué)模型

（一）變量定義

根據(jù)上訴算法和下述模型相關(guān)參數(shù)解釋如下：

（二）數(shù)學(xué)模型

本文基于CDM機(jī)制下航空公司自由指派時(shí)隙，最終使得各個(gè)航空公司的每個(gè)航班延誤成本均衡，由此可以提高航空公司的積極性。

目標(biāo)函數(shù)為每個(gè)航空公司的每個(gè)航班的平均延誤成本與所有航空公司每個(gè)航班的平均延誤成本之差的絕對(duì)值：

三、算例驗(yàn)證

（一）假設(shè)條件

首先根據(jù)模型做出如下假設(shè)：

（1）空管部門提供的時(shí)隙都是已知的;

（2）所有航空公司都可以自由分配時(shí)隙;

（3）旅客延誤時(shí)間為計(jì)劃進(jìn)出場(chǎng)時(shí)間與初始進(jìn)出場(chǎng)時(shí)間的差值。

（二）實(shí)例分析

根據(jù)文獻(xiàn)[4]中對(duì)廣州機(jī)場(chǎng)2008年某日4點(diǎn)到5點(diǎn)的實(shí)際數(shù)據(jù)，利用遺傳算法進(jìn)行處理的結(jié)果，本文在此基礎(chǔ)上對(duì)該實(shí)際數(shù)據(jù)運(yùn)用本文算法進(jìn)行處理，結(jié)果表明，本文算法相比遺傳算法可以得出更優(yōu)化的平均延誤成本。

首先該實(shí)際數(shù)據(jù)中涉及到10架飛機(jī)，有5架飛機(jī)屬于CAG航空公司，另外5架屬于CES航空公司，這10架飛機(jī)參與了當(dāng)天下午的地面等待程序（GDP），地面等待程序的時(shí)間由下午4：00到5：48。兩個(gè)航空公司在CDM機(jī)制基礎(chǔ)下對(duì)時(shí)隙進(jìn)行二次分配。由于不同航空器的運(yùn)營(yíng)成本不同，航班進(jìn)行時(shí)隙選擇時(shí)首先要考慮運(yùn)營(yíng)成本較高的航班，各類飛機(jī)延誤運(yùn)營(yíng)成本見(jiàn)表1。在對(duì)航班時(shí)刻表分別利用RBS算法進(jìn)行初次指派和利用本文算法和遺傳算法進(jìn)行二次指派結(jié)果，如表2所示。

結(jié)語(yǔ)

本文研究了在機(jī)場(chǎng)時(shí)隙資源短缺情況下航空公司結(jié)合自身決策目標(biāo)參與對(duì)時(shí)隙進(jìn)行的二次分配問(wèn)題。由于目前少有對(duì)航空公司公平性進(jìn)行研究，本文首先結(jié)合compression算法和固定優(yōu)先權(quán)TTC算法總結(jié)出一種新的算法，其次利用該算法對(duì)航空公司不取消航班情況下建立的模型進(jìn)行求解。最終分配結(jié)果顯示，相比RBS算法和遺傳算法對(duì)模型的求解結(jié)果來(lái)看，本文算法不僅能降低航空公司總延誤成本，同時(shí)更能均衡航空公司平均延誤成本。然而，本文主要只考慮了航班延誤的顯性成本，下一步可以將航班延誤成本中的隱形成本考慮進(jìn)來(lái)。

參考文獻(xiàn)：

[1]? 胡明華，徐肖豪.空中交通流量控制的地面保持策略[J].南京航空航天大學(xué)學(xué)報(bào)，1994，（S1）：26-30.

[2]? Vossen T W M，Ball M O.Slot Trading Opportunities in Collaborative Ground Delay Programs[J].Transportation Science，2006，40（1）：29-43.

[3]? Vossen T，Ball M.Optimization and mediated bartering models for ground delay programs[J].Naval Research Logistics，2010，53（1）：75-90.

[4]? 張榮，周小數(shù).CDM時(shí)隙初始分配公平性研究[J].指揮信息系統(tǒng)與技術(shù)，2010，1（2）：51-55.

[5]? Bono J W，Wolpert D，Xie D，et al.Decision-Theoretic Prediction and Policy Design of GDP Slot Auctions[J].Ssrn Electronic Journal，2011，3（1）：232-235.