基于CDM機制下不同航空公司的時隙分配研究

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

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

關鍵詞：航空運輸;Compression算法;固定優(yōu)先權TTC算法;時隙交換;CDM

中圖分類號：U8? ? ? 文獻標志碼：A? ? ? 文章編號：1673-291X（2019）02-0184-03

引言

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

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

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

一、算法介紹

（一）RBS算法

RBS算法用于初次分配機場進場的時隙資源，主要流程如下：

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

（2）對每一類航班按最初的時刻表順序排序;

（3）將所有的可用時隙進行升序排列，然后依次排給航班隊列中的每一個航班。

（二）Compression算法+TTC算法

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

具體算法步驟如下所示：

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

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

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

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

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

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

（一）變量定義

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

（二）數(shù)學模型

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

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

三、算例驗證

（一）假設條件

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

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

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

（3）旅客延誤時間為計劃進出場時間與初始進出場時間的差值。

（二）實例分析

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

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

結語

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

參考文獻：

[1]? 胡明華，徐肖豪.空中交通流量控制的地面保持策略[J].南京航空航天大學學報，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時隙初始分配公平性研究[J].指揮信息系統(tǒng)與技術，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.