考慮載重影響的動力電池回收車輛路徑問題研究

方云飛，王玉歡，劉玉飛

（福州大學，經濟與管理學院，福州 350108）

0 引言

與傳統燃油車輛相比，電動汽車（Electric Vehicle，EV）因其由可再生能源驅動，對環境友好等優勢受到我國政府的大力推崇。經過數年的普及和推廣，我國電動汽車產業得到良好的發展，第一批電動汽車動力電池退役的高峰期即將來臨，預計到2025 年，電池退役數量將達到78 萬t[1]。當前動力電池回收市場亂象叢生，國內僅有27 家動力電池正規回收企業[2]，退役的動力電池更多地流入非正規渠道中，非專業的拆解程序會對環境造成嚴重的污染。動力電池的回收利用對經濟及環境的影響重大，針對現存的回收難題，在生產者責任延伸制度下，制造商作為動力電池回收的責任主體，必須更為合理地規劃動力電池的回收程序[3]。

在動力電池回收過程中，運輸成本在總回收成本中的占比極高[4]，存在較大的可壓縮空間。近年來，電動汽車在貨物運輸行業逐步得到應用，針對此類車輛行駛路徑的研究被稱為電動汽車車輛路徑問題（Electric Vehicle Routing Problem，EVRP）。雖然在逆向回收運輸方面，電動汽車尚處于起步階段，但李英等[5]在研究電動汽車/傳統汽車混合車隊車輛配置問題時，認為電動汽車具有高固定成本和低可變成本的特點，結合電動汽車的運輸成本優勢和制造商的資源優勢，考慮采用電動汽車開展動力電池回收工作能夠大幅度降低回收成本。

當前研究各行業回收路徑優化的文獻頗多[6-8]，而對采用電動汽車開展逆向物流作業的研究較少。Qin等[9]對現有的電動汽車車輛路徑問題進行了綜述，將EVRP 歸納為9 類，并對各類問題的模型約束及求解策略展開了分析。目前國內外學者對電動汽車車輛路徑問題的研究主要集中在考慮里程約束的日常路徑規劃上。Schneider 等[10]提出帶時間窗和換電站的EVRP問題模型，考慮了車輛容量及電池容量的約束，建立車輛使用數量最少及行駛距離最小的雙目標模型，結合禁忌搜索原理設計變鄰域搜索算法對模型進行求解。Keskin 和?atay[11]、揭婉晨等[12]均在Schneider 等[10]的基礎上對電動汽車車輛路徑問題進行研究。前者通過放寬電動汽車在充電站處只能進行完全充電的限制，建立帶有時間窗的允許部分充電的EVRP 模型，并提出自適應大鄰域搜索算法來改善路徑決策；后者則擴展了車輛類型的多樣性，設計以列生成為基礎的分支定價算法對模型進行求解。程坦等[13]在部分充電策略下的多車型電動汽車車輛路徑問題中，考慮了車型載重、固定成本、可變成本、續航里程和充電速率的異質性，設計了包含局部搜索的自適應大規模鄰域搜索算法，并分析對比了完全充電和部分充電兩種策略下的實驗結果。趙冰[14]考慮配送中存在多個配送中心的實際情況，研究了多車場EVRP 問題，以配送過程中產生的總成本最低作為決策目標，建立含時間窗和電量約束的模型，根據問題的特點設計了兩階段混合算法。揭婉晨等[15]在考慮行駛里程限制、車輛數量限制以及采用換電策略的基礎上，研究了顧客需求可拆分的EVRP問題，設計了以列生成為基礎的分支定價算法。邵賽等[16-17]在考慮充電、里程和載重三方面共同約束的基礎上，研究了動態的EVRP問題，分別考慮客戶的動態需求以及車輛動態行駛時間的影響，建立了相應模型并進行求解。

上述研究都假設電動汽車的能源消耗直接與行駛里程相關，忽略了載重因素對車輛電能消耗的影響。部分學者將能源消耗模型進行擴展，使研究更符合實際情況。Goeke 等[18]將EVRP 擴展到由電動汽車和燃油汽車組成的混合車隊，在綜合考慮因車輛行駛速度克服空氣阻力等因素影響的基礎上建立了能源消耗模型。沈續昌[19]將貨物重量對電動汽車能源消耗的影響考慮在內，在Goeke 等[18]提供的能源消耗模型基礎上，建立同時取送貨的EVRP 模型，并采用遺傳算法進行求解。Macrina 等[20]針對允許部分充電的帶時間窗的EVRP問題，提出了多屬性的能源消耗模型。

