不同車型新能源車在城市冷鏈物流配送中的路徑優化

閆淼， 初良勇,2

(1.集美大學航海學院，福建 廈門 361021; 2.福建航運研究院，福建 廈門 361021)

0 引 言

隨著城市化進程的不斷推進，物流行業向“綠色化”轉型升級已是大勢所趨，新能源車憑借其低污染優勢迅速占據市場，并逐漸取代傳統燃油貨車，成為滿足城市配送需求和解決環境污染問題的首選運輸工具。因此，如何在物流配送中高效利用新能源車受到國內外學者的廣泛關注。

新能源車在配送過程中存在續航能力短、電池容量小、充電不便等短板。為在有限條件下對新能源車進行合理調度，提高經濟效益，部分學者基于充電設施的選址問題和充電行為選擇問題進行研究：楊珺等[1]構建了純電動汽車物流配送系統的換電站選址與配送路徑優化模型，并利用禁忌搜索算法和改進Clark-Wright節省算法的兩階段啟發式算法來求解模型。ADLER等[2]研究了對應不同充電站數量的電動汽車最短路徑問題。HOF 等[3]設計了一種自適應可變鄰域搜索算法來解決電動汽車電池更換站的選址與路徑雙層規劃問題。L?FFLER等[4]考慮到完全和部分充電的可能性，開發了大鄰域搜索和顆粒禁忌搜索的簡單混合算法，以解決由此產生的帶時間窗和單次充電的電動汽車路線問題。同時，也有部分學者的研究側重于新能源車的配送路徑規劃方面：BELTRAN等[5]提出將電動車應用于城市交通運輸中。ARTMEIER等[6]在構建電動汽車的路徑優化模型時，考慮車輛的續駛里程、充電時長、制動時的能量回收等因素，確定成本最低的配送路線。KO?等[7]提出一種基于模擬退火啟發式的精確求解方法來解決新能源車的路徑優化問題。肖建華等[8]構建了基于城市道路限行的多能源多車型混合車輛路徑優化模型，將城市分區域、分車型等限行因素引入車輛路徑問題中，并提出變鄰域搜索算法求解該模型。LI等[9]提出一種融合模因算法和序貫變量鄰域下降法的混合優化算法解決混合動力電動車輛的路徑優化問題。馬冰山等[10]結合多配送中心聯合服務模式的特點和純電動物流車輛的行駛特征，構建了帶時間窗的半開放式多配送中心純電動車輛路徑優化模型。ZHANG等[11]考慮服務時間、電池能量消耗和行駛時間等不確定因素的影響，建立了基于模糊優化的數學模型。

冷鏈物流是隨著制冷技術的發展而建立起來的，已被眾多產品配送所選用。因此，如何將新能源車應用到城市冷鏈物流中，已成為當前研究的重點。馮杰等[12]研究了供應商使用同一車型的純電動冷藏車進行配送，為生鮮產品的路徑優化問題提供了思路。趙志學等[13]依據時變交通路網特點，設計了基于路段劃分策略的行駛時間計算方法，構建時變交通下電動車在城市生鮮配送中的路徑優化模型，根據模型特點設計了自適應改進的蟻群算法。

綜上，雖然已有研究將新能源車應用到城市物流配送中，但鮮有研究考慮在滿足客戶時間窗的條件下，將新能源車應用到城市冷鏈物流中，也缺少考慮新能源車在配送過程中充電需求的研究。同時，當前的研究未考慮根據客戶的實際需求量選擇合適的車型進行配送，不能達到充分利用車輛資源、降低配送成本的目的。基于此，本文討論在客戶時間窗限制下，新能源車的充電需求對車輛配送過程的影響；結合冷鏈配送的實際情況，考慮不同車型新能源車在運輸過程中的耗電，以及在裝卸搬運過程中為維持溫度恒定而產生的耗電，構建不同車型新能源車在冷鏈物流配送中的路徑優化模型，并利用改進的蟻群算法求解相對最優解，驗證模型的有效性。

