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

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

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

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

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

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

目前的大多數(shù)研究都將ALP 制定為多個(gè)目標(biāo)：最小化總延遲、最大化跑道容量等。研究了飛機(jī)在單條跑道上著陸的動(dòng)態(tài)多目標(biāo)調(diào)度方法，但大部分僅給出了一組權(quán)重，而在實(shí)際中，不同的利益相關(guān)者可能會(huì)給出不同的權(quán)重。在中國民航發(fā)展快速的今天，空管- 航班的綜合優(yōu)化成為減少延誤的重要措施。

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

1 模擬退火方法

為了避免產(chǎn)生局部最優(yōu)解，我們采用了模擬退火（SA）方法，接受較差的解。模擬退火算法是使局部最優(yōu)解能概率性地跳出并最終趨于全局最優(yōu)的方法。SA 在達(dá)到最優(yōu)結(jié)果時(shí)終止，完成預(yù)定的迭代次數(shù)被認(rèn)為是自適應(yīng)大鄰域搜索的停止準(zhǔn)則。

2 算法模擬步驟

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

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

3 參數(shù)設(shè)置與初始化模式

初始優(yōu)化序列為A0，初始優(yōu)化調(diào)度時(shí)間為X0。

wk的值以表1 呈現(xiàn)。表1 中每一行代表了不同目標(biāo)狀態(tài)的重要性（相對重要性）。每一組不同的權(quán)重代表不同的利益相關(guān)者。

表1 面向多股東的不同利益權(quán)重矩陣

4 模型構(gòu)建

4.1 先來先模式算法（FCFS）

在FCFS 的服務(wù)規(guī)則和算法中，每架飛機(jī)都有一個(gè)不受約束的時(shí)間。

假設(shè)有P 架次航班（a1，a2，…，ap），它們的最佳著陸時(shí)間（PLT）為Ti。每一架次航班ai的屬性包含（航班號(hào)，最早到達(dá)時(shí)間，計(jì)劃到達(dá)時(shí)間，最新到達(dá)時(shí)間, 航空器類別）。假設(shè)由PLT 自動(dòng)生成的著陸次序?yàn)锳0。Ai-1及Ai之間的安全間隔為SAi-1，Ai。每個(gè)航班的預(yù)定著陸時(shí)間（SLT），x（Ai）計(jì)算公式如下所示。

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

4.2.1 序列更新模式

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

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

4.2.2 局部貪婪搜索算法

確定序列時(shí)，只使用最早的到達(dá)時(shí)間。初始SLT 的計(jì)算公式如下。

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

PSA 的目的是將表1 中加權(quán)值對應(yīng)的SA 計(jì)算分配給工人進(jìn)行并行退火計(jì)算。PSA 如圖2 所示。

圖2 并行SA 算法

5 TOPSIS 評估方法

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

wij是第i 個(gè)利益相關(guān)者確定的的第j 個(gè)目標(biāo)值的權(quán)重。

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

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

6 結(jié)論

通過上文利用天津機(jī)場的實(shí)際數(shù)據(jù)，得到了FCFS、常規(guī)SA 和PSA 的測試結(jié)果，見表2。

表2 比較計(jì)算時(shí)間

通過與常規(guī)SA 和FCFS 的比較，證明了基于PSA(TOPSIS&PSA) 的擴(kuò)展TOPSIS 的有效性。MATLAB 分析器對FCFS 報(bào)告的計(jì)算時(shí)間為0.389 秒。結(jié)合常規(guī)SA 的著陸順序和調(diào)度著陸時(shí)間和常規(guī)SA 的五種成本由MATLAB 分析器進(jìn)行的常規(guī)SA 報(bào)告的計(jì)算時(shí)間為135秒。對PSA 的結(jié)果進(jìn)行TOPSIS 評價(jià)，將不同的權(quán)重集來進(jìn)行效率比較?？梢缘贸鯬SA(TOPSIS&PSA)報(bào)告結(jié)果的TOPSIS 評估計(jì)算時(shí)間為99 秒。

通過表3 可以發(fā)現(xiàn)FCFS 的計(jì)算時(shí)間是最短的，但是這五個(gè)成本大于其他兩種方法。與其他兩種方法相比，常規(guī)的SA 消耗更多的計(jì)算時(shí)間，但其五個(gè)成本低于FCFS。TOPSIS&PSA 的計(jì)算時(shí)間比常規(guī)的SA 的計(jì)算時(shí)間低，而且其四種成本都低于常規(guī)的SA。常規(guī)SA 的計(jì)算速度可能太慢，導(dǎo)致ATC 響應(yīng)時(shí)間的顯著減少。

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

而后我們對各個(gè)方法的結(jié)果敏感性進(jìn)行分析。首先通過改變權(quán)重來進(jìn)行研究，觀察評估結(jié)果是如何隨著權(quán)重的改變進(jìn)行反饋的。其次從理論上詳細(xì)推導(dǎo)出使評估結(jié)果不變的變化范圍，并對三種方法進(jìn)行比較和討論，計(jì)算時(shí)間和五種方法的對應(yīng)成本，見圖3。

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

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

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