高英騰，廖志高

廣西科技大學 經(jīng)濟與管理學院，廣西 柳州 545006

2020年突發(fā)疫情使得用戶的消費行為向線上遷移，生鮮電商呈爆發(fā)式增長，當年冷鏈物流市場規(guī)模為4 698 億元，同比增幅38.5%，冷鏈物流市場規(guī)模及同比增幅均創(chuàng)歷史新高。生鮮產(chǎn)品有著易腐敗的特質，在運輸過程中極易產(chǎn)生損耗。同時，由于存在制冷環(huán)節(jié)，冷鏈運輸產(chǎn)生的碳排放要遠高于普通貨物運輸時產(chǎn)生的碳排放，隨著配送路程及配送時間的增加，運輸成本及碳排放量也會大大增加。為提高冷鏈運輸效率，減少資源消耗，眾多學者對冷鏈車輛路徑問題展開了研究。

車輛路徑問題最初以總路程最短為目標，運用貪婪算法[1]、模擬退火算法[2]等進行求解。隨著研究的深入，葛斌等[3]在最短路徑的基礎上引入時間窗的概念，融合蟻群算法和遺傳算法，為蟻群算法增加動態(tài)參數(shù)，提高了算法的收斂速度。易云飛等[4]則在此基礎上引入軟時間窗的概念，運用改進伊藤算法進行求解。宋芹[5]引入“油耗節(jié)約最大化”和“高載重路段延后”的思想，基于禁忌搜索法提出最大油耗節(jié)約算法，從最小油耗的角度對路徑進行規(guī)劃。為突出運輸過程中碳排放對環(huán)境的影響，Bekta?等[6]提出了污染路徑問題。王智憶等[7]建立了以碳排放量最低為目標的配送路徑優(yōu)化模型，并采用蟻群算法進行求解。Jabir等[8]則在綜合考慮經(jīng)濟成本和碳排放成本的情況下，構造了多基地綠色車輛路徑問題，提出了一種將可變鄰域搜索與蟻群算法結合的混合算法，每只螞蟻求出初始解后，通過可變鄰域搜索再進行連續(xù)優(yōu)化，不斷提高解的質量。

相比于車輛路徑問題，冷鏈車輛路徑問題需要考慮的因素更多。Ahumada等[9]以生產(chǎn)者收益最大為優(yōu)化目標，建立了帶時間窗的冷鏈車輛路徑問題優(yōu)化模型。Shukla 等[10]以運輸成本、腐爛程度為優(yōu)化目標函數(shù)，構建數(shù)學模型來解決生鮮農(nóng)產(chǎn)品冷鏈物流問題。梁承姬等[11]則從制冷成本的角度出發(fā)，將溫度引入決策變量中，通過調(diào)節(jié)車廂溫度來降低配送成本。王淑云等[12]考慮了不同產(chǎn)品的保存溫度不同，建立了隨機需求下帶有時間窗的冷鏈多溫共配路徑優(yōu)化模型。陳久梅等[13]在此基礎上，綜合考慮生鮮農(nóng)產(chǎn)品多品種與小批量以及易腐性的特性，以車輛行駛成本最小為優(yōu)化目標構建數(shù)學模型，設計了一種改進粒子群算法求解。

在某些場景中生鮮產(chǎn)品由配送時間產(chǎn)生的成本遠高于由配送距離產(chǎn)生的成本，而路況的變化嚴重影響著運輸時間。為了減小由路況問題導致的成本偏差，學者們開始在冷鏈運輸路徑問題中引入交通路況信息，考慮道路擁堵如何通過影響車輛行駛速度來影響道路選擇。蘭輝等[14]將配送路段的距離矩陣轉化為運輸時間矩陣，以總成本最小為目標構建了冷鏈物流車輛路徑問題數(shù)學模型，設計遺傳算法與2-opt 算法結合的混合遺傳算法進行求解。Xu、Fan 等[15-16]考慮到實際情況中車速的變化是平滑的而不是階梯狀的變化，使用三角函數(shù)來替代階梯變化的速度。Woensel等[17]考慮了車輛隨機行駛時間，在考慮配送成本的同時引入農(nóng)產(chǎn)品配送的服務質量，設計改進禁忌搜索算法尋找配送服務質量與配送成本之間的平衡點。