本文研究的問題可被描述為：一個配送中心擁有多輛新能源車，不同車型的車輛有其相應的額定載質量、最大可充電量等限制；車輛從配送中心發出，為若干個客戶進行服務，客戶時間窗已知，車輛完成任務后返回配送中心；合理設置充電站，以滿足車輛在配送過程中的充電需求。為保證生鮮產品的新鮮度和顧客的滿意度，以配送總成本最低為目標，建立帶軟時間窗的整數規劃模型對城市冷鏈物流配送路徑進行優化。

1 模型構建

1.1 符號說明

已知一個配送中心(用“1”表示)、客戶點集合N和充電站集合A；V={1}∪N∪A為所有節點的集合，i,j∈V；M為車輛類型集合，m∈M；Lm表示車型為m的車輛集合，l∈Lm。Cs,m表示車型為m的車輛的發車成本；Ct,m表示車型為m的車輛單位距離運輸成本；Cc為車輛的單位時間充電成本；dij為節點i與節點j之間的距離；Qm表示車型為m的車輛最大載質量；em表示車型為m的車輛的電池最大容量；qi為節點i的需求量；v為車輛的平均行駛速度；ta,iml、ea,iml分別為車型為m的第l輛車到達節點i時的時間和剩余電量；tv,iml、ev,iml分別為車型為m的第l輛車離開節點i時的時間和剩余電量；rm1表示車型為m的車輛在運輸過程中所產生的單位時間可變耗電量；rm2表示車型為m的車輛在裝卸搬運過程中所產生的單位時間可變耗電量；ts,i為在節點i的服務時間；tc,i為在節點i的充電時間；[te,i,tv,i]為節點i允許服務的時間窗；ε為等待成本和延誤成本懲罰系數；δ為在[0.25,0.30]區間內的一個隨機數。

決策變量：xijml，若車型為m的第l輛車由節點i駛向節點j，則xijml=1，否則xijml=0；yiml，i∈N，若車型為m的第l輛車為節點i服務，則yiml=1，否則yiml=0；ziml，i∈A，若車型為m的第l輛車在節點i充電，則ziml=1，否則ziml=0。

1.2 數學模型

以配送總成本最低為目標，考慮新能源車配送時的電量消耗，構建不同車型新能源車在冷鏈物流配送中的路徑優化模型。若無特別說明，j∈V，i∈V，m∈M，l∈Lm。

min

(1)

s.t.

(2)

(3)

(4)

(5)

(6)

ea,iml≤ev,iml-rm1(dij/v)xijml+em(1-xijml),

(7)

?i,j∈N

ea,iml≥δem

(8)

(9)

tv,iml=max{ta,iml,te,i}+ts,iyiml+tc,iziml

(10)

ta,iml=tv,iml+(dij/v)xijml

(11)

(12)

xijml,yiml,ziml∈{0,1}

(13)

式(1)為目標函數，表示配送總成本最低，配送總成本包括固定成本、運輸成本、懲罰成本和充電成本。式(2)～(15)為模型約束條件：式(2)和(3)表示所有客戶均得到服務且僅被一輛車服務；式(4)表示到達節點與離開節點的車輛相同；式(5)表示車輛的初始出發點和最終到達點均為配送中心；式(6)為車輛載質量約束；式(7)表示車輛的電量與行駛里程之間的關系；式(8)考慮到不同車型新能源車的電池特性及駕駛員的里程焦慮，保證車輛的剩余電量不低于該車輛最大電池容量的25%～30%；式(9)表示車輛離開節點的電量；式(10)和(11)分別表示車輛的離開和到達時間；式(12)為每個節點的時間窗約束；式(13)為決策變量約束。

2 算法設計

本文研究的問題是典型NP難問題，傳統精確算法難以對該類問題進行快速求解，故應用元啟發式算法求解。蟻群算法[14](ant colony optimization, ACO)具有正反饋性和自組織性，是解決車輛路徑問題的有效算法之一，但也存在初期收斂速度較慢、易陷入局部最優等問題。海洋掠食者算法[15](marine predators algorithm，MPA)擁有強大的搜索能力和較好的開發性能。因此，本文設計一種融合MPA與ACO的算法(記為MPA-ACO)對模型進行求解。

2.1 MPA預搜索路徑