上述文獻綜合考慮了各方面因素對電動汽車電池能源消耗的影響，一定程度上解決了EVRP問題中對于能源消耗量化的難題，但多數考慮的是傳統配送貨的場景，很少研究逆向物流動力電池的回收車輛路徑問題，且上述研究沒有同時考慮載重影響能耗以及多車場協同回收因素。在動力電池進行回收的過程中，由于動力電池重量較大，載重對車輛電能消耗的影響在制定路徑規劃方案中變得越發重要，必須考慮載重量和行駛里程對電池能量消耗的共同影響。另一方面，目前我國動力電池回收服務網點數量呈爆發式增長，考慮多個制造商共同負責回收更為合理。本文建立采用電動物流車回收、考慮電池能量消耗、多車場的動力電池回收車輛路徑問題，并針對此問題設計了文化基因算法進行求解。

1 問題描述與數學模型

1.1 問題描述

假設有多個制造商負責對附近的多個回收服務網點的動力電池進行回收。制造商車場處有若干輛電動物流車，車輛以滿電的狀態從車場出發，行駛至各回收服務網點處進行動力電池回收。假設回收過程中車輛不進行充電，當車輛完成回收任務或者剩余電池電量低于安全電量時需要返回車場。回收過程需要保證每個網點處的動力電池都能得到回收，且車輛不能超載。要求合理規劃車輛的路徑以回收各服務網點處的動力電池，使得回收的物流總成本最低。為了便于研究問題，做出以下假設：

（1）各回收服務網點的位置、動力電池數量，以及各制造商車場的位置均已知。

（2）一輛車可以服務多個回收網點，但一個回收網點有且僅由一輛車為其服務。

（3）車輛的額定載重和電量相同，從網點回收到的動力電池總重量不超過其額定載重。

（4）每個回收網點均在車輛行駛里程范圍內，且網點的動力電池重量不超過車輛的額定載重。

（5）車輛充滿電從車場出發，不考慮回收過程的中途充電，但剩余電量不低于其安全電量。

（6）回收過程中車輛的能耗與行駛距離和載重有關，不考慮裝卸過程中的能耗。

1.2 數學模型

為了便于構建模型，定義如下相關參數和變量：

D表示制造商車場集合；

S表示回收服務網點集合；

N表示制造商和回收服務網點的集合，N=D∪S；

K表示車輛集合；

dij表示節點i到節點j的最短道路距離，km；

vij表示車輛從節點i到節點j的平均行駛速度，km/h；

A1表示車輛使用的固定成本，元/輛；

A2表示司機的時薪，元/h；

A3表示車輛的單位充電成本，元/kW·h；

Cd表示空氣阻力系數；

Cr表示滾動阻力系數；

E表示車輛的額定電量，kW·h；

g表示萬有引力系數；

hf表示發動機額定功率，kW；

qi表示回收服務網點i處可回收的動力電池重量；

Q表示車輛的額定載重，kg；

R表示車輛正面面積，m2；

W表示車輛自重，kg；

M表示一個較大的正數值；

β表示車輛最低安全電量水平；

ρ表示空氣密度，kg/m3；

bij表示實數變量，表示車輛從節點i到節點j消耗的電量，kW·h；

yi表示實數變量，表示車輛訪問節點i后的累計載重量，kg；

ei表示實數變量，表示車輛訪問節點i后的累計耗電量，kW·h；

xij表示0-1 變量，若有車輛從節點i行駛到節點j，則為1，否則為0。

本文以回收過程中產生的物流總成本最低為目標建立模型，其中總成本由三方面構成：

（1）固定成本 每輛電動物流車因執行任務而產生的成本，假設每輛車產生的成本為定值，即固定成本只與使用的車輛數量相關。

（2）行駛成本 因支付司機工資等產生的成本，假設車輛以勻速進行行駛，則司機的工作時間可用總行駛距離和車輛平均行駛速度表示。

