部分充電策略下的多車型電動汽車車輛路徑優化問題研究

程 坦，陳 鵬，張國偉，朱 寧

（1.天津大學，管理與經濟學部，天津 300072；2.復旦大學，管理學院，上海 200433；3.廣東美的制冷設備有限公司，佛山 528311）

0 引言

在新能源汽車購置補貼、路權便利等政策的引導下，諸多大型物流企業紛紛采用電動汽車替代傳統燃油型物流車。然而，電動汽車在實際使用過程中卻面臨著行駛里程受限、充電困難等問題。因此，通過對電動汽車行駛路徑、充電策略進行優化，以提高配送效率，降低配送成本，實現電動貨運的進一步推廣。

傳統車輛路徑規劃問題主要研究燃油車路徑優化，并在多場景得到應用，例如物流配送[1]、物流包裝回收[2]、垃圾回收[3]等。然而隨著電動汽車的普及與發展，電動汽車的車輛路徑規劃問題（Electrical Vehicle Routing Problem，EVRP）受到更多的關注。Schneider 等[4]提出可變鄰域搜索算法與禁忌搜索算法相結合的混合啟發式算法，引入有限車輛數和顧客時間窗兩個約束，分析具有時間窗的電動汽車車輛路徑優化問題。Desaulniers 等[5]研究了單一車型電動汽車4種不同充電策略，在考慮顧客時間窗約束條件下，設計精確算法對問題進行求解，結果表明部分充電策略可以降低配送總成本。Macrina 等[6]研究了混合車隊中電動汽車充電策略問題，并考慮了行駛過程中加速、減速對能耗的影響，設計了大規模鄰域搜索算法進行求解。Penna 等[7]考慮不同類型電動汽車，結合集合分割模型，提出一種迭代鄰域搜索算法，求解具有時間窗的多車型電動汽車車輛路徑優化問題。Montoya等[8]在考慮電池充電時間為非線性函數的條件下，設計一個混合啟發式算法，并對比分析了線性充電函數和非線性充電函數的影響。楊珺等[9]采用兩階段啟發式算法，考慮電動汽車物流配送網絡的設施選址和配送路徑優化問題。揭婉晨等[10]構建了包含時間窗的多車型電動汽車VRP 模型，運用分支定價算法進行最優化求解。何東東和李引珍[11]設計改進禁忌搜索算法，考慮油耗和碳排放量的問題，研究了帶時間窗的EVRP問題。郭放等[12]采用啟發式算法，考慮了差異化服務成本與充電策略問題，并建立出整數規劃數學模型。楊森炎等[13]基于時空狀態網絡建立整數規劃模型，并利用前項標號法進行求解。

綜上所述，現有的電動汽車EVRP問題的研究已經取得了一定的進展，但是缺少對車型的考慮。然而城市道路交通網絡日益復雜，多車型配送也愈發普遍，已有文獻中的完全充電策略受充電時長和顧客時間窗限制，必須選擇更多的車輛來滿足任務需求，增加了配送總費用。本研究根據實際物流配送場景，引入多車型，采用部分充電策略，放松充電需要充滿電的假設，考慮時間窗和資源約束，構建部分充電策略下的多車型車輛路徑問題的混合整數規劃模型，設計局部搜索算法增強的自適應大規模鄰域搜索算法對模型進行求解，通過數值實驗驗證算法的有效性和策略的可行性。同時利用不同規模算例與完全充電策略進行對比，結果表明部分充電策略提升了配送效率和車輛滿載率，減少了配送車輛使用數量，從而降低了配送總成本。

1 數學模型

1.1 問題描述

車輛從配送中心出發，對顧客進行商品配送，并在充電站對車輛進行充電，直至完成所有配送任務回到配送中心，該問題的示意如圖1所示。

圖1 多車型純電動汽車車輛路徑規劃問題示意圖

模型考慮電動汽車電量約束、行駛里程約束、電動汽車容量約束、顧客點時間窗約束，以最小化固定成本和可變成本為目標函數，并做如下假設：

