基于模擬退火算法的民航運輸路徑優(yōu)化技術研究

王珺

（西安航空職業(yè)技術學院，陜西西安 710089）

民航運輸具有速度快、效率高的特點，但也較易受到其他因素的影響。例如空中資源分配不均、航線延誤及運輸上座率低等問題，均會大幅增加民航運輸?shù)某杀綶1]。而解決此類問題的有效途徑之一，便是對民航運輸路徑進行優(yōu)化。

傳統(tǒng)的民航路徑選擇算法使用專家經驗法，該方法主觀性較強、穩(wěn)定性較差、效率也較低，且無法有效地降低成本。該文對民航貨物運輸路徑選擇[2]問題進行了研究，并針對運載情況復雜多變、航線選擇困難等問題，使用帶時間窗[3]的路徑優(yōu)化算法來對該問題進行建模。同時將模擬退火算法（Simulated Annealing，SA）[4-6]和遺傳 算法（Genetic Algorithm，GA）[7-9]相結合并進行改進，使算法兼具局部求解和全局求解能力。為驗證該文所提算法，使用Matlab進行建模，并與其他路徑優(yōu)化算法相對比，驗證了該文算法的優(yōu)異表現(xiàn)。

1 帶時間窗的民航運輸路徑模型建立

1.1 場景建立

民航運輸?shù)奶攸c是對運輸時長較為敏感，因此，該文建立了帶有時間窗的民航運輸路徑模型。

假設民航班機從某個中心機場出發(fā)，并按照運輸節(jié)點要求完成運輸任務，最后返回中心機場。中心機場是飛機的起飛點，在其完成所需貨物或乘客的運輸后會重新返回。

1.2 目標函數(shù)

該文目標函數(shù)由3 個函數(shù)體組成，分別為總里程成本、時間變化成本以及機組成本。

1）總里程成本

班機的運輸成本[10]主要為燃油費，其與運輸距離呈正相關。故在配送時，需選擇配送路徑距離最短的一條。運輸成本可表示為：

式中，c表示單位距離運輸成本，i、j表示目標節(jié)點的序號，k表示班機的序號，dij表示節(jié)點i到節(jié)點j之間的距離。

2）時間變化成本

對于時間窗模型而言，在規(guī)定時間內將貨物運送至指定地點可節(jié)省成本。假設貨物到達的時間區(qū)間為[T1,T2]，Ti為第i架班機達到的時間，則時間損失成本如下：

式中，a和b為班機提早到達與晚點到達的單位時間損失成本。

3）機組成本

機組成本主要是班機的保養(yǎng)及維護費用，而固定成本與同一航線的航班數(shù)量也有關系，其可表示為：

式中，C為單架班機的固定費用，Nk為第k架班機，sign 作為符號函數(shù)可判斷班機的使用情況。

1.3 模型建立

由上文所述，最終得到的目標優(yōu)化函數(shù)如下所示：

式（7）表示中心機場的班機執(zhí)行完配送任務后，再次裝載貨物返回中心機場。式（8）表示中心機場完成運輸任務共需m架班機。式（9）中，Q表示班機的最大載重量，qi表示節(jié)點i所需的貨物，該公式表明目標節(jié)點所需物流量不能超過班機的最大載重量。式（10）中，L表示班機最長運輸距離，該式表明班機運輸距離不可超過自身最長行駛距離。

2 遺傳模擬退火算法

2.1 模擬退火算法

模擬退火算法[11]由物理原理模擬得到，在金屬冶煉過程中金屬受熱會發(fā)生融化，當停止加熱后則會重新固化，這也是對問題最優(yōu)解進行搜索的過程。該算法的優(yōu)點是能對全局最優(yōu)解加以搜索并避免算法陷入局部解中，同時其無需函數(shù)初值即可得到結果。

使用數(shù)學模型對模擬退火過程進行描述，其自適應狀態(tài)函數(shù)可由式（11）表示：

由式（11）可知，E(i)和E(j)是模擬退火過程中的兩個能量狀態(tài)。當E(i)＞E(j)時，表明狀態(tài)能被正常切換；而當E(j)＞E(i)時，切換狀態(tài)成功概率則將大幅降低。上式中，K為時間常數(shù)，T為金屬溫度。

模擬退火算法的基本步驟如圖1 所示。其在局部搜索中的優(yōu)勢較大、概率跳變特性顯著并具有較強的魯棒性。但同時該算法的參數(shù)依賴性也較強、迭代次數(shù)多且算法效率較低，因此需對其進行改進。

圖1 模擬退火算法實現(xiàn)流程

2.2 改進的遺傳模擬退火算法

遺傳算法主要用來求解組合優(yōu)化問題[12]，其可將多個問題看作是一個種群，問題的解則看作是種群的最優(yōu)化繁殖。數(shù)學模型主要是將組合問題的目標函數(shù)轉換成適應度函數(shù)，同時根據(jù)該函數(shù)對個體加以篩選。然后個體進行交叉[13]、變異[14]等操作，使自身適應度不斷增加，進而形成種群的最優(yōu)解。

由遺傳算法求解過程可知，該算法有較強的全局搜索性，故在求解組合問題時容易收斂，因此迭代次數(shù)過少將難以求得最優(yōu)解。