可以看到，隨著研究不斷深入，對車輛路徑問題的研究逐漸由單一算法向混合算法過渡，算法所得結果越來越精確，對冷鏈車輛路徑問題的研究也越來越貼合實際需求。但上述研究僅考慮配送點之間只有一條道路通行。在實際配送時由于市區(qū)道路的復雜性，車輛往往有多條道路可以選擇，使得問題與傳統(tǒng)的旅行商問題不同，除配送點外還存在許多可重復到達的轉運節(jié)點。此時若采用蟻群算法，螞蟻會在行駛成本較低的路段重復搜索，而采用貪心規(guī)則的Dijkstra算法計算量大，且易陷入局部最優(yōu)。針對這一問題，本文嘗試利用蟻群算法正反饋的特點以及Dijkstra 搜索能力強的特點設計蟻群-Dijkstra 混合算法，用蟻群算法選擇下一配送點，通過Dijkstra 算法搜索兩配送點之間的最短路徑，并在每輪迭代后利用蟻群算法留下的信息素調(diào)整不同時刻的道路運輸成本，使得貪心規(guī)則的Dijkstra 算法能考慮到總成本最低而不是當前路徑的最低成本。同時預留修正成本文件，減少計算量，最終達到提高響應速率、優(yōu)化行駛路徑的目的。

1 模型建立

本文研究基于市區(qū)實況路網(wǎng)的冷鏈車輛運輸規(guī)劃問題，考慮配送點之間有多條道路可以選擇，綜合考慮固定成本、時間變動成本、路程變動成本、時間窗懲罰成本及碳成本，以總成本最低為目標函數(shù)建立數(shù)學模型。

1.1 問題假設

為更好地界定研究問題，提出假設如下：（1）有且僅有一個配送中心，車輛從配送中心出發(fā)，在車內(nèi)貨物配送完畢后返回配送中心，且車輛僅負責送貨，不負責取貨。（2）配送中心車輛充足，每個零售商的需求量不會高于單次配送能力。（3）每個零售商的位置、需求量、服務時間以及時間窗已知，且所需貨品為同一品類。（4）配送點與物流中心約定好貨品送達時間窗，若車輛未按時間窗約定的時間送達，需要付出罰金。（5）運輸車輛型號統(tǒng)一，能耗及油耗相同，司機均接受過相同的技能培訓，油耗不會隨主觀因素變化。（6）車輛在每條道路上的行駛速度為該道路當前能夠行駛的最大速度。

1.2 符號和變量

為方便研究描述，引入符號及相關含義如下：α為信息素啟發(fā)因子；β為成本啟發(fā)因子；λ為信息素揮發(fā)因子；N為配送點數(shù)量；K為所需車輛總數(shù)；fk為第k輛冷藏車的固定成本；a為運輸時制冷成本系數(shù)；b為裝卸時制冷成本系數(shù)；qj為客戶j對產(chǎn)品的需求量；為車輛k選擇從客戶點i到客戶點j的概率；P為產(chǎn)品單位價格；?1為貨物運輸時的衰減系數(shù)；?2為貨物裝卸時的衰減系數(shù)；為車輛k從配送中心出發(fā)時間；為車輛k對客戶點j的服務時間；為車輛k從客戶點i到客戶點j時的載重；Q為車輛最大載重；ε1為車輛早于時間窗送達的懲罰系數(shù)；ε2為車輛晚于時間窗送達的懲罰系數(shù)；ρ0為車輛空載行駛時的燃油消耗率；ρQ為車輛滿載行駛時的燃油消耗率；為車輛從客戶i到客戶j的運輸距離；R為最高賠償金額；為車輛k從配送點i到配送點j的行駛速度；Pf為單位體積的燃油價格；PC為碳排放價格；TC為單位燃料產(chǎn)生的碳排放量。

1.3 決策變量的制定

客戶點由i、j表示(i,j=1,2,…,n)，決策變量xijk為0-1變量，取值如下：

