帶時間窗的電動汽車物流配送車輛路徑問題研究

黃敏芳，劉敬，郭瓊

（1.華北電力大學 經濟與管理學院，北京 102206；2.新能源電力與低碳發展研究北京市重點實驗室（華北電力大學），北京 102206）

1 引言

電子商務環境下城區物流配送呈現小批量、多品種、多頻次、短周期和送貨時間嚴格等特點。近年來，網上零售企業，如蘇寧易購、當當、亞馬遜等，其網上交易訂單量日益增長，由此引發更加頻繁的交通運輸活動。據兩會報道顯示，我國快遞量去年一年達到400億件，占世界超40%的市場份額。國際能源署（IEA）2009年發布的《運輸、能源與二氧化碳：邁向可持續發展》[1]的報告顯示，全球25%的二氧化碳等溫室氣體的排放來源于交通運輸。如何通過發展“綠色物流”來減少電子商務物流配送對環境的污染，做好物流配送中的“最后一公里”服務，是當前物流業面臨的主要難題。北京市《關于對部分機動車采取交通管理措施降低污染物排放的通告》[2]提出對城區內送貨車輛環保問題的監控勢在必行。電動汽車逐漸成為電子商務環境下頻繁的城區物流配送活動的最佳選擇。2014年物流與運輸車輛高峰論壇[3]首次提出可將電動三輪車用于解決電子商務城區物流配送活動。據國家電網報顯示，至2017年10月底，全國充電網絡已覆蓋26個省、273個城市，充電樁數量達到4.5萬個。

車輛路徑問題（vehicle routing problem，VRP）是物流運作管理面臨的難點問題，該問題可定義為：對一系列發貨點/收貨點，安排適當的行車路線，使車輛有序通過，在滿足一定約束條件（如貨物需求量、發貨量、交貨時間、車容量限制、行駛里程限制等）下，達到一定的目標，如路程最短、費用最小、時間盡量少、使用車輛盡量少等[4]。目前對于VRP的研究方向多集中在單車場[5]、多車場[6]、單車型[5-6]、多車型[7]、帶時間窗約束[8-9]、隨機需求[10-12]等，研究方法可歸結為精確算法[8]、傳統啟發式算法[5]以及現代啟發式算法[6-7,9-11]。如今，隨著國家大力倡導節能減排，電動物流車已廣泛應用到我國的各大城市，電動汽車在物流中的應用已成為該行業相關學者的研究熱點。目前，國內外已有諸多學者將電動汽車應用到物流配送問題上，并展開研究，如：M Schneider等[13]研究了帶時間窗和充電站的車輛路徑問題，以最小化車輛數和總行駛距離為目標，采用變鄰域搜索算法和禁忌搜索算法進行求解，并設計兩種算例分別用CPLEX和禁忌搜索算法得出結果。Siddiqi等[14]研究了粒子群算法求解電動汽車在多種約束下的路徑優化問題。Baouche[15]建立定位的節能路徑優化模型使能源消耗最低。Kobayashi等[16]研究不需要充電、充電一次和充電多次三種情況下電動汽車的路徑搜索，將路徑分為多條子路徑后采用Dijkstra算法精確求解。Wang和Song[17]研究了帶時間窗的電動汽車的定位和路徑優化問題，通過禁忌搜索算法和大規模鄰域搜索算法相結合求解。Keskin和Gatay[18]研究了帶時間窗的電動汽車不完全充電情況下的車輛路徑問題，采用自適應大規模鄰域搜索算法求解。以上文獻均為本文研究的展開提供了借鑒。

本文研究的是帶軟時間窗的電動汽車物流配送車輛路徑問題，除了傳統VRP帶來的求解難度以外，電動汽車的應用會涉及到行駛過程中的充電問題，大大提升了問題的復雜度。目前，在電動汽車車輛路徑問題的相關研究上，關于具體的成本核算部分，多數文獻采用不計充電成本或按充電次數計費的方式，這種粗略核算的方式會降低結果的精確度。本文選擇的是由充電度數決定的充電成本，提高了充電成本核算的精確性，解決了由粗略計算充電成本導致的車輛路線與實際情況偏差較大的缺陷，增強了電動汽車在物流配送問題上的應用靈活性。由于遺傳算法具有可并行搜索、編碼方式多樣等優良特點，可用于解決較復雜的組合優化問題，因此本文采用遺傳算法進行求解，并結合問題實際特征改進算法。

