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