非線性充電函數(shù)電動(dòng)汽車配送路徑問(wèn)題研究

王 芳，秦 盼，匡梓君

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

0 引言

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

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

本研究具有以下意義：

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

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

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

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

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

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

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

2 模型構(gòu)建

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

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

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

2.1 問(wèn)題描述

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

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

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

2.2 基本假設(shè)

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

允許充電站被多次訪問(wèn)。

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

假設(shè)這些站點(diǎn)的所有電動(dòng)汽車具有相同的SOC 時(shí)間曲線。

電動(dòng)汽車從倉(cāng)庫(kù)出發(fā)時(shí)是滿電狀態(tài)。

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

車輛的行駛速度恒定。

2.3 數(shù)學(xué)模型

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

決策變量如下：

問(wèn)題的數(shù)學(xué)模型如下：

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

3 啟發(fā)式方法

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

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

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

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

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

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

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

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

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

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

Step 4.5 將當(dāng)前客戶加入未服務(wù)點(diǎn)集Qw 中。

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

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

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

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

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

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

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

3.3 節(jié)約里程法

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

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

3.4 同時(shí)考慮時(shí)間窗與距離的求解方法

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

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

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

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

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

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

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

Table 1 Comparison of experimental results表1 實(shí)驗(yàn)結(jié)果比較

5 結(jié)語(yǔ)

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