基于蟻群算法的低碳冷鏈物流配送路徑優(yōu)化

鄭娟毅, 付姣姣, 程秀琦

(西安郵電大學 通信與信息工程學院， 陜西 西安 710121)

隨著經(jīng)濟發(fā)展和人民生活水平的提高，人們對生鮮產(chǎn)品的需求不斷增加，進而促使生鮮物流服務需求與日俱增。生鮮物流的核心是冷鏈配送環(huán)節(jié)[1],車輛路徑(vehicle routing problem,VRP)問題是冷鏈物流服務的關(guān)鍵，其旨在滿足約束條件下,選擇最優(yōu)的配送路線，完成對配送點運輸服務[2]。在生鮮產(chǎn)品的物流配送過程中會產(chǎn)生大量碳排放，不僅會污染環(huán)境，而且會增加物流公司的配送成本，故合理減少配送過程中的碳排放值得關(guān)注。

對冷鏈物流路徑的相關(guān)研究，大多采用遺傳算法[3]和蟻群算法[4]進行求解。如文獻[5]采用遺傳算法研究冷鏈物流配送路徑，但未考慮卸載時間帶來的貨物損壞問題；文獻[6]基于改進混合遺傳算法對冷鏈物流配送中心選址進行優(yōu)化，但未考慮碳排放問題；文獻[7]考慮碳排放因素，提出了一種采用遺傳算法求解的城市配送車輛路徑問題，但未考慮碳排放成本中碳稅因素。通常遺傳算法的計算量大，且具有早熟現(xiàn)象，容易過早收斂到局部最優(yōu)解。相對而言，蟻群算法具有較強的魯棒性且具有正反饋機制，更適合于研究車輛路徑問題。如文獻[8]采用蟻群算法求解生鮮農(nóng)產(chǎn)品冷鏈物流低碳配送路徑，但未考慮貨損成本中的卸載時間因素。文獻[9]將細菌覓食-蟻群算法用于求解冷鏈低碳物流配送路徑模型，但在計算貨損成本時沒有考慮卸載時間，且在總成本中未考慮時間懲罰成本。

根據(jù)生鮮產(chǎn)品冷鏈物流的特性及成本，本文擬提出一種基于蟻群算法的低碳冷鏈物流配送路徑優(yōu)化方法。首先，在考慮生鮮產(chǎn)品冷鏈物流的運輸成本、固定成本、制冷成本和時間懲罰成本的同時，引入行駛距離、車載量的碳排放成本和因卸載時間差異引起生鮮產(chǎn)品損壞的成本來構(gòu)建數(shù)學模型。其次，對蟻群算法進行改進，在狀態(tài)轉(zhuǎn)移概率中引入負荷因子，在全局信息素更新策略中引入向?qū)Р呗?并采用非線性方式對達到一定迭代次數(shù)要求的信息素總量進行自適應調(diào)整。最后，利用改進后的蟻群算法對所建立的低碳冷鏈物流配送模型求解，以期實現(xiàn)冷鏈物流的低碳配送路徑優(yōu)化。

1 蟻群算法

蟻群算法是一種路徑尋優(yōu)智能算法[10]。算法中螞蟻以較大概率選擇信息素濃度高的路徑并釋放一定量的信息素，增強該路徑上的信息素濃度，形成一個正反饋，最終螞蟻會找到覓食路徑中的最短路徑。對基本蟻群算法做如下描述。

1)設蟻群數(shù)量為m，節(jié)點i和節(jié)點j間的距離為dij,t時刻路徑(i,j)的信息素濃度為τij。

2)每只螞蟻的爬行方向由信息素濃度確定，用禁忌表存儲在i節(jié)點的所有螞蟻下一步行動節(jié)點集合。

3)在路徑搜索過程中，通過狀態(tài)轉(zhuǎn)移概率公式計算螞蟻選擇下一節(jié)點的概率。

螞蟻根據(jù)每條路徑上的信息素濃度選擇下一個覓食點，假設螞蟻k在t時刻從節(jié)點i出發(fā)以一定概率選擇節(jié)點j的狀態(tài)轉(zhuǎn)移概率[10]表達式為