（3）充電成本 車輛行駛過程中消耗電量產生的成本，假設能耗與行駛距離和載重有關。總成本可表示為：

特別地，bij為車輛從節點i到節點j消耗的電量，是載重和行駛距離的函數。參考相關資料[17]，車輛行駛過程中的能源消耗函數如下：

根據上文問題描述及定義的相關符號，本文研究的動力電池回收路徑規劃問題可構建為如下非線性混合整數規劃模型：

路徑約束：式(4)表示從車場出發的車輛數不超過給定的車輛數；式(5)表示車輛在每個節點滿足流平衡約束，即若訪問該節點則必離開該節點；式(6)表示每個服務網點只能被訪問一次；式(7)表示車輛不能在不同車場之間行駛。

載重約束：式(8)表示若車輛經過弧()i,j，則車輛在節點j的載重量等于節點i的載重量加上節點j處回收的動力電池的重量；式(9)表示車輛訪問每個回收服務網點后的載重量不能超過其額定載重；式(10)表示車輛離開車場時的載重為0。

電量約束：式(11)、(12)表示離開車場或回收服務節點i后到達節點j的累積耗電量等于駛離節點i的耗電量加上在路程()i,j之間行駛消耗的電量；式(13)表示電動物流車的能耗不超過其安全電量。式(14)、(15)定義了變量的取值范圍。

2 算法設計

2.1 文化基因算法框架

本文研究的動力電池回收路徑規劃問題屬于車輛路徑問題，是NP-hard 問題，其復雜性隨問題規模增大而迅速增加，難以在合理時間內通過優化軟件求出問題的精確解。因此設計高性能算法獲取問題的高質量解是一種較為切實可行的求解思路。針對所研究問題，本文提出了一種基于遺傳算法(Genetic Algorithm，GA)的全局廣域搜索和基于個體的局部深度搜索算法（Local Search，LS）相結合的文化基因算法(Memetic Algorithm，MA)。相較于傳統的GA 或LS，MA 具有更好的收斂性和跳出局部最優的能力。在算法中，將Prins[21]和Fallahi 等[22]提出的單車場路徑無分隔符編碼和解碼方式推廣適用于多車場情形；采用染色體分片段交叉的思路獲得可行子代染色體；在局部搜索過程中，設計了四種局部搜索算子以及快速評估鄰域解的方法，以提高算法的尋優效率；此外，通過引入種群管理策略[23]，保證種群具有多樣性，避免算法過早收斂。算法流程如圖1所示。

圖1 文化基因算法流程圖

2.2 染色體編碼與解碼

