混合柔性充電策略支持下的電動汽車配送路徑優化

毛慧婷，石建邁，周玉珍，陳 超

（國防科技大學 系統工程學院 信息系統工程重點實驗室，湖南 長沙 410073）

1 引言

隨著溫室氣體的大量排放以及全球氣候變暖等環境問題日益嚴重，近年來關于如何降低交通運輸領域碳排放的研究越來越多。根據歐盟的統計數據，大約20%—25%全球能源消耗和二氧化碳排放量源于交通運輸系統，其中陸上交通占75%[1]。目前國內外各大商業公司已經意識到充電汽車在綠色物流領域具有明顯優勢，開始研究以充電汽車為主導的物流配送系統。

車輛路徑問題（vehicle routing problem，VRP）是物流運作管理的經典問題，通過優化配送車輛的行駛路徑來提高物流配送的效益，如路程最短、費用最小、時間盡量少、使用車輛盡量少等[2]。應用電動汽車替代傳統汽車進行物流配送，在帶來環境和成本等方面效益的同時，也為車輛路徑規劃問題帶來了新的挑戰，引起了國內外學者的廣泛關注。相對于傳統路徑規劃，電動汽車的路徑規劃問題增加了中途充電站的選擇決策，使得解空間的組合更多，求解難度更高。

從當前充電站的主流服務方式來看，一般分為快速充電和更換電池兩種模式。在快速充電模式下，一般假設電動汽車在充電站充滿電池，其充電時間由到達充電站時的剩余電量決定[3-8]。Schneider等[3]研究了帶時間窗口的電動汽車路徑規劃問題，以最小化車輛數和總行駛距離為目標，提出了一種變鄰域搜索與禁忌搜索相結合的混合啟發式算法。Hiermann等[5]研究了電動汽車與燃油汽車混合模式下的路徑規劃問題，并設計了分支定價與混合啟發式算法。Montoya等[6]分析了非線性充電速率對電動汽車路徑規劃的影響，并設計了針對非線性充電情況的搜索算子。Guo等[7]提出應用遺傳算法求解帶時間窗口的電動汽車路徑規劃問題。國內學者黃敏芳等[8]提出了帶軟時間窗及充電站定位的電動汽車車輛路徑問題，并設計改進了遺傳算法進行求解。在快速充電模式下，電動汽車也可以選擇部分充電，而不是一次充滿，從而節約時間和費用[9-11]。Keskin等[9]研究了部分充電模式下的路徑規劃問題，實驗結果顯示，部分充電策略相比較于完全充電策略可以有效減少配送里程。Ding等[10]通過實驗對比，證明了部分充電模式下電動汽車的充電時間、客戶點的等待時間以及行駛時長都相對較短。Macrina等[11]研究了混合車隊中電動汽車允許部分充電情況下的車輛路徑規劃問題，并應用大鄰域搜索算法進行了求解。Verma[12]提出了快速充電與電池更換兩種模式下的電動汽車路徑規劃，并限定電動汽車采用快速充電時必須充滿。

從電動汽車物流系統的運行來看，完全或部分快速充電策略的充電成本較低，但是需要一定的充電時間，可能使得電動汽車由于客戶時間窗口不滿足而減少客戶訪問數量；直接更換電池的策略在時間上可以忽略不計，但一般成本較高。當前文獻大多研究一種充電策略下的路徑規劃，很少考慮兩種充電策略混合模式下的電動汽車路徑優化。當電動汽車在充電站既可以選擇快速部分充電，也可以選擇更換電池時，電動汽車的充電策略更加靈活柔性，進而降低總體成本。但是這種混合柔性的充電策略使得電動汽車路徑規劃的建模和求解更加復雜。在傳統電動汽車路徑規劃模型的基礎上，本文研究了柔性充電策略下帶時間窗的電動汽車路徑規劃問題，建立了問題的非線性混合整數規劃模型。通過結合蟻群算法和局部搜索策略，設計了一種改進型蟻群算法，提高了問題的求解效率。通過三種不同客戶分布模式下的路徑優化實驗，驗證了算法的有效性，并分析了柔性充電方式對于降低配送總成本的效果。

