王 芳，秦 盼，匡梓君

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

0 引言

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

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

本研究具有以下意義：

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

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

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

1 相關(guān)研究綜述

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

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

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

2 模型構(gòu)建

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

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

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

2.1 問題描述

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

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

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

2.2 基本假設(shè)

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

允許充電站被多次訪問。

假設(shè)每個CS 具有同時為多個EV 服務(wù)的無限容量。

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

電動汽車從倉庫出發(fā)時是滿電狀態(tài)。

假設(shè)路網(wǎng)處于恒定的交通環(huán)境中。

車輛的行駛速度恒定。

2.3 數(shù)學模型

相關(guān)參數(shù)如下：

決策變量如下：

問題的數(shù)學模型如下：

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

3 啟發(fā)式方法

3.1 時間窗優(yōu)先的求解方法

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

Step 1 初始化參數(shù)。初始車輛數(shù)為0，初始里程為0。

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

Step 3 判斷Q 中個體數(shù)是否等于0，若等于0，則操作終止，輸出最優(yōu)路徑；否則，轉(zhuǎn)Step 4。

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

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

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

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

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

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

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

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

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

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

3.2 距離優(yōu)先的求解方法

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

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

3.3 節(jié)約里程法

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

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

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

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

4 結(jié)果比較與分析

Fig.2 Time window first solution method圖2 時間窗優(yōu)先的求解方法

Fig.3 Distance-first solution method圖3 距離優(yōu)先的求解方法

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

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

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

Table 1 Comparison of experimental results表1 實驗結(jié)果比較

5 結(jié)語

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