（1）配送中心具有多種電動汽車，不同車型固定成本、單位里程使用成本不同，但數量均充足，所有車輛從配送中心出發，完成任務后返回配送中心。

（2）車輛能耗與行駛距離成正比，且車輛保持勻速行駛。

（3）充電速率固定，充電電量與時間成正比。

（4）充電站內充電樁無數量限制，多輛車可以同時充電。

（5）早于顧客時間窗下界或晚于顧客時間窗上界，均無法服務。

（6）所有顧客點均被服務但僅被一輛電動汽車服務。

1.2 變量說明

N=C∪P表示配送網絡節點，其中C為顧客點集合，P表示充電站集合；考慮網絡流模型流平衡約束，將每個充電站拓展出l個虛擬充電站，并定義所有虛擬充電站集合為P′。0 表示配送中心，n+1 表示虛擬配送中心，定義N0=N∪{0}，Nn+1=N∪{n+1}，包含虛擬充電站的集合分別記作N′0，N′n +1。本研究問題考慮多車型，定義車型集合V，車型v載重、滿電續航里程、充電速率、單位里程可變成本、使用固定成本分別為W v、Bv、ηv、αv和f v；節點i到j的距離為dij，行駛時間為tij，則車型v通過弧(i,j)的可變成本可表示為cij=αv·dij；車輛在節點i最小剩余電量所對應的續航里程為min{dij,j∈Por{0,n+1}}；需求量為?i的顧客點時間窗約束為[lbi,ubi]；其服務時間為si。ai為車輛到達節點i的時間；bi為車輛到達i處的剩余里程；wi為車輛到達節點i的剩余容量；ρi為車輛在充電站i充電而增加的續航里程；為車輛v是 否經過弧(i,j)，經過為1，否則取0。

1.3 多次部分充電策略下的多車型電動汽車車輛路徑優化數學模型

式（1）～（13）建立了多次部分充電策略下的數學模型，其中目標函數（1）表示完成配送任務總成本最小，包括車輛行駛的可變成本和使用的固定成本；公式（2）表示一個顧客有且只能有一輛車對其服務；公式（3）表示每個虛擬充電站至多服務一輛電動汽車，公式（4）表示經過節點的流平衡約束；公式（5）表示從配送中心出發的車輛數等于回到配送中心的車輛數；公式（6）和（7）分別表示車輛不進行和進行充電操作時節點間的時間關系，具體來說，如果i不是顧客點，則到達j的時間不早于電動汽車到達i的時間加上在節點i的充電時間與弧(i,j)的行駛時間；公式（8）表示車輛開始服務時間必須在顧客時間窗內；公式（9）表示車輛行駛過程中的容量約束；公式（10）和（11）分別表示車輛不進行和進行充電的行駛里程；如果車輛不進行充電，則其從節點i行駛至節點j后的剩余電量里程不大于節點i處的剩余電量減去弧(i,j)的長度，反之則加上節點i處的充電里程；公式（12）表示車輛的充電電量約束，在節點i的充電電量不能超過電動汽車電池總容量；公式（13）為0-1決策變量。

2 局部搜索增強的自適應大規模鄰域搜索算法

2.1 算法設計

自適應大規模鄰域搜索算法（Adaptive Large Neighborhood Search，ALNS）[14]是由大規模鄰域搜索算法發展而來的，允許在同一搜索中使用多個摧毀算子和重建算子。在迭代過程中，算子使用的頻率是通過其權重確定的，并在求解過程中動態調整。通過多個摧毀算子和重建算子對現有解進行操作，得到現有解的鄰域，本文在此基礎上對鄰域進行局部搜索（Local Search，LS）操作以增強尋優能力。ALNS-LS的具體方法如下：

Step1 生成初始可行解；

Step2 根據算子權重選擇摧毀算子和重建算子；

Step3 對解進行摧毀-重建-局部搜索操作；

