多車場多車型電動汽車路徑優(yōu)化研究

張惠珍，姜 晶

（上海理工大學 管理學院，上海 200093）

0 引言

車輛路徑問題（Vehicle Routing Problem，VRP）作為一個經(jīng)典的NP-hard 問題，研究最早開始于20 世紀50 年代末［1］。VRP 問題如今已不是單純的理論研究［2-6］，所需要考慮的因素越來越多，因此根據(jù)其特性可將其分為很多種，其中，開閉合車輛路徑問題、有容量（比如配送中心、車輛）約束的車輛路徑問題、帶時間窗的車輛路徑問題、考慮周期性的車輛路徑問題、多配送中心或單配送中心的車輛路徑問題、考慮貨物類別和客戶滿意度的車輛路徑問題、新能源汽車車輛路徑問題等是目前比較常見的車輛路徑問題。隨著現(xiàn)代物流業(yè)的崛起，新型的VRP 問題不斷涌現(xiàn)，使其更具有研究價值和現(xiàn)實意義。揭婉晨等［7］用精確算法求解了多車型電動車車輛路徑問題；文展等［8］使用改進的粒子群算法求解帶時間窗的車輛路徑問題，通過對垃圾回收運輸實例的分析，說明相比其他算法，改進后的粒子群算法能夠更有效地減少路徑距離；孔繼利等［9］根據(jù)汽車的能源消耗和污染情況研究綠色車輛路徑問題；辜勇等［10］通過將多配送中心轉換成單配送中心的方式，并且使用三階段算法求解帶時間窗的多中心半開放式車輛路徑混合問題，能夠高效解決大規(guī)模的多配送中心路徑問題；Yu 等［11］在CVRP 的基礎上研究了通過第三方物流參與的開放式選址車輛路徑問題（Open Vehicle Routing Problem，OVRP），其與CVRP 的不同之處在于車輛在服務完所有客戶之后，不用返回配送中心，并提出一種基于模擬退火的算法求解該OLRP 問題，該算法可求解最多318 個客戶、4 個配送中心的車輛路徑問題；Amine 等［12］提出一種基于變鄰域搜索的混合算法求解帶時間窗的車輛路徑問題。

雖然國內外學者已針對使用不同車型進行配送的車輛路徑問題進行了大量研究［13-18］，但將電動汽車應用于物流行業(yè)尚處于初級階段［19-22］，研究多車場多車型電動汽車車輛路徑問題的文獻幾乎沒有。本文在揭婉晨等［7］的基礎上，利用啟發(fā)式算法代替精確算法對多車型的電動車車輛路徑問題進行研究，與揭婉晨等的研究相比，本文能夠在較短時間內對大規(guī)模算例進行求解，并求得最優(yōu)解。針對多車場多車型電動汽車車輛路徑問題，本文在配送線路內增加了鄰域搜索對蟻群算法進行改進，用于求解多車場多車型電動汽車車輛路徑問題［11，23-24］，然后采用數(shù)值實驗進行仿真優(yōu)化，最后通過算例測試驗證了該算法的可行性與有效性，能夠在較短時間內對較大規(guī)模的多車場多車型電動汽車車輛路徑問題求得最優(yōu)解，為多車場多車型電動汽車車輛路徑問題提供了一種新的解決方案。本文采用二階段算法（Two-phase heuristic algorithm，2-phase HA）對模型進行求解，二階段算法的主要優(yōu)勢在于對第二階段蟻群算法的改進，可在給定范圍內使用輪盤賭法隨機進行變動，并通過增加鄰域搜索算子的蟻群算法對MDHEVRP 問題進行求解，得到該問題的最優(yōu)解，從而使蟻群算法擴大了可行域搜索范圍，盡可能避免算法過早陷入局部最優(yōu)，提高了算法收斂速度。

1 問題描述及數(shù)學模型

1.1 問題描述

多車場多車型電動汽車車輛路徑問題（Multi-depot Heterogeneous Electric Vehicle Routing Problem，MDEVRP）是指某企業(yè)有若干配送中心，每個配送中心有多種不同類型的運輸車輛，并且每輛電動汽車的容量都有所限制，每輛電動汽車有一個最大的單次行駛里程，車輛運輸成本與運輸距離成正比。同一個客戶可由多輛車提供服務，且客戶需求量已知。每輛車屬于一個配送中心，從該中心出發(fā)，需要在客戶規(guī)定的時間窗內服務客戶，服務完成后回到該中心。電動汽車從配送中心出發(fā)時電量是充滿的狀態(tài)，在行駛過程中會消耗電量，在必要時需到換電站更換電池，之后繼續(xù)服務客戶，直到服務完成后回到配送中心。該研究的最終目的是為每輛車規(guī)劃合理的路徑，使企業(yè)的物流成本最低。