遺傳模擬退火算法將遺傳算法與模擬退火算法相結合，可有效提升模擬退火算法的運行效率及遺傳算法的局部解搜索能力。遺傳模擬算法實現(xiàn)的流程如圖2 所示。

圖2 遺傳模擬算法實現(xiàn)流程

該文對遺傳模擬算法進行了改進，以便充分發(fā)揮算法的局部求解和全局求解能力。改進之處共有兩點：

1）在計算初始階段，算法進行局部求解，但此時易陷入局部最優(yōu)，因此使用混沌理論（Chaos theory）初始化種群。該文使用的Logistic混沌公式如下：

式中，Θ為混沌公式的控制變量，yn為第n次迭代的值，yn+1則為第n+1 次迭代的值。該公式通過動態(tài)的映射能夠充分保持種群多樣性，從而避免計算進入局部最優(yōu)的狀態(tài)。

2）在遺傳模擬退火算法中，遺傳算子的選擇與計算較為重要，文中使用自適應公式對圖2 中的遺傳算子（交叉算子、變異算子）進行改進，由此便可使遺傳算法隨著適應度的變化而改變。

交叉算子及變異算子的自適應函數(shù)如下所示：

上式中，pc和pm為交叉算子及變異算子，pc1和pc2為交叉算子的控制系數(shù)，pm1和pm2則為變異算子控制系數(shù)，f為遺傳算法適應度，fmax與favg分別為算法的最大適應度和平均適應度。

因此，該文算法的具體流程如下：

1）初始化參數(shù)，包括退火算法的初始、結束溫度以及遺傳算法的交叉、變異概率；

2）使用混沌理論Logistic 混沌公式進行種群初始化；

3）計算種群適應度、平均適應度及最大適應度，并對種群個體進行選擇；

4）使用自適應函數(shù)優(yōu)化交叉算子與變異算子，以得到最優(yōu)的個體適應度；

5）遺傳算法輸出性能和狀態(tài)最優(yōu)的個體；

6）數(shù)據(jù)輸入至模擬退火算法，再由其求得最終解。

3 算法測試

3.1 數(shù)據(jù)訓練

該文使用有時間窗路徑優(yōu)化問題（Vehicle Routing Problems with Time Windows，VRPTW）[15-16]專用的Soloman 數(shù)據(jù)集。該數(shù)據(jù)集包含有56 個算例，文中使用其對民航班機的貨物運輸過程進行模擬。算例所包含的數(shù)據(jù)類型也較多，包括配送目的地坐標、需求貨量、中心機場班機數(shù)量與班機最大載重量等。

同時為了驗證模型的性能，還使用了Matlab 進行編程仿真。所采用的硬件平臺如表1 所示。

表1 硬件環(huán)境

3.2 仿真結果分析與對比

在算法仿真中，對數(shù)據(jù)集算例進行了相應運算并得到了算法最優(yōu)值，再將其與數(shù)據(jù)集最優(yōu)值、其他算法運算最優(yōu)值加以對比。算法總體的路徑優(yōu)化目標即路徑最短、運輸班機最少，同時多次求解保證算法的客觀性。對比算法選用了模擬退火算法（算法1）和遺傳算法（算法2），而算法評估指標則為班機數(shù)量求解誤差值與里程求解誤差值。仿真求解結果如表2、3 所示。

表2 班機數(shù)量求解結果

表3 飛行里程求解結果

由上表可以看出，該文算法在不同算例中的表現(xiàn)也有所不同，由于航班數(shù)與配送點數(shù)正相關，因此從算例1 到算例7，其配送點數(shù)均在不斷增加。由于遺傳算法的全局特性較好，因此在簡單場景下的優(yōu)勢更大。模擬退火算法在復雜場景下的表現(xiàn)更優(yōu)，顯示出其優(yōu)良的局部求解能力。而該文算法的誤差率在每個算例中整體較為平均，這也表明其兼具局部求解和全局求解能力。而對于該文算法而言，迭代次數(shù)指標也是關鍵的一項。算例2 的迭代過程如圖3 所示。

圖3 算例2的迭代過程

圖3 中縱坐標表示的是求解距離，橫坐標則表示算法的迭代次數(shù)。由圖可知，在算法運行初期，計算距離在不斷下降，表明該文算法可在短時間內靠近最優(yōu)求解值。而隨著迭代次數(shù)的增加，求解值也趨于穩(wěn)定。這也說明了該算法兼具模擬退火算法與遺傳算法的優(yōu)點，且具有良好的收斂性及穩(wěn)定性。

4 結束語

民航運輸是我國物流運輸體系中的重要一環(huán)，而運輸路徑的選擇對民航運輸?shù)某杀居绊戄^大。傳統(tǒng)的航空路徑選擇主要依靠人工經驗指導，其主觀性較強且穩(wěn)定性較差。該文對遺傳模擬退火算法加以改進，使用了混沌理論初始化種群，并對變異算子和交叉算子的實時性進行了自適應優(yōu)化。在建模實驗中，該文算法的班機數(shù)量求解與實際值相差最小，且擁有較快的收斂速度，由此證明了該文算法的性能優(yōu)良，并可應用于實際工程中。