徐釗
摘要:文章認(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)確性。