決策變量yjk為0-1變量，取值如下：

1.4 成本分析

（1）固定成本C1

固定成本包括司機的工資，車輛折損、保養(yǎng)等費用。這部分成本僅與運輸車輛的數(shù)量有關，故固定成本C1可表示為：

（2）路程變動成本C2

路程變動成本主要為車輛行駛產(chǎn)生的油耗，油耗的計算方式采用負載估計法[18]。車輛負載量為時的燃油消耗率ρM為：

則在車輛行駛過程中的總油耗fuel為：

路程變動成本等于油耗成本C2，表示為：

（3）時間變動成本C3

考慮時間變動成本時，需要考慮不同路況對運輸時間的影響，車輛k從點i到點j所需的時間可表達為：

時間變動成本包括制冷成本及貨損成本。制冷成本包括運輸時消耗制冷劑的成本及制冷的油耗。考慮運輸及裝卸時車廂溫度不同，對制冷劑及燃油的消耗不同，在模型中將二者系數(shù)分別合并為a、b，分別代表運輸及裝卸時的制冷成本系數(shù)。此時制冷成本C31可表達為：

由于生鮮產(chǎn)品的品質會隨著運輸時間的增長而不斷下降，且隨時間的增長，品質的下降程度呈指數(shù)型增長，故在此使用L(t)表示貨物的衰減程度[19]：

卸貨時，由于貨物已經(jīng)送達，此時貨損僅計算卸貨后剩余部分，則貨物在運輸過程中的貨損成本為：

在裝卸時的貨損成本為：

貨損成本C32可表達為：

（4）時間窗懲罰成本C4

在實際情況中，配送點和配送中心約定時間窗(Ei,Li)，商品j應在時間窗內(nèi)送達。若商品提前送達，需賠償配送點由于未做好接貨準備而造成的損失，若商品延遲送達，則需賠償由延誤造成的損失。但是由于商品價值有限，該成本不會無限量地增加，故在此設定賠償上限R，使得賠償成本不會高于R值。時間窗懲罰成本C4可表示為：

（5）碳排放成本C5

車輛運行中所產(chǎn)生的碳排放主要分為兩部分，一部分是車輛行駛的燃油消耗成本，另一部分則來自制冷所消耗的燃油及制冷劑。考慮到制冷劑消耗量較少，以制冷成本消耗的燃油代替計算相應的碳排放量。這兩部分成本見式（5）及式（8），則車輛行駛中的碳排放主要由燃油燃燒產(chǎn)生。

2021年全國碳排放市場上線交易啟動，若企業(yè)總碳排放未超出碳配額，可以交易出售；反之則需購買超排數(shù)量。此時碳配額可看作企業(yè)已有收益，產(chǎn)生的碳排放需以碳市場價格支付成本，故此處以碳市場價格描述單位碳排放成本。故碳排放成本C5可表示為：

綜上所述，總成本C的表達式為：

式（16）表示每個客戶都被服務且僅被服務一次。式（17）表示車輛服務于客戶時其貨物數(shù)量能夠滿足客戶需求。式（18）表示每輛車從配送中心出發(fā)，返回配送中心。

2 模型求解

首先嘗試采用蟻群算法求解。在算法初期，由于路徑之間的信息素相同，螞蟻較大概率選擇兩點之間成本較低的節(jié)點，而經(jīng)過中轉節(jié)點時，該節(jié)點不被列入禁忌表，也不會觸發(fā)時間窗懲罰成本，因此螞蟻會在某些抵達成本較低的節(jié)點中來回走動。Dijkstra算法能夠避免重復搜索問題，故擬利用蟻群算法選擇下一配送點，通過Dijkstra 算法搜索兩配送點之間的最短路徑，并在每輪迭代后利用蟻群算法留下的信息素調(diào)整不同時刻的道路搜索成本，使得貪心規(guī)則的Dijkstra 算法能考慮到總成本最低而不是當前路徑的最低成本。

2.1 啟發(fā)式因子設計

