陳晨

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都 610065)

0 引言

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

1 模型建立

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

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

P：飛機(jī)；

R：跑道；

Ei：飛機(jī)i的最早降落時(shí)間，i∈P；

Ti：飛機(jī)i的目標(biāo)（最佳）降落時(shí)間，i∈P；

Li：飛機(jī)i的最晚降落時(shí)間，i∈P；

Sij≥0：當(dāng)飛機(jī)i比飛機(jī) j提前降落在相同跑道時(shí)，飛機(jī)i和飛機(jī) j的最小間隔時(shí)間；

sij≥0：當(dāng)飛機(jī)i比飛機(jī) j提前降落在不同跑道時(shí)，飛機(jī)i和飛機(jī) j的最小間隔時(shí)間。

決策變量如下：

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

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

yir?i∈P，r∈R ，二元變量，yir=1當(dāng)且僅當(dāng)飛機(jī)i降落在跑道r上；

xi≥0，飛機(jī)i的計(jì)劃降落時(shí)間。

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

2 理想情況模擬

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

圖1 飛機(jī)i和飛機(jī) j的安全時(shí)間間隔

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

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

3 求解目標(biāo)

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

4 解決方案

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

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

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

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

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

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

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

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

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

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

5 結(jié)語

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

參考文獻(xiàn)：

[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]張偉.求解飛機(jī)調(diào)度問題的優(yōu)化算法研究.天津大學(xué)碩士學(xué)位論文，2012.