基于模擬退火算法的單機(jī)場(chǎng)地面等待優(yōu)化策略

張虹 熊靜 黃曉丹 尤闊闊 張文成

摘 要： 隨著航空運(yùn)輸需求的不斷增加，導(dǎo)致各大機(jī)場(chǎng)時(shí)隙資源緊張，很多航班不能按時(shí)降落，只能在空中排隊(duì)等待降落。文章研究了基于模擬退火算法的單機(jī)場(chǎng)地面等待優(yōu)化策略，將空中等待策略轉(zhuǎn)變?yōu)榈孛娴却呗?，讓未起飛航班在原機(jī)場(chǎng)等待避開高峰期并對(duì)時(shí)隙進(jìn)行重新分配。這不僅可以極大的減少航空公司延誤損失，還可以提高安全性。最后利用真實(shí)數(shù)據(jù)在Python中仿真測(cè)試得出結(jié)果并和RBS算法進(jìn)行對(duì)比，最終結(jié)果表明，使用模擬退火算法相對(duì)RBS算法可以減少航空公司延誤損失的27.9%。

關(guān)鍵詞： 地面等待； 模擬退火算法； RBS算法； 時(shí)隙

中圖分類號(hào)：V355 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1006-8228（2019）03-09-04

Simulated annealing algorithm based single airport ground waiting optimization strategy

Zhang Hong， Xiong Jing， Huang Xiaodan， You Kuokuo， Zhang Wencheng

（Shanghai University of Engineering Science， Air Transport Institute， Shanghai 201600， China）

Abstract： With the increasing demand for air transportation， the time slot resources of major airports are tight， and many flights cannot land on time and can only wait in line in the air for landing. In this paper， the optimization strategy of single airport ground waiting based on simulated annealing algorithm is studied， and the air waiting strategy is changed into the ground waiting strategy， so that non-departing flights can wait at the original airport to avoid the rush hour and reallocate the time slot， which can not only greatly reduce airline delay losses but also improve safety. Finally， the simulation results in Python with real data are compared with RBS algorithm. The final results show that the simulated annealing algorithm can reduce the delay loss of airlines by 27.9% compared with RBS algorithm.

Key words： ground waiting； simulated annealing algorithm； RBS algorithm； time slot

0 引言

人們對(duì)航空運(yùn)輸?shù)男枨笳鸩綌U(kuò)大，空中交通越來越擁擠。機(jī)場(chǎng)遇到惡劣天氣時(shí)，很多航班不能按計(jì)劃起飛。而如果航班不能按時(shí)降落，那么飛機(jī)就不得不在空中等待，這不僅會(huì)增加危險(xiǎn)系數(shù)，還會(huì)導(dǎo)致巨大的延誤損失。如果預(yù)知目的機(jī)場(chǎng)擁擠時(shí)，可以讓未出發(fā)的飛機(jī)在原機(jī)場(chǎng)等待即實(shí)施地面等待策略。

在實(shí)行地面等待策略時(shí)，空中交通流量管理部門統(tǒng)一將時(shí)隙進(jìn)行重新分配，從而達(dá)到延誤成本最小化的目標(biāo)。地面等待策略主要有兩大研究方向，分別是集權(quán)式分配方式和分布式分配方式。本文主要研究集權(quán)式分配方式。用集權(quán)式分配方式研究地面等待策略是短期高效策略中的一種重要方式。

1987年，Odoni首次系統(tǒng)地闡述了空中交通流量問題的研究領(lǐng)域、基本概念和主要問題，提出了重新安排飛機(jī)起飛時(shí)間以使擁擠成本最小化的思想[1]。1989年Terrab和Odoni將單機(jī)場(chǎng)確定型模型轉(zhuǎn)化成了網(wǎng)絡(luò)流模型，提出用最小費(fèi)用流來求解模型[2]。2001年P(guān)ulugurtha1等將人工智能遺傳算法引入到GHP問題中，采用遺傳算法求解靜態(tài)模型[3]，加快了模型求解的速度，促進(jìn)了GHP模型在實(shí)際中的應(yīng)用。2017年，Roland Deroo主要提出了一種新的基于運(yùn)籌學(xué)方法的出發(fā)排序算法，進(jìn)而可以進(jìn)一步優(yōu)化時(shí)隙的分配問題[4]。

2016年，田勇在基于突發(fā)事件下導(dǎo)致的機(jī)場(chǎng)容量急劇下降的情況下，首次引入生物地理學(xué)優(yōu)化算法對(duì)建立的進(jìn)離場(chǎng)時(shí)隙分配模型進(jìn)行求解[5]。2016年，吳東暉在基于突發(fā)事件的基礎(chǔ)上提出了對(duì)起飛和未起飛航班的延誤成本進(jìn)行區(qū)分研究，并建立機(jī)場(chǎng)突發(fā)事情機(jī)場(chǎng)時(shí)隙分配模型并利用BBO算法進(jìn)行求解[6]。2014年，陳亞青對(duì)基于CDM下GHP時(shí)隙分配和模型進(jìn)行研究，并提出了未來的研究方向主要是對(duì)隨機(jī)容量的研究[7]。2014年，樊憲標(biāo)提出了在考慮了不確定天氣信息的影響下，結(jié)合靜態(tài)時(shí)隙的不足之處建立了動(dòng)態(tài)時(shí)隙配置模型[8]。

