基于時間離散化的飛機降落問題研究

陳晨

（四川大學計算機學院，成都 610065)

0 引言

近年來，中國經(jīng)濟高速發(fā)展，航空事業(yè)迅速發(fā)展，機場數(shù)量和規(guī)模，航班排版數(shù)量持續(xù)增長。在航空事業(yè)高速發(fā)展的今天，如何讓航空公司的飛機調(diào)度更加合理高效地運行，為人們提供更快捷便利的服務，改善空中交通狀況是眾多專家學者關(guān)注的焦點。飛機降落問題也在此環(huán)境下應運而生，該問題是指對每一架進入機場的飛機分配一條跑道和一個安全的降落時間。每架飛機需要在事先預定好的時間降落在跑道上，同時，任何兩架飛機之間必須有一定的距離間隔來保障安全。

1 模型建立

對于每一架進入目標機場雷達測距范圍的飛機，都會收到來自空中交通管制的命令，為其分配一條降落跑道和一個降落時間。降落時間需要在最早降落時間和最晚降落時間之間。最早降落時間對應的是飛機以最快飛行速度飛行時的著陸時間。最晚降落時間對應的是飛機由于某些因素降低飛行速度造成延遲的最晚著陸時間。目標降落時間是我們希望飛機降落的時間。在目標降落時間之前或之后降落都會給機場帶來一定的困擾，因此和目標降落時間的偏離會給機場帶來一筆額外的開銷。

對于飛機降落問題，我們給出以下理想模型：

P：飛機；

R：跑道；

Ei：飛機i的最早降落時間，i∈P；

Ti：飛機i的目標（最佳）降落時間，i∈P；

Li：飛機i的最晚降落時間，i∈P；

Sij≥0：當飛機i比飛機 j提前降落在相同跑道時，飛機i和飛機 j的最小間隔時間；

sij≥0：當飛機i比飛機 j提前降落在不同跑道時，飛機i和飛機 j的最小間隔時間。

決策變量如下：

δ2ij?i,j∈P(i≠j)，二元變量，=1當且僅當飛機i比飛機 j提前降落在不同跑道；

zij?i,j∈P(i＜j)，二元變量，zij=1當且僅當飛機 i和飛機 j降落在相同跑道；

yir?i∈P，r∈R ，二元變量，yir=1當且僅當飛機i降落在跑道r上；

xi≥0，飛機i的計劃降落時間。

模型PB具體需遵從以下約束：

2 理想情況模擬

利用時間分離化方法分解矩陣S。Sij代表先降落的飛機i和后降落的飛機 j降落所需的最小間隔時間。假設(shè)S可以分解成具有相同列向量a（非負項）和相同行向量b（非負項）的矩陣之和，即Sij=ai+bj,ai≥0,bj≥0。將每架飛機看作是分享同一個資源（跑道）的活動i，當飛機i提前于飛機 j降落在同一條跑道上時，兩架飛機的安全時間間隔如下圖所示。

圖1 飛機i和飛機 j的安全時間間隔

使用這種分解方法，我們可以在有限數(shù)量的飛機降落場景中模擬飛機降落問題。每種飛行場景在時間窗對應一個著陸時間，一架飛機降落的場景數(shù)等于時間窗口中的時間槽。因此，飛機降落問題可以由下式表達：

其中，（10）表示同一時間每架飛機有且僅有一種降落場景，（11）表示在時間規(guī)劃范圍內(nèi)，同一個時間最多允許一架飛機降落。H代表時間槽的集合，Scen(i)表示飛機i的場景集合。

3 求解目標

用cik表示飛機i在場景k情況下的降落開銷，Ti表示i的預計（理想）降落時間，tik表示飛機i在場景k的實際降落時間，gi,hi分別表示tik比Ti提前和延遲到達的開銷函數(shù)。

4 解決方案

對于任何分離時間矩陣S，總是可以通過rank2矩陣進行近似估算。有很多方法來逼近矩陣S。分離時間矩陣S與飛機機型（分別為重型heavy，中型medi?um，輕型light），用C表示飛機機型。線性變化如下式：

我們使用模型PB中的限制條件并把結(jié)果添加到PSC中。用tik表示飛機i在場景k情況下的降落時間，xi可以表示為 xi=sumk∈Scen(i)tikλik。飛機降落在哪條跑道上取決于場景和環(huán)境，定義runwikr=1表示飛機i在場景k的情況下降落在跑道r上，否則runwikr=0，那么yir可以表示成 yir=sumk∈Scen(i)runwikrλik。

只考慮重要的限制條件，算法如下：

1. 使用下邊界矩陣初始化，(PB)=PSC(SLB,sLB)；

2.解(PB)，將結(jié)果記為λ；

3. 計算 xi=sumk∈Scen(i)tikλik,?i∈P ；

4. 在相同跑道上找出滿足條件 xi≤xj且xi+Sij＞xj的飛機i和飛機 j；

5. 在不同跑道上找出滿足條件 xi≤xj且xi+sij＞xj的飛機i和飛機 j；

6. 如果發(fā)現(xiàn)違反不等式的條件，用 λik,δ1ij,δ2ij,zij表達的式子代入PB并重復步驟2，否則結(jié)束。

該算法得到的結(jié)果滿足所有限制約束。

5 結(jié)語

本文提出了一種飛機降落問題的解決辦法，該方法基于對分離時間矩陣的近似值估計和時間離散化。這種近似值估算方法通過降低邊界來解決飛機降落問題。如果時間規(guī)劃范圍增大，每架飛機降落可能的時間場景將會劇增，因此本文還有許多需要進一步研究和改進的地方。

參考文獻：

[1]L.Bianco,P.Dell’Olmo,S.Giordani,Scheduling Models for Air Traffic Control in Terminal Areas,Journal of Scheduling 9,2006：(3)223-253.

[2]K.Artiouchine,P.Baptiste,C.Durr,Runway Sequencing with Holding Patterns,European Journal of Operational Research,2008，189(3)：1254-1266.

[3]楊秋輝，游志勝，馮子亮，樊鴻.Journal of Sichuan University(Natural Science Edition)，2004.

[4]張偉.求解飛機調(diào)度問題的優(yōu)化算法研究.天津大學碩士學位論文，2012.