啟發(fā)式因子是螞蟻選擇下一目的地的重要依據(jù)，通常隨目的地的重要程度增大而增大。算法以總成本最低為目標，故以成本因素作為啟發(fā)式因子。因此設計啟發(fā)式因子ηij為：

其中，Cij代表車輛從點i到點j的成本。

2.2 信息素更新

螞蟻在經(jīng)過的道路上會留有信息素，并通過信息素的含量判斷該道路是否重要。為防止算法陷入局部最優(yōu)，在交通擁堵時找到更好的代替配送路徑，在每輪所有螞蟻巡回完畢后，同時選擇所有輪次總成本最低以及當前輪次總成本最低的螞蟻經(jīng)過路徑更新信息素。

最優(yōu)路徑上信息素更新規(guī)則為：

非最優(yōu)路徑上信息素更新規(guī)則為：

其中，λ為信息素揮發(fā)因子，目的是減少最初搜索時殘留信息素的影響。但為了使得算法在交通變動時仍能選出次優(yōu)路徑，該值不宜過小。

為防止算法過快收斂，在此引入一個不斷增大的q0(q0∈[0,1])，在每次螞蟻選擇下一個配送點時會先產(chǎn)生一個隨機數(shù)qi，將q0與qi進行比較，根據(jù)比較結果來選擇下一配送點。具體表達式如下：

當qi小于等于q0時，在可選路徑中選擇修正成本最高（實際成本最低）的路徑。反之按照輪盤賭的方式進行選擇。

2.3 混合算法流程設計

考慮到運輸過程中需要根據(jù)交通變化情況實時調(diào)整路線，而Dijkstra算法計算量較大，故將算法分為兩階段進行求解計算。第一階段為預處理過程，此時算法以蟻群算法為主，通過反復迭代更新不同時刻不同道路上的信息素含量，得到初始配送路徑及修正成本地圖。預處理階段混合算法流程如圖1所示。

圖1 預處理階段的混合算法流程Fig.1 Hybrid algorithm flow in preprocessing stage

當途經(jīng)路況發(fā)生變化時，無需全部重新計算，通過已有的修正成本地圖，修正對應時刻的道路成本，然后按照貪心規(guī)則的Dijkstra算法搜索即可。此時算法流程如圖2所示。

圖2 路況變動時混合算法流程Fig.2 Hybrid algorithm flow when road conditions change

3 實證分析

3.1 數(shù)據(jù)獲取

高德開放平臺提供了API接口，可以查詢指定區(qū)域內(nèi)所有道路的交通態(tài)勢。反饋內(nèi)容包括當前時間、道路名稱、道路坐標、道路速度以及當前擁堵情況。數(shù)據(jù)獲取間隔為5 min，得到2020年9月至2020年12月共三個月的交通態(tài)勢信息，根據(jù)獲取到的道路坐標繪制出街道道路圖如圖3所示。

圖3 市區(qū)街道道路圖Fig.3 Urban street map

3.2 車速預測

車速使用BP 神經(jīng)網(wǎng)絡方法進行預測，設輸出層有m個神經(jīng)元，BP網(wǎng)絡的實際輸出為y，期望輸出為y′，則損失函數(shù)ε為：

權值的修正值為：

考慮到坐標點較多，對每個點的速度進行預測計算量極大，故對同一道路速度取平均值，預測整條路的速度。綜上，將當前時間、道路名稱以及道路速度三個因素作為輸入值，確定輸入節(jié)點數(shù)為3，輸出值為預測道路名稱及道路所對應的速度。經(jīng)處理，共有115 條道路，即輸出層所對應的節(jié)點數(shù)為115。隱藏層選為4 層，節(jié)點數(shù)分別為64、128、256、128。網(wǎng)絡結構如圖4 所示。經(jīng)檢驗，日均速度誤差為4.24%，預測結果在可接受范圍內(nèi)。

圖4 車速預測神經(jīng)網(wǎng)絡結構Fig.4 Neural network structure of vehicle speed prediction

通過數(shù)據(jù)清洗，剔除外圍高速、高架等道路，以交通路口為節(jié)點，根據(jù)主城區(qū)交通布局得到路口節(jié)點分布及其連通情況。

