基于并行模擬退火的多目標航空器著陸問題的TOPSIS 分析

李春霖 王赫 牛海晴 喬櫟霏 趙嘉晨 楊群亭

（中國民航大學，空中 交通管理學院，天津 300300）

由于航空器在終端區著陸的排序機制和管制員的服務順序以及航班量的增加等問題，航班延誤的現象愈加頻繁。飛機著陸排隊問題（ALP）便是導致延誤現象的主要影響因素之一。由于機場跑道容量的有限性，當有大量航班同時降落于同一機場時，部分航班便不能在他們首選的降落時間（PLT）降落，因此造成了延誤。

本文主要研究如何通過合理的航班排序來減小延誤時長，提高綜合保障能力。我們設計了一個多目標飛機著陸問題（MOALP）模型，將MOALP 分解為兩個子問題：飛機排序問題和最優著陸時間搜索問題。因此造成了可行解數量龐大的問題，為此我們使用了并行計算來減少計算時間。

此外，為了幫助決策者從有限的備選方案中選擇最優方案，我們采用了TOPSIS 賦值方法，將TOPSIS 算法伴隨PSA(TOPSIS&PSA)應用于飛機著陸問題的工作。這種技術基于的原則是，所選的替代方案與正理想的距離最小，與負理想的距離最大。TOPSIS 被廣泛用于處理現實世界中的多標準決策問題，在我們的工作中，我們通過最小化最大延遲和預定著陸時間和首選著陸時間之間的方差來表達公平性。

目前的大多數研究都將ALP 制定為多個目標：最小化總延遲、最大化跑道容量等。研究了飛機在單條跑道上著陸的動態多目標調度方法，但大部分僅給出了一組權重，而在實際中，不同的利益相關者可能會給出不同的權重。在中國民航發展快速的今天，空管- 航班的綜合優化成為減少延誤的重要措施。

本文主要成果可以總結如下：（1）首次將TOPSIS 應用于探索多目標飛機著陸問題的滿意解決方案, 以相對較低的成本解決了多目標的問題。（2）我們提出了一種單機多線程并行SA 算法來加快多目標飛機著陸問題的解決。

1 模擬退火方法

為了避免產生局部最優解，我們采用了模擬退火（SA）方法，接受較差的解。模擬退火算法是使局部最優解能概率性地跳出并最終趨于全局最優的方法。SA 在達到最優結果時終止，完成預定的迭代次數被認為是自適應大鄰域搜索的停止準則。

2 算法模擬步驟

通過最小化飛機之間延遲的差異來最大化公平性

公式（6）是根據MOLAP 模型對不同的類別設置不同參數以確保虧損最小化。條件（8-9）保證了著陸次序。條件(10) 確保所有航班都被安排著陸。條件（11）意味著不同航班的著陸時間必須滿足最小著陸間隔時間（MST）。

3 參數設置與初始化模式

初始優化序列為A0，初始優化調度時間為X0。

wk的值以表1 呈現。表1 中每一行代表了不同目標狀態的重要性（相對重要性）。每一組不同的權重代表不同的利益相關者。

表1 面向多股東的不同利益權重矩陣

4 模型構建

4.1 先來先模式算法（FCFS）

在FCFS 的服務規則和算法中，每架飛機都有一個不受約束的時間。

假設有P 架次航班（a1，a2，…，ap），它們的最佳著陸時間（PLT）為Ti。每一架次航班ai的屬性包含（航班號，最早到達時間，計劃到達時間，最新到達時間, 航空器類別）。假設由PLT 自動生成的著陸次序為A0。Ai-1及Ai之間的安全間隔為SAi-1，Ai。每個航班的預定著陸時間（SLT），x（Ai）計算公式如下所示。

4.2 單線程模擬退火算法（SA）

4.2.1 序列更新模式

單線程SA 算法中的序列更新采用雙交換法和三交換法以相同的概率更新飛行著陸序列，見圖1。

圖1 二交換法（上）、三交換法（下）

4.2.2 局部貪婪搜索算法

確定序列時，只使用最早的到達時間。初始SLT 的計算公式如下。

4.3 并行模擬退火算法（PSA）

PSA 的目的是將表1 中加權值對應的SA 計算分配給工人進行并行退火計算。PSA 如圖2 所示。

圖2 并行SA 算法

5 TOPSIS 評估方法

步驟1：根據決策矩陣計算歸一化的決策值矩陣，用以下公式計算：

wij是第i 個利益相關者確定的的第j 個目標值的權重。

步驟3：從加權歸一化決策值矩陣中確定正理想解和負理想解。由于這五個屬性都是基于成本的，所以正

第6 步：按降序排序，得到TOPSIS 結果。Ci的值越低，對應的解更接近理想解。

6 結論

通過上文利用天津機場的實際數據，得到了FCFS、常規SA 和PSA 的測試結果，見表2。

表2 比較計算時間

通過與常規SA 和FCFS 的比較，證明了基于PSA(TOPSIS&PSA) 的擴展TOPSIS 的有效性。MATLAB 分析器對FCFS 報告的計算時間為0.389 秒。結合常規SA 的著陸順序和調度著陸時間和常規SA 的五種成本由MATLAB 分析器進行的常規SA 報告的計算時間為135秒。對PSA 的結果進行TOPSIS 評價，將不同的權重集來進行效率比較。可以得出PSA(TOPSIS&PSA)報告結果的TOPSIS 評估計算時間為99 秒。

通過表3 可以發現FCFS 的計算時間是最短的，但是這五個成本大于其他兩種方法。與其他兩種方法相比，常規的SA 消耗更多的計算時間，但其五個成本低于FCFS。TOPSIS&PSA 的計算時間比常規的SA 的計算時間低，而且其四種成本都低于常規的SA。常規SA 的計算速度可能太慢，導致ATC 響應時間的顯著減少。

表3 比較三種方法的五種成本

而后我們對各個方法的結果敏感性進行分析。首先通過改變權重來進行研究，觀察評估結果是如何隨著權重的改變進行反饋的。其次從理論上詳細推導出使評估結果不變的變化范圍，并對三種方法進行比較和討論，計算時間和五種方法的對應成本，見圖3。

圖3 不同單一變異比條件下的閉合系數

通過對比我們發現這五個成本將隨著權重集數量的增加而降低，這意味著我們可以通過增加權重集數量來提高獲得更理想解的概率。所以理論上，TOPSIS&PSA比常規SA 更理想和有效，在不同的權重集下，得到理想解的概率至少是常規SA 的幾倍。

本文提出了一種基于PSA 的飛機著陸問題多目標優化TOPSIS 評價方法，用于飛機著陸問題的多目標優化和不同股東利益的權衡。通過對比實驗結果發現，當采用常規SA 方法求解著陸問題時，各目標的權重對多目標優化結果有很大影響。此外，即使已經設置了適當的參數設置，如果只運行一次常規SA，就很難得到最優解，TOPSIS 和PSA 比常規SA 更容易獲得理想的解決方案。盡管利益方給出的權重并不準確，但仍然可以以相對較低的成本找到令人滿意的解決方案。在未來，我們將探索一種更有效的模擬退火算法來代替貪婪算法以減少計算時間。此外，通過多計算機分布式并行計算，增加可用線程的數量和權重集，以實現最優解，還需進一步的研究。