基于改進差分進化算法的多重交通網(wǎng)絡(luò)運輸調(diào)度問題研究

徐釗

摘要：文章認為多重交通網(wǎng)絡(luò)運輸調(diào)度問題就是在特定的約束條件下允許采用不同交通運輸工具的組合，差分進化算法以其自身的智能算法優(yōu)勢在解決這個問題時具有獨特優(yōu)勢。然而這種算法在解決多重交通網(wǎng)絡(luò)運輸調(diào)度問題時容易陷入局部搜索困局，采用構(gòu)造梯度算子可解決這一不足，并通過實例證明了這種改進算法是可行的。

關(guān)鍵詞：多重交通網(wǎng)絡(luò);差分進化算法;梯度算子;遺傳算法

中圖分類號：U491 文獻標識碼：A DOI：10.13282/j.cnki.wccst.2019.10.043

文章編號：1673-4874（2019）10-0156-03

0引言

隨著我國經(jīng)濟的快速發(fā)展，我國的公路、鐵路、航運以及航空運輸都得到了迅猛發(fā)展。隨著市場經(jīng)濟的開放，我國的交通運輸壓力也隨之增加，在多重交通網(wǎng)絡(luò)運輸條件下，如何提高交通運輸?shù)男室约敖?jīng)濟效益成為了一個難題，并從最初的基本車輛路徑問題上衍生出了多重交通運輸網(wǎng)絡(luò)綜合調(diào)度問題。

對于這個問題，國內(nèi)外學(xué)者進行了大量研究。文獻基于大量數(shù)據(jù)分析，研究了在多重交通運輸情況下，最優(yōu)化線路以及交通運輸方式組合對于提高交通運輸效率和經(jīng)濟性的必要性。文獻采用數(shù)字模擬技術(shù)分析了多重交通運輸網(wǎng)絡(luò)的優(yōu)化組合問題。文獻通過借鑒最新數(shù)學(xué)算法問題對多重運輸網(wǎng)絡(luò)調(diào)度問題進行了深入的分析和研究。

多重交通網(wǎng)絡(luò)問題的優(yōu)化和組合，其本質(zhì)就是采用數(shù)學(xué)計算理論，結(jié)合該問題設(shè)計的環(huán)境污染、經(jīng)濟效益以及社會影響等因素，為交通運輸選擇經(jīng)濟性最好且節(jié)能環(huán)保的綠色運輸組合。對多重交通網(wǎng)絡(luò)問題進行研究，并提出最優(yōu)化運輸組合方式，對我國經(jīng)濟發(fā)展及節(jié)能減排具有重大意義。本文基于差分進化算法，對多重交通網(wǎng)絡(luò)問題進行了研究，并通過實例進行分析，證明該方法對解決多重交通網(wǎng)絡(luò)問題是可行的。

1差分進化算法介紹

差分進化算法是由國外學(xué)者Rainer和Kenneth在1997年提出的，是在遺傳算法基礎(chǔ)上進行改進的，其本質(zhì)就是多目標的優(yōu)化算法，這種計算方法常用于多維空間最優(yōu)化問題的求解。

和遺傳算法相比，兩種計算方法共同點都是隨機生成初始的種群，以種群中每個個體的適應(yīng)度作為選擇標準。這個過程包括選擇、變異以及交叉三個步驟。兩種算法不同之處在于：差分進化算法變異是由父代差分向量產(chǎn)生，和父代的個體進行選擇;而遺傳算法是根據(jù)適應(yīng)度來控制的。差分進化算法相對于遺傳算法逼近目標效果更加有效。

差分進化算法的計算過程如圖1所示。

通過對多重交通網(wǎng)絡(luò)的分析，建立交通網(wǎng)絡(luò)最優(yōu)化數(shù)學(xué)模型，充分利用差分進化算法的優(yōu)勢，同時考慮對計算結(jié)果會產(chǎn)生影響的時間價值以及時間窗口等因素，對最優(yōu)化組合的交通運輸方式進行分析。通過一個實例的分析驗證，表明差分進化算法能夠有效解決多重交通網(wǎng)絡(luò)的組合選擇問題。

