今天給大家帶來的是電動汽車路徑規劃問題(Electric Vehicle-Routing Problem, EVRP)的介紹，按照慣例先上目錄，其中第三部分的主要內容出自文獻“The Electric Vehicle-Routing Problem with Time Windows and Recharging Stations”。

目錄

• 問題簡介

• VRP與EVRP

• E-VRPTW

• 參考文獻

問題簡介

我們古代的時候有沒有類似物流一樣的東西呢？我想古代總有到處跑運送物資或者信件的吧，不是還有鏢局呢嘛，當然肯定跟我們現在研究的物流有很多不一樣的地方。古代運輸基本靠動物作為交通工具，到了近代開始有各種機械，比如小時候送信的郵差大多騎的是自行車，現在的物流配送比較多的是用汽車(這里不討論長距離的)。

我們可以發現業務需求都大同小異，但是運輸工具不斷變化。我們說的車輛路徑規劃問題，同樣的需求放古代可能就是馬匹路徑規劃問題，雖然作用是一樣的，但是由于不同的工具會有不同的特點從而會影響路徑的規劃。就算都是汽車，大一點小一點也可能會造成路線規劃的不同。既然以前的運輸交通工具在變化，那么現在的運輸交通工具應該也會不斷變化。現在是汽車、電動車，以后可能還有會飛的，可能走出地球了要考慮星系中的路徑規劃了，你看三體里水滴要摧毀人類的艦隊不也得解一下路徑問題么。

扯遠了扯遠了，那么今天要說的呢就是用電動汽車作為運輸工具的時候的路徑規劃，也就是電動汽車路徑規劃(Electric Vehicle Routing Problem, EVRP)。

電動汽車最近幾年的發展是比較迅速的，世界上也有很多地方推廣用電動的替代燃燒化石燃料的。至于原因，大家可以想到減少尾氣的排放讓空氣質量更好。歐盟在2010年的統計顯示交通運輸活動排放的溫室氣體占比將近20%，其中大部分在道路運輸的過程中產生。此外還有噪音污染也是存在的，在一些接近高速路的民居附近會安裝相應的減少噪音的裝置，電動汽車的發動機和傳統汽車的發動機不一樣，電動汽車的產生的噪聲要少得多，而且電動汽車使用的能源是可再生的。

VRP與EVRP

既然電動汽車有這么多好處，為啥企業不用呢？當然是因為····貴啊。但是就算現在電動汽車大減價，價格跟燃油汽車差不多，那配送車隊會進行更換嗎？目前還不一定噢。因為電動汽車要大規模應用還是有些問題要解決的。電動汽車是充電用的，手機也是充電用的，大家出門一天不帶充電寶不帶充電線，電量很低的時候是不是會很慌？其實開電動車也有這樣的顧慮，叫里程焦慮(Range Anxiety)，也就是因擔心突然沒電引起的精神痛苦或者憂慮（Tredeau and Salameh 2009; Botsford and Szczepanek 2009）。

那燃油汽車就沒有這樣的焦慮嗎？幾乎沒有，因為加油站到處都有，相當于到處都有你這個手機插座和充電線，而且充電還賊快。即使未來充電站鋪設好了，充電速度可能也無法和加油媲美，這樣一來配送過程就要多花一些時間在這上面了。此外電池容量低也會導致車輛一次充電的行駛里程相較于燃油的短，而且電池電量還會受環境溫度的影響。

充電和電池使得EVRP相較于傳統的VRP需要考慮更多東西，在里程比較短，充電站還不夠多的情況下，選擇在哪個充電站進行充電就需要算法進行選擇了，要在電量、里程焦慮、繞路去充電之間作權衡。例如下面這個途中，從顧客2到顧客3的路線可以是去充電然后出發去顧客3。不擔心電量的話可以直接出發去顧客3。如果是電量不足以先去服務顧客3再回場站但是又足夠回場站的話，就要權衡是不是直接回場站再派另一輛車服務顧客3還是先去充電再接著服務，