Step4 根據新解的質量更新算子權重；

Step5 重復Step2～Step4，直至滿足終止條件。

2.2 初始解的生成

ALNS-LS 作為啟發式算法的一種，初始解的質量尤為關鍵，高質量的初始解可以提升求解速度，但往往構造時間較長。因此權衡初始解的構造時間和質量就顯得尤為重要。

本文采用沿線插入算法進行初始化。定義由于時間約束而不能被同一輛電動汽車服務的任意顧客點集合為S(Ci)，并定義S(Ci)的并集為S(C)，同時定義路線Ri中所有顧客的近鄰顧客點的并集為N(Ri)。在近鄰的定義中，由于不考慮物流車在顧客點處的等待成本，因此直接采用物流車旅行時間作為近鄰的計算標準。近鄰顧客點數量的選取也十分重要，太大會產生較高的計算成本，需要根據計算規模的不同靈活地進行調整。算法具體步驟如下：

Step1 根據約束在所有待規劃顧客點U(C)中計算S(C)；

Step2 隨機選擇S(Ci)∈S(C)，ci∈S(Ci)和v∈V初始化路線Ri，如果S(C)為空，則隨機選擇ci∈U(C)和v∈V初始化路徑Ri，并更新N(Ri)；

Step3 遍歷ci∈N(Ri)，如果當前路徑有可行插入位置，則更新Ri，U(C)，N(Ri)；否則，Ri即為一個初始解子集，如果S(C)和U(C)為非空，轉Step1。

2.3 摧毀算子

摧毀算子（D={di|i=1,…,m}）在構建鄰域中起到至關重要的作用，每個算子di被選擇的概率為，其中μdi為算子di的權重。考慮算法搜索的深度與廣度，本文采用以下四種摧毀算子：

（1）隨機刪除

從路徑中隨機選擇多個顧客點直接刪除，并記錄于待規劃顧客點集合。

（2）最差刪除

路徑上每增加一個顧客點，一定會造成總成本某種程度上的增加，定義顧客點i的服務成本為icost=，其 中和分別表示路徑中服務顧客點i和不服務顧客點i的成本。最差刪除是將路徑上服務成本k最大的顧客點移除。

（3）基于距離刪除

車輛從配送中心出發有序訪問顧客點或充電站構成的路徑是由多個弧組成，計算每個弧的長度，并刪除起終點不是配送中心或充電站且距離最長的弧。

（4）基于角度刪除

車輛配送的路徑所圍成的區域多數是扇形區域。如果路徑上的顧客配送距離都比較近，那么圍成的扇形區域的角度大半徑小，反之圍成的扇形區域角度小半徑大。基于角度的刪除是通過計算路徑服務顧客所圍成扇形的夾角與半徑來確定要刪除的顧客點。

2.4 重建算子

重建算子（R={ri|i=1,…,l}）同摧毀算子一樣在構建鄰域中起到重要的作用，每個算子ri被選擇的概率為，其中μri為算子ri的權重。本文采用以下三種重建算子：

（1）成本最小插入

遍歷待規劃顧客集合，每次從其中選出一個顧客重新插入路徑，直至待規劃顧客集合為空。定義Δc(i,r)為顧客點i插入路徑r中最優位置后的成本，則顧客的最優插入成本為iinssertcost=min{Δc(i,r)|r∈Ω}。

（2）后悔插入

每一個顧客點在每一條路徑上均有最小增加費用Δe(i,r)，下一個候選插入點的確定公式為：

式中：U(C)為待規劃顧客點的集合；Δe(i,r*)表示顧客點i插入的最低費用增加，且最低費用對應的路徑為r*；Δe(i,rj)表示除最低費用對應路徑外其他路徑中的最低插入費用；z為顧客點i可插入路徑的個數。通過遍歷待規劃顧客，將其插入各自最低費用路徑中的最優位置。

（3）充電站最優插入