3.3 參數(shù)設計

在算法運行時，考慮到希望算法在初期能夠盡可能擴大搜索范圍，避免陷入局部最優(yōu)，而在后期則能夠較好收斂，設置隨機數(shù)q0與當前搜尋次數(shù)相關，隨著搜尋次數(shù)的增加而增大。

其中，l為當前輪次，lmax為總輪次，此處取50。其余參數(shù)設置：信息素啟發(fā)因子α=3，成本啟發(fā)因子β=2，螞蟻數(shù)量m=15，為在搜索后期保留更多次優(yōu)路徑以供路況發(fā)生擁堵時選擇，信息素揮發(fā)因子λ=0.9。冷藏車以福田祥菱M1后雙輪冷藏車為原型，空車燃油消耗系數(shù)ρ0=1.2，滿載燃油消耗系數(shù)ρQ=2.4，空車重量Qk=3 385 kg，滿載重量Qm=4 880 kg?？紤]裝載時貨物不能填滿空間，設載質利用系數(shù)Ψ=0.92，貨物單價P=20 元/kg，運輸時衰減系數(shù)?1=0.03，裝卸時衰減系數(shù)?2=0.06，早到懲罰系數(shù)ε1=0.002，晚到懲罰系數(shù)ε2=0.005，運輸時制冷成本系數(shù)a=0.01，裝卸時制冷成本系數(shù)b=0.02，油價Pf=7.62 元/L，公路運輸中單位燃料燃燒產(chǎn)生的碳排放量通常為2～5 kg/L，綜合考慮載重、配送距離、坡度等因素確定單位燃料的碳排放成本為2.67 kg/L[20-21]。2021年首批全國碳交易市場中碳交易價格為50 元/T，算得單位碳排放價格PC=0.138 元/L。

各節(jié)點分布及連通情況如圖5所示，其中藍色點為交通節(jié)點，橙色點為配送點，綠色點為配送中心，連線表示兩節(jié)點之間可以通行（連線長度不代表兩點之間實際距離，實際距離為獲取數(shù)據(jù)中道路真實長度）。

圖5 各節(jié)點分布及連通情況Fig.5 Distribution and connectivity of nodes

考慮到市區(qū)規(guī)劃，模擬出各配送點的坐標及其配送需求如表1所示。其中點（14，4）為配送中心，其余點為配送點。

表1 配送點坐標及需求（情景1）Table 1 Coordinates and demand of point（Scene 1）

3.4 對比分析

情景1配送需求如表1所示。

（1）交通情況正常

交通情況正常時，單獨使用蟻群算法，在算法運行過程中螞蟻會在運輸成本較低的節(jié)點中循環(huán)往復，即使將最近經(jīng)過的若干節(jié)點引入禁忌表依然無法收斂。

交通情況正常時，單獨使用Dijkstra 算法得到的運行軌跡如圖6所示，算法之間運算結果對比如表2所示。

表2 交通正常時各算法對比（情景1）Table 2 Comparison of algorithms in normal traffic（Scene 1）

圖6 交通正常時Dijkstra算法車輛A-B行駛路線Fig.6 Vehicle A-B route in normal traffic when using Dijkstra algorithm

相同情況下，使用蟻群-Dijkstra 混合算法得到運行軌跡如圖7所示。

圖7 交通正常時混合算法車輛A-B行駛路線Fig.7 Vehicle A-B route in normal traffic when using hybrid algorithm

（2）交通發(fā)生擁堵

模擬5：40某路段發(fā)生交通事故造成擁堵且擁堵在40 min 后恢復時，單獨使用Dijkstra 算法時得到運行軌跡如圖8所示。

圖8 交通擁堵時Dijkstra算法車輛A-B行駛路線Fig.8 Vehicle A-B route in traffic congestion when using Dijkstra algorithm

相同情況下，使用蟻群-Dijkstra 混合算法得到運行軌跡如圖9所示，運算結果對比如表3所示。

圖9 交通擁堵時混合算法車輛A-B行駛路線Fig.9 Vehicle A-B route in traffic congestion when using hybrid algorithm