其中：τij表示i,j節(jié)點間信息素濃度；ηij表示i,j節(jié)點間距離的啟發(fā)信息；α表示信息素所占的比重；β表示啟發(fā)因子；Ak表示處于節(jié)點k的螞蟻 下一步選擇訪問的節(jié)點集合。

4)當螞蟻完成一次遍歷，對路徑上的信息素濃度進行調(diào)整。t+1時刻信息素濃度更新[10]公式為

τij(t+1)=(1-ρ)τij(t)+Δτij(t,t+1)。

其中：Δτij(t,t+1)表示在(t,t+1)時段內(nèi)，所有螞蟻在路徑(i,j)上的信息素增量；ρ為信息素揮發(fā)系數(shù)，其大小影響路徑規(guī)劃效率，ρ越大，算法的全局搜索能力越強，但收斂速度越慢；ρ越小，收斂速度越快，但全局搜索能力越弱。

5)當搜索次數(shù)達到最大時，找到最短路徑。

2 冷鏈物流模型的建立

2.1 基本假設

假定配送中心能夠合理安排服務車輛和配送路線，使得配送成本達到最低，需要滿足的條件如下：

1)只有1個配送中心，且配送中心和多個配送點的位置坐標已知。

2)配送車輛從配送中心出發(fā)后必須返回配送中心。

3)配送車輛類型一致，每輛車的車載量盡量達到滿載，但不能超過車容量限制。

4)車輛只進行送貨服務，不涉及取貨服務。

基于以上假設，本文研究的生鮮農(nóng)產(chǎn)品冷鏈服務配送問題可以描述為：在滿足目標函數(shù)最優(yōu)的情況下，僅有一個生鮮農(nóng)產(chǎn)品配送中心通過冷藏貨車進行冷鏈服務配送。

2.2 模型建立

由于配送貨物為生鮮產(chǎn)品，因此在數(shù)學建模時要考慮冷藏車輛運輸成本、固定成本、制冷成本、貨物運輸過程中的損壞成本、運輸車輛的時間懲罰成本以及碳排放成本等多重目標。

1)運輸成本

運輸成本通常與配送產(chǎn)品價格和配送車輛的耗油因素相關(guān)，車輛行駛的距離越長配送成本越高。設運輸成本為

其中：k=1,2,…,m表示車輛數(shù)；i,j=1,2,…,n分別表示配送點；dij表示配送點i,j之間的距離；w1表示產(chǎn)品價格；xijk表示與車輛k運輸成本相關(guān)的配送狀態(tài)系數(shù)，xijk=1表示車輛k完成從配送點i到j配送，xijk=0表示車輛k未完成配送。

2)固定成本

冷鏈服務固定成本是一個定值，通常與駕駛司機的工資和配送車輛損耗因素相關(guān)，設固定成本為

其中ck表示第k輛車的固定配送成本。

3)制冷成本

制冷的主要目的是保持一個恒定溫度來保證生鮮產(chǎn)品的新鮮度。設制冷成本主要包括配送車輛在運輸過程中為保證車廂溫度恒定所產(chǎn)生的成本E31、配送車輛早到等待的成本E32和配送車輛遲到的成本E33，則制冷成本為

E3=E31+E32+E33。

其中

式中：s表示每小時車輛的制冷成本；[Ei,Li]表示配送點i的配送時間窗，Ei表示最早可接受時間，Li表示最遲可接受時間；Ti表示對配送點i的實際配送完成時間。

4)貨物損壞成本

冷鏈服務的貨物是生鮮產(chǎn)品，容易受到空氣溫度、氧氣濃度和卸載時間等因素的影響。本文主要從溫度和卸載時間兩個因素進行分析。配送過程中，農(nóng)產(chǎn)品的溫度會發(fā)生變化，導致產(chǎn)品的質(zhì)量下降，出現(xiàn)貨物損壞成本。