從近幾年的研究看，對(duì)集權(quán)式分布的研究較多，而少有人用模擬退火算法對(duì)此問題進(jìn)行分析。我們經(jīng)過分析認(rèn)為，將時(shí)隙分配問題當(dāng)成一個(gè)指派問題來求解，得出的方案更優(yōu)。本文利用模擬退火算法將時(shí)隙分配問題當(dāng)成工人工作的指派問題來求解，最終得出的結(jié)果是可以減少航空公司的延誤損失。

1 單機(jī)場(chǎng)地面等待策略模型

在建立單機(jī)場(chǎng)地面等待策略模型之前，我們先作如下假設(shè)。

⑴ 在時(shí)間段[0，T]內(nèi)，目的機(jī)場(chǎng)Z的航班著陸出現(xiàn)擁擠，且目的機(jī)場(chǎng)Z是空中交通網(wǎng)絡(luò)中惟一的容量限制單元和唯一產(chǎn)生航班延誤的原因。

⑵ 有N個(gè)航班（F1、F2…Fn）預(yù)計(jì)在[0，T]內(nèi)到達(dá)目的機(jī)場(chǎng)且每個(gè)航班的起飛時(shí)間和飛行時(shí)間是已知并且確定的，并且所有航班最后都在[0，T]內(nèi)到達(dá)。

⑶ 時(shí)間區(qū)間[0，T]內(nèi)，機(jī)場(chǎng)容量c（T）已知。根據(jù)c（T）變化，把時(shí)間區(qū)間[0，T]劃分為n個(gè)著陸時(shí)間段，每個(gè)著陸時(shí)間段內(nèi)有且只有一架航班著陸。航班Fi的地面等待成本系數(shù)，i∈{1，2，…，N}已知。

根據(jù)假設(shè)建立地面等待策略的成本最小化模型：

2 算法介紹

2.1 RBS算法

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

⑴ 首先按免除航班、執(zhí)行過地面等待程序的航班、其他航班這三類。

⑵ 對(duì)每一類航班按最初的時(shí)刻表順序排序。

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

2.2 模擬退火算法

模擬退火算法是模仿自然界退火現(xiàn)象而得，利用了物理中固體物質(zhì)的退火過程與一般優(yōu)化問題的相似性從某一初始溫度開始，伴隨溫度的不斷下降，結(jié)合概率突跳特征在解空間中隨機(jī)尋找全局最優(yōu)解。模擬退火算法的計(jì)算步驟如下。

⑴ 初始化、任選初始解，i∈S，給定初始溫度T0，終止溫度Tf，令迭代指標(biāo)k=0，Tk=T0。

⑵ 隨機(jī)產(chǎn)生一個(gè)領(lǐng)域解，j∈N（i）（N（i）表示的領(lǐng)域）計(jì)算目標(biāo)值增量Δf=f（j）-f（i）。

⑶ 若Δf<0，則令i=j轉(zhuǎn)⑷（j比i好，無條件轉(zhuǎn)移）；否則產(chǎn)生ε∈U（0，1），若exp（-Δf/Tk）>ε，則令i=j（j比i好，有條件轉(zhuǎn)移）。

注：Tk高時(shí)，廣域搜索；Tk低時(shí)，局域搜索。

⑷ 若達(dá)到熱平衡（內(nèi)循環(huán)次數(shù)大于n（Tk））轉(zhuǎn)⑸，否則轉(zhuǎn)⑵。

⑸ k=k+1降低Tk，若Tk

注：降低Tk的方法有兩種。一是Tk+1=Tk*r，其中r∈（0.95-0.99）（優(yōu)點(diǎn)：簡(jiǎn)單易行）。二是Tk+1=Tk-ΔT。

3 算例驗(yàn)證

結(jié)合實(shí)際情況，我們選取某機(jī)場(chǎng)4點(diǎn)-5點(diǎn)之間的實(shí)際數(shù)據(jù)。由于天氣原因，飛機(jī)的降落架數(shù)由10架降為了5架，對(duì)此執(zhí)行地面等待策略， 由于飛機(jī)的尾流類型不同，延誤成本也有所不同，按照國際民航組織（ICAO）的標(biāo)準(zhǔn)，并按照飛機(jī)的尾流強(qiáng)弱，將飛機(jī)分為3類，如表1所示。在表1的基礎(chǔ)上，根據(jù)上述模型建立成本矩陣M。