傳統ACO通常將初始信息素設為一個定值，這也導致了ACO在初期收斂速度慢的問題，本文先采取MPA對車輛路徑進行預搜索，再將其搜索到的路徑上的初始信息素含量提高，從而提高算法的初期搜索能力。

2.1.1 優化階段

MPA用獵物代表可行解，一個獵物代表一條路徑，每個獵物都有其位置向量，以及在位置下的適應度，獵物在不同階段采取不同的策略進行移動。若獵物適應度在新位置下更優，則更換位置，其中表現最優異的獵物將會被視為掠食者。經過多次迭代，實現路徑預搜索任務。MPA分為以下3個主要階段，其數學模型表示如下：

階段1當迭代次數小于最大迭代次數的1/3時，種群中的掠食者速度比獵物速度快，算法進入探索階段，其優化過程如下：

(14)

式中：掠食者和獵物均為搜索個體h，sh為其步長；RB為呈正態分布的布朗運動隨機向量；Eh為n×d維的頂級掠食者矩陣，n為種群規模，d為個體維度值；Ph為獵物矩陣；P為等于0.5的常數；R為0至1內的均勻隨機向量。

階段2當迭代次數大于最大迭代次數的1/3而小于其2/3時，掠食者速度與獵物速度相同，獵物基于Lévy游走策略負責開發，掠食者則基于布朗游走策略負責探索，算法進入探索與開發階段，其優化過程如下：

(15)

(16)

式中：RL為符合Lévy游走的隨機向量；c為控制掠食者運動步長的自適應參數。

階段3當迭代次數大于最大迭代次數的2/3時，掠食者速度比獵物速度慢，算法進入開發階段，其優化過程如下：

(17)

2.1.2 魚類聚集裝置效應及渦流效應

為避免算法在尋優過程中出現過早收斂的情況，加入魚類聚集裝置(fish aggregating devices, FAD)和渦流效應來改變動物覓食行為：

Ph=

(18)

式中：Fs為0.2，表示優化過程中受FAD影響的概率；U為二進制向量；r為0到1內的隨機數；Pr1和Pr2表示獵物矩陣的隨機索引；Xmax和Xmin為包含維度上下限的向量。

2.2 螞蟻尋優策略及信息素更新方式

2.2.1 可行路徑的構建

考慮到新能源車在配送過程中存在電量耗盡的風險，在選擇下一個配送點時，應考慮該點距離其最近充電站的距離，距離越小被選擇的概率越大。將轉移概率根據車輛所在地點不同分為：充電站與配送點的轉移概率和配送點之間的轉移概率。

(1)螞蟻k從充電站i到配送點j的轉移概率

pkij(t)=

(19)

式中：τij(t)為在t時刻在節點i與節點j上存留的信息素；ηij(t)為啟發函數，ηij(t)=1/dij；tth,j為客戶j的時間窗寬度；tw,j為客戶j的等待時間；Ak為螞蟻k接下來有權訪問的客戶點的集合；α、β分別表示信息素和啟發信息在螞蟻尋找路徑中的重要程度；γ、λ分別為時間窗寬度、等待時間在螞蟻尋找路徑中的重要程度。

(2)螞蟻k從配送點i到配送點j的轉移概率

pkij(t)=

(20)

式中：ξj(t)為電量補給難易函數，ξj(t)=1/mindjp，mindjp為客戶點j到最近的充電站p的距離，djp越大說明選擇客戶點j時在途中耗盡電量的風險越大，電量補給越難；θ為電量補給難易因子。

2.2.2 信息素更新方式

信息素指引著螞蟻的移動，在完成所有節點的配送后，將按照當前螞蟻所選擇的路徑對全局信息素進行更新。信息素蒸發公式及更新公式如下：

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

0<ρ≤1

(21)

Δτij=Q/DT

(22)

式中：ρ為信息素蒸發率；Δτij為本次循環中螞蟻所選定路徑的信息素增加量；Q為常數；DT為該螞蟻所構建完整路徑的總距離。

2.3 MPA-ACO設計

