王珺

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

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

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

1 帶時(shí)間窗的民航運(yùn)輸路徑模型建立

1.1 場(chǎng)景建立

民航運(yùn)輸?shù)奶攸c(diǎn)是對(duì)運(yùn)輸時(shí)長(zhǎng)較為敏感，因此，該文建立了帶有時(shí)間窗的民航運(yùn)輸路徑模型。

假設(shè)民航班機(jī)從某個(gè)中心機(jī)場(chǎng)出發(fā)，并按照運(yùn)輸節(jié)點(diǎn)要求完成運(yùn)輸任務(wù)，最后返回中心機(jī)場(chǎng)。中心機(jī)場(chǎng)是飛機(jī)的起飛點(diǎn)，在其完成所需貨物或乘客的運(yùn)輸后會(huì)重新返回。

1.2 目標(biāo)函數(shù)

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

1）總里程成本

班機(jī)的運(yùn)輸成本[10]主要為燃油費(fèi)，其與運(yùn)輸距離呈正相關(guān)。故在配送時(shí)，需選擇配送路徑距離最短的一條。運(yùn)輸成本可表示為：

式中，c表示單位距離運(yùn)輸成本，i、j表示目標(biāo)節(jié)點(diǎn)的序號(hào)，k表示班機(jī)的序號(hào)，dij表示節(jié)點(diǎn)i到節(jié)點(diǎn)j之間的距離。

2）時(shí)間變化成本

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

式中，a和b為班機(jī)提早到達(dá)與晚點(diǎn)到達(dá)的單位時(shí)間損失成本。

3）機(jī)組成本

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

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

1.3 模型建立

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

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

2 遺傳模擬退火算法

2.1 模擬退火算法

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

使用數(shù)學(xué)模型對(duì)模擬退火過(guò)程進(jìn)行描述，其自適應(yīng)狀態(tài)函數(shù)可由式（11）表示：

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

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

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

2.2 改進(jìn)的遺傳模擬退火算法

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

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

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

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

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

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

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

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

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

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

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

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

2）使用混沌理論Logistic 混沌公式進(jìn)行種群初始化；

3）計(jì)算種群適應(yīng)度、平均適應(yīng)度及最大適應(yīng)度，并對(duì)種群個(gè)體進(jìn)行選擇；

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

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

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

3 算法測(cè)試

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

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

同時(shí)為了驗(yàn)證模型的性能，還使用了Matlab 進(jìn)行編程仿真。所采用的硬件平臺(tái)如表1 所示。

表1 硬件環(huán)境

3.2 仿真結(jié)果分析與對(duì)比

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

表2 班機(jī)數(shù)量求解結(jié)果

表3 飛行里程求解結(jié)果

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

圖3 算例2的迭代過(guò)程

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

4 結(jié)束語(yǔ)

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