基于蟻群算法冷鏈物流運(yùn)輸路徑最優(yōu)化設(shè)計(jì)

曾 勝,戴賢君,肖 文,倪天偉,胡徐勝,滕官宏偉

(1.皖江工學(xué)院 電氣工程學(xué)院,安徽 馬鞍山 243000;2.中國(guó)計(jì)量大學(xué) 生命科學(xué)學(xué)院,浙江 杭州 310018;3.中國(guó)人民解放軍陸軍裝備部,湖南 株洲 4120022)

本文以冷鏈運(yùn)輸過程中的車輛為監(jiān)測(cè)對(duì)象,對(duì)冷鏈物流車調(diào)度展開研究,同時(shí)對(duì)冷鏈物流調(diào)度算法進(jìn)行仿真優(yōu)化,利用傳統(tǒng)的蟻群算法來對(duì)冷鏈物流路徑進(jìn)行優(yōu)化設(shè)計(jì)并與改進(jìn)過后的算法進(jìn)行對(duì)比。

1 車輛調(diào)度模型的建立

1.1 車輛調(diào)度模型基本條件的設(shè)定

配送車輛行駛距離必須能滿足現(xiàn)實(shí)條件;每個(gè)冷鏈物流車輛調(diào)度必須滿足冷鏈物流公司的產(chǎn)品運(yùn)輸量;冷鏈物流車須從調(diào)度中心出發(fā),收到貨物需回到調(diào)度車輛的出發(fā)點(diǎn);調(diào)度車輛在接收到產(chǎn)品調(diào)度時(shí),冷鏈物流公司不能夠臨時(shí)增加任務(wù)情況;每次調(diào)度冷鏈物流產(chǎn)品時(shí),必須使調(diào)度車輛的數(shù)量足夠;調(diào)度車輛的司機(jī)必須知道冷鏈物流產(chǎn)品具體位置,冷鏈物流公司也必須知道調(diào)度車輛的具體位置;所有冷鏈物流車配置與型號(hào)相同;對(duì)于每輛車的溫濕度等參數(shù)設(shè)定保持不變。另外對(duì)冷鏈物流車空車與載物時(shí)的行駛路徑不同,但是正好能夠形成一個(gè)完整的閉合行駛路線。

1.2 調(diào)度車輛相關(guān)參數(shù)的設(shè)定

首先建立目標(biāo)函數(shù)并對(duì)基本條件進(jìn)行界定:m表示每個(gè)調(diào)度點(diǎn)冷鏈物流車的數(shù)量;C表示冷鏈運(yùn)輸公司的運(yùn)輸成本;rm表示第m輛車的運(yùn)行成本;R0表示每輛車的運(yùn)行成本;U表示運(yùn)輸車輛每行駛1 km所需要的費(fèi)用;Sij表示第i輛車與第j個(gè)物流公司之間的距離(其一是調(diào)度中心的車輛行駛到物流中心距離,此路徑必須保證物流車是空車,距離較近,即次路;二是調(diào)度車裝滿貨物過后行駛到調(diào)度中心距離,此路徑必須行駛正常路況,即主路);λ1表示配送過程中單位時(shí)間內(nèi)維持車內(nèi)溫度的能源損耗;λ2表示卸載貨物時(shí)外界熱量進(jìn)入車廂內(nèi)使溫度降低而產(chǎn)生的損失;p表示冷鏈物流公司裝載貨物消耗的時(shí)間;v表示冷鏈運(yùn)輸車輛配送貨物過程的平均速度;ρ1為冷鏈物流配送過程中單位時(shí)間貨物所產(chǎn)生損失比例;k1為單位時(shí)間內(nèi)產(chǎn)生的費(fèi)用;ρ2為冷鏈物流貨物卸載時(shí)所產(chǎn)生損失比例;k2為卸貨時(shí)所產(chǎn)生的單位比例費(fèi)用。

若供貨中心有M輛車的成本固定且均為rm=(m=1,2,3…M),即運(yùn)輸車輛固定成本為:

(1)

只與車輛行駛距離有關(guān)的運(yùn)輸過程成本分別為空車行駛成本、載物行駛成本、冷鏈物流運(yùn)輸車的冷卻成本為:

(2)

運(yùn)輸過程中產(chǎn)生損失的運(yùn)算公式為:

(3)

冷鏈運(yùn)輸過程中產(chǎn)生的總成本即為以下幾種冷鏈運(yùn)輸過程中的損耗與成本之和:

水泥緩凝劑是用于改善水泥凝結(jié)時(shí)間的添加劑，使用量為水泥質(zhì)量的3%-5%。磷石膏可替代天然石膏、脫硫石膏作為水泥緩凝劑，延長(zhǎng)水泥的凝結(jié)時(shí)間，減緩水泥水化速度。目前，磷石膏產(chǎn)量最大的甕福集團(tuán)與周邊水泥廠合作，提供磷石膏作為水泥廠的水泥緩凝劑，同時(shí)給予消耗磷石膏的企業(yè)一定的補(bǔ)貼。根據(jù)調(diào)查，西南水泥廠目前利用甕福集團(tuán)產(chǎn)生的磷石膏作為水泥緩凝劑，近三年磷石膏用量在水泥中的占比大約為2%左右。

C=C11+C12+C13+C2+C3

(4)

2 傳統(tǒng)蟻群算法的模型建立

2.1 ACA蟻群算法具體步驟

(5)

螞蟻單詞循環(huán)不可重復(fù)訪問的轉(zhuǎn)移概率由下式確定:

(6)

設(shè)定ρ表示信息素?fù)]發(fā)程度。即公式為:

Cij(t+1)=(1-ρ)*Cij(t)+ΔCij

(7)

ΔCij=∑ΔCijk

(8)

ΔCijk為第k只螞蟻在車輛行駛位置點(diǎn)i與車輛行駛位置點(diǎn)j之間釋放增加信息素濃度;ΔCij為所有螞蟻在i與j之間釋放增加的信息素濃度;其信息素增加公式如下

τi+1=στij(t)+Δτij(t,t+1)

(9)

(10)

(11)

比較NC和Nmax的大小,計(jì)算結(jié)果并輸出。Lk表示螞蟻?zhàn)哌^的路線總長(zhǎng)度;Nmax表示最大路線迭代次數(shù);Q表示釋放的信息素總量。

2.2 仿真計(jì)算結(jié)果

由于該冷鏈物流車的行駛路徑較多,本論文以五條路徑線作為模型,但是車輛調(diào)度過程中調(diào)度中心空車行駛到物流中心的路徑與物流中心滿載貨物行駛到調(diào)度中心的路徑不同,此外空車與滿載過程中的路徑正好形成一個(gè)完整的閉合路線。如圖1所示。

對(duì)冷鏈物流車最近距離進(jìn)行蟻群算法的仿真,圖1中路徑3即為最優(yōu)路徑。表1是冷鏈物流車行駛的52個(gè)坐標(biāo)位置,即為本次行駛最優(yōu)路徑距離,用MATLAB2014平臺(tái)對(duì)路徑3進(jìn)行仿真。路徑坐標(biāo)如表1所示。

圖1 調(diào)度車輛行駛路徑圖Figure 1 Travel route diagram of dispatching vehicle

表1 路徑坐標(biāo)表格Table 1 Path coordinate

由于兩直線距離最短,利用如下公式進(jìn)行計(jì)算:(此距離是理論距離計(jì)算公式的1.2倍)。

(12)

運(yùn)行參數(shù)設(shè)置為:蟻群中螞蟻數(shù)量m為52(螞蟻數(shù)量取各個(gè)坐標(biāo)位置數(shù)量);a是信息素濃度因子為1;期望啟發(fā)因子b為5;信息素?fù)]發(fā)系數(shù)ρ為0.5;最大迭代次數(shù)Ncmax=100。ACA蟻群算法其仿真運(yùn)行結(jié)果如圖2所示。

由圖2可知:由于車輛在調(diào)度過程中調(diào)度車輛在空車時(shí)與滿載時(shí)行駛路徑不同且能夠形成一個(gè)完整的折線包圍圈,本文設(shè)置第45點(diǎn)坐標(biāo)為車輛調(diào)度點(diǎn),第52點(diǎn)坐標(biāo)為物流中心點(diǎn),且車輛來回是兩條不同的路線。

圖2 ACA最優(yōu)化車輛調(diào)度路徑軌跡圖Figure 2 Scheduling path trajectory of ACA optimal vehicle

空車路徑一:52-11-51-33-43-10-9-8-41-19-45(空車行駛3.1 km)。滿載路徑二:余下的路徑坐標(biāo)點(diǎn)(滿載行駛4.7 km)。蟻群經(jīng)過10次運(yùn)算結(jié)果:空車與滿載最優(yōu)路徑為7 753.117 6 m;假設(shè)所涉及到的運(yùn)輸成本為:每輛車司機(jī)成本300元,冷鏈物流公司需要每個(gè)調(diào)度點(diǎn)調(diào)度車輛為10輛,每公里花費(fèi)運(yùn)輸成本為5元;車輛運(yùn)輸過程中單位時(shí)間汽油損耗λ1為6元/h;當(dāng)給客戶卸載貨物時(shí)車門開啟單位時(shí)間能源損耗λ2為12元/h,車輛空車速度與滿載速度為40 km/h;車輛在卸裝貨物時(shí)消費(fèi)時(shí)間為2 h,ρ1為0.5,ρ2為0.3,k1單位損失為5元,k2單位損失為4元。成本計(jì)算:運(yùn)輸車輛固定成本即司機(jī)成本C11=3 000元;空車駕駛成本C12=3.875元;載物成本C13=5.875元;冷卻成本C2=247.05元;損失費(fèi)用C3=12.95元;總成本C=3 269.75元。