2 多重交通運輸網(wǎng)絡(luò)問題分析

多重交通運輸網(wǎng)絡(luò)問題的本質(zhì)，就是選擇最優(yōu)化組合。下面以某鋼鐵企業(yè)運輸問題為例進行分析，鋼鐵企業(yè)需要將一批貨物從A地運輸?shù)紹地。在運輸過程中需要經(jīng)過m個中轉(zhuǎn)站，兩個中轉(zhuǎn)站之間有n種運輸方式可以選擇，每種運輸方式的費用、耗費時間以及運輸能力都是不同的。且從一個運輸方式轉(zhuǎn)換為另外一種運輸方式需要支付中轉(zhuǎn)費用以及耗費一定中轉(zhuǎn)時間。貨物需要在規(guī)定的期限內(nèi)運輸?shù)侥康牡兀绾芜x擇合理的運輸組合方式，使規(guī)定時間內(nèi)運輸?shù)侥康牡亟?jīng)濟性最好，這就需要研究多重運輸網(wǎng)絡(luò)問題。

在上述約束條件情況下，求出式（1）的最優(yōu)解，就能解決多重交通運輸網(wǎng)絡(luò)問題。下面采用改進差分進化算法，對上述問題進行分析。

3 改進差分進化算法

目前差分進化算法在迭代計算取得某一代種群最優(yōu)解后，不能充分利用梯度信息進一步進行局部探索最優(yōu)解，因此傳統(tǒng)差分進化算法局部搜索能力不足。改進差分進化算法基于梯度尋求最優(yōu)解的思想，通過構(gòu)造梯度加速算子，提高了差分進化算法的局部搜索能力。為了避免計算過程中出現(xiàn)無效計算，在計算分析時設(shè)置一個啟用要求：如果在求解某一代最優(yōu)解陷入停滯狀態(tài)時，啟用附加操作算子，算子設(shè)計如下：

參數(shù)λ有多種計算方法，如搜索法、試算法以及微分法等。為了提高算法的效率采取了試算，即初始假定一個λ值，然后檢驗判定條件是否成立，如果成立就采用計算步長;如果檢驗條件不滿足，就減小步長迭代計算。

4 算例分析

假定某鋼鐵廠需要將一批鋼材，從場地O運輸?shù)侥康牡谼，運輸過程中需要經(jīng)過P1、P2、P3、P4中轉(zhuǎn)城市，在各個點之間交通運輸方式有航空、火車、水運以及輪船四種方式，各種運輸方式的運輸費用F、時間T、能力A如表1所示。

在每個中轉(zhuǎn)點轉(zhuǎn)換交通運輸工具，就會涉及到中轉(zhuǎn)時間和中轉(zhuǎn)費用，在各個中轉(zhuǎn)城市之間的中轉(zhuǎn)時間以及中轉(zhuǎn)費用如表2所示。

采用改進的差分進化算法對綜合交通運輸方案進行分析，假定需要運輸鋼材800t，根據(jù)相關(guān)市場調(diào)研資料，各參數(shù)取值如下：Fmin=0.65、Fmox=0.92、θ=110，每個步驟迭代次數(shù)為300次，進行10次迭代計算。計算過程如圖2所示。

通過分析可以看出，最低運輸費用為8192元，各種交通運輸組合方式為起點O→P1→P2→P3采用火車運輸，P3→P4采用汽車運輸，P4→D采用輪船進行運輸。

5 結(jié)語

多重交通運輸調(diào)度問題其本質(zhì)就是對于多種交通運輸方式組合的最優(yōu)化選擇問題，從而使得經(jīng)濟性和效率達到最優(yōu)。差分進化算法以其自身全局并行和直接搜索的特點，在解決這個多重交通組合的問題上，比其他智能算法更具有優(yōu)越性。但是差分進化算法在求解后期，容易陷入局部最優(yōu)解的求解問題。為了解決這個問題，在既有的差分進化算法基礎(chǔ)上，構(gòu)造了梯度算子，解決了算法最優(yōu)化求解問題，提高了計算效率和精度。通過實例分析表明，改進的差分進化算法在解決多重交通運輸調(diào)度問題上具有較高的計算速度和準確性。