1.2 模型假設

假設某企業(yè)有m 個配送中心，每個配送中心有n 種類型的電動運輸車輛，并且車輛容量有所限制，每輛電動汽車都有一個最大的單次行駛里程，車輛運輸成本與運輸距離成正比。每個客戶只能由一輛車提供服務，且客戶需求量已知。每輛車屬于一個配送中心，電動汽車從配送中心出發(fā)時電量是充滿的狀態(tài)，在行駛過程中會消耗電量，在必要時需到換電站更換電池。要求同一輛電動汽車經(jīng)過同一充電站不超過一次，更換完電池后繼續(xù)服務客戶，直到服務完成回到配送中心，且電動汽車只能在配送中心或換電站進行充電。

1.3 模型參數(shù)說明

M：配送中心集合，M=｛1，2，…，m｝；F：換電站集合，F(xiàn)=｛m+1，2，…，m+f｝；N：客戶集合，N=｛m+f+1，2，…，m+f+n｝；V：N∪M∪F，V=｛1，2，…，m+f+n｝；K：車輛集合，K=｛1，2，…，k｝；qj：客戶j 點的需求量；Uk：車輛k 的最大可載量；Q：電動汽車電池最大容量；第k 輛車到達i 點之后的剩余電量（kwh）；第k 輛車離開i 點時的剩余電量（kwh）；h：電動車行駛過程中的耗電率（電動汽車每行駛1km 路程所消耗的電量，kwh/km）；dij：i 點到j 點之間距離；C0：距離的單位成本（電動汽車每行駛1km 路程所需費用）；Ck：每輛車的成本（每輛電動車所需的固定成本）；C1：更換電池次數(shù)的單位成本（即電動車每更換一次電池的費用）；zijk：為0-1 變量，指第k 輛電動汽車從節(jié)點i 行駛到節(jié)點j 處，即zijk=1，否則zijk=0。

1.4 模型建立

目標是使總成本最低，總成本包括車輛路徑費用、車輛使用費用以及電池更換費用。約束1 表示每個客戶都有一輛車為其服務；約束2 表示同一電動汽車進入同一充電站的次數(shù)不超過一次；約束3 表示車輛到達同一節(jié)點的次數(shù)和離開該節(jié)點的次數(shù)相同，即表示從配送中心離開的車輛必須回到配送中心；約束4 表示為客戶服務的車輛總數(shù)不能超過配送中心擁有的車輛總數(shù)；約束5 表示每輛電動汽車載重量不能超過其最大載重量；約束6 表示電動汽車兩點之間的電量約束，必須保證電動汽車有足夠的電量到達下一節(jié)點；約束7 表示電動汽車離開配送中心和換電站時電量為充滿狀態(tài)；約束8 表示電動汽車在客戶點處停留時是不耗電的；約束9 中zijk為0-1 變量，值為1 時表示第k輛電動汽車從i 點行駛到達j 點。

2 算法

2.1 編碼方式

本文所求問題的解采用實數(shù)編碼，將問題的解編為M+F+N 的自然數(shù)染色體串，每條染色體都由若干子串組成，每個子串表示一條車輛路徑。子串解如圖1 所示，其含義為車輛從某一配送中心出發(fā)，按順序逐個訪問配送路徑上的客戶點，最后返回該配送中心。其中，M 為候選的配送中心點數(shù)量，F(xiàn) 為候選的換電站數(shù)量，N 為客戶點數(shù)量。在該示例中共有32 個節(jié)點，其中配送中心點數(shù)量為2（M=2），候選的換電站數(shù)量為10（F=10），客戶點數(shù)量為20（N=20），通過MATLAB 計算得出問題的解。

Fig.1 Expression of substring solution圖1 子串解表達