3 蟻群算法改進(jìn)

3.1 引入搜索方向機(jī)制

在ACA蟻群算法的啟發(fā)信息(13)中,dij表示可選路徑的長(zhǎng)度,即螞蟻dij距離越短,則該螞蟻行駛的邊際路線被選取的可能性較大。在求解冷鏈物流路徑最優(yōu)化問題時(shí),假如啟發(fā)信息仍然用式(13)表示,則沒有考慮到由車輛調(diào)度源點(diǎn)到物流中心具體搜索方向性的問題,導(dǎo)致的結(jié)果是沒能夠完成最優(yōu)搜索方向性問題與整體路徑最優(yōu)化問題。由此對(duì)啟發(fā)信息因子修改如下:

ηij=1/dij

(13)

3.2 引入搜索熱區(qū)機(jī)制

引入搜索公式:

(14)

其中Φij(t)表示在t時(shí)刻根據(jù)邊(i,j)是否在搜索熱區(qū)中而取不同的值。

(15)

公式(14)與(15)代表了搜索概率與搜索邊緣的問題。在螞蟻進(jìn)行熱搜索時(shí)有熱搜索區(qū)域與非熱搜索區(qū)域,導(dǎo)致的的結(jié)果是螞蟻爬行距離不相同。

3.3 實(shí)驗(yàn)結(jié)果

運(yùn)行參數(shù)設(shè)置為:蟻群中螞蟻數(shù)m為52(螞蟻數(shù)量取城市數(shù)量);a是信息素濃度因子為1;期望啟發(fā)因子b為5;信息素?fù)]發(fā)系數(shù)ρ為0.5;最大迭代次數(shù)Ncmax=100,Q=1 000,信息素初始值為τij=20。通過算法改進(jìn)對(duì)路徑3的距離、行駛時(shí)間重新優(yōu)化。

表2 兩種算法路徑與時(shí)間對(duì)比圖Table 2 Comparison of paths and spending time from the two algorithms

傳統(tǒng)蟻群算法調(diào)度車輛它的最優(yōu)行駛距離為7.75 km,此路徑雖然選取了最優(yōu)路徑,但是行駛過程中傳統(tǒng)算法進(jìn)行優(yōu)化的路徑偏長(zhǎng),其空車行駛距離與滿載行駛距離都較長(zhǎng),所以冷鏈物流所花的成本較高。而ACA蟻群算法改進(jìn)后此冷鏈物流車的行駛距離明顯縮短,則所花費(fèi)用較少。

3.2 實(shí)際運(yùn)算結(jié)果

實(shí)際冷鏈物流車行駛路徑是從杭州江干區(qū)市中心到馬鞍山市,行駛過程中有多條路徑,選取最優(yōu)化路徑進(jìn)行計(jì)算。實(shí)際兩城市距離為300 km,公路國(guó)道行駛距離:345 km,高速行駛距離:314 km,車輛行駛在公路時(shí)間大約為3.5 h,行駛在高速路上的時(shí)間大約為4 h,實(shí)際改進(jìn)算法的行駛時(shí)間為3.4 h。通過實(shí)際計(jì)算結(jié)果進(jìn)行對(duì)比,對(duì)冷鏈物流運(yùn)輸成本進(jìn)行分析。由表3所示可以看出該冷鏈物流實(shí)際距離與車輛優(yōu)化后行駛的距離基本上差不多,雖然有點(diǎn)差距但足以說明該冷鏈物流調(diào)度算法完全符合車輛調(diào)度,符合該冷鏈物流監(jiān)控系統(tǒng)。

表3 實(shí)際路程運(yùn)算結(jié)果Table 3 Calculation results of actual distance

注:實(shí)際距離計(jì)算結(jié)果。

4 結(jié) 語

本文通過調(diào)度算法與冷鏈物流進(jìn)行結(jié)合設(shè)計(jì)路徑最優(yōu)化,使得此冷鏈物流的監(jiān)控方案與運(yùn)輸方案得到最優(yōu)化設(shè)計(jì),減少了整個(gè)運(yùn)輸成本與運(yùn)輸時(shí)間。利用蟻群算法仿真模擬來實(shí)現(xiàn),目的是降低冷鏈物流運(yùn)輸過程中運(yùn)輸成本。同時(shí)本文主要介紹了設(shè)計(jì)中所有的車輛調(diào)度算法,建立了基于蟻群算法的車輛調(diào)度模型并對(duì)算法進(jìn)行了仿真實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果顯示通過該調(diào)度算法能夠設(shè)計(jì)出距離優(yōu)、成本低的路徑進(jìn)行車輛調(diào)度。