在所設計算法中，問題的解編碼為由車場狀態向量和回收服務網點序列構成的染色體，其編碼規則如下：令表示從車場d出發的車輛k訪問的回收服務網點序列，那么車場d中全部車輛所服務的網點序列為，則(S1,S2,…,S|D|)可表示染色體中的服務網點序列向量。注意到車場d服務的網點總數為|Sd|，各車場服務的第一個網點分別是網點序列向量的第1，|S1|+1，|S1|+|S2|+1，…個分量對應的網點，則可用(1，|S1|+1，|S1|+|S2|+1，…表示染色體中的車場狀態向量（若車場不服務任何網點，則其狀態為0），其含義表示車場1 服務的是網點序列向量中1～|S1|分量對應的網點，車場2 服務的是網點序列向量中|S1|+1～|S1|+|S2|分量對應的網點，其他車場服務的網點可類似推導。按照上述編碼方式，對于原問題的解，可編碼為(1,|S1|+1,…,+1,S1,S2,…,S|D|)形式的染色體。注意本文采用無分隔符編碼方式，在服務網點對應的染色體片段中不出現代表車場或車輛的基因，此種編碼縮短了染色體長度且有利于簡化染色體間的交叉運算。

染色體的解碼過程，首先需要確定每個車場訪問哪些服務網點。其次，考慮車輛載重和電量的限制，分配給每個車場的多個服務網點可能無法由一輛車完成所有服務，需要確定車場啟用的車輛數以及每輛車訪問網點的路線。由于采用無分隔符編碼方式，染色體并沒有顯性地表達出每輛車的路徑，因此需要對既定的染色體作劃分以確定不同車輛的路徑，即在滿足各約束的前提下，將一個無分隔符的染色體劃分出車場的若干條可行路徑。

Prins[21]提出了一種splitting 算法對既定的染色體進行最優劃分解碼，以獲得最佳路徑。如圖2所示，在單條染色體中，splitting算法從左往右掃描染色體1—2—3—4—5—6，依次為每個節點生成標記，并標出所有的可行路徑。隨后，splitting算法根據各節點的標記對整條染色體進行最優劃分，最優劃分需從染色體末尾開始：首先，最末位即節點6 的標記L6=3，表示把節點3 的后繼節點，即節點4，作為路徑的第一個訪問點，節點6作為路徑的最后訪問點，劃分出路徑0—4—5—6—0，其路長為80。以此類推，根據節點3 的標記L3=1，劃分出路徑0—2—3—0，路長為68。根據節點1 的標記L1=0，劃分出路徑0—1—0，路長為28。至此，染色體被解碼為這3條路徑，其路徑總長為176。

圖2 染色體splitting解碼示意圖

圖3 給出了染色體編碼和解碼過程的示例。該染色體由3 個車場和11 個服務網點組成。考慮染色體的車場狀態（圖3(a)）時，可以看到車場1 和車場3 是啟用的，而車場2 未被使用，并且可以看到分配給1 號和3 號車場的第一個網點的索引分別為7和1，這意味著服務網點序列中索引在1和6之間的網點（即4—10—6—8—9—2）被分配到車場3，索引在7 和11 之間的網點（即11—5—7—1—3）被分配到車場1（圖3(b)）。在進行完上述分配之后，通過使用上文的splitting 算法進行路徑劃分過程（圖3(c)），最終獲得該染色體解碼的最優回收路徑（圖3(d)）。

圖3 染色體編碼和解碼示意圖

2.3 種群初始化

初始種群采用隨機產生樣本的方式依次生成個體，然后計算新個體與種群現有個體的差別，即目標差值。若差值大于給定閾值，則將該新個體添加到初始種群，否則舍棄該個體并重新產生新個體。不斷重復執行上述操作，直到初始種群中個體數量達到規定的種群規模。通過設定個體差值閾值，可在一定程度上保證種群個體的多樣性。

2.4 選擇算子

采用二元錦標賽[24]的方式對種群中的個體進行選擇操作。從生成的初始種群中隨機選擇2 個個體，需要注意的是，在進行此項操作的過程中每個個體被選擇的概率相同，將2 個個體進行比較，選擇其中表現較好的一個作為父代，重復執行上述操作，一共選出兩個個體作為交叉操作的父代。

2.5 交叉算子

對選擇算子選出的兩個父代染色個體采用交叉算子操作生成一個子代染色體，以在搜索空間中尋找新的解。交叉算子是通過交換父代之間的一些信息來獲得新子代。染色體由兩種不同的編碼類型組成，即車場狀態的整數編碼和服務網點的排列編碼。因此，染色體的這兩部分分別使用不同的交叉算子。在所設計算法中，對應車場狀態的染色體片段使用單點交叉[25]，對應服務網點序列的染色體片段使用順序交叉（OX）[26]。

如圖4 所示，在單點交叉過程中，在父代染色體P1和P2車場片段上隨機選擇一個剪切點進行分割，將P1位于剪切點右側的染色體車場片段與P2相應片段進行交換，從而得到子代染色體C 的車場片段。在順序交叉過程中，在父代染色體服務網點序列片段上隨機選擇兩個剪切點，需要注意的是，在此過程中兩條染色體被選取的位置必須是相同的，將P1兩個剪切點之間的基因片段復制到子代染色體C 中對應的位置，然后從P2中獲取C缺失的基因，從第一個基因位置開始按照順序補充到C 剩余的基因位上。將新生成的染色體車場片段和服務網點序列片段組合即得到子代染色體。

圖4 交叉示意圖

2.6 局部搜索

MA 沒有使用變異操作，而是采用路徑移除、單點移除、交換和合并四種經典算子對交叉產生的子代進行局部搜索，以使種群個體的進化更迅速，從而提高算法尋找優質解的效率。

路徑移除：從某個車場出發的路徑中隨機移除一條路徑，并將其分配給其他車場。該算子不改變網點的服務順序，只調整服務的車場，是一種搜索范圍較小的操作。

單點移除：隨機選擇一個回收服務網點，將其從當前位置移除，并插入到屬于同一車輛或不同車輛的最佳位置。若路徑中只有一個回收服務網點，則移除后該路徑完全消失，此操作可以節約車輛的固定成本。

交換：隨機選擇兩個回收服務網點，將其所在路徑中的位置進行交換。只有當交換之后的路徑仍然能夠滿足車輛的載重、電量約束，且交換之后的目標值更小時才會選擇保留當前的交換操作。

合并：隨機選擇兩條路徑，將其合并為一條新的路徑，操作分兩個步驟。首先將第一條路徑的服務網點整體插入到第二條路徑的最佳位置，或是將第二條路徑的服務網點整體插入到第一條路徑的最佳位置；其次是將合并的服務網點序列分配給最佳車場。在每個合并操作中對所有可行的合并方案進行評估，選擇成本節約最大的方案作為最終操作。

2.7 種群管理

不同于GA 對種群大部分個體進行選擇復制、交叉、變異操作，MA 的種群規模較小。通過種群管理策略[17]可以動態控制小種群高質量個體的多樣性，從而避免算法過早收斂，同時減少運算，提高算法尋優的效率。

種群管理策略是依據一定條件決定是否接受局部搜索得到的子代改進解C*來更新種群替換其中的某個個體。對于個體數量為n的種群Ω，假設個體目標值最小和最大的個體分別表示為P1和Pn。如果子代C*滿足Z(C*) Z(Pn)，則舍棄C*；如果Z(P1) ≤Z(C*) ≤Z(Pn)，并且滿足?ω∈Ω{Pk} :|Z(ω)-Z(C*)|≥Δ,{k|k∈Z,n/2 ≤k≤n}，則允許C*替換掉種群中的個體Pk。其中，Δ 是大于0的閾值，用于控制種群個體之間的“距離”，保證種群的多樣性。Δ 值隨著MA 算法迭代的次數增加而線性遞增。因此，在算法初期，C*較易進入種群，在算法后期，C*的目標值必須與種群個體的目標值有顯著差異，方可進入種群。

3 仿真實驗分析

為了驗證模型的可靠性以及算法的有效性，選擇多組算例作為測試數據進行仿真實驗。在本節仿真實驗中程序采用MATLAB 2018b 編程，在Windows10 操作系統、3.60GHzCPU、16 G 內存的環境下運行。

3.1 實驗參數說明

本節算例由標準算例Cordeau’s Instance（http：//www.bernabe.dorronsoro.es/vrp/）調整而來。實驗數據采用標準算例中的客戶和車場的坐標、需求，在此基礎上加入車輛能耗參數[17]以及電動車相關參數[18]，參數具體取值如表1 和表2 所示。對于與Lingo 比較的小規模算例，隨機選取標準算例中的一部分客戶和車場產生，其余參數見表1 和表2。實驗中，每個算例測試5 次，取其平均值為最終結果，結果保留兩位小數。

表1 模型相關參數

表2 純電動物流車相關參數

3.2 實驗結果及分析

3.2.1 實驗一：與LINGO最優解的比較

首先對文化基因算法的求解性能進行實驗。由于本文構建的模型中含有非線性約束，采用LINGO 11.0 軟件對模型求解隨機生成10 組不同規模的算例，結果如表3所示。其中，| |D表示車場數量，|S|表示回收服務網點數量，Obj為求解目標值，T(s)為問題求解時間。

由表3 可以看到，MA 能夠快速求解表中10個算例，而LINGO 只能求解9 個算例，對于算例pr10無法在2h內給出可行解。對于所測試的算例pr01～pr09，MA 求得目標值變化范圍為5 094.78～9 558.05，計算時間變化范圍為2.57～3.99 s，其均值分別為7 290.73 和3.09 s。從目標函數來看，MA 與LINGO 求得的結果十分相近，相對差在0.00%～1.23%之間，平均相對差為0.67%。從求解效率來看，對于同一規模的算例，MA 明顯優于LINGO 的求解效率。LINGO 求解時間在427～1 253 s 之間，平均求解時間為784.78 s，是MA 求解時間的254 倍。當求解算例pr10 時，LINGO 已經無法在7 200 s 求出問題的最優解，而MA 能夠在4.25 s 給出較好的解。從表3 可以看出，針對小規模算例本文構建的MA 能夠高效地給出高質量解。

表3 MA與LINGO求解結果比較

3.2.2 實驗二：與遺傳算法的比較

對選用的MDVRP標準算例進行調整，分別用本文設計的MA 和GA 進行求解。為公平地比較，GA 所采用的選擇、交叉操作與MA 相關操作一樣，GA 變異算子與MA 鄰域搜索算子一樣。結果如表4和圖5所示。

表4 MA與GA結果比較

圖5 MA和GA目標函數及運行時間

由表4 可以看到，對于所測試的10 個算例分為4車場、6車場兩組算例。對于每一組算例，隨著客戶數增加，MA 或GA 的目標值和計算時間總體呈增長趨勢，具體可見圖5。從目標函數來看，MA優于GA，相對差均為負值，其數值在3.04%～14.16%之間，平均相對差為7.94%，MA 求得的目標值明顯優于GA 求得的目標值。從求解效率來看，GA 求解時間在13.75～61.42 s 之間，平均求解時間為37.26 s；而MA 求解時間在4.73～50.02 s 之間，平均求解時間為24.28 s，只有GA 的0.65 倍，MA 明顯優于GA 的求解效率。可見，對于中大規模算例，MA在求解時間以及求解質量均優于GA。

3.2.3 實驗三：車輛類型對路徑方案的影響

考慮電動物流車型號對回收方案的影響，設置三種不同大小電動物流車的相關參數，并進行分組實驗，結果如表5所示。

表5 不同車輛類型下目標函數值的比較

由表5可以看出，混合車型的整體結果要優于三種單車型的結果，但是求解時間顯著增加。這是因為混合車型的引入增加了問題的復雜度，除了考慮車場服務的網點外，還需要考慮由車場的哪種類型車輛服務，相當于增加了一個決策維度。同時本文算法雖然經過一定調整可求解多車型問題，但主要是針對單車型問題設計的，沒有充分考慮多車型問題的屬性，因而求解效率并不高。從三種單車型結果看，使用中型電動物流車進行回收時目標值最小。與中型車相比，小型車產生的成本較大，最大相差40.21%，最小相差23.43%，平均相差32.77%；大型車產生的成本最大相差5.16%，最小相差0.97%，平均相差2.00%。產生這種結果的主要原因在于：小型電動物流車的額定載重及額定電量小，使得完成回收任務時需要使用更多的車輛，車輛啟用的固定總成本高；大型電動物流車的整車質量大，行駛過程中對電池能量消耗大，最終導致總成本高于中型電動物流車。因此，相關企業在運輸車輛類型的選擇過程中，需要進行多方面因素的綜合考慮以便做出最佳決策。

4 結語

隨著電動汽車市場不斷發展，退役的動力電池處理回收問題變得愈發重要。本文研究了以車輛啟用成本、行駛成本及能耗成本為總目標的動力電池回收多車場車輛路徑問題。首先構建考慮貨物載重的電動物流車路徑規劃模型，考慮了運輸距離和貨物載重對車輛能耗的影響；其次，針對問題的特性設計了遺傳算法和局部搜索相結合的文化基因算法，通過多種局部搜索算子、種群管理等策略來提高算法的求解質量和效率。仿真實驗結果驗證了與優化軟件LINGO及傳統的遺傳算法相比，本文所設計的文化基因算法能夠快速有效求解考慮載重影響的動力電池回收路徑規劃問題，可為企業開展動力電池回收車型選擇和路線規劃提供參考。

本文所開展的研究是考慮充電設施不足，假定回收過程中電動物流車不充電的情形。隨著充電樁、換電站等基礎設施不斷建設和完善，后續研究考慮車輛中途充換電、基于分時充電價格等因素更具現實意義，此外考慮車輛充電排隊等待時間、回收網點的服務時間有利于企業制定更加精準的回收方案，在控制回收成本的同時提升服務水平。