還有一個問題是電動汽車充電并不是像汽車加油那樣基本是一個線性的過程，汽油在整個加油過程中流速不會有太大的變化。但是電動汽車的電池在充電和放電的效率上并不是線性的，例如在重新充電的時候最后的10%-20%花的時間要比之前的多(Marra et al. 2012)。

由于充電的時間比加油的時間長的多使得充電時間不能被忽視，因此會用一個充電函數來描述這一過程，簡化版本的呢會用線性函數來構建，也有研究非線性的充電函數的。但是在實際應用中這兩者的差別還是挺大的，使用簡化后的線性函數構建充電函數在實際應用中可能會有較大的誤差。如下圖選取不同的數據作線性函數的擬合，會有相差較大的結果，在實際應用中是需要避免出現這樣的問題的。

在現實世界中電量的消耗速度還和載荷、車速、坡度甚至風速等等因素相關。

E-VRPTW

在小包裹運輸行業，一些大公司，如DHL、UPS和DPD已經開始使用電動汽車進行“最后一公里”的配送，特別是在城市地區。在現階段而言，路徑規劃還是能為這些使用電動汽車的企業做些事情的。

今天我們要介紹的是帶時間窗約束的車輛的電動汽車路徑規劃問題，因為時間窗約束在這最后一公里的配送中是比較常見的約束。

文章里使用的算法是變鄰域搜索算法和禁忌搜索算法的混合算法。變鄰域搜索算法我們曾經仔細地介紹過，這里就不過多的介紹了，補課鏈接"干貨 | 變鄰域搜索算法(Variable Neighborhood Search,VNS)超詳細一看就懂"。這里的混合變鄰域搜索算法跟一般的變鄰域搜索算法的shaking階段是相同的，但是在領域搜索上這里的混合算法使用的是禁忌搜索算法，此外在解的接受上也借鑒了模擬退火算法的思想，也就是說在鄰域中搜索得到的解比現有的解差時，算法會以一定的幾率接受這個解，如果比現有的解更優的話是一定會接受的。后面會介紹一下一些環節用到的方法。

3.1 數學模型

問題定義就不說了吧，帶時間窗約束的車輛路徑規劃我們也做過很多推文了，這里在定義上把汽車限定在了電動汽車。定義上沒有特別大的不同，差異主要體現在我們上文中所介紹的充電環節上。

這個模型的充電函數是線性的，以一個穩定的速率充電。具體的定義小編就假設各位讀者人均英語四級以上能夠看懂啦(因為公眾號整公式符號是真滴難受)

其中優化目標是使得行駛距離最短，約束(2)、約束(3)保證訪問的顧客節點和充電站節點是連通的；約束(4)則是保證節點的流守恒，即入的流和出的流要相等；約束(5)、約束(6)保證離開節點在時間上的可行性；約束(7)滿足時間窗約束；此外約束(5)~約束(7)也能夠防止子回路的出現；約束(8)和約束(9)保證顧客的需求得到滿足；約束(10)和約束(11)保證汽車電量不會在0以下。在解問題的算法上由于這個問題是NP-Hard問題，因此算法上還是跟我們之前所介紹的差不多，小規模的精確性算法和啟發式算法，文獻里用的方法是變鄰域搜索和禁忌搜索的混合算法。

3.2 初始解的構造

在進行初始解的構造之前，可以根據一些條件去掉圖中一些明顯不可行的邊，這樣可以減少搜索域。滿足以下約束的邊都是不可行的：

不可行的原因是因為滿足約束(13)的邊是超過容量約束的邊，滿足約束(14)和約束(15)的邊是不滿足時間窗約束的邊，而滿足約束(16)的邊則是違反電池的容量約束的邊。

去掉上面這些邊后隨機選擇一個顧客點，該點與場站可以確定一條射線，其余的點也可以與場站確定一條射線，這些射線與第一條射線會形成一個夾角。按照夾角角度的大小將顧客顧客節點做一個排序。根據這些排序將顧客一個一個地指派給一輛車輛的行駛路線，并且安排在增加的行駛距離最小的位置上。如果當前的路線已經超過載貨容量或者電池容量的限制了則開啟新的行駛線路，直到所有的顧客都被安排上。