根據(jù)MDHEVRP 問題所求出解的編碼方式如圖2 所示，圖中給出了一條完整的車輛路徑方案，從該方案中可看出車輛從配送中心出發(fā)，并且最終需要回到配送中心。該解表示有兩輛車分別從1 號配送中心和2 號配送中心出發(fā)，其中一輛車的路徑為1-14-16-29-17-27-31-19-25-23-1，該車從1 號配送中心出發(fā)后在途中會為9 位客戶提供服務。另一輛車的路徑為2-13-21-24-18-30-28-6-20-6-20-26-15-22-32-2，由于路程較長，電動汽車的電量不足以完成整條路徑上的配送服務，因此電動汽車會在配送途中進入6 號換電站更換電池，最后服務完單條路徑上的所有客戶后回到2 號配送中心。綜上所述，將會有2 輛車從配送中心出發(fā)，電動汽車在配送服務過程中會經(jīng)過6號換電站更換電池，共為20 位客戶提供配送服務，服務完成后回到各自的配送中心。

Fig.2 Example of vehicle route solution圖2 車輛路徑解示例

2.2 K-means 聚類算法

初始解質量不僅會影響問題解的求解質量，還會影響求解速度。為了更快、更好地得到問題最優(yōu)解，本文使用兩階段算法對MDHEVRP 問題進行求解［25，26］，從而獲得初始解。第一階段使用K-means 聚類算法將所有客戶分配到各自的配送中心，因為在K-means 聚類算法初始階段要選取k 個節(jié)點作為初始聚類中心，然后在此基礎上進行n 次迭代。因此，選取的節(jié)點不同，聚類結果即可能有所不同。K-means 算法的聚類結果對初值較為敏感，算法對初值的依賴性導致聚類結果不穩(wěn)定。因此，對K-means 聚類算法初始聚類中心選取方法進行改進是非常必要的。第二階段為每組客戶建立合適的TSP 路線。具體步驟如下：

（1）選取所有配送中心節(jié)點（k 個）作為初始聚類中心。

（2）首先，計算每個客戶點分別到k 個聚類中心的距離，將該點分配到最近的聚類中心，分配完成之后根據(jù)式（11）計算各個類的重心，從而得出新的聚類中心。其中，n代表各類中所有節(jié)點個數(shù)，c 代表每個聚類中的所有節(jié)點集合。

（3）進行多次迭代得到新的聚類中心，以及分配到各聚類中心的節(jié)點。

（4）根據(jù)兩點之間的距離公式（12）計算每個配送中心（k 個）到所有聚類中心（k 個）的距離。

（5）根據(jù)Wi值選擇聚類中心可替代的配送中心，根據(jù)Wi值從大到小的順序對每個聚類中心重新進行排列。對每個聚類中心依次選擇Wi值最大的配送中心，如果該配送中心已選擇，則選擇Wi值第二大的配送中心，以此類推，直到所有配送中心選擇完畢。

（6）重新計算每個客戶點分別到k 個配送中心的距離，將該點分配到最近的配送中心。

（7）為每組客戶建立TSP 路線。計算每組待訪問客戶集中每個客戶到各自配送中心的距離，隨機挑選一個客戶作為該條路線上的第一個客戶，然后將該點從待訪問集中刪除，并選擇待訪問集中離該點最近的一個客戶作為下一個訪問客戶。每增加一個客戶，計算當時的車輛容量及電動車所剩電量，如果同時滿足兩個要求，則繼續(xù)選擇下一個客戶，并將已分配客戶放入禁忌表。若不滿足車輛容量要求，則插入這條路徑開始的配送中心編碼。如果還有未訪問客戶，再重新插入該組客戶的配送中心編號，啟用一輛車進行一條新的路徑規(guī)劃。若不滿足電量要求，則隨機選擇一個最近的電動車換電站更換電池，然后繼續(xù)行駛，直到分配完所有客戶。按照分配順序為已安排的客戶建立TSP 路線，即為初始解。

2.3 改進的蟻群算法

蟻群算法一次迭代過程中主要包括信息素更新規(guī)則和移動規(guī)則［23，27］。

2.3.1 轉移概率

轉移概率計算方法如式（14）所示。

其中，ηij(t)為啟發(fā)函數(shù)，表示螞蟻從城市i轉移到城市j的期望程度；allowk為螞蟻k待訪問城市集合；禁忌表tabuk用于存儲螞蟻k 已訪問過的城市，tabuk=N-al?lowk；α為信息素重要程度因子，該值越大，表示信息素濃度在轉移過程中所起作用越大；β為啟發(fā)函數(shù)重要程度因子，其值越大，表示啟發(fā)函數(shù)在轉移過程中所起作用越大，即螞蟻會以較大概率轉移到距離近的城市。

2.3.2 輪盤賭法

為了保證路徑的多樣性，采用輪盤賭法以加大算法搜索能力，輪盤賭法具體步驟如下：

（1）根據(jù)轉移概率公式（14）計算出群體中每個個體適應度f(xi)，xi∈allowk。