2 問題描述及模型構建

2.1 問題描述

本文研究的是配送中心在收到客戶貨物后，用電動物流車給客戶配送。由于電動汽車具有一定的續駛里程限制，在電量耗盡之前需要及時進行能源補給，目前能源補給的方式主要有三種：常規充電、快速充電和更換電池。在電子商務環境下“最后一公里”配送過程中，因客戶對時間窗有較嚴格的限制，所以只能通過快充或更換電池進行能源補給。而更換電池的專業化要求較高，換電車輛需要專業的維修保養，所以本文考慮的是較為便捷的充電模式。一般情況下，在同城區中會配置有多個充電站，為電動汽車的正常行駛提供便利。

本文構建模型的目標是使整個配送過程中總物流成本最小。為簡化研究，做出如下假設：

（1）每個客戶點只能由一輛車配送，一輛車可以服務多個客戶點，電動汽車在配送期間最多可充電一次。不考慮配送車輛的巡回使用；

（2）配送中心數量為單個；

（3）所有車輛從配送中心出發時均為滿電狀態；

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

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

為更清楚的描述問題，本文給出如圖1所示的車輛線路示例。圖1中有1個配送中心（0），2個充電站（B1，B2），8個客戶點（1，2，…，8），圖1（a）為各個點的位置分布情況，圖1（b）為經過計算機求解后的最終行駛路線結果，即為配送中心→1→6→3→B1→7→8→配送中心（路線1），配送中心→2→4→5→配送中心（路線2）。

圖1 車輛路線圖

2.2 符號定義

本文使用的各參數定義如下：

N=Na?Nc?B，表示配送中心、客戶和充電站的集合，其中，Na表示配送中心的集合，這里為單一配送中心，用o表示，Nc表示客戶點的集合，B表示充電站的集合，A={(i,j)|i,j∈N,i≠j}表示路段的集合，客戶i的時間窗為(ei,li)，i∈Nc，配送車輛的集合為K，配送車輛用符號k表示，k∈K，單位車輛的啟動成本為f（元/輛），電動汽車單位距離的運輸成本為y（元/km），單位距離消耗的電量為e（kW·h/km），單位充電成本為c（元/kW·h），其它符號定義如下：

Z：配送總成本；

qi：客戶點i的需求量；

Qk：配送車輛k的車載容量，k∈K；

Qik：配送車輛k離開i點時最多可剩余貨物量，k∈K，i∈N；

dij：i點到j點的距離（單位：km），i,j∈N；

V：配送車輛勻速行駛速度；

U：配送車輛的最大電池容量；

：車輛k到達i點時的剩余電量；

：車輛k離開i點時的剩余電量；

r：充電率；

Ti：配送車輛到達客戶點i的時間；

：配送車輛離開客戶點i的時間；

Wi：配送車輛在i點的等待時間；

Si：配送車輛在客戶點i的服務時間。

決策變量為：

物流配送電動汽車車輛路徑問題需考慮客戶訂單的時間窗。時間窗分為硬時間窗、軟時間窗和混合時間窗。硬時間窗要求車輛必須要在時間窗內到達，早到必須等待，而遲到則拒收。軟時間窗是客戶對時間窗要求具有較大的彈性，允許配送員（車輛）提前或延后到達客戶，在實際生活中更實用、更靈活。軟時間窗需要考慮準時到達、提前到達與延遲到達等不同情形下的懲罰成本，因此帶軟時間窗的求解難度更大。混合時間窗表示若配送員（車輛）在期望時間窗內到達，則客戶滿意度為100%，若在期望時間窗外，但在允許時間窗內到達，則客戶滿意度會隨著時間差的增大而降低。本文對帶軟時間窗的物流配送電動汽車充電站定位與車輛路徑問題進行剖析，用EPU表示車輛提前到達產生的單位時間機會成本，LPU表示車輛延遲到達產生的單位時間懲罰成本，則客戶i的懲罰成本Pi(Ti)可表示為：