假設在運輸過程中冷藏車溫度不變，生鮮產(chǎn)品的腐爛率λ1為一個定值，則運輸過程產(chǎn)生的貨損成本為E41；當配送車輛到達配送點進行貨物卸載時，需要打開車門，致使生鮮產(chǎn)品所處溫度發(fā)生變化，腐爛率會隨著溫度的增加而變大，設腐爛率變?yōu)棣?(λ2>λ1)，并且卸載時間Tx越長貨物損壞情況越嚴重，令卸載過程產(chǎn)生的貨損成本為E42。則貨物損壞成本可以表示為

5)時間懲罰成本

配送時間懲罰成本與配送車輛是否滿足配送點時間窗有關(guān)，當配送車輛在配送點所需時間窗之前到來時，產(chǎn)生早到等待的損失費用E51；當配送車輛在配送點所需時間窗之后到來，產(chǎn)生延遲懲罰費用E52。則時間懲罰成本為

其中：w2表示單位時間等待成本；w3表示單位時間延遲成本。

6)碳排放成本

碳排放成本主要是指在冷鏈物流中冷藏車輛產(chǎn)生的碳排放量成本。碳排放量為耗燃量與CO2排放系數(shù)[11]之積。車輛的油耗與車輛的載重量和行駛距離有關(guān)，運輸車輛單位距離耗油量與車載量的關(guān)系[12]可以表示為

其中：ρ0表示運輸車輛空載時單位距離油耗；ρ*表示運輸車輛滿載時單位距離油耗；D表示車滿載量；vij表示車輛在配送點i到配送點j之間的貨運量。

則碳排放成本為

其中：θ表示碳稅；w4表示碳排放系數(shù)。

綜上所述，物流冷鏈服務的目標函數(shù)為

minE=E1+E2+E3+E4+E5+E6。

(1)

約束條件為

(2)

(3)

(4)

(5)

Ti+ti+t′+tij=Tj,

(6)

(7)

其中：ti表示在配送點i的等待時間；t′表示卸載時間；tij表示從配送點i到配送點j的運行時間；Tj表示車輛從配送中心經(jīng)配送點i到配送點j的時間；xi0k表示車輛k從配送中心出發(fā)到達節(jié)點i；xojk表示車輛k從節(jié)點j返回配送中心。

式(1)是冷鏈物流配送所需費用最低的目標函數(shù)，其中配送所需費用與路徑成正比例關(guān)系；式(2)-(3)保證每個配送點僅有一輛車進行配送服務；式(4)保證每輛車的負荷量不超過其自身最大負荷量；式(5)保證每輛車的軌跡路線必須為一個閉環(huán)，且每輛車必須從配送中心出發(fā)；式(6)保證滿足配送點時間窗要求。

3 改進算法的物流配送優(yōu)化

3.1 算法流程

改進算法的思想是將模擬退火算法[13]得到的解作為蟻群算法的初始解，然后采用鄰域算法[14]對蟻群算法得到的路徑進行交換得到一個新的路徑，并對蟻群算法和鄰域算法相應路徑的值進行比較獲得全局最優(yōu)解。改進算法流程如圖1所示。

圖1 改進算法流程

首先對模擬退火參數(shù)初始化，將模擬退火算法得到的解作為蟻群算法的初始信息素，并對參數(shù)進行初始化。將各個螞蟻放在配送中心，根據(jù)改進后的狀態(tài)轉(zhuǎn)移規(guī)律選擇下一個節(jié)點，得到當前最優(yōu)解。在當前最優(yōu)解的鄰域中通過鄰域算法的交換方式找到另一個解，比較2個解的大小，并判斷是否接受新解作為當前解。對路徑上的信息素濃度進行更新。判斷是否達到最大迭代次數(shù)，若達到輸出最優(yōu)解，否則繼續(xù)循環(huán)。

3.2 利用模擬退火算法調(diào)整初始解

模擬退火算法的冷卻過程[13]可以表示為

Ta+1=hTa,a=1,2,…,A-1。

其中：Ta表示第a次迭代的溫度；h表示降溫系數(shù)；A表示模擬退火算法的總迭代次數(shù)。

