鄭娟毅, 付姣姣, 程秀琦

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

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

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

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

1 蟻群算法

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

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

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

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

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

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

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

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

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

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

2 冷鏈物流模型的建立

2.1 基本假設(shè)

假定配送中心能夠合理安排服務(wù)車(chē)輛和配送路線，使得配送成本達(dá)到最低，需要滿(mǎn)足的條件如下：

1)只有1個(gè)配送中心，且配送中心和多個(gè)配送點(diǎn)的位置坐標(biāo)已知。

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

3)配送車(chē)輛類(lèi)型一致，每輛車(chē)的車(chē)載量盡量達(dá)到滿(mǎn)載，但不能超過(guò)車(chē)容量限制。

4)車(chē)輛只進(jìn)行送貨服務(wù)，不涉及取貨服務(wù)。

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

2.2 模型建立

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

1)運(yùn)輸成本

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

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

2)固定成本

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

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

3)制冷成本

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

E3=E31+E32+E33。

其中

式中：s表示每小時(shí)車(chē)輛的制冷成本；[Ei,Li]表示配送點(diǎn)i的配送時(shí)間窗，Ei表示最早可接受時(shí)間，Li表示最遲可接受時(shí)間；Ti表示對(duì)配送點(diǎn)i的實(shí)際配送完成時(shí)間。

4)貨物損壞成本

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

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

5)時(shí)間懲罰成本

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

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

6)碳排放成本

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

其中：ρ0表示運(yùn)輸車(chē)輛空載時(shí)單位距離油耗；ρ*表示運(yùn)輸車(chē)輛滿(mǎn)載時(shí)單位距離油耗；D表示車(chē)滿(mǎn)載量；vij表示車(chē)輛在配送點(diǎn)i到配送點(diǎn)j之間的貨運(yùn)量。

則碳排放成本為

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

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

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

(1)

約束條件為

(2)

(3)

(4)

(5)

Ti+ti+t′+tij=Tj,

(6)

(7)

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

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

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

3.1 算法流程

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

圖1 改進(jìn)算法流程

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

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

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

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

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

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

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

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

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

(8)

其中：λij表示路徑(i,j)的道路阻抗系數(shù)；q表示在單位時(shí)間內(nèi)通過(guò)路徑(i,j)的車(chē)輛數(shù)；y表示單位時(shí)間內(nèi)車(chē)輛的成本；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是設(shè)定的閾值；q∈[0,1]為隨機(jī)值，當(dāng)q>q0時(shí)采用式(8)進(jìn)行搜索。

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

為避免蟻群算法在完成一次遍歷后過(guò)早收斂于局部最優(yōu)解，在全局信息素更新策略中引入向?qū)б蜃樱瑒?dòng)態(tài)地更新全局信息素。算法初期每條路徑上的信息素濃度較低，此時(shí)向?qū)б蜃討?yīng)該較小，保證所有螞蟻以一個(gè)公平的概率去選擇下一個(gè)覓食點(diǎn)，不易陷入局部最優(yōu)；隨著路徑上的信息素濃度逐漸增加，向?qū)б蜃討?yīng)相應(yīng)增大，加快全局收斂速度。第t+1時(shí)刻的全局信息素表達(dá)式為

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

(10)

(11)

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

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

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

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

為驗(yàn)證算法和模型的性能，利用實(shí)際冷鏈物流配送數(shù)據(jù)和Solomon標(biāo)準(zhǔn)算例進(jìn)行驗(yàn)證，分別設(shè)置模型參數(shù)和算法參數(shù)如下。

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

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

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

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

(a) 實(shí)際地圖中的配送點(diǎn)位置

(b) 各個(gè)配送點(diǎn)位置的坐標(biāo)點(diǎn)

(c) 算法的路徑

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

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

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

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

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

5 結(jié)語(yǔ)

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