非線性充電函數電動汽車配送路徑問題研究

王 芳，秦 盼，匡梓君

（武漢科技大學恒大管理學院，湖北武漢 430065）

0 引言

近年來，隨著工業的飛速發展，人們的生活水平不斷提高，對汽車的需求量也逐步提升。因此，對環境造成的影響日益嚴重，其中包括對生態環境的破壞、對礦物資源的破壞以及對環境的污染等。普通汽車燃燒汽油供汽車行駛，并產生大量尾氣。首先，產生的汽車尾氣會污染空氣；其次，汽油是不可再生化石燃料，在地球上的貯藏量有限。因此，清潔能源引起了人們的極大興趣。

在該背景下，國家對綠色能源的關注與日俱增，計劃到2022 年，初步建成布局合理、生態友好、清潔低碳、集約高效的綠色出行服務體系，綠色出行環境明顯改善，綠色出行裝備水平明顯提升。電動汽車行業目前處于穩步發展階段，發展前景良好［1-4］。另一方面，當前燃油價格不斷上漲，且排放標準日益嚴格，物流企業紛紛采用電動汽車代替內燃機汽車，尤其在最后的配送環節中。

本研究具有以下意義：

（1）理論方面，可進一步豐富與發展電動汽車配送路徑問題相關理論知識，為電動汽車電池電量計算提供了新方向，并為路徑規劃算法提供了理論依據，具有一定參考價值。

（2）經濟方面，電動汽車行駛相同距離消耗的電力成本大約是傳統汽車燃料成本的1/10～1/7。另外，如果電動汽車在低用電量期間充電（如在午夜，單位電價僅為中國部分省份正常電價的1/3），成本可進一步降低。

（3）環保方面，隨著保護環境、節約能源的呼聲日益高漲，電動汽車的環保特性（如沒有溫室氣體排放、降低噪音污染、高能源效率）不僅對環境有益，而且可幫助使用電動汽車的物流企業樹立更加綠色、健康的企業形象。

1 相關研究綜述

就能量消耗而言，現有模型大部分采用線性函數近似方法［5-6］，即電池能量增長隨充電時間的延長而線性增長。然而，這種線性增長的方式過于理想化，實際應用中有很多額外因素都會對電量消耗產生影響。此外，即使為電池充相等的電能，從不同的電池狀態開始充電，充電時間也會有很大不同。在這方面，Goeke 等［7］和Lin 等［8］在考慮電動汽車參數及其負載的情況下，使用實際道路網絡計算電池能量消耗。譚學怡等［9］、趙雅蘭［10］分析電動汽車質量、速度與道路坡度對電動汽車電量消耗的影響，構建了基于非線性電量消耗的電動車路徑規劃模型；蔡銀怡［11］在分析電動車能量消耗影響因素與能量轉換過程的基礎上，構建更符合實際的能量消耗函數。為模擬更真實的充電過程，Montoya 等［12］引入帶有非線性充電函數的電動汽車路徑問題（E-VRP-NL），但引入非線性充電函數后，現有研究都對函數進行了線性化近似，而近似過程可能會對實驗結果產生影響［13-14］。因此，本文首次不對非線性充電函數進行線性化近似，而是直接使用。

目前已有的電動汽車配送路徑方案中，針對電動汽車充電問題，主要存在兩種解決方法：①通過復制充電站生成多個充電站的虛擬節點解決充電站訪問問題，每個充電站最多只能被一輛車訪問一次［15-16］，但是這種解決辦法有很大缺陷。一方面，當充電站數量很多時，將增加問題的復雜性。另一方面，設置虛擬充電站時無法預知每個充電站的虛擬節點數目；②通過設置一個決策變量Xijc判斷電動車在從客戶i到客戶j的路徑中是否訪問了充電站，訪問充電站時，決策變量Xijc=1，否則Xijc=0，但是這種方法同樣會增加問題的復雜性［17-18］。

Zuo 等［19］提出一種新的更為高效的方法解決車輛訪問充電站問題，使用該方法時，其模型復雜度高于傳統VRP模型。N表示客戶節點集，N′表示客戶與倉庫的集合。首先為每個客戶定義一組附近的充電站Ci（Ci∈C），然后引入一個二進制變量yic，說明車輛在離開客戶之后是否訪問充電站，訪問即yic=1，否則yic=0。該變量的引入不增加模型復雜度，因此本文模型沿用此二進制變量。

2 模型構建

本文沿用文獻［19］相關假設，假設穿過節點弧（i，j）時的電能消耗是一個常數dij（根據標準距離單位（SDU）2測量），并假設弧上消耗的能量等于弧距離（單位：sdu），而行程時間也等于以分鐘為單位測量的弧距離。本文使用的充電函數是Teo 于2015 年擬合的［20］。經過計算，電池電量充滿大約需要108min（見圖1）。