表3 交通擁堵時各算法對比（情景1）Table 3 Comparison of algorithms in traffic congestion（Scene 1）

情景2配送需求如表4所示。

表4 配送點坐標及需求（情景2）Table 4 Coordinates and demand of point（Scene 2）

（1）交通情況正常

交通情況正常時，單獨使用Dijkstra 算法得到運行軌跡如圖10所示，算法之間運算結果對比如表5所示。

表5 交通正常時各算法對比（情景2）Table 5 Comparison of algorithms in normal traffic（Scene 2）

圖10 交通正常時Dijkstra算法車輛A-B-C行駛路線Fig.10 Vehicle A-B-C route in normal traffic when using Dijkstra algorithm

相同情況下，使用蟻群-Dijkstra 混合算法得到運行軌跡如圖11所示。

圖11 交通正常時混合算法車輛A-B-C行駛路線Fig.11 Vehicle A-B-C route in normal traffic when using hybrid algorithm

（2）交通發(fā)生擁堵

模擬5：40某路段發(fā)生交通事故造成擁堵且擁堵在40 min 后恢復時，單獨使用Dijkstra 算法得到運行軌跡如圖12所示。

圖12 交通擁堵時Dijkstra算法車輛A-B-C行駛路線Fig.12 Vehicle A-B-C route in traffic congestion when using Dijkstra algorithm

相同情況下，使用蟻群-Dijkstra 混合算法得到運行軌跡如圖13所示，運算結果對比如表6所示。

圖13 交通擁堵時混合算法車輛A-B-C行駛路線Fig.13 Vehicle A-B-C route in traffic congestion when using hybrid algorithm

可見，在城市交通網(wǎng)絡內(nèi)蟻群算法無法完成搜尋任務。相比于Dijkstra算法，混合算法通過預留信息素，綜合考慮需求時間窗、懲罰成本等因素，緩解了在純貪心規(guī)則下由于選擇當前道路成本最低而提高整體成本的問題。同時，由于在每輪搜索時在當前成本最低和總成本最低的路徑上同時留下信息素，使得當總成本最低路徑出現(xiàn)擁堵時，也能較好找到次優(yōu)解。

在情景1與情景2中，當路徑出現(xiàn)擁堵時，若采用貪心Dijkstra 算法進行計算，所得路徑總成本較使用貪心Dijkstra 算法計算且交通情況不擁堵時分別增加了16.76%、11.01%；若采用混合算法進行計算，所得路徑總成本較混合算法進行計算且交通情況不擁堵時分別僅增加了11.51%、8.38%；而當路徑出現(xiàn)擁堵時，采用混合算法進行計算較Dijkstra 算法相比，所得路徑總成本降低了14.89%、8.02%。同時，由于預留了成本修正地圖，在交通情況發(fā)生變化時不需要重新計算所有路徑成本，只需計算交通情況變化路段的成本，因此計算時間大大縮短，由原先的124.03 s分別降低到了34.17 s、41.03 s。

通過對比分析，混合算法能夠有效降低搜尋路徑成本，同時通過預留修正成本地圖，減少計算量，提高搜尋效率，進而提高反應速度。

4 結束語

本文以城市局部網(wǎng)絡模型為對象，利用歷史數(shù)據(jù)對未來一段時間內(nèi)不同道路的車輛運行速度進行預測，并在此基礎上，分別用蟻群算法、Dijkstra 算法以及蟻群-Dijkstra混合算法進行求解。實例證明：（1）在城市內(nèi)交通網(wǎng)絡復雜的情況下，混合算法能夠有效改善蟻群算法無法有效收斂、Dijkstra算法易陷入局部最優(yōu)的問題，得到較優(yōu)結果。（2）通過預留修正成本文件，能夠大幅降低算法計算時間，提高應對交通異常時的響應速率。（3）計算電腦配置為Intel Xeon Processor（Skylake，IBRS）2.30 GHz（4處理器），考慮到單臺電腦計算能力有限，若使用邊緣云計算有望能提高運算速度，達到實時處理交通異常問題的能力。