模擬退火算法的冷卻過程容易受降溫系數(shù)的影響，降溫系數(shù)較小，搜索的最優(yōu)解精度低，收斂速度快；降溫系數(shù)較大，收斂速度慢，算法求解精度高。為了提高算法的求解精度和收斂速度，本文對降溫過程進行自適應調(diào)整。在冷卻過程引入回火機制，即自行設置回溫過程，以較高的概率選擇所有解集里較差的解重新加入最新解集，避免算法陷入局部最優(yōu)。將回火溫度設置為區(qū)間[T1,T2]，當溫度T下降到T1時，回火機制立即將其回升到T2。設置最大回火次數(shù)G，當回火次數(shù)Gs達到最大回火次數(shù)即停止回火。

3.3 利用狀態(tài)轉(zhuǎn)移概率選擇配送點

狀態(tài)轉(zhuǎn)移概率是螞蟻選擇下一節(jié)點的關(guān)鍵步驟，直接影響算法的求解速度和精度。一方面，考慮車載量的影響，將生鮮產(chǎn)品的需求量引入到狀態(tài)轉(zhuǎn)移概率中，使得在選擇下一節(jié)點時會考慮油耗量。另一方面，物流配送需要考慮交通擁堵的情況，引入交通工程學中的道路阻抗系數(shù)。

假設有m輛車n個配送點，每輛車從配送中心出發(fā)，在t時刻以一定概率選擇下一個配送點，此時狀態(tài)轉(zhuǎn)移概率可以表示為

(8)

其中：λij表示路徑(i,j)的道路阻抗系數(shù)；q表示在單位時間內(nèi)通過路徑(i,j)的車輛數(shù)；y表示單位時間內(nèi)車輛的成本；e和b為阻滯系數(shù)，e∈(0.1,0,2),b∈(1,4)。

為了避免出現(xiàn)停滯現(xiàn)象，本文采用蟻群系統(tǒng)[15](ant colony system, ACS)的狀態(tài)轉(zhuǎn)移概率，其公式為

(9)

其中：q0是設定的閾值；q∈[0,1]為隨機值，當q>q0時采用式(8)進行搜索。

3.4 采用信息素更新策略調(diào)整信息素濃度

為避免蟻群算法在完成一次遍歷后過早收斂于局部最優(yōu)解，在全局信息素更新策略中引入向?qū)б蜃樱瑒討B(tài)地更新全局信息素。算法初期每條路徑上的信息素濃度較低，此時向?qū)б蜃討撦^小，保證所有螞蟻以一個公平的概率去選擇下一個覓食點，不易陷入局部最優(yōu)；隨著路徑上的信息素濃度逐漸增加，向?qū)б蜃討鄳龃螅涌烊质諗克俣?。第t+1時刻的全局信息素表達式為

τij(t+1)=(1-ρ)τij(t)+
Δτij(t,t+1)δ,

(10)

(11)

其中：di表示配送中心到節(jié)點i的距離；dj表示節(jié)點j到配送中心的距離；Lbest表示當前循環(huán)次數(shù)中最優(yōu)解的路徑長度。

3.5 利用鄰域算法優(yōu)化最優(yōu)解

為提高算法收斂速度，利用鄰域算法[14]對蟻群算法每次迭代產(chǎn)生的可行解進行優(yōu)化。尋找鄰域解有插入、逆轉(zhuǎn)和交換三種方式。本文采用交換方式尋找鄰域解，即首先獲得蟻群算法每一次迭代產(chǎn)生的解，然后在得到解的路徑中隨機選擇第n1、n2次訪問的配送點交換兩者的位置，進行隨機擾動并重新計算得到新解。若新解優(yōu)于原解，則更新解，否則保持不變。重復上述操作，直到達到最大迭代次數(shù)時獲取最優(yōu)解。

4 仿真結(jié)果及分析

為驗證算法和模型的性能，利用實際冷鏈物流配送數(shù)據(jù)和Solomon標準算例進行驗證，分別設置模型參數(shù)和算法參數(shù)如下。