先通過MPA預求解出車輛配送路徑，然后將相應路徑上的信息素含量提高。螞蟻從固定配送中心出發并隨機選擇配送車型，從滿足載質量、距離、電量和客戶時間窗約束的需求點中，根據尋優策略中的概率進行選擇，在完成當前需求點的配送服務后，將該點置入禁忌表。若電量不足以完成配送，則應根據就近原則選擇充電站補充電量。若不能滿足客戶點需求，則應返回配送中心。螞蟻可在配送中心重新選擇車輛進行補貨作業，并繼續選擇需求點執行配送服務，當所有需求點均被服務后，螞蟻停止配送服務。算法步驟如下：

步驟1初始化算法相關參數：ACO迭代次數、信息啟發式因子、螞蟻數、期望啟發式因子等參數。

步驟2根據MPA預搜索出的路徑設置初始信息素。

步驟3螞蟻從配送中心出發，隨機選擇不同車型的車輛。

步驟4根據轉移概率(式(19)和(20))選擇滿足約束條件且不在禁忌表內的需求點，放置到當前解中，并錄入禁忌表。

步驟5在螞蟻搜索到的可行路徑中找到最優路徑后，根據式(21)和(22)更新全局信息素。

步驟6判斷是否已經達到最大迭代次數。如果未達到，則轉到步驟2；否則停止運算，輸出當前值作為最優路徑。

3 算例驗證與結果分析

3.1 實驗設置

采用實際數據并結合算例進行分析。實際數據來自廈門市某生鮮食品公司的40個訂單數據，如表1所示。算例改編自SOLOMON[16]的帶時間窗的車輛路徑問題(vehicle routing problem with time window, VRPTW)數據集。為模擬實際配送情況，做出如下修改：(1)車輛在充電站的充電時間受車輛充電效率、到達充電站的剩余電量影響，設定車輛離開充電站時，電池為滿電狀態。(2)假設配送中心擁有A、B兩種車型的新能源車，車廂內溫度需要根據外界氣溫的變化控制在-4 ℃至4 ℃，平均行駛速度為45 km/h，車輛單位充電成本為1元/(kW·h)，平均充電速度1.5 kW·h/min。(3)早于或晚于客戶時間窗服務所產生的單位時間懲罰成本為ε=0.5元/min。車輛相關參數見表2。

表1 實際訂單數據

表2 車輛相關參數

3.2 實際應用

根據廈門市某生鮮食品公司實際節點數，設置螞蟻數量K=75。根據多次實驗，設置基本參數如下：α=1，β=4，γ=1，ρ=0.3，最大迭代次數為100次。程序運行20次，取其中的最優路徑。最優路徑圖見圖1，具體優化結果見表3。

圖1 最優路徑圖

表3 車輛路徑優化結果

通過計算可得，配送總成本為2 337.1元，使用7輛電動車，固定成本為1 520元，運輸成本為401.95元，懲罰成本為294.81元，行駛里程為680.21 km，其中有2輛車在配送過程中進行了充電，充電成本為120.34元。數據表明，本文提出的模型和算法在綜合考慮了不同車型的指派、客戶時間窗和新能源車的充電需求的基礎上，有效減少了行駛里程，提高了客戶滿意度。本文所構建的不同車型新能源車在冷鏈物流配送中的路徑優化模型對該生鮮食品公司在降低配送總成本方面具有重要參考價值。同時，本研究為采用新能源車作為運輸工具的物流配送企業的實際操作提供了優化模型和算法支持。

3.3 模型對比分析

為明確不同車型新能源車在冷鏈物流配送中的作用，將原模型的決策變量xijml改為xijl，構建單一車型新能源車在冷鏈物流配送中的路徑優化模型(簡稱為“單一車型配送模型”)，與上述所構建的不同車型新能源車在冷鏈物流配送中的路徑優化模型(簡稱為“多車型配送模型”)的結果進行對比，采用MPA-ACO求解，并以SOLOMON[16]的VRPTW數據集為參照。SOLOMON的數據集設計了R(隨機分布)、RC(混和分布)和C(成群分布)3種類型的客戶點分布，其中：R類客戶點的地理位置分布較為分散；C類的為堆分布，表現為客戶的地理位置向一個或者多個小范圍內聚集；RC類的為半堆分布，表示客戶的地理位置是混合分布的。對比結果見表4。