2 數學模型構建

2.1 問題描述

本文研究的電動汽車路徑規劃問題中，每個客戶點都有特定的服務時間窗口以及服務時長。配送車隊均由同一類型的電動汽車組成，具有固定大小的車載容量以及最大的行駛里程。在行駛過程中，電量隨著行駛距離成比例消耗。電動汽車電量不足時，可以訪問充電站補充電量。所有充電站均可提供兩種充電方式：（1）快速充電，可以根據電動汽車的實際需要進行部分充電或充滿；（2）更換電池，直接為電動汽車更換上新的滿電電池。考慮到電池替換所花的時間很短，這里我們假設電池更換的時間可忽略不計。

在本文的模型中,目標函數是最小化配送總成本，包括車輛固定成本、行駛成本、等待成本以及充電成本。建模中的其他設定如下：

（1）每個客戶點只能由一輛車配送，一輛車可以服務多個客戶點；

（2）配送中心數量為單個，所有車輛從配送中心出發并回到配送中心；

（3）所有車輛從配送中心出發時均為滿電狀態，并且不考慮配送車輛的重復使用；

（4）不考慮充電站車輛排隊等候，即車輛進入充電站就可直接充電，并且車輛在充電站不必充滿電再駛離；

（5）車輛在客戶點停留過程中不消耗電能。

2.2 符號定義

在建模過程中，V={1,...,N}表示客戶點集合，F表示充電站集合，頂點0和N+1分別為出發點和結束點，兩者重合，為配送中心的位置。設集合V'=V?F，為了區別不同實例中的倉庫，以0或者N+1作 為 該 集 合 的 下 標 ，如?{0} 和?{N+1}。 A={(i,j)|i,j∈表示路段的集合。每一條路段都有相應的距離值dij以及行駛時間tij，車輛電池的電量消耗率為r。在充電站采用快速充電方式時，電動汽車的充電率為g。若選擇更換電池，則每次電池替換的成本為cs。Di表示客戶i的需求量，si為客戶服務時長，客戶點的服務時間窗口為[ei,li]。電動汽車的容量表示為C，電池容量為Q。模型中的連續決策變量包括：τi,ui和vi分別為車輛到達客戶點i的服務開始時間，剩余貨物容量和剩余電量水平，qi為電動汽車在充電站采用快充模式時的充電量，Yi為車輛離開充電站i時的電量水平，δi為在客戶點i∈N處的等待時間。如果路徑中含有路段(i,j)，0-1決策變量xij的值取1，否則取0；如果在充電站i∈F選擇了電池交換技術0-1決策變量yi的值取1，否則取0；如果在充電站i∈F選擇了傳統充電方式0-1決策變量zi的值取1，否則取0。

模型中所用到的符號總結如下，見表1。

2.3 數學模型

混合柔性充電策略支持下的電動汽車配送路徑優化數學模型如下：

表1 模型中的符號表示

模型中公式（1）為目標函數，最小化總體成本。約束（2）和（3）確保每個客戶點都恰好被一輛車訪問一次。約束（4）為網絡流平衡條件。約束（5）和（6）確保了路徑中客戶點之間時間窗的連續可行性。約束（7）保證車輛服務開始的時間在時間窗內。約束（5）-（7）同時消除了路徑中的子回路。約束（8）和（9）確保滿足所有客戶點的需求量。約束（10）和（11）限定電池的電量始終非負。約束（12）計算車輛離開充電站時的電量水平。約束（13）限制車輛在充電站至多只能選擇一種充電方式。約束（14）確保車輛充完電后的電量不超過最大電池容量。約束（15）-（17）限定所有決策變量的取值范圍。

3 求解算法設計