3.3 目標函數

文章中的優化目標是使得行駛距離最短。變鄰域搜索和禁忌搜索很多時候都會允許非可行解的存在以擴大搜索空間，但是在優化的目標函數上會對違反約束的解增加懲罰項。VRPTW問題會懲罰違反容量約束和時間窗約束的解，使用電動汽車的時候，除了上述這兩個約束以外還會懲罰違反電池容量約束的解。

至于約束違反如何計算相信就不用過多介紹了，因為容量通過加減就可以計算出來。時間窗和電量都可以通過計算到達每個節點時的時間和剩余電量進行計算。

3.4 變鄰域搜索部分

這里的shaking階段跟一般的VNS相同，局部搜索會用后面介紹的禁忌搜索部分替代。領域結構由循環交換算子定義。舉個例子，如果有三條線路參與循環交換，那么循環交換是這樣的

文中用到的鄰域結構如下：

每一個小表格中的第二列是參與上述算子的路線的數量，第三列是一條路線中允許移動的連續節點的最大數量。實際移動的數量會取路線上的節點數量和這個最大數量中的最小值。

3.5 禁忌搜索部分

這里的禁忌搜索替代一般的VNS中的局部搜索，可以看作是一種改進吧。這里用到的搜索算子有2-opt*、exchange、relocate和根據問題提出的stationInRe。

這個2-opt*可能說的并不多，我們之前的推文有介紹過2-opt算法，算法的操作像下面這樣

但是這個算法在有時間窗約束的情況下并不是特別適用，因為這個算法會反轉一部分顧客節點的訪問順序，破壞解的可行性的可能性會變大。2-opt*正是為了盡可能避免這種破壞提出來的，即同樣是交換一對邊，但是保留訪問順序。舉個例子，在圖上的一條路線是一個環，2-opt*算法就是在兩個環上交換一對邊，并且保持剩下的節點的訪問的先后順序。如下圖

這里要介紹一下文里提出的stationInRe。這里的station是指充電站，In指的是insertion, Re指的是removal。這個算子針對的是所有與充電站相連的邊，即邊(v,w)，其中點v為充電站，令w-為點w的上一個顧客節點。如果(v,w)不是解的一部分，那么就將這個邊插入到(w-,w)之間。反之則將(v,w)移除掉。

至于禁忌規則跟我們以往介紹的差不多，被移除的邊在接下來的特定次數的迭代中不能重新插入到一些地方。特赦原則與一般的禁忌搜索相同，接受處于禁忌狀態但是比當前最優解更優的可行解。

參考文獻

Schneider M, Stenger A, Goeke D, et al. The Electric Vehicle-Routing Problem with Time Windows and Recharging Stations[J]. Transportation Science, 2014, 48(4): 500-520.

Marra F, Yang G, Larsen E, et al. Demand profile study of battery electric vehicle under different charging options[C]. power and energy society general meeting, 2012: 1-7.

Montoya A, Gueret C, Mendoza J E, et al. The electric vehicle routing problem with nonlinear charging function[J]. Transportation Research Part B-methodological, 2017: 87-110.

Davis B, Figliozzi M A. A Methodology to Evaluate the Competitiveness of Electric Delivery Trucks[J]. Transportation Research Part E-logistics and Transportation Review, 2013, 49(1): 8-23.

Botsford C, Szczepanek A (2009) Fast charging vs. slow charging: Pros and cons for the new age of electric vehicles. EVS24 Internat. Battery, Hybrid and Fuel Cell Electric Vehicle Sympos., Stavanger, Norway.

Tredeau F P, Salameh Z M. Evaluation of Lithium iron phosphate batteries for electric vehicles application[C]. vehicle power and propulsion conference, 2009: 1266-1270.