基于模擬退火算法的單機場地面等待優化策略

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

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

關鍵詞： 地面等待； 模擬退火算法； RBS算法； 時隙

中圖分類號：V355 文獻標志碼：A 文章編號：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 引言

人們對航空運輸的需求正逐步擴大，空中交通越來越擁擠。機場遇到惡劣天氣時，很多航班不能按計劃起飛。而如果航班不能按時降落，那么飛機就不得不在空中等待，這不僅會增加危險系數，還會導致巨大的延誤損失。如果預知目的機場擁擠時，可以讓未出發的飛機在原機場等待即實施地面等待策略。

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

1987年，Odoni首次系統地闡述了空中交通流量問題的研究領域、基本概念和主要問題，提出了重新安排飛機起飛時間以使擁擠成本最小化的思想[1]。1989年Terrab和Odoni將單機場確定型模型轉化成了網絡流模型，提出用最小費用流來求解模型[2]。2001年Pulugurtha1等將人工智能遺傳算法引入到GHP問題中，采用遺傳算法求解靜態模型[3]，加快了模型求解的速度，促進了GHP模型在實際中的應用。2017年，Roland Deroo主要提出了一種新的基于運籌學方法的出發排序算法，進而可以進一步優化時隙的分配問題[4]。

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

從近幾年的研究看，對集權式分布的研究較多，而少有人用模擬退火算法對此問題進行分析。我們經過分析認為，將時隙分配問題當成一個指派問題來求解，得出的方案更優。本文利用模擬退火算法將時隙分配問題當成工人工作的指派問題來求解，最終得出的結果是可以減少航空公司的延誤損失。

1 單機場地面等待策略模型

在建立單機場地面等待策略模型之前，我們先作如下假設。

⑴ 在時間段[0，T]內，目的機場Z的航班著陸出現擁擠，且目的機場Z是空中交通網絡中惟一的容量限制單元和唯一產生航班延誤的原因。

⑵ 有N個航班（F1、F2…Fn）預計在[0，T]內到達目的機場且每個航班的起飛時間和飛行時間是已知并且確定的，并且所有航班最后都在[0，T]內到達。

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

根據假設建立地面等待策略的成本最小化模型：

2 算法介紹

2.1 RBS算法

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

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

⑵ 對每一類航班按最初的時刻表順序排序。

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

2.2 模擬退火算法

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

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

⑵ 隨機產生一個領域解，j∈N（i）（N（i）表示的領域）計算目標值增量Δf=f（j）-f（i）。

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

注：Tk高時，廣域搜索；Tk低時，局域搜索。

⑷ 若達到熱平衡（內循環次數大于n（Tk））轉⑸，否則轉⑵。

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

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

3 算例驗證

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

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

將上述成本矩陣M導入模擬退火算法中，在python下進行仿真運算，運行結果如圖1所示，將運行結果和RBS算法對時隙的分配結果作對比，對比結果如表2所示。其中表2的OTA/OTD指的是初始計劃進離場時間，CTA/CTD指的是控制進離場時間。

由上述運行結果可知，最終的運行結果在10226終止，說明最優結果為10226。將上述仿真結果統計如表2。

本文將航班的時隙分配問題轉化為指派問題之后，運用模擬退火算法對所有時隙進行指派研究，最后得出延誤損失為10266相比RBS算法分配結果所得延誤損失減少了27.9%。可知運用模擬退火算法并將時隙分配優化問題轉化為指派問題可以有效的減少延誤損失。

4 結束語

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

參考文獻（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] 田勇，吳東暉，萬莉莉等.基于突發事件的機場進離場時隙分

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

[6] 吳東暉.機場時隙分配優化技術研究[D].南京航空航天大學，

2016.

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

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

[8] 樊憲標.機場時隙資源協同動態配置研究[D].南京航空航天

大學，2014.