目視回收流程優化問題研究*

于靜遠 鄭 錦

（91404部隊91分隊 秦皇島 066000）

1 引言

1.1 問題研究背景

目視回收優化問題來源于飛機回收流程，在跑道資源緊缺，飛機油量有限的前提下，如何更好更快更安全地回收飛機，即在安全回收的前提下，提供一種既快速又穩定的調度方案，就是這一優化問題的主要內容。

機場的飛機起飛降落調度是典型的單機調度問題。在理論上，它可以看作是其他調度問題的特殊形式。相比一般單機調度問題，目視回收優化問題具備多目標、動態性等特點，這些問題都需要特別考慮分析。

1.2 問題研究難點

目視回收優化問題的難點有兩個。

一是該問題的優化目標多。優化目標多意味著問題的目標函數會很復雜，若優化目標之間相互制約，則在設計優化函數時還需要另外設計啟發式算法來決定目標函數。

二是該問題的動態優化特性。具有實時性，因此在設計算法時只能考慮動態優化算法。同時與時間相關的突發事件的不確定性，這可能需要額外引入概率分析的手段分析問題。

2 問題描述

目視回收航線問題是回收飛機的第I類回收模型。在此模型中，在等待區域有若干飛機排成一個隊列等候降落。飛機必須按排成的隊列順序依次進行降落。每架飛機著陸時的總重量（即機重加油量）必須滿足給定的安全著陸重量的范圍，否則必須進行備降。在飛機著陸時有可能發生逃逸事情（鉤鎖失敗）或復飛事件（跑道故障），復飛的飛機需要進入復飛航線進行重新著陸。在飛機著陸過程中，必須保證任意兩架連續著陸的飛機的著陸時間滿足最小的時間間隔。

可將該問題大體上分為五個狀態（航線），分別為等待狀態，進近狀態，復飛狀態，著陸狀態和備降狀態。如圖1為目視回收航線調度的俯視示意圖。圖2為目視回收的復飛航線圖。

圖1 目視回收航線俯視圖

圖2 目視回收的復飛航線圖

2.1 子問題劃分

該問題可以分解為兩個子問題來求解。

第一個子問題是，在不發生任何逃逸事件或跑道故障事件的情況下，各飛機的最優離開等待狀態的時間如何確定的問題。

第二個子問題是，在某一時刻t（正整數），正在著陸的飛機發生逃逸事件或跑道故障事件，該飛機應插入到處于等待狀態的飛機的哪個位置的問題。

2.2 靜態子問題描述

下面給出靜態子問題的決策變量，約束條件以及目標函數。

1）決策變量

第i隊飛機過檢查點退出等待進入進近航線的時刻xi；

2）約束條件

（1）第1隊飛機從檢查點退出等待進入進近航線的時刻x1=0；

（2）xi≥xi-1+mΔti=2，…，l

m為每隊飛機的數量，Δt為任意兩架飛機的著陸時間間隔。

3）目標函數

其中，f1為安全著陸的飛機數目（最大化），f2為回收所有飛機的總時間（最小化），f3為飛機總的放油量（最小化）；Wi，j為飛機的機身重量（kg）；為飛機的初始油量（kg）；為從檢查點到跑道著陸的時間間隔。

不難發現，三個目標函數中，f1為第一優化目標，f2次之，f3最弱。因此，總的目標函數可寫成

f=α1f1-α2f2-f3

這里α1?α2?0。

2.3 動態子問題描述

在基于靜態子問題模型的基礎上，我們考慮動態子問題，即在某一時刻t，正在著陸的飛機j發生逃逸事件或者跑道故障的情況下，如何對現有方案進行重新調度，以實現最優化2.2節所提及的三個目標函數的目的。

下面給出動態子問題的決策變量，約束條件以及目標函數。

1）決策變量

（1）在當前時刻仍處于等待狀態的各隊飛機退出等待進入進近航線的時間xi；

（2）第k次發生復飛的第i隊第j架飛機的復飛時間長度yi，j，k；

（3）第k次發生復飛的第i隊第j架飛機的復飛時刻zi，j，k。

2）約束條件

（3）若第i隊飛機j未曾復飛，則

即任一飛機與復飛的飛機降落到跑道的時間間隔不小于Δt；若第i隊飛機j已復飛，則

（5）Pt+Pf=1，Pt，Pf∈{0，1}。任一時刻最多只發生一次逃逸或復飛。

3）目標函數

與2.2節目標函數一致，但其中f2變為

3 算法求解與分析

3.1 靜態子問題求解

根據2.3節的目標函數可知，退出等待時刻xi越小，則f1越大，f2越小，f3越大，因此xi應盡量的小，該問題的最優解為

直觀上來看，各架飛機只要在滿足安全時間間隔的前提下盡可能早地離開等待航線，進近，著陸即可。

3.2 動態子問題求解

在動態子問題中，最核心的約束有兩個，分別為約束b）和約束c）。

這兩個約束實際上是由復飛后的飛機插入到未著陸的飛機編隊序列中的位置決定的，即需要復飛的飛機應處于未著陸的若干架飛機的什么位置。

如圖3所示，一旦復飛的飛機插入的位置確定，則yj，k的值以及等待區域的飛機新的值就可以根據前面提到的約束來確定。因此，新的飛機調度方案可確定為

圖3 復飛飛機yi*，j*插入位置的選擇

復飛的飛機插入的位置為p之后，則對飛機（編隊）p以及p之前的飛機，調度方案不變，受到影響的只有p之后的飛機。對于新的調度方案，有兩種情況要分別討論。

第一種情況，在p位置上的是一個飛機編隊，處在進近航線中，為狀態S2或S3，如圖4所示。此時計算的值。由于目標函數的要求，xp越小越好，因此可得關系式：

圖4 復飛插入后新調度方案示意圖

則飛機h（h＞p）的新調度時間，若飛機的狀態為S1或S5，則

若飛機狀態為S2或S3，則x不變，完善邊界條件，得：

即后續所有飛機均延遲Δt的時間即可。

第二種情況，p位置上是一架正在復飛的飛機，為狀態S4，如圖5所示。

圖5 復飛插入后新調度方案示意圖

飛機h（h＞p）的新調度時間，與第一種情況相同。

4 結語

目視回收航線問題表面上看起來比較簡單，但經過仔細研究可以發現問題本質上是非常有深度的。首先是問題的描述方面，將這一實際應用問題抽象出來，采用時空狀態圖的方式去理解。再者，在問題的決策求解方面，由于復飛和甲板故障事件的突發性、實時性和不確定性，導致了在決策時除了考慮當前格局的優度，還要考慮當前局面的穩定和可靠程度。