車輛路徑規(guī)劃中的Electric Vehicle-Routing Problem簡(jiǎn)介
今天給大家?guī)淼氖请妱?dòng)汽車路徑規(guī)劃問題(Electric Vehicle-Routing Problem, EVRP)的介紹，按照慣例先上目錄，其中第三部分的主要內(nèi)容出自文獻(xiàn)“The Electric Vehicle-Routing Problem with Time Windows?and Recharging Stations”。
目錄
問題簡(jiǎn)介
VRP與EVRP
E-VRPTW
參考文獻(xiàn)
???????我們古代的時(shí)候有沒有類似物流一樣的東西呢？我想古代總有到處跑運(yùn)送物資或者信件的吧，不是還有鏢局呢嘛，當(dāng)然肯定跟我們現(xiàn)在研究的物流有很多不一樣的地方。古代運(yùn)輸基本靠動(dòng)物作為交通工具，到了近代開始有各種機(jī)械，比如小時(shí)候送信的郵差大多騎的是自行車，現(xiàn)在的物流配送比較多的是用汽車(這里不討論長(zhǎng)距離的)。
???????我們可以發(fā)現(xiàn)業(yè)務(wù)需求都大同小異，但是運(yùn)輸工具不斷變化。我們說的車輛路徑規(guī)劃問題，同樣的需求放古代可能就是馬匹路徑規(guī)劃問題，雖然作用是一樣的，但是由于不同的工具會(huì)有不同的特點(diǎn)從而會(huì)影響路徑的規(guī)劃。就算都是汽車，大一點(diǎn)小一點(diǎn)也可能會(huì)造成路線規(guī)劃的不同。既然以前的運(yùn)輸交通工具在變化，那么現(xiàn)在的運(yùn)輸交通工具應(yīng)該也會(huì)不斷變化。現(xiàn)在是汽車、電動(dòng)車，以后可能還有會(huì)飛的，可能走出地球了要考慮星系中的路徑規(guī)劃了，你看三體里水滴要摧毀人類的艦隊(duì)不也得解一下路徑問題么。
扯遠(yuǎn)了扯遠(yuǎn)了，那么今天要說的呢就是用電動(dòng)汽車作為運(yùn)輸工具的時(shí)候的路徑規(guī)劃，也就是電動(dòng)汽車路徑規(guī)劃(Electric Vehicle Routing Problem, EVRP)。
???????電動(dòng)汽車最近幾年的發(fā)展是比較迅速的，世界上也有很多地方推廣用電動(dòng)的替代燃燒化石燃料的。至于原因，大家可以想到減少尾氣的排放讓空氣質(zhì)量更好。歐盟在2010年的統(tǒng)計(jì)顯示交通運(yùn)輸活動(dòng)排放的溫室氣體占比將近20%，其中大部分在道路運(yùn)輸?shù)倪^程中產(chǎn)生。此外還有噪音污染也是存在的，在一些接近高速路的民居附近會(huì)安裝相應(yīng)的減少噪音的裝置，電動(dòng)汽車的發(fā)動(dòng)機(jī)和傳統(tǒng)汽車的發(fā)動(dòng)機(jī)不一樣，電動(dòng)汽車的產(chǎn)生的噪聲要少得多，而且電動(dòng)汽車使用的能源是可再生的。
???????既然電動(dòng)汽車有這么多好處，為啥企業(yè)不用呢？當(dāng)然是因?yàn)椤ぁぁぁべF啊。但是就算現(xiàn)在電動(dòng)汽車大減價(jià)，價(jià)格跟燃油汽車差不多，那配送車隊(duì)會(huì)進(jìn)行更換嗎？目前還不一定噢。因?yàn)殡妱?dòng)汽車要大規(guī)模應(yīng)用還是有些問題要解決的。電動(dòng)汽車是充電用的，手機(jī)也是充電用的，大家出門一天不帶充電寶不帶充電線，電量很低的時(shí)候是不是會(huì)很慌？其實(shí)開電動(dòng)車也有這樣的顧慮，叫里程焦慮(Range Anxiety)，也就是因擔(dān)心突然沒電引起的精神痛苦或者憂慮（Tredeau and Salameh 2009; Botsford and Szczepanek 2009）。
????? ?那燃油汽車就沒有這樣的焦慮嗎？幾乎沒有，因?yàn)榧佑驼镜教幎加校喈?dāng)于到處都有你這個(gè)手機(jī)插座和充電線，而且充電還賊快。即使未來充電站鋪設(shè)好了，充電速度可能也無法和加油媲美，這樣一來配送過程就要多花一些時(shí)間在這上面了。此外電池容量低也會(huì)導(dǎo)致車輛一次充電的行駛里程相較于燃油的短，而且電池電量還會(huì)受環(huán)境溫度的影響。
???????充電和電池使得EVRP相較于傳統(tǒng)的VRP需要考慮更多東西，在里程比較短，充電站還不夠多的情況下，選擇在哪個(gè)充電站進(jìn)行充電就需要算法進(jìn)行選擇了，要在電量、里程焦慮、繞路去充電之間作權(quán)衡。例如下面這個(gè)途中，從顧客2到顧客3的路線可以是去充電然后出發(fā)去顧客3。不擔(dān)心電量的話可以直接出發(fā)去顧客3。如果是電量不足以先去服務(wù)顧客3再回場(chǎng)站但是又足夠回場(chǎng)站的話，就要權(quán)衡是不是直接回場(chǎng)站再派另一輛車服務(wù)顧客3還是先去充電再接著服務(wù)，
???????還有一個(gè)問題是電動(dòng)汽車充電并不是像汽車加油那樣基本是一個(gè)線性的過程，汽油在整個(gè)加油過程中流速不會(huì)有太大的變化。但是電動(dòng)汽車的電池在充電和放電的效率上并不是線性的，例如在重新充電的時(shí)候最后的10%-20%花的時(shí)間要比之前的多(Marra et al. 2012)。
???????由于充電的時(shí)間比加油的時(shí)間長(zhǎng)的多使得充電時(shí)間不能被忽視，因此會(huì)用一個(gè)充電函數(shù)來描述這一過程，簡(jiǎn)化版本的呢會(huì)用線性函數(shù)來構(gòu)建，也有研究非線性的充電函數(shù)的。但是在實(shí)際應(yīng)用中這兩者的差別還是挺大的，使用簡(jiǎn)化后的線性函數(shù)構(gòu)建充電函數(shù)在實(shí)際應(yīng)用中可能會(huì)有較大的誤差。如下圖選取不同的數(shù)據(jù)作線性函數(shù)的擬合，會(huì)有相差較大的結(jié)果，在實(shí)際應(yīng)用中是需要避免出現(xiàn)這樣的問題的。
在現(xiàn)實(shí)世界中電量的消耗速度還和載荷、車速、坡度甚至風(fēng)速等等因素相關(guān)。
???????在小包裹運(yùn)輸行業(yè)，一些大公司，如DHL、UPS和DPD已經(jīng)開始使用電動(dòng)汽車進(jìn)行“最后一公里”的配送，特別是在城市地區(qū)。在現(xiàn)階段而言，路徑規(guī)劃還是能為這些使用電動(dòng)汽車的企業(yè)做些事情的。
???????今天我們要介紹的是帶時(shí)間窗約束的車輛的電動(dòng)汽車路徑規(guī)劃問題，因?yàn)闀r(shí)間窗約束在這最后一公里的配送中是比較常見的約束。
??????文章里使用的算法是變鄰域搜索算法和禁忌搜索算法的混合算法。變鄰域搜索算法我們?cè)?jīng)仔細(xì)地介紹過，這里就不過多的介紹了，補(bǔ)課鏈接"干貨 | 變鄰域搜索算法(Variable Neighborhood Search,VNS)超詳細(xì)一看就懂"。這里的混合變鄰域搜索算法跟一般的變鄰域搜索算法的shaking階段是相同的，但是在領(lǐng)域搜索上這里的混合算法使用的是禁忌搜索算法，此外在解的接受上也借鑒了模擬退火算法的思想，也就是說在鄰域中搜索得到的解比現(xiàn)有的解差時(shí)，算法會(huì)以一定的幾率接受這個(gè)解，如果比現(xiàn)有的解更優(yōu)的話是一定會(huì)接受的。后面會(huì)介紹一下一些環(huán)節(jié)用到的方法。
???????
3.1?數(shù)學(xué)模型
???????問題定義就不說了吧，帶時(shí)間窗約束的車輛路徑規(guī)劃我們也做過很多推文了，這里在定義上把汽車限定在了電動(dòng)汽車。定義上沒有特別大的不同，差異主要體現(xiàn)在我們上文中所介紹的充電環(huán)節(jié)上。
??????這個(gè)模型的充電函數(shù)是線性的，以一個(gè)穩(wěn)定的速率充電。具體的定義小編就假設(shè)各位讀者人均英語(yǔ)四級(jí)以上能夠看懂啦(因?yàn)楣娞?hào)整公式符號(hào)是真滴難受)
????? ?其中優(yōu)化目標(biāo)是使得行駛距離最短，約束(2)、約束(3)保證訪問的顧客節(jié)點(diǎn)和充電站節(jié)點(diǎn)是連通的；約束(4)則是保證節(jié)點(diǎn)的流守恒，即入的流和出的流要相等；約束(5)、約束(6)保證離開節(jié)點(diǎn)在時(shí)間上的可行性；約束(7)滿足時(shí)間窗約束；此外約束(5)~約束(7)也能夠防止子回路的出現(xiàn)；約束(8)和約束(9)保證顧客的需求得到滿足；約束(10)和約束(11)保證汽車電量不會(huì)在0以下。在解問題的算法上由于這個(gè)問題是NP-Hard問題，因此算法上還是跟我們之前所介紹的差不多，小規(guī)模的精確性算法和啟發(fā)式算法，文獻(xiàn)里用的方法是變鄰域搜索和禁忌搜索的混合算法。
3.2 初始解的構(gòu)造
在進(jìn)行初始解的構(gòu)造之前，可以根據(jù)一些條件去掉圖中一些明顯不可行的邊，這樣可以減少搜索域。滿足以下約束的邊都是不可行的：
不可行的原因是因?yàn)闈M足約束(13)的邊是超過容量約束的邊，滿足約束(14)和約束(15)的邊是不滿足時(shí)間窗約束的邊，而滿足約束(16)的邊則是違反電池的容量約束的邊。
???????去掉上面這些邊后隨機(jī)選擇一個(gè)顧客點(diǎn)，該點(diǎn)與場(chǎng)站可以確定一條射線，其余的點(diǎn)也可以與場(chǎng)站確定一條射線，這些射線與第一條射線會(huì)形成一個(gè)夾角。按照夾角角度的大小將顧客顧客節(jié)點(diǎn)做一個(gè)排序。根據(jù)這些排序?qū)㈩櫩鸵粋€(gè)一個(gè)地指派給一輛車輛的行駛路線，并且安排在增加的行駛距離最小的位置上。如果當(dāng)前的路線已經(jīng)超過載貨容量或者電池容量的限制了則開啟新的行駛線路，直到所有的顧客都被安排上。
3.3 目標(biāo)函數(shù)
????? ?文章中的優(yōu)化目標(biāo)是使得行駛距離最短。變鄰域搜索和禁忌搜索很多時(shí)候都會(huì)允許非可行解的存在以擴(kuò)大搜索空間，但是在優(yōu)化的目標(biāo)函數(shù)上會(huì)對(duì)違反約束的解增加懲罰項(xiàng)。VRPTW問題會(huì)懲罰違反容量約束和時(shí)間窗約束的解，使用電動(dòng)汽車的時(shí)候，除了上述這兩個(gè)約束以外還會(huì)懲罰違反電池容量約束的解。
????? ?至于約束違反如何計(jì)算相信就不用過多介紹了，因?yàn)槿萘客ㄟ^加減就可以計(jì)算出來。時(shí)間窗和電量都可以通過計(jì)算到達(dá)每個(gè)節(jié)點(diǎn)時(shí)的時(shí)間和剩余電量進(jìn)行計(jì)算。
3.4?變鄰域搜索部分
這里的shaking階段跟一般的VNS相同，局部搜索會(huì)用后面介紹的禁忌搜索部分替代。領(lǐng)域結(jié)構(gòu)由循環(huán)交換算子定義。舉個(gè)例子，如果有三條線路參與循環(huán)交換，那么循環(huán)交換是這樣的
文中用到的鄰域結(jié)構(gòu)如下：
每一個(gè)小表格中的第二列是參與上述算子的路線的數(shù)量，第三列是一條路線中允許移動(dòng)的連續(xù)節(jié)點(diǎn)的最大數(shù)量。實(shí)際移動(dòng)的數(shù)量會(huì)取路線上的節(jié)點(diǎn)數(shù)量和這個(gè)最大數(shù)量中的最小值。
3.5?禁忌搜索部分
這里的禁忌搜索替代一般的VNS中的局部搜索，可以看作是一種改進(jìn)吧。這里用到的搜索算子有2-opt*、exchange、relocate和根據(jù)問題提出的stationInRe。
這個(gè)2-opt*可能說的并不多，我們之前的推文有介紹過2-opt算法，算法的操作像下面這樣
但是這個(gè)算法在有時(shí)間窗約束的情況下并不是特別適用，因?yàn)檫@個(gè)算法會(huì)反轉(zhuǎn)一部分顧客節(jié)點(diǎn)的訪問順序，破壞解的可行性的可能性會(huì)變大。2-opt*正是為了盡可能避免這種破壞提出來的，即同樣是交換一對(duì)邊，但是保留訪問順序。舉個(gè)例子，在圖上的一條路線是一個(gè)環(huán)，2-opt*算法就是在兩個(gè)環(huán)上交換一對(duì)邊，并且保持剩下的節(jié)點(diǎn)的訪問的先后順序。如下圖
這里要介紹一下文里提出的stationInRe。這里的station是指充電站，In指的是insertion, Re指的是removal。這個(gè)算子針對(duì)的是所有與充電站相連的邊，即邊(v,w)，其中點(diǎn)v為充電站，令w-為點(diǎn)w的上一個(gè)顧客節(jié)點(diǎn)。如果(v,w)不是解的一部分，那么就將這個(gè)邊插入到(w-,w)之間。反之則將(v,w)移除掉。
至于禁忌規(guī)則跟我們以往介紹的差不多，被移除的邊在接下來的特定次數(shù)的迭代中不能重新插入到一些地方。特赦原則與一般的禁忌搜索相同，接受處于禁忌狀態(tài)但是比當(dāng)前最優(yōu)解更優(yōu)的可行解。
?
參考文獻(xiàn)
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.
?贊 賞?
長(zhǎng)按下方二維碼打賞感謝您，支持學(xué)生們的原創(chuàng)熱情！
?
---The End---
文案?&&?編輯：莊浩城審稿人：秦時(shí)明岳（華中科技大學(xué)管理學(xué)院）指導(dǎo)老師：秦時(shí)明岳（華中科技大學(xué)管理學(xué)院）
如對(duì)文中內(nèi)容有疑問，歡迎交流。PS:部分資料來自網(wǎng)絡(luò)。如有需求，可以聯(lián)系：秦虎老師（[email protected]）莊浩城 (華中科技大學(xué)管理學(xué)院本科四年級(jí)：[email protected])