分析表4可得：(1)多車型配送策略下的配送總成本低于單一車型配送策略下的配送總成本，前者明顯比后者低了0.55%～4.10%，表明采用不同車型進行配送，可以合理調配車輛資源，降低整體運輸成本，為企業盈利帶來增長空間。(2)單一車型配送策略下，不同噸位大小的車輛在不同應用場景中各有優勢。通過對比采用A、B兩種單一車型的車輛的使用數量和充電次數可知，采用B車型可使配送車輛數量和充電次數明顯減少，表明B車型更適應長時間、遠距離運輸。然而，在進一步分析兩種車型的各項成本后發現，A車型具有較低的固定成本和運輸成本，其配送總成本比采用B車型的低0.02%～0.03%，表明在整體配送區域較小、單個客戶點需求量較小的環境中，采用小噸位車型比采用大噸位車型配送更具有成本優勢。

3.4 算法對比分析

為進一步驗證算法的有效性，采用R112算例對MPA-ACO與傳統ACO進行比較。設置1個配送中心、50個客戶點、5個充電站。實驗隨機進行20次，求解結果對比見圖2。圖3為其中一次實驗的迭代對比圖。

表4 兩種模型結果對比

圖2 MPA-ACO與ACO求解結果對比

圖3 MPA-ACO與ACO迭代對比

由圖2可知，MPA-ACO求得的配送總成本平均低于ACO求得的配送總成本。由圖3可知，本文算法在尋優能力和收斂速度上都有大幅度提高:在優化初期，得益于MPA的路徑預搜索，MPA-ACO具有較強的搜索能力；在優化中后期，MPA-ACO能更早收斂，且找到的路徑更優。通過實驗計算可得，雖然MPA-ACO的平均運行時間為12.19 s，ACO的平均運行時間為9.06 s，但兩者均能在較短時間內得到最優解。綜上說明，引入MPA，能夠有效提高ACO的局部搜索能力和全局收斂能力，為ACO的改進提供新思路。

3.5 充電站數量靈敏度分析

在采用不同車型新能源車進行配送的情況下，為分析充電站數量的影響，針對R、RC和C這3類客戶點分布，在其他條件不變的情況下調整充電站的數量對模型進行求解。對每個算例求解10次，選擇其中的最優解進行比較，結果見表5。

分析表5可得：(1)配送總成本會隨著充電站數量的增加而降低，而當配送總成本降低到一定程度后變化趨于平緩。在3類客戶中，當充電站數量超過6時，配送總成本的變化不再明顯，這是因為在一定區域內，充電站數量的增加雖然可以為車輛提供更多的路徑選擇，但若該區域的充電站數量已達到飽和狀態，則過多的充電站將增加充電站的建設和維護成本，降低該區域充電站的平均使用率。(2)對于呈聚集分布的C類客戶而言，隨著充電站數量的增加，優化效果更佳；R類和RC類客戶的配送總成本受充電站數量的影響較小，當充電站數量增加至4～5時，配送總成本的下降趨于平緩。C類客戶的配送總成本的下降趨勢最明顯，這是因為其分布具有聚類特點，在客戶聚集地周圍建設充電站，可明顯降低車輛的運輸成本和充電成本；同時隨著充電站數量的增加，配送車輛也由6輛減少至5輛，表明針對聚集分布的客戶，合理建造充電站可以有效減少車輛投入。

4 結 論

本文以城市冷鏈物流配送為研究對象，在采取新能源車進行配送的基礎上，結合不同車型的優勢，以包括固定成本、運輸成本、懲罰成本和充電成本的配送總成本最低為目標，同時考慮了車輛載質量約束、客戶時間窗限制、車輛充電需求等因素，構建了不同車型新能源車在冷鏈物流配送中的路徑優化模型。利用融合了海洋掠食者算法(MPA)的蟻群算法(ACO)對該問題進行求解，并驗證了算法的有效性。本文的研究成果可證明，將不同車型新能源車用在城市冷鏈物流配送中可以有效降低整體配送成本，減少車輛資源的閑置與浪費，為企業在城市配送中的資源分配提供有益啟示。

表5 不同客戶點分布類型下充電站數量靈敏度分析