將模型參數(shù)設置為生鮮產(chǎn)品價格w1=3 000 元/噸，單位時間等待成本w2=150 元/小時，單位時間延遲成本w3=200 元/小時，配送車輛最大載重量D=10 噸，配送車輛運行固定成本c=70 元，運輸途中的單位貨損成本P=5 元/千米，運輸中的腐壞率λ1=0.02，卸貨中的腐壞率λ2=0.04，制冷成本s=200 元/小時，空載油耗ρ0=1 升/千米，滿載油耗ρ*=2 升/千米，碳排放系數(shù)w4=2.61 千克/升，碳稅θ=20 元/千克。

將算法參數(shù)選擇為信息素重要程度α=1，啟發(fā)因子β=1，信息素揮發(fā)系數(shù)ρ=0.95，螞蟻數(shù)量m=30，最大迭代次數(shù)umax=100，信息素釋放總量為100，回火溫度設置為[500,1000]，降溫系數(shù)h=0.9，最大回火次數(shù)G=4，阻滯系數(shù)e,b分別取值0.15和3，采用交換方式尋找鄰域解。

在Window10操作系統(tǒng)和Matlab2016a的運行環(huán)境中，進行仿真驗證。

采用西安市某市場生鮮供應商的實際冷鏈配送數(shù)據(jù)驗證算法。該供應商為西安市區(qū)24個配送點實施冷鏈配送。已知各個配送點的需求量和時間窗要求，算法運行結(jié)果如圖2所示。其中0代表配送中心。

(a) 實際地圖中的配送點位置

(b) 各個配送點位置的坐標點

(c) 算法的路徑

(d) 算法的迭代次數(shù)與最低成本圖2 算法運行結(jié)果

由圖2可知，迭代次數(shù)為15時，本文算法趨于穩(wěn)定，最優(yōu)值為3 143元。

為證明算法的有效性和穩(wěn)定性，選用Solomon算例中21組數(shù)據(jù)，結(jié)合冷鏈物流配送過程進行實驗分析。將本文算法、標準蟻群算法和文獻[16]的遺傳算法進行比較，其結(jié)果如圖3所示。

圖3 3種算法的仿真結(jié)果對比

由圖3可知，本文算法在迭代次數(shù)為15時趨于穩(wěn)定，最優(yōu)值為2 125元；文獻[16]的算法迭代次數(shù)為26時趨于穩(wěn)定，最優(yōu)值為2 168元；標準蟻群算法迭代次數(shù)為42時趨于穩(wěn)定，最優(yōu)值為2 178元。本文算法的最優(yōu)值與收斂速度相比于文獻[16]的算法和標準蟻群算法均有一定的改進。這是因為，在螞蟻數(shù)量大的環(huán)境中，標準蟻群算法容易陷入局部最優(yōu)。同時，由于其搜索路徑復雜，會造成搜索次數(shù)增多，收斂速度不穩(wěn)定等問題。文獻[16]算法具有早熟現(xiàn)象，影響算法收斂速度。而本文算法的收斂速度和解的質(zhì)量之所以高于其他兩種算法，是因為引入模擬退火算法和在狀態(tài)轉(zhuǎn)移概率中引入蟻群系統(tǒng)，提高了解的質(zhì)量；對達到一定迭代次數(shù)要求的信息素總量采用非線性方式進行自適應調(diào)整，提高了收斂速度。

5 結(jié)語

針對冷鏈物流車輛路徑問題，建立了包含冷鏈配送服務的固定成本、運輸成本、貨物損壞成本、制冷成本、時間懲罰成本和碳排放成本在內(nèi)的冷鏈物流車輛路徑模型。對標準蟻群算法的狀態(tài)轉(zhuǎn)移概率和全局信息素更新策略進行改進。利用改進后的蟻群算法求解冷鏈物流最優(yōu)車輛路徑。仿真結(jié)果表明，相比于遺傳算法和標準蟻群算法，改進的算法可以提高解的質(zhì)量和算法的收斂速度，能夠應用到冷鏈物流配送中。