在路徑合適位置插入充電站以延伸電動汽車的行駛里程，提升電動汽車使用效率。找到不滿足里程約束的顧客點并在其之前插入充電站，如果該點無法插入充電站則充電站依次往前移動直到找到合適的位置。

2.5 局部搜索

本文對ALNS 算法進行摧毀和重建操作后的解應用鄰域搜索算法以增強算法的尋優能力，具體采用以下六種操作：

（1）Swap

Swap 算法是路徑間搜索，通過交換路徑r1和路徑r2的部分連續有序顧客點來實現，Swap(p,q)表示將路徑r1上的p個連續有序顧客點與路徑r2上的q個連續有序顧客點進行交換。

（2）Shift

Shift 算法是路徑間提升算法，將路徑r1的部分顧客轉移到路徑r2上。例如Shift(n,0)表示將r1的n個連續顧客點轉移到r2，通常包括Shift(1,0)，Shift(2,0)兩種情況。

（3）Exchange

同樣為路徑間搜索，操作與Swap 相似，但不強調數量。路徑r1和路徑r2分別選擇一個分割點，對分割點后的路徑進行交換。

（4）2-Opt

2-Opt 為路徑內搜索，通過移除路徑內任意兩個不相鄰的弧后，重新插入兩條新弧構成路徑。

（5）充電站位置優化方法

由于電動汽車受里程限制較大，因此合理的充電策略可以有效地延長電動汽車行駛里程，實現降本增效的目標。通過向路徑中插入虛擬充電站（增加充電次數），避免了違反車輛續航里程約束；或移除已存在路徑中的虛擬充電站（減少充電次數），降低車輛因不必要的充電行為而增加的配送成本。

（6）車型優化方法

在滿足路徑中顧客點容量約束和續航里程約束的前提下，迭代過程中以一定的概率調整車型的指派關系。該概率隨著算法迭代次數的增加而降低。

2.6 權重的更新

ALNS中多種不同摧毀-重建算子的應用在迭代過程會產生不用優化效果，所以在每次迭代結束后各個算子的權重采用以下更新方式：

其中是第t次迭代時算子i的權重，是0-1 之間的參數，wi是算子當前的得分，由當前解與新生成解的優劣決定。算子生成新解的質量越高，其得分越高，具體如下所示：

3 算例分析

3.1 算例設計

以Solomon算例[15]為基礎，合理地增加充電站信息。不同類型算例車輛信息如表1所示。

表1 車輛信息表

續表1

3.2 算法有效性分析

首先檢驗ALNS-LS 算法的有效性，在顧客規模為50，車型信息為R1 的10 組算例，設置迭代次數為200 次，運行時間為3 600 s，分別對比完全充電策略和部分充電策略。求解的結果過如表2所示。

算例以“類別_顧客點數量_充電站點數量_實驗次數”命名，解以“車型編號：該車型數量，車型編號：該車型數量，……”表示。從表2 可以看出，完全充電策略算例均可以在3 600 s 內求解，算法性能較好。7 組算例部分充電策略配送成本優于完全充電策略，平均節約成本12.6 %。但值得注意的是有3組算例結論相反，其主要原因是部分充電策略在優化過程中需要決策每輛車在充電站的充電電量，因此每次迭代所用時間更長，在相同時間內對解空間的搜索不夠充分。

表2 算例結果（1）

為了進一步驗證部分充電策略在配送成本上的優越性，本文分別利用C1、C2、R1、R2、RC1、RC2 共6 種車型，設計顧客規模為20、50 和100 的算例進行求解，實驗結果如表3所示。

表3 算例結果（2）

從表3 中可以看出，13 個算例中12 個算例部分充電策略的配送總成本優于完全充電策略，就求解耗時而言，部分充電策略用時更久。算例規模與時間間隔百分比沒有明顯的單調關系，但是隨著顧客點的增加使得車型組合更為復雜，部分充電策略在成本上的優勢也更為明顯。

3.3 算法收斂性驗證

