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

徐釗

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

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

中圖分類號：U491 文獻(xiàn)標(biāo)識碼：A DOI：10.13282/j.cnki.wccst.2019.10.043

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

0引言

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

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

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

1差分進(jìn)化算法介紹

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

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

差分進(jìn)化算法的計(jì)算過程如圖1所示。

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

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

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

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

3 改進(jìn)差分進(jìn)化算法

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

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

4 算例分析

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

在每個(gè)中轉(zhuǎn)點(diǎn)轉(zhuǎn)換交通運(yùn)輸工具，就會(huì)涉及到中轉(zhuǎn)時(shí)間和中轉(zhuǎn)費(fèi)用，在各個(gè)中轉(zhuǎn)城市之間的中轉(zhuǎn)時(shí)間以及中轉(zhuǎn)費(fèi)用如表2所示。

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

通過分析可以看出，最低運(yùn)輸費(fèi)用為8192元，各種交通運(yùn)輸組合方式為起點(diǎn)O→P1→P2→P3采用火車運(yùn)輸，P3→P4采用汽車運(yùn)輸，P4→D采用輪船進(jìn)行運(yùn)輸。

5 結(jié)語

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