2.3 模型構建

基于上述參數定義、決策變量、假設條件和懲罰成本函數，構建了帶軟時間窗的電動汽車車輛路徑問題的非線性規劃模型。

模型中式（1）為目標函數，表示配送總成本最小，包括啟動車輛成本、運輸成本、充電成本以及表示客戶滿意度的懲罰成本；式（2）表示每個客戶點到達和離開的車輛數相等，即流量平衡；式（3）表示配送車輛的起點和終點都是配送中心；式（4）表示車輛裝載容量和客戶需求量之間的關系，若配送車輛從客戶i到客戶j進行配送，則車輛離開j點的最多可剩余貨物量至多為車輛離開i時的最多可剩余貨物量減去j點的需求量，否則該約束松弛；式（5）表示車輛k從配送中心出發時滿載；式（6）表示每輛電動汽車服務客戶的需求量之和不超過車載容量；式（7）表示配送車輛離開i點時的時間；式（8）表示配送車輛離開i點到達j點的時間；式（9）表示電動汽車若提前到達，則需等待，等待時間為ei-Ti，否則，無需等待，等待時間為0；公式（10）表示配送車輛離開j點時的時間；式（11）和式（12）分別表示配送車輛離開配送中心與充電站時電量均充滿；式（13）表示配送車輛在客戶點服務期間不消耗電能；式（14）表示電量與行駛里程的關系；式（15）確保電動汽車有足夠的電量到達路線上的每一個點；式（16）保證每次配送任務都以配送中心為起點和終點。

3 算法設計

3.1 算法原理

算法求解原理如圖2所示。

圖2 算法流程圖

3.2 算法步驟

算法設計中的核心內容如下：

（1）編碼設計。遺傳算法的編碼方式有二進制編碼、格雷碼編碼以及自然數編碼。本文采用應用較為普遍的自然數編碼。染色體長度為m+ch+k+2，其中m表示客戶點數量，ch表示充電站數量，k表示所需車輛數，數字2代表車輛出發和返回均在配送中心。配送中心編碼為0，客戶點序列為1，2，…，m，充電站序列用m+1，m+2，…，m+ch表示。如用3輛車為8個客戶服務，充電站個數為2，則其某一染色體可以是0，6，5，7，0，8，9，1，0，2，3，10，4，0，表示路線一為車輛1從配送中心出發，依次為客戶6，5，7服務后返回配送中心，路線二為車輛2從配送中心出發，在為客戶8服務后去充電站9充電，再為客戶1服務后返回配送中心，路線三為車輛3從配送中心出發，先為客戶2，客戶3服務后去充電站10充電，再去服務客戶4，最后返回配送中心。

（2）約束處理與適應度函數。對于電動汽車的行駛里程以及載重限制，若直接對染色體操作，則會導致染色體長度不同，進而無法進行之后的交叉、變異等操作，故本文采用懲罰函數的形式對行駛里程和載重進行約束。為尋求最經濟的配送方案，本文以物流成本作為優化目標，對于其中的充電成本，目前有按充電次數計費以及不計充電成本兩種方式，不計充電成本適用于有自建充電站的物流企業，但對于沒有自建充電站的企業來說，按充電次數來計算充電成本是不夠準確的，為增加成本核算的精確度，這里選擇根據充電度數計算充電成本，引入矩陣Dis來記錄所有路線方案中車輛到達某一點i（i∈N）的已行駛路程，一旦判斷車輛到達充電站j（j∈B），即可通過矩陣Dis獲取該充電站對應的已行駛里程數，記為dj。由假設條件電動車在充電站充滿電再駛離，可通過公式dj*e*c計算得出在充電站j花費的充電成本（若c的單位為元/h，則是根據充電時長計算的，這里是根據充電度數）。這種方式增加了電動汽車配送成本核算的靈活性。最后制定出的目標函數如下：