為了解決混合充電模式下的電動汽車路徑優化問題，本文設計了一種改進的蟻群算法。蟻群算法是一種源于生物界的新仿生類隨機型搜索算法，由意大利學者Dorigo等提出，具有群體合作、正反饋選擇、并行計算等特點。作為一種有效的啟發式算法，近年來蟻群算法逐漸被用于求解各種車輛路徑規劃問題[13-17]。

為適應本文中的電動汽車路徑優化求解，對蟻群算法進行了兩方面的改進。首先考慮到充電站的選擇和充電策略的優化，設計了一個最優充電站插入啟發式；其次鑒于問題的復雜性，引入局部搜索算法，擴大蟻群算法迭代過程中的搜索空間，增加最優解的搜索概率。改進蟻群算法的主要步驟見算法1。

算法1:改進蟻群算法

Step1 參數初始化；

Step2 鄰近點搜索構造初始可行解ψ0；

Step3 設定初始信息素濃度；

Step4 讓k只螞蟻同時從配送中心出發，并行搜索產生k個未插入充電站的解φ；

Step5 調用充電站插入算法，插入充電站；

Step6 調用局部搜索算法，進行局部搜索；

Step7 信息素更新；

Step8 若算法循環到最大次數NCmax后停止，輸出最優可行解Ψbest；否則，轉到Step4。

3.1 蟻群初始解構造

蟻群是正反饋系統，在覓食過程中，每只螞蟻會在所經過的路徑上留下一種化學物質—信息素，后面的螞蟻可分辨其強度，從而選擇信息素濃度高的路徑。隨著信息素的揮發，采用正反饋機制，螞蟻將會選擇相對較短且信息素濃度較高的路徑。隨著路徑上的信息素不斷進行更新和累積，螞蟻最終會找到覓食的最短路徑。

本文利用鄰近點搜索及充電站插入算法來生成初始可行解（ψ0）。所有路徑的信息素初始濃度設為該初始解目標函數值的倒數。設蟻群系統的規模為P，螞蟻在生成解的過程中不斷選擇下一個客戶點進行訪問，直至沒有滿足條件的客戶點。然后該螞蟻返回配送中心重新出發，直到訪問完所有客戶點。螞蟻在選擇下一個客戶點 j是根據一個轉移概率公式來決定的，該概率公式同時考慮了信息素濃度以及路徑的距離長短。轉移概率公式如下：

其中dij為邊的長度。

3.2 信息素更新

在搜索過程中信息素的更新至關重要。首先由于自然界中螞蟻留下的信息素會隨著時間的推移而揮發，因此在更新過程中引入了信息素揮發機制。其次本文采取了精英螞蟻策略，即除了螞蟻搜索產生的最優解所經過的路徑之外，其余精英螞蟻所產生的較優可接受路徑也會被用來更新信息素的濃度。本文中，信息素濃度按如下方式進行更新：

其中，Q是一個常數，Costib為當前最優解，為δth精英螞蟻的解。

3.3 充電站啟發式插入算法

由于電動汽車電池容量有限，其行駛里程往往受到電量水平的限制。蟻群算法所構造的未插入充電站的解（φ0）往往存在違背里程約束的路徑。因此，這些路徑中需要插入充電站對車輛進行適當充電才能順利完成該條路徑的配送。為此本文設計了一個充電站最優插入啟發式算法，主要步驟見算法2。

算法2:充電站啟發式插入算法

輸入：未插入充電站的解γ0

輸出：最優可行解γfea

Step1 找出解γ0中所有違背電動里程約束的不可行路徑；

Step2 找到電動汽車出發后能到達的最遠客戶點；

Step3 對最遠點與配送中心或者前一個充電站之間的所有點進行以下循環；

Step4 在當前點后插入距離最近的充電站；

Step5 確定充電水平；

Step6 檢查時間窗可行性；

Step7 若該條路徑違背時間窗，則移除相應的客戶點到移除點集合Vunvisit；

Step8 若算法已遍歷所有可插充電站位置，則循環停止，否則轉到Step3;

Step9 若集合Vunvisit不為空，則用鄰近點搜索并重復以上Step1-9，否則算法停止。