（2）根據(jù)公式（15）計算出每個個體被遺傳到下一代群體中的概率。

（3）根據(jù)式（16）計算出每個個體的累積概率。

（4）在［0，1］區(qū)間內產生一個均勻分布的隨機數(shù)r。

（5）若r≤qi，則選擇個體i，否則選擇個體k，使得r≤qi成立。

（6）重復d 和e，直到所有客戶都被訪問。

2.3.3 信息素濃度更新機制

每只螞蟻在構造出一條從起點到終點的路徑后，蟻群算法還要求根據(jù)路徑總長度更新該路徑上所有路徑段的信息素濃度。信息素濃度更新機制如式（17）-式（19）所示。

ρ表示信息素揮發(fā)程度，信息素濃度隨著時間的推移而逐漸減少；Δτijk(t)表示螞蟻k在從城市i出發(fā)到達城市j的路上留下的信息素總量；Δτij表示所有螞蟻在城市i與城市j 連接路徑上釋放的信息素濃度之和，其中Q代表信息素常數(shù)，表示螞蟻循環(huán)一次釋放的信息素總量，Lk代表第k只螞蟻經(jīng)過的路徑長度。其計算方式如式（18）、（19）所示。

2.3.4 鄰域搜索

為防止蟻群算法陷入局部最優(yōu)，引入單點交換、插入、單點插入、移除和逆轉5 種鄰域搜索機制，以擴大解空間搜索范圍。

單點交換模式：隨機選擇節(jié)點i和節(jié)點j兩個位置，交換相應的位置編號。

插入模式：隨機選擇節(jié)點i的位置，將換電站編號插入到該節(jié)點之后。

單點插入模式：隨機選擇節(jié)點i和節(jié)點j兩個位置，將節(jié)點i的編號插入到節(jié)點j的編號之前。

移除模式：隨機選擇換電站節(jié)點i或配送中心節(jié)點i的位置，刪除換電站或配送中心編號。

逆轉模式：隨機選擇節(jié)點i和節(jié)點j兩個位置，將兩個節(jié)點間的所有節(jié)點反向排列。

根據(jù)蟻群算法產生的當前解，分別隨機采用以上鄰域搜索方式產生鄰域解，從而擴大解空間搜索范圍。改進后的蟻群算法鄰域搜索方式如表1 所示。

Table 1 Neighborhood search methods of ant colony algorithm表1 蟻群算法鄰域搜索方式

2.3.5 改進的蟻群算法流程

算法步驟如下：

（1）初始化參數(shù)。蟻群算法需要對參數(shù)進行初始化，初始化參數(shù)是指對相關參數(shù)進行初始化，如螞蟻數(shù)量、信息素重要程度因子、啟發(fā)函數(shù)重要程度因子、信息素揮發(fā)因子、信息素常數(shù)、最大迭代次數(shù)等。然后輸入數(shù)據(jù)，計算兩點之間的距離。

（2）使用K-means 聚類算法產生初始解，并刪除初始解中的配送中心與換電站編號。

（3）候選配送中心選擇。重新隨機選擇一個配送中心作為起點，m 只螞蟻從各自選擇的配送中心出發(fā)，并且最終回到各自的配送中心。

（4）根據(jù)轉移概率公式計算轉移概率，確定下一個訪問節(jié)點，判斷節(jié)點是否滿足約束條件。將已訪問客戶放入禁忌表，在滿足所有約束條件的情況下，在全局路徑中插入可選擇的配送中心和換電站，將全局路徑分為若干局部路徑段。

（5）直到所有螞蟻完成路徑搜索，計算各螞蟻經(jīng)過的路徑長度。

（6）對每只螞蟻經(jīng)過的路徑進行鄰域搜索，計算并保存產生的可行解，比較每個可行解的適應度值，記錄當前迭代次數(shù)的最優(yōu)解。

（7）信息素更新。

（8）判斷是否滿足最大迭代次數(shù)。

（9）得到全局最優(yōu)路徑。

二階段算法流程如圖3 所示。

Fig.3 Two-phase algorithm flow圖3 二階段算法流程

3 實例仿真

為了驗證算法的有效性，本文對兩組規(guī)模不同的算例進行測試，測試數(shù)據(jù)相關信息如表2 所示。

Table 2 The relative data of tested instances表2 測試算例相關信息