為了進一步驗證算法收斂性和魯棒性，從每種類型算例中各選取一組顧客數量規模為50，充電站為8 的算例，共6 組算例。設置終止條件為迭代次數到達500 次，運行時間為3 600 s，在部分充電策略下對每組算例求解5次，得到最優迭代曲線和平均迭代曲線，以及最優解迭代過程中算例車輛配置信息。以C1_50_8_1 為例繪制收斂信息圖和車型配置信息圖，分別如圖2 和圖3 所示。算法收斂較快，在40代后結果趨于穩定，最優曲線與平均曲線之間間隔較少，僅為6.21%，算法魯棒性較好，值得注意的是車型3的固定成本和可變成本相對較高，因此在車輛數量充足的情況下未出現在最優解中。

圖2 收斂信息圖

圖3 車輛配置信息圖

3.4 算例仿真

選擇規模為100 的Solomon 的RC2 型算例，從中隨機選取50 個節點作為顧客點，9 個節點改造為充電站構造算例。算例的配送中心點、顧客點、充電站的坐標信息、時間窗、服務時間及需求量見表4。

表4 配送中心、顧客點和充電站節點信息

續表4

在完全充電和部分充電兩種策略下對問題進行求解，分別得到配送路線方案如表5 與表6 所示，方案包括具體指派關系及顧客訪問順序，總成本由單位成本和車輛使用成本構成，距離為該路徑對應的行駛距離，滿載率（%）為車輛所載顧客需求的總重量比對應車型的最大載重量。

表5 完全充電策略下配送路徑優化方案

續表5

表6 部分充電策略下配送路徑優化方案

完全充電策略下使用1型車8輛，2型車1輛，3型車1輛，共計10輛，部分充電策略下使用1型車7輛，2 型車1 輛，3 型車1 輛，共計9 輛，后者要比前者少使用一輛電動汽車。雖然兩種充電策略下的總成本相差不大，但是部分充電策略下的80%以上車輛的滿載率超過60%。兩種配送路徑方案可視化分別如圖4（a）和（b）所示。

圖4 配送路徑方案可視化圖

3.5 靈敏度分析

物流企業電動汽車的使用成本相對固定，是否選擇使用其完成配送任務主要取決于它們的可變成本。現在考慮當電動汽車固定成本一定時，可變成本變化對數值實驗結果的影響。構造顧客點數量為20，充電站數量為3的算例。選擇車輛信息類型為R1 的多車型集合，控制其他車輛可變成本一定，在考慮多次部分充電策略下，設置3 型電動汽車的單位可變成本分別為1.2，1.3，1.4，1.5 進行求解，其靈敏度分析實驗結果如表7所示。

表7 靈敏度分析結果

從表7 可以看出，所有算例均在660 s 內得到計算結果，配送總成本隨著車型3單位可變成本的上升而增加，最優解中出現車型3的數量也隨之減少，但是對于給定的算例，車型3 的數量在減少到一定程度時將保持穩定，可變成本和固定成本沒有單調性。然而對于最優解中不包含車型3 的算例而言，車型3單位可變成本的擾動不會對最優解以及最優值帶來任何影響。

4 結束語

本文針對電動汽車運行里程受限，在模型中考慮部分充電策略，利用電動汽車使用的固定成本和單位里程可變成本構建目標函數，考慮車輛異質問題，建立了多車型電動汽車車輛路徑規劃模型，并設計局部搜索增強的自適應大規模鄰域搜索算法進行求解。通過算例分析驗證算法的有效性和收斂性，并且對比了多次部分充電策略和多次完全充電策略對配送成本的影響。研究結果表明，部分充電策略的使用可以在一定程度上降低配送成本、減少配送車輛的使用數量、提升電動汽車的滿載率。然而本研究沒有考慮交通網絡狀態對電動汽車運行的影響，進一步研究可以引入基于擁堵情況的電能消耗、突發情況等復雜場景，從而構建含有不確定參數的魯棒優化模型。