充電站插入算法的基本思路是對于超過車輛最大里程的回路，找到電動汽車出發后能到達的最遠客戶點，即車輛從配送中心或者充電站出發可到達但無法繼續到達下一個客戶點。在該客戶點后插入距離最近的充電站。若余下的路徑仍里程違背，則繼續按此方式插入充電站。在搜索過程中，遍歷所有可插入充電站的位置。

在插充電站過程中，充電方式的選擇將會決定充電之后的電池電量水平。由于路徑中充電次數不定，假定當快速充電模式下所需的充電時間超過某一個閾值T0時，將選擇電池交換技術作為充電方式。否則，選擇快速充電方式按照實際需求對車輛進行部分充電。T0的定義如下：

其中，σ是一個0-1之間的參數，Q g表示將電量為0的電池進行快速充電至充滿所需要的時間。

當充電水平確定之后，檢查該回路上的客戶點時間窗是否仍然滿足。若有客戶點的時間窗不滿足，則將該客戶點從該路徑中移除并將其添加到集合Vunvisit。在整個充電站插入的過程中，可行解的接受第一準則首先是盡可能保留較多的客戶點，其次則是接受較低配送成本的可行解。

3.4 局部搜索算法

為了進一步防止蟻群算法陷入局部優，引入局部搜索算法，擴大蟻群算法每次迭代過程中的搜索空間，提高可行解尋優的質量。本文中，局部搜索算法的核心是移除算子和插入算子。在搜索過程中，考慮到客戶點位置每一次的重新調整都很可能會導致充電站最優插入位置的改變，因此局部搜索是在當前解移除充電站之后的路徑上進行的。在每一次迭代之后，重新對調整后的路徑應用充電站插入算法，生成可行解。

3.4.1 移除算子。本文中使用的移除算子分為兩類：路徑移除和客戶點移除。路徑移除是指移除被選中回路上的所有客戶點，而客戶點移除則是移除一定數量λ的客戶點。λ由總的客戶點數量決定，在一個特定區間內隨機選擇。

（1）最短路徑刪除算子：該算子從當前解中挑選出最短的一條回路，刪除該回路上所有客戶點并將這些客戶點放進移除列表中，該算子的目的是盡可能最大化車載量的利用率。

（2）結束最早路徑刪除算子：該算子從當前解中選擇配送時間結束最早的一條回路，刪除該回路上所有客戶點并將這些客戶點放進移除列表中，該算子的目的是基于現實因素考慮，盡可能達到相應的工作時長。

（3）隨機客戶點刪除算子：該算子從當前解中隨機選擇λ客戶點刪除，隨機性的刪除操作可以使得搜索過程更加多樣化，防止陷入局部優。

（4）最差客戶點刪除：該算子計算出當前解中每個客戶點距離前后鄰接的客戶點距離之和，按此數值進行降序排序，選擇前λ個客戶點進行刪除。

3.4.2 插入算子。插入算子是將移除列表中的客戶點重新插回被破壞的當前解中，在插入過程中需要考慮該條回路的車容量及時間窗的可行性，但不需要考慮車輛里程的限制。

（1）貪婪插入：將被移除客戶點依次插回到當前解最優的位置，使得每次插入增加的成本最低。

（2）后悔值-2插入：找出所有被移除客戶點的最優和次優插入位置，并計算最優插入成本和次優插入成本，取兩者的差值，將差值較大的客戶點優先插入其最優位置。

在搜索過程中，所有移除和插入算子均有一個相同的權重，按照輪盤賭進行隨機選擇組合。局部搜索算法的主要步驟見算法3。

算法3:局部搜索算法

輸入：未插入充電站的初始解φ0

輸出：最優可行解Ψbest

Step1 對各個算子的權重進行初始化；

Step2 將初始解φ0插入充電站產生當前可行解，Ψcurrent，Ψbest←Ψcurrent；

Step3 移除當前可行解中的充電站；

Step4 隨機挑選一個移除算子，生成客戶點移除列表?；