Fig.1 Non-linear charging function圖1 非線性充電函數

函數斜率即電動車電池充電速率，通過觀察函數可看到函數斜率隨時間的增長呈下降趨勢，也即是說電池充電效率隨著時間的增長不斷降低。并且，當電池從不同的電量狀態開始充電，需要充相同電量時，起始電池電量越多，充電時間越長。具體而言，同樣為電池充0.1的電，從電池狀態為0.2時開始充，所需時間為14.184 6-9.192 3=4.992 3min，而從電池狀態為0.7時開始充，所需時間為52.695 4-42.382 5=10.312 9min，所需充電時間顯著增加。

2.1 問題描述

電動汽車配送路徑問題為一組已知地理位置、需求、服務時間窗和服務時間的客戶進行配送服務，服務車輛是一組已知車輛容量、車輛最大行駛距離和電量消耗速率的同質車隊。車輛在行駛過程中，電池剩余電量隨著行駛距離的增加而下降，車輛可在充電站充電后繼續行駛，充電站數量及位置已知。

目前研究電動汽車路徑問題時，針對電動車行駛過程中的能耗問題，大部分學者引入的是線性充電函數，也即充電能量與充電時間成正比，但實際上大多數電動汽車充電能量與充電時間不成正比，充電速率隨著充電時間的增加而逐步下降。

該問題的目標是規劃可行的路徑方案并使其行駛里程最小，可行方案需滿足以下條件：為每個客戶服務并且只服務一次。到達每個客戶點以及最后完成配送任務回到倉庫都在規定的時間窗內。電動汽車在路徑上任一點，電池電量都在0～Q 之間。

2.2 基本假設

所有客戶只能被一輛車服務，不允許訂單拆分。

允許充電站被多次訪問。

假設每個CS 具有同時為多個EV 服務的無限容量。

假設這些站點的所有電動汽車具有相同的SOC 時間曲線。

電動汽車從倉庫出發時是滿電狀態。

假設路網處于恒定的交通環境中。

車輛的行駛速度恒定。

2.3 數學模型

相關參數如下：

決策變量如下：

問題的數學模型如下：

公式（1）為目標函數，表示總行駛里程最小；公式（2）、（3）表示每個客戶只能被訪問和離開一次；公式（4）判斷車輛是否在離開客戶i后訪問充電站；公式（5）-（8）計算車輛從客戶i到客戶j的實際行駛里程；公式（9）確定行駛時間；公式（10）、（11）跟蹤路徑上的時間；公式（12）、（13）顯示倉庫點不需要服務；公式（14）為客戶i開始服務的時間在可以為客戶i進行服務的時間窗口內；公式（15）指電動車在到達客戶i時車輛負荷不小于客戶需求；公式（16）、（17）跟蹤路徑上車輛的負載；公式（18）指車輛在路徑上任意位置的負載不大于車輛最大容量；公式（19）、（20）限制行駛到客戶途中的能量變化；公式（21）限制行駛到倉庫途中的能量變化；公式（22）、（23）限制行駛到充電站途中的能量變化；公式（24）說明車輛是滿電量從倉庫出發的；公式（25）指車輛到達充電站時剩余能量不小于安全閾值；公式（26）保證充電后電動車能量不超過最大電池容量；公式（27）約束了電動車充電時間；公式（28）、（29）定義了所有決策變量范圍。

3 啟發式方法

3.1 時間窗優先的求解方法

時間窗優先的求解方法即將各客戶按可以服務的截止時間升序進行排序，然后對排序后的客戶逐一進行判斷求解，無法服務的客戶直接放入下一輪重新判斷，直到所有客戶都完成配送服務，如圖2 所示。具體流程如下：

Step 1 初始化參數。初始車輛數為0，初始里程為0。

Step 2 計算客戶、倉庫及充電站各點間的距離，生成距離矩陣。構造當前無法服務的客戶點集Qw，并將未服務的客戶點按可以服務的截止時間升序進行排序，將排序后的客戶點集存入Q 中。

Step 3 判斷Q 中個體數是否等于0，若等于0，則操作終止，輸出最優路徑；否則，轉Step 4。

Step 4 按Q 中的客戶排序判斷每個客戶點能否為其服務。

Step 4.1 判斷服務當前客戶點是否滿足時間窗與容量需求，并判斷如果進行服務，之后能否在指定時間窗內回到倉庫點。若滿足要求，則轉入Step 4.2；否則，轉入Step 4.5。

Step 4.2 判斷如果進行服務，服務完成后剩余電量能否回到倉庫或充電站。如果可以，則進行服務并更新數據，轉到Step 4；否則，轉入Step 4.3。

Step 4.3 判斷剩余電量能否直接到達充電站。若滿足要求，進入充電站充電，并轉入Step 4.4；否則，轉入Step 4.5。