本文將此優(yōu)化問題轉(zhuǎn)變成工作指派問題，將控制進(jìn)場(chǎng)的時(shí)間看作工人，將原計(jì)劃進(jìn)場(chǎng)時(shí)間看作工作，將控制進(jìn)場(chǎng)時(shí)間分配給原計(jì)劃進(jìn)場(chǎng)時(shí)間之差為航班延誤時(shí)間，將此延誤時(shí)間看作工人所做工作時(shí)間。但需要注意的是控制進(jìn)場(chǎng)時(shí)間不可早于計(jì)劃時(shí)間，只可以晚于計(jì)劃時(shí)間，而工作指派問題中沒有這一問題，因此成本矩陣中，將早于計(jì)劃時(shí)間的情況用無窮大的成本數(shù)字表示（這邊用10000表示），保證程序指派時(shí)會(huì)跳過這些組合并通過單機(jī)場(chǎng)地面等待模型可得出成本矩陣M如下：

將上述成本矩陣M導(dǎo)入模擬退火算法中，在python下進(jìn)行仿真運(yùn)算，運(yùn)行結(jié)果如圖1所示，將運(yùn)行結(jié)果和RBS算法對(duì)時(shí)隙的分配結(jié)果作對(duì)比，對(duì)比結(jié)果如表2所示。其中表2的OTA/OTD指的是初始計(jì)劃進(jìn)離場(chǎng)時(shí)間，CTA/CTD指的是控制進(jìn)離場(chǎng)時(shí)間。

由上述運(yùn)行結(jié)果可知，最終的運(yùn)行結(jié)果在10226終止，說明最優(yōu)結(jié)果為10226。將上述仿真結(jié)果統(tǒng)計(jì)如表2。

本文將航班的時(shí)隙分配問題轉(zhuǎn)化為指派問題之后，運(yùn)用模擬退火算法對(duì)所有時(shí)隙進(jìn)行指派研究，最后得出延誤損失為10266相比RBS算法分配結(jié)果所得延誤損失減少了27.9%?？芍\(yùn)用模擬退火算法并將時(shí)隙分配優(yōu)化問題轉(zhuǎn)化為指派問題可以有效的減少延誤損失。

4 結(jié)束語

本文研究了基于模擬退火算法的單機(jī)場(chǎng)地面等待策略并進(jìn)行了仿真實(shí)驗(yàn)，主要是通過模擬退火算法將單機(jī)場(chǎng)時(shí)隙分配優(yōu)化問題轉(zhuǎn)化為類似工人工作的指派問題，將控制進(jìn)/離場(chǎng)時(shí)間早于計(jì)劃進(jìn)/離場(chǎng)時(shí)間的組合用無窮大延誤數(shù)據(jù)表示，讓程序可以跳過這些組合，最終得出延誤成本最低的時(shí)隙指派組合。結(jié)果顯示，運(yùn)用本文的方法相對(duì)于RBS算法延誤成本減少了27.95%。由此可見，運(yùn)用模擬退火算法可以有效的解決時(shí)隙的分配優(yōu)化問題。本文只研究了單機(jī)場(chǎng)時(shí)隙分配情況，而如今延誤一般都涉及到多機(jī)場(chǎng)，所以多機(jī)場(chǎng)時(shí)隙分配策略也將是我們研究的重點(diǎn)。

參考文獻(xiàn)（References）：

[1] Odoni A R.The flow management problem in air traffic

control[C]//Flow control of congested networks. Berlin： Springer-Verlag，1987：269-298

[2] AIAA. Ground-holding strategies for ATC flow control[J].

[3] Pulugurtha S S， Nambisan S S. Using Genetic Algorithms

to Evaluate Aircraft Ground Holding Policy in Real Time[J]. Journal of Transportation Engineering，2001.127（5）：442-448

[4] Deroo R， Gama A. Optimization of Take-Off Runway

Sequences for Airports Under a CDM Framework[M]//Applied Simulation and Optimization 2. Springer International Publishing，2017.

[5] 田勇，吳東暉，萬莉莉等.基于突發(fā)事件的機(jī)場(chǎng)進(jìn)離場(chǎng)時(shí)隙分

配研究[J].武漢理工大學(xué)學(xué)報(bào)（信息與管理工程版），2016.38（1）：28-32

[6] 吳東暉.機(jī)場(chǎng)時(shí)隙分配優(yōu)化技術(shù)研究[D].南京航空航天大學(xué)，

2016.

[7] 陳亞青，羅亮.基于CDM的GHP時(shí)隙分配模型和算法研究[J].

中國西部科技，2014.12：3-5

[8] 樊憲標(biāo).機(jī)場(chǎng)時(shí)隙資源協(xié)同動(dòng)態(tài)配置研究[D].南京航空航天

大學(xué)，2014.