Step5 隨機選擇一個插入算子，將列表?中的客戶點重新插入當前解；

Step6 調用插入算法，插入充電站生成當前可行解Ψcurrent；

Step7 若當前可行解的總成本低于最優解，則Ψbest←Ψcurrent；

Step8 若算法循環到最大次數NCmax后停止，輸出最優可行解Ψbest；否則，轉到Step3。

4 實驗結果及分析

為了對模型和算法進行驗證，采用三個典型客戶分布的算例進行實驗。每個算例中共包含122個點，其中一個配送中心、100個客戶點、21個充電站。三個算例中，算例A的客戶點呈隨機分散分布，如圖1所示；算例B中客戶點呈簇狀聚集分布，如圖2所示；算例C中的客戶點分布兼具簇狀聚集和隨機分散的特點，如圖3所示。

圖1 算例A中點的分布

圖2 算例B中點的分布

圖3 算例C中點的分布

在實驗中電動汽車的相關成本參數見表2。電池更換成本設定為給一個電量為0的電池進行快速充電充滿所需成本的1.2倍。

表2 電動汽車成本相關參數值

蟻群算法相關的參數值設定為P=30，α=5，β=5，φ =0.25，Q=100，算法所有代碼由Visual C++編程實現。

4.1 局部搜索算法的效果

為了防止蟻群算法陷入局部最優，本文設計了以移除和插入算子為核心的局部搜索算法，與蟻群算法集成，來擴大解空間的搜索效率。傳統蟻群算法（ACO）和集成局部搜索的蟻群算法（ACO-LS）求解三個算例的計算結果見表3，負Δ%值意味著最優解質量的提高。實驗結果證實，局部搜索可以大大增強算法全局尋優的能力，從而顯著地提高最優解的質量。

表3 蟻群算法改進效果對比實驗結果

4.2 充電策略對比分析

基于三個實例，進一步對比分析了不同充電策略即允許部分充電的快充策略、更換電池以及兩者混合的充電策略對配送成本的影響，實驗結果見表4。結果顯示，對于三個不同的實例，混合充電策略相比于單一充電策略均能有效降低配送總成本，這是因為多種充電方式能更靈活地安排充電模式，使得車輛成本、等待成本及充電成本都相對較低。雖然單一電池更換策略使得車輛數能最大程度地減少，但是由于換電池的成本顯著增加了，所以配送總成本不僅沒有降低反而有所上升。而單一部分快充策略雖能最大程度地降低充電成本，但由于其充電時間較長，會出現更多客戶點的時間窗不可行，導致需要更多的車輛去服務客戶，從而大幅度增加了車輛使用成本，使得總成本上升。

表4 不同充電策略對比

5 總結與展望

為了更好地降低充電時間對客戶時間窗的影響，本文提出了混合柔性充電方式支持下帶時間窗的電動汽車路徑問題。柔性充電策略的引入為充電汽車的應用提供了更加靈活的運作方式，也提供了進一步降低配送時間和成本的可行途徑。針對電動汽車的中途充電需求，在傳統車輛路徑的基礎上，本文設計了一種充電站啟發插入算法快速計算充電站的插入位置。同時，通過設計局部搜索算法并集成到蟻群算法的迭代過程中，提出了一種改進的蟻群算法。以三個具備典型客戶點分布的實例為基礎，對比了改進蟻群算法的效果。實驗結果顯示蟻群算法中嵌入的局部搜索對于提高解的質量有著顯著的優勢。通過混合充電策略和單一充電策略的對比試驗，驗證了混合充電策略對于降低配送成本的作用。為物流公司選擇充電方式提供了具有參考價值的建議。

在下一步的研究中，電動汽車路徑規劃問題可以考慮更多的現實約束因素。例如，配送過程中的交通道路擁堵情況往往會影響配送的效率。在大規模配送場景中，多配送中心的電動汽車路徑規劃問題具有很高的應用潛力，具有較大的研究意義。此外，考慮充電樁的選址與路徑問題相結合也是未來研究的方向之一。