Step 4.4 判斷充電并服務完當前客戶后是否仍能回到充電站或倉庫。若滿足要求，對其進行服務并更新數據；否則，轉入Step 4.5。

Step 4.5 將當前客戶加入未服務點集Qw 中。

Step 5 判斷服務完最后一個客戶后能否回到倉庫。

Step 5.1 判斷服務完最后一個客戶后車輛能否回到倉庫。若滿足要求，更新數據，并轉到Step 3；否則，轉到Step 5.2。

Step 5.2 判斷服務完最后一個客戶后能否回到充電站。若滿足要求，則轉到Step 5.3；否則，去掉最后一個服務的客戶點，轉到Step 5.1。

Step 5.3 判斷允許充電的最大時間是否大于回到倉庫所需充電的時間。若滿足要求，則回到倉庫，更新數據，并轉到Step 3；否則，去掉最后一個服務的客戶點，轉到Step 5.1。

3.2 距離優先的求解方法

距離優先的求解方法即在未服務點集中選取離剛服務的客戶最近的滿足時間窗、電量及車輛容量等約束的客戶點進行配送服務，直到所有客戶都完成配送服務的過程，具體流程如圖3 所示。

由圖3 可清晰地看出，以距離為優先的求解方法在整個循環邏輯上與以時間窗為優先的求解方法基本一致，主要區別在于選取即將服務的客戶時參考數據不一樣（文字進行了加粗），時間窗參考的是可服務客戶里可服務截止時間最早的一個，而距離優先選取的是與剛服務的客戶距離最近的客戶，以致中間數據更新環節有一些不同。

3.3 節約里程法

節約里程法［20］是指依次將運輸問題中的兩個回路合并為一個回路，每次使合并后的總里程減少最多，直到達到車輛的最大載重量，再進行下一輛車的優化。首先根據節約里程公式計算連接每兩點相應的節約里程數，然后在未服務點集中選取與剛服務的客戶連接時，節約距離最大的滿足時間窗、電量及車輛容量等約束的客戶點進行配送服務，直到所有客戶都完成配送服務。

與時間窗優先及距離優先一致，節約里程法在循環邏輯上也與前兩者相同。不同的是節約里程法選取即將服務的客戶時，參考的是閉合兩個回路成一個回路時產生的最大節約距離，這里不再贅述。

3.4 同時考慮時間窗與距離的求解方法

該方法在考慮下一個可配送客戶時，還使用線性加權方法，將時間窗優先與距離優先同時考慮進來，二者的權重系數相加為1。本文設計了0.2/0.8、0.4/0.6 兩種權重比例。

4 結果比較與分析

Fig.2 Time window first solution method圖2 時間窗優先的求解方法

Fig.3 Distance-first solution method圖3 距離優先的求解方法

本文使用經典Solomon 的VRPTW 實例［20］，集合C 中的客戶地理數據呈聚集性特點，而集合R 中的客戶地理數據是隨機分布的。集合RC 中的客戶地理數據結合了隨機與聚集兩個特點。R 型和RC 型問題的客戶服務時間為10，C型問題的服務時間為90。其中，充電站橫坐標由計算得出，縱坐標由計算得出，i、j表示客戶點。

采用不同求解方法，針對不同客戶集合類型進行求解，并將結果與現有數學模型求解結果進行對比分析，如表1 所示［19］。

經過對數據的觀察對比，對于R 類客戶集合，使用節約里程法得到總里程的AVG 值最大，而使用距離與時間窗加權的方法得到的結果最小，其中0.4/0.6 權重的平均結果最好。幾種方法得到的結果均優于現有數學模型求解結果，而其中表現最優的為0.4/0.6 權重方法。對于C 類客戶集合，表現最差的依然是節約里程法，表現最好的為時間窗優先的求解方法。0.2/0.8 權重方法在單個案例中表現較好，有C102-104 共3 個案例的求解結果優于數學模型的結果。而對于RC 類客戶集合，表現最差的是距離優先的方法，表現最好的為0.2/0.8 權重方法。不論哪種方法都能求出可行解，而采用CPLEX 求解在某些案例中甚至求不出可行解，并且好的啟發式方法可求得比CPLEX 更好的解，尤其是綜合考慮時間窗與路徑的求解方法表現較好。

Table 1 Comparison of experimental results表1 實驗結果比較

5 結語

本文考慮有客戶需求、車輛容量和電池容量等約束的車輛路徑問題，并在電池容量計算中引入非線性充電函數，同時使用一種新的模型構建方法。該方法都能對問題進行快速求解，并且相當一部分案例能獲得比數學模型求解更好的結果，說明啟發式求解方法在求解大規模問題時具有一定優勢。本文設計的求解方法較為簡單，下一步可對求解方法進行改進，以進一步提高尋優能力。