本文在Windows10 系統(tǒng)的MATLAB2016a 版本下實現(xiàn)MDHEVRP 問題求解及相關算例驗證。對于每一個參數(shù)，需要進行多次測試取平均值，本文共運行了10 次。在算法開發(fā)過程中發(fā)現(xiàn)了一組關鍵參數(shù)，與其他參數(shù)相比，這些參數(shù)對解的質量影響較大。在測試活動中從基礎設置開始，連續(xù)細化每個關鍵參數(shù)的值，對每個參數(shù)連續(xù)測試5個值，保留最佳值作為各參數(shù)的最終設置，并繼續(xù)調整下一個參數(shù)。調整后的參數(shù)如表3 所示。

Table 3 Parameter setting表3 參數(shù)設置

電動汽車類型如表4 所示，共有A、B、C 3 種類型的車輛，其中A 型車輛的車容量為300 kg，單次使用價格為100元，配送中心共有30 輛A 型車輛；B 型車輛的車容量為500 kg，單次使用的價格為150 元，配送中心共有20 輛B 型車輛；C 型車輛的車容量為800kg，單次使用的價格為200 元，配送中心共有10 輛C 型車輛。所有電動汽車的電池類型相同。

Table 4 Vehicle information表4 車輛信息

4 結果分析

增加鄰域搜索對蟻群算法進行改進后，采用二階段算法對算例進行測試，利用MATLAB 計算得出結果。當客戶數(shù)量為20 時，計算總時間為27.52s，總車輛行駛里程為108.23km，配送車輛為2 輛，配送成本為1 449.8 元。采用改進算法后的對比數(shù)據(jù)如表5 所示，每輛車的測試路徑結果如圖4 所示。優(yōu)化后的結果顯示：路徑總長度減少了8.3km，使用車輛數(shù)減少了1 輛，且總成本降低了133 元。在蟻群算法的基礎上，路徑距離減少了7%，總成本降低了8.5%。

Table 5 Comparison of two-phase heuristic algorithm for 20 customers before and after optimization表5 20 個客戶時二階段算法優(yōu)化前后對比

Fig.4 Test route results of 20 customers圖4 20 個客戶測試路徑結果

當客戶數(shù)量為50 時，計算總時間為79.19s，總車輛行駛里程為66.84km，配送車輛為5 輛，配送成本為1 468.4元。采用改進算法后的對比數(shù)據(jù)如表6 所示，每輛車的測試路徑結果如圖5 所示。優(yōu)化后的結果顯示：路徑總長度減少了40.13km，總成本降低了351.3 元。在蟻群算法的基礎上，路徑距離減少了37.5%，總成本降低了19.3%，所以該方案為可行方案。

Table 6 Comparison of two-phase heuristic algorithm for 50 customers before and after optimization表6 50 個客戶二階段算法優(yōu)化前后對比

Fig.5 Test route results of 50 customers圖5 50 個客戶測試路徑結果

蟻群算法與改進的蟻群算法性能比較如表7 所示。

Table 7 Performance comparison of ant colony algorithm and improved ant colony algorithm表7 蟻群算法與改進的蟻群算法性能比較

為進一步驗證二階段算法的求解效率，本文選擇CL?RP 標準數(shù)據(jù)庫（http：//prodhonc.free.fr/Instances/instancesus.htm）中的6 組數(shù)據(jù)進行比較。從表8 可以看出，在6 組算例中，GRASP 算法能求出4 最優(yōu)解，2-phase 能求出5 組最優(yōu)解，求解正確率為83.33%，相比GRASP 算法提高了16.67%。二階段算法雖然比GRASP 算法求解時間略長，但也在可接受范圍內。盡管二階段算法只能求出5 組最優(yōu)解，但其在求解質量上具有一定穩(wěn)定性，充分說明二階段算法在求解MDHEVRP 問題上具有良好性能。

Table 8 Comparative results of model algorithms表8 模型算法效果比較

5 結語

電動汽車的車輛路徑問題是現(xiàn)代物流的主要研究方向之一，已受到國內外學者的重點關注。通過研究多車場多車型電動汽車車輛路徑問題及其求解算法，可有效地對電動汽車配送路徑進行優(yōu)化，從而降低配送成本、提高車輛使用率、減少資源浪費，進而減少環(huán)境污染，并解決目前能源短缺的問題。電動汽車車輛路徑問題是一個值得研究的重要課題，但要將電動汽車廣泛應用于物流行業(yè)還需作進一步研究?？蓮碾妱悠嚹芎?、充電方式及客戶所要求的配送時間等方面對電動汽車車輛路徑問題進行研究，從而使其能更好地與實際相結合。