其中，d1(i)代表某條染色體的總運輸距離（這里的i是染色體的序號），e2(i)（這里的i是染色體的序號）代表所有車輛在所有充電站前電動汽車行駛的總距離，ddd(i)和qqq(i)設計時均為0或1，滿足里程條件或載重條件的為0，否則為1，M是很大的正數，使得不滿足約束條件的染色體的目標值很大。由于動態線性標定法可以擴大適應度函數尋優能力[11]，故本文采用此方法進行計算，具體適應度函數如下：

（3）選擇。采用輪盤賭的方式，計算初始染色體的適應度。生成一個隨機數，根據選擇概率判斷是否進行選擇操作，若滿足條件，則選擇適應度大的兩條染色體作為父代染色體，否則，不進行選擇操作。

（4）交叉。為獲得較好性能的染色體，提高算法的尋優能力，本文采用交換某段子路徑的交叉方式，具體操作如下：

Step1：分別在兩個父代染色體上隨機選擇一段子路徑（如子路徑A和子路徑B）。

父代染色體1：

父代染色體2：

Step2：被選擇的子路徑前置。將父代染色體1中的子路徑A前置，同時，將該染色體中除子路徑A外的編碼按父代染色體2中的順序排列，在末尾填0，最后再將剩余的0插入到除子路徑外的染色體段中，得到子代染色體1。同理得到子代染色體2。

父代染色體1：

父代染色體2：

（5）變異。選擇2-交換變異算子進行染色體變異，即在父代染色體上隨機選擇2個位置進行交換，再將變異后的染色體重插入子代中去。

4 算例分析

選取一個中等規模算例來驗證本文提出模型和求解算法的有效性，算例中共包含42個點，包括1個配送中心，35個客戶，6個充電站。各個點的位置坐標、客戶需求量、時間窗和客戶點停留時間均給定（也可由計算機在一定范圍內隨機生成）。電動汽車的續航里程為200km，其他參數數值設置見表1。

表1 初始參數值

采用MATLAB語言編寫程序，在處理器為Intel(R)Core(TM)i5-3230M，內存為4G的筆記本上運行，交叉和變異概率分別為0.9和0.05，迭代500次，重復求解10次，取最小的運行結果做為最優路線，得到的最小配送成本為3 525.63元。

表2 車輛路線表

圖3 車輛路線圖

表3 配送成本與車輛數數據表

改變配送車輛數，重新求解，結果見表3，發現隨著車輛數的增加，配送成本總體呈上升趨勢，這是由于車輛的啟動成本在總成本中所占比重大于充電成本、行駛成本和懲罰成本的比重，使得增加車輛的代價較大。然而也出現了增加車輛數成本反而降低的現象，原因是雖然車輛數量的增多增加了啟動成本，但其通過提高配送效率所降低的懲罰成本已大于增加的車輛啟動成本了。

5 結語

從網上零售商的配送中心角度出發，提出了帶軟時間窗及充電站定位的電動汽車車輛路徑問題，從配送中心角度分析了車輛使用數量與使用成本對總物流配送成本的影響。借助計算機實現了基于遺傳算法的求解方法，獲得最優配送路線。提出的根據充電度數來計算充電成本的方式，增強了成本核算的精確性，克服了已有研究中不計充電成本或粗算充電成本的不足。此外，在采用遺傳算法求解問題時，采用改進交叉算子，使得優秀的子路徑能夠最大程度上被保留，該方法比采用順序交叉、循環交叉、位置交叉更適用于多車輛配送的車輛路徑問題。

物流配送活動中會產生不確定性情況，如路況、車況等，可結合該類情況提出更實用的問題求解方法；電動汽車到達充電站往往會產生等待時間，可通過對車輛的排隊分布進行模擬，獲得合理的等待時間，在問題求解中將該時間因素考慮進去。