基于時(shí)空間優(yōu)化的充電站空間布局優(yōu)化模型

基于時(shí)空間優(yōu)化的充電站空間布局優(yōu)化模型

1充電站布局的影響因素新能源汽車，尤其是電動(dòng)汽車，近年來引起了越來越多的關(guān)注。電動(dòng)汽車對(duì)于緩解能源危機(jī)、氣候變化、大氣污染與日益增長(zhǎng)的交通需求之間的矛盾具有重大意義。然而,充電設(shè)施的缺乏嚴(yán)重阻礙了電動(dòng)汽車的推廣,研究認(rèn)為充電站的建設(shè)對(duì)發(fā)展電動(dòng)汽車至關(guān)重要:有限的充電站空間覆蓋水平將影響出行的便利性,從而降低消費(fèi)者的購(gòu)買意愿;另一方面,電動(dòng)汽車需求市場(chǎng)的蕭條將影響制造商的研發(fā)投入,降低運(yùn)營(yíng)商投資充電站的意愿,使推廣電動(dòng)汽車陷入“先有雞還是先有蛋”的困境。由政府或社會(huì)力量先行投資建設(shè)初始充電站網(wǎng)絡(luò)成為打破這種困境的有效選擇。考慮到充電站建設(shè)成本較高,以及有限的財(cái)政預(yù)算約束,如何充分考慮充電站布局影響因素,提高其布局效率顯得尤為重要。本文結(jié)合電動(dòng)汽車的行駛局限性和充電需求特性,在總結(jié)已有供應(yīng)站布局優(yōu)化研究成果的基礎(chǔ)上,從出行者充電需求時(shí)空分布和充電決策過程角度出發(fā),建立了一種新的電動(dòng)汽車充電站布局模型——時(shí)空間約束下布局優(yōu)化模型(Time-SpatialLocationModel,TSLM),并對(duì)該模型和目前廣泛應(yīng)用的截流選址模型(FlowCapturingLocationModel,簡(jiǎn)稱FCLM模型)在算例路網(wǎng)上的模擬計(jì)算結(jié)果進(jìn)行比較分析,據(jù)此提出未來的研究方向。2基于fclm的截流選址模型根據(jù)補(bǔ)充燃料需求產(chǎn)生形式和優(yōu)化方法的差異,既有新能源供應(yīng)站優(yōu)化布局的方法和模型可歸為兩類:點(diǎn)需求模型和流量需求模型。點(diǎn)需求模型通常假設(shè)補(bǔ)充燃料需求產(chǎn)生于路網(wǎng)中的節(jié)點(diǎn),其優(yōu)化目標(biāo)是定位給定的p個(gè)供應(yīng)站并分配每個(gè)需求點(diǎn)到一個(gè)特定的供應(yīng)站,從而滿足所有需求點(diǎn)與供應(yīng)站之間的平均距離最小。這類模型中應(yīng)用最多、最廣泛的是P-Median模型,它通常假設(shè)燃料需求產(chǎn)生點(diǎn)為住所或工作地點(diǎn),因此實(shí)際應(yīng)用中可將供應(yīng)站配置在人們的居住區(qū)附近,較便利地滿足人們的出行需求。Lin等通過假設(shè)路網(wǎng)中的任一點(diǎn)都有可能因燃料耗盡而成為需求產(chǎn)生點(diǎn),提出了考慮“折返就近加油”方法(Fuel-Travel-Back)的平均加油旅行時(shí)間最短的優(yōu)化目標(biāo),改進(jìn)了P-Median模型關(guān)于需求產(chǎn)生點(diǎn)的假設(shè),然而該模型假設(shè)車輛在燃料耗盡后就近尋找供應(yīng)站,尋求供應(yīng)站時(shí)機(jī)的假設(shè)與現(xiàn)實(shí)存在較大差距。第二類流量需求模型的優(yōu)化目標(biāo)是對(duì)p個(gè)供應(yīng)站選址使得供應(yīng)站所能服務(wù)的顧客流量最大。流量需求模型中的燃料需求不再局限于路網(wǎng)中的節(jié)點(diǎn),而采用路段上的車流量表示,其基礎(chǔ)模型是Hodgson于1990年提出的截流選址(FCLM)模型。與點(diǎn)需求模型相比,FCLM模型可以更好地?cái)M合人們的出行行為,即人們不是為了接受服務(wù)而出行,而是在出行過程中順道接受服務(wù)。但FCLM模型沒有對(duì)出行距離的長(zhǎng)短加以區(qū)別,假設(shè)只要出行路徑中存在一處供應(yīng)站便能滿足出行需求。這一假設(shè)適用于非長(zhǎng)距離出行(例如不超過100km),但對(duì)于行駛里程有限的電動(dòng)汽車來說,完成一次較長(zhǎng)距離的出行可能需要接受兩次或更多的服務(wù),這就需要在行駛路徑上設(shè)置多處供應(yīng)站,FCLM模型顯然無法解決這樣的現(xiàn)實(shí)問題。針對(duì)這一問題,Kuby等綜合考慮行駛里程參數(shù)和站點(diǎn)組合,建立了續(xù)航選址模型(FlowRefuelingLocationModel,FRLM),該模型可以兼顧長(zhǎng)距離和短距離出行,更加符合現(xiàn)實(shí)情況,伴隨這一模型的應(yīng)用還出現(xiàn)了尋找備選站點(diǎn)的相關(guān)研究。然而,FCLM和FRLM均假設(shè)路徑上的供應(yīng)站能夠滿足該路徑上所有車流量補(bǔ)充燃料的需求,而忽略了供應(yīng)站的同時(shí)服務(wù)容量限制。Upchurch等通過考慮有限容量因素修正了FRLM模型,建立了有限容量續(xù)航選址模型(CapacitatedFlowRefuelingLocationModel)。上述各種流量需求模型均采用了最短路徑假設(shè),即使只需繞行很短的距離就可以獲得服務(wù),也不允許有任何的繞道行為。但是現(xiàn)實(shí)中出行者可能樂意繞行來獲得服務(wù),而且現(xiàn)實(shí)路網(wǎng)中擁堵路段上的車流往往選擇其他路徑而非最短路徑。楊珺等提出了考慮服務(wù)半徑的截流選址模型(FlowCapturingLocationModelwithServiceRadius,簡(jiǎn)稱SR-FCLM模型),該模型假設(shè)如果供應(yīng)站到顧客流量通過的路線上至少一個(gè)節(jié)點(diǎn)的距離不超過路徑服務(wù)半徑d,路徑上的顧客會(huì)愿意偏離原來的路線,繞2d距離去接受供應(yīng)站的服務(wù),再返回到原來的路線。近年來還出現(xiàn)了一些多目標(biāo)選址優(yōu)化模型的研究,如最大覆蓋/最短路徑問題(MaximumCovering/ShortestPathProblem,簡(jiǎn)稱MCSPP模型),最小費(fèi)用/最大覆蓋問題(MinimumCost/MaximumCoverageProblem,簡(jiǎn)稱MCMCP),以及結(jié)合P-Median和FCLM的最大流量/最短距離問題(MaximumCapturing/MinimumDistanceProblem,簡(jiǎn)稱MCMDP)。此外,基于Agent的模型也被應(yīng)用在布局問題中,這類研究主要基于動(dòng)態(tài)反饋思想,其中一個(gè)顯著的成果是引入了擔(dān)憂系數(shù),描述了在初始新能源供應(yīng)站較少的情況下,新能源汽車購(gòu)買者對(duì)于燃料耗盡后不能及時(shí)得到服務(wù)的擔(dān)心。電動(dòng)汽車快速充電時(shí)間約為30分鐘,受充電站的同時(shí)服務(wù)能力的限制,充電需求時(shí)間上的集中必然引起排隊(duì)等待,或者尋找其他可用充電站的行為。遺憾的是,既有模型僅考慮了補(bǔ)充燃料需求的空間分布,卻忽視了時(shí)間限制約束。當(dāng)考慮充電站優(yōu)化布局問題時(shí),需要考慮充電的行為決策過程,即:何時(shí)需要充電,去何地充電,以及當(dāng)因充電站同時(shí)服務(wù)容量限制而產(chǎn)生排隊(duì)時(shí)作何選擇等問題。3在時(shí)間空間限制下，優(yōu)化模型的結(jié)構(gòu)布局3.1tslm模型的充電算法電動(dòng)汽車使用者在出行中除了考慮出行起迄點(diǎn)間的最短行駛路徑外,還需要考慮充電站的可獲得性、充電站的排隊(duì)情況,在電量耗盡之前到達(dá)距離起迄點(diǎn)間最短路徑較近的充電站,同時(shí)滿足總出行時(shí)間(包括排隊(duì)時(shí)間、可能的繞行時(shí)間和到達(dá)終點(diǎn)的行駛時(shí)間)最小。電動(dòng)汽車在到達(dá)某充電站i時(shí)將面臨3種選擇:(1)剩余電量不能到達(dá)其他充電站,必須在站點(diǎn)i接受充電;(2)剩余電量可以到達(dá)其他充電站,選擇在站點(diǎn)i接受充電;(3)剩余電量可以到達(dá)其他充電站,選擇不在站點(diǎn)i接受充電。后兩種情況取決于備選站點(diǎn)的排隊(duì)情況,以及出行者可能需要繞行的距離或者時(shí)間。其中站點(diǎn)i的排隊(duì)等待時(shí)間受等待車輛數(shù)、充電樁個(gè)數(shù)、以及充電時(shí)間的影響。電動(dòng)汽車在每個(gè)短時(shí)段根據(jù)剩余電量和充電站排隊(duì)信息做出判斷,選擇最佳充電站和路徑,并不局限于最短路徑。下面以設(shè)定的情景來說明TSLM模型的充電規(guī)則。圖1所示的5個(gè)節(jié)點(diǎn)簡(jiǎn)單路網(wǎng)中,A和E為一對(duì)起迄點(diǎn),充電站設(shè)在C、D處,其中站點(diǎn)C在A-E之間的最短路徑ACE上,A-D之間的最短路徑為ABD。l1表示A、B兩節(jié)點(diǎn)間的距離;VMTAm表示電動(dòng)汽車m在點(diǎn)A的剩余行駛里程;NCm表示電動(dòng)汽車m到達(dá)站點(diǎn)C時(shí),該站點(diǎn)的車輛數(shù);qC表示站點(diǎn)C的充電樁個(gè)數(shù);WCm表示電動(dòng)汽車m在站點(diǎn)C的等待時(shí)間;TmCE表示電動(dòng)汽車m在點(diǎn)C和E之間沿最短路徑的行駛時(shí)間;U表示路網(wǎng)中消失的電動(dòng)車輛數(shù),可用來評(píng)價(jià)充電站網(wǎng)絡(luò)的服務(wù)水平。電動(dòng)汽車m將按以下順序選擇是否需要充電以及在何處充電:由充電選擇行為可知,TSLM對(duì)最短路徑的考慮顯著區(qū)別于傳統(tǒng)模型,它將任意兩點(diǎn)之間的最短路徑作為出行者的首選,但允許車輛繞道以完成充電服務(wù),且繞道后不必返回原來的路線,而是沿充電結(jié)束地與目的地之間的最短路徑行駛。3.2電動(dòng)汽車充電系統(tǒng)模型出行者在出行過程中的充電需求相當(dāng)復(fù)雜,受多種因素的影響,為了更加全面和準(zhǔn)確的描述現(xiàn)實(shí)狀況和充電站布局的影響因素,以及建模的需要,做出如下假設(shè):(1)所有電動(dòng)汽車出行者對(duì)充電站的位置以及各個(gè)站點(diǎn)在某一時(shí)刻的排隊(duì)情況完全可知,因此可以準(zhǔn)確地做出當(dāng)前時(shí)刻的最佳決定。(2)不考慮道路交通狀況的影響,電動(dòng)汽車以相同的速度40km/h行駛,電量的消耗與行駛里程呈線性關(guān)系。(3)考慮充電站同時(shí)充電容量限制,當(dāng)待充電車輛數(shù)大于某站點(diǎn)充電樁個(gè)數(shù)時(shí),車輛需要等待以完成充電服務(wù)。(4)電動(dòng)汽車出發(fā)時(shí)刻為服從均勻分布的隨機(jī)時(shí)刻。(5)電動(dòng)汽車在出發(fā)時(shí)刻的剩余電量可支持的行駛里程是區(qū)間[60km,100km]之間的服從正態(tài)分布N(0,1)的隨機(jī)數(shù),接受充電服務(wù)后的可行駛里程為100km。(6)電動(dòng)汽車快速充電所需時(shí)間均為30分鐘,不考慮剩余電量和車輛類型的影響。(7)每個(gè)充電站的充電樁個(gè)數(shù)為定值,不考慮投資規(guī)模和用地條件的限制。其中假設(shè)1和2與傳統(tǒng)模型類似,假設(shè)3-7則從出發(fā)時(shí)刻分布、出發(fā)時(shí)剩余電量、充電時(shí)間、以及排隊(duì)時(shí)間等角度提出緩解傳統(tǒng)模型脫離現(xiàn)實(shí)假設(shè)的約束條件,TSLM模型區(qū)別于傳統(tǒng)模型的最大特點(diǎn)在于其動(dòng)態(tài)性。3.3模型1:單排隊(duì)時(shí)間根據(jù)上述充電選擇行為分析及模型假設(shè),建立TSLM模型如下:式中:p為充電站總個(gè)數(shù),p=1,2,…;i為路網(wǎng)節(jié)點(diǎn)或充電站點(diǎn);m為電動(dòng)汽車編號(hào);Xi為決策變量,如果節(jié)點(diǎn)i建有充電站,等于1,否則為0;Sim為狀態(tài)指示變量,如果電動(dòng)汽車m選擇在站點(diǎn)i充電,等于1,否則為0;Wim為電動(dòng)汽車m在站點(diǎn)i的等待時(shí)間;Tm為電動(dòng)汽車m完成本次出行的行駛時(shí)間。目標(biāo)函數(shù)(1)表示所有車輛的總等待時(shí)間和總行駛時(shí)間之和最小。約束條件(2)表示建立的充電站總數(shù)為p個(gè);約束條件(3)和(4)表示決策變量Xi和Sim為0-1變量。模型中對(duì)排隊(duì)情況的處理采用多服務(wù)臺(tái)單隊(duì)列排隊(duì)模型。當(dāng)Xi=1且Sim=1時(shí),式中:rim為電動(dòng)汽車m到達(dá)站點(diǎn)i的時(shí)刻;gim為電動(dòng)汽車m離開站點(diǎn)i的時(shí)刻;Wim為電動(dòng)汽車m在站點(diǎn)i的等待時(shí)間;Mim為電動(dòng)汽車m到達(dá)站點(diǎn)i時(shí),站點(diǎn)i已有的電動(dòng)車輛集合;τ為充電時(shí)間,為定值30分鐘;Nim為電動(dòng)汽車m到達(dá)站點(diǎn)i時(shí),站點(diǎn)i的車輛數(shù);qi為站點(diǎn)i的充電樁個(gè)數(shù)。TSLM是一個(gè)動(dòng)態(tài)模型,充分考慮了時(shí)間因素的影響,更加符合現(xiàn)實(shí)情況,但求解也較為復(fù)雜。傳統(tǒng)模型的求解方法難以應(yīng)用,而需要用仿真方法來實(shí)現(xiàn)。4計(jì)算與分析4.1路網(wǎng)中交通流量的分配為驗(yàn)證TSLM模型的有效性,考慮圖2所示的具有25個(gè)節(jié)點(diǎn)的路網(wǎng),該網(wǎng)絡(luò)由Berman和Simchi-Levi提出,被眾多研究者用作驗(yàn)證算例。圖2中圓圈內(nèi)的數(shù)字表示路網(wǎng)節(jié)點(diǎn)的編號(hào),圓圈的大小表示該節(jié)點(diǎn)的吸引力權(quán)重(例如人口規(guī)模),路段上的數(shù)字表示兩節(jié)點(diǎn)間的路段長(zhǎng)度。任一O-D之間的交通流量根據(jù)重力模型計(jì)算獲得:ODij=WiWj/dij×1.5,其中Wi和Wj分別表示起迄點(diǎn)的吸引力權(quán)重,dij表示i和j之間的最短路徑長(zhǎng)度。根據(jù)3.1節(jié)的充電選擇行為假設(shè),路網(wǎng)中的交通流量首先加載到最短路徑上,然后在出行過程中根據(jù)充電站的排隊(duì)等待情況將某一O-D之間的交通流量部分或全部分配到其他路徑上;當(dāng)車輛出發(fā)時(shí)刻的剩余電量不能支持沿最短路徑的往返出行時(shí),便產(chǎn)生了充電需求,所有在出行過程中需要充電的車輛構(gòu)成了路網(wǎng)中的充電總需求。下文選取考慮高峰小時(shí)系數(shù)后得到的具有101次充電需求的場(chǎng)景介紹模型的充電需求和應(yīng)用結(jié)果,其中圖2中路段的寬度表示了需充電的交通流量在路段上的分布情況,圖3顯示了101次充電需求在OD之間的空間分布情況。4.2tslm模型分析TSLM受到多種時(shí)間約束,傳統(tǒng)整數(shù)規(guī)劃優(yōu)化方法無法再現(xiàn)和解決其內(nèi)在的動(dòng)態(tài)影響過程,因此本研究采用微觀仿真方法驗(yàn)證模型的有效性。由于求解過程較為復(fù)雜,且復(fù)雜度隨著網(wǎng)絡(luò)的擴(kuò)大和充電站數(shù)目的增多而增大,本文僅驗(yàn)證充電站的數(shù)量為2,且各充電站充電樁個(gè)數(shù)均為25時(shí)的優(yōu)化結(jié)果。通過MapInfo軟件平臺(tái)建立路網(wǎng)拓?fù)浣Y(jié)構(gòu),應(yīng)用MapBasic語(yǔ)言開發(fā)了車輛在各備選站點(diǎn)的決策模型,以及整體系統(tǒng)優(yōu)化模型。為便于比較不同組合之間的差異,本研究采用了窮舉法,分別計(jì)算全部300個(gè)可能選址組合的等待時(shí)間和行駛時(shí)間,從中找出出行總時(shí)間最小的組合作為充電站的最優(yōu)位置,總時(shí)間最小的前10種組合見表1。算例路網(wǎng)上2個(gè)充電站的最優(yōu)位置分別位于點(diǎn)14和24,可以滿足全部101次充電需求,需要總等待時(shí)間654分鐘,總出行時(shí)間7380分鐘(僅包括等待時(shí)間和路段行駛時(shí)間,不包括充電時(shí)間),其中與最短路徑相比繞行了405分鐘,占最短路徑行駛總時(shí)間的6.4%。從節(jié)約出行能源的角度來看,點(diǎn)14和24組合的繞行時(shí)間也較低,是次優(yōu)選擇(僅比點(diǎn)14和2組合多9分鐘,遠(yuǎn)遠(yuǎn)低于其他選址組合)。此外,總出行時(shí)間最小的前10種組合幾乎全部包含了節(jié)點(diǎn)24,統(tǒng)計(jì)表明以節(jié)點(diǎn)24為出行起點(diǎn)或出行終點(diǎn)的充電需求約占了全部需求的25%。采用目前廣泛應(yīng)用的FCLM模型進(jìn)行比較(表2),通過貪婪算法得到了2組相同優(yōu)化目標(biāo)的充電站最優(yōu)位置組和,分別為點(diǎn)14和13,以及點(diǎn)14和19,服務(wù)的總需求數(shù)均為97次,總行駛時(shí)間均為6321分鐘(未考慮排隊(duì)等待時(shí)間)。FCLM模型無法提供更多的信息來判斷哪個(gè)組合更優(yōu),而且無法提供全部101次充電服務(wù)。由于FCLM沒有考慮等待時(shí)間,TSLM允許繞行,因此TSLM服務(wù)的車流量和總時(shí)間均大于FCLM的結(jié)果在意料之中。通過比較可知,TSLM和FCLM的應(yīng)用結(jié)果均包含了節(jié)點(diǎn)14,這也在一定程度上表明了兩模型的相似之處。FCLM模型的優(yōu)化目標(biāo)是布局給定數(shù)目的燃料供應(yīng)站,使得通過供應(yīng)站至少一次的車流量總和最大,并且假設(shè)任何一條路徑上只要存在一處供應(yīng)站便認(rèn)為該路徑上的交通流量獲得了服務(wù)。因此模型的求解通常采用貪婪算法,首先將站點(diǎn)設(shè)在交通流量最大的節(jié)點(diǎn),同時(shí)去掉所有已獲得服務(wù)的交通流量,然后依次增加其他能獲得最多剩余流量的節(jié)點(diǎn),以使總流量最大。由圖3可知,節(jié)點(diǎn)14是路網(wǎng)中交通流量最大的點(diǎn),因此,FCLM的兩組結(jié)果中均包含了節(jié)點(diǎn)14。對(duì)TSLM模型而言,其優(yōu)化目標(biāo)是總出行時(shí)間最小,并且允許繞道充電,當(dāng)車流量較多的節(jié)點(diǎn)上設(shè)有充電站時(shí)必然會(huì)減少排隊(duì)等待時(shí)間和繞行充電時(shí)間,因此路網(wǎng)中車流量最多的節(jié)點(diǎn)14包含在了TSLM的模型結(jié)果中。由此可知,TSLM模型和流量需求模型FCLM均傾向于選取路網(wǎng)中交通流量最大的節(jié)點(diǎn)作為充電站點(diǎn)。上述討論結(jié)果反映了TSLM模型在實(shí)際應(yīng)用中的價(jià)值。相關(guān)研究表明,出行者樂意在比較熟悉的地方補(bǔ)充燃料,如家或工作場(chǎng)所附近;出行者更愿意在出行的起點(diǎn)或終點(diǎn)添加燃料,而不是在出行途中;同時(shí)出行者普遍在出行中順道添加燃料,以添加燃料為單一目的的出行非常少。TSLM模型有效結(jié)合了上述兩個(gè)模型的優(yōu)勢(shì),可以使充電站的布局更好地?cái)M合人們?cè)诔鲂羞^程中的充電需求。此外,本文建立的TSLM模型具有兩個(gè)顯著特點(diǎn):(1)重新定義了出行路徑的選擇機(jī)制,而非最短路徑,(2)在時(shí)間因素的約束下增加了充電選擇規(guī)則。為驗(yàn)證這兩點(diǎn)的合理性和有效性,首先對(duì)TSLM模型增加最短路徑的限制,同時(shí)保持其他條件不變,則優(yōu)化結(jié)果的充電站位置和得到服務(wù)的車輛數(shù)與FCLM模型相同,但等待時(shí)間分別為1274(14&13)和1131分鐘(14&19),均遠(yuǎn)大于TSLM模型(654分鐘),同時(shí)總時(shí)間7595和7452均大于TSLM的7380分鐘(表2)。這一結(jié)果表明如果將人們的出行限制在最短路徑上,起迄點(diǎn)間的路段行駛時(shí)間雖然最短,但因排隊(duì)引起的等待時(shí)間將導(dǎo)致整個(gè)出行時(shí)間增加。因此TSLM模型緩解了傳統(tǒng)模型最短路徑假設(shè)而獲得了更優(yōu)的結(jié)果,允許繞行充電的假設(shè)在增加服務(wù)流量的同時(shí)減少了總時(shí)間。進(jìn)一步考察TSLM模型制定的充電規(guī)則的合理性,通過將TSLM模型增加最短路徑限制,同時(shí)去掉充電規(guī)則,即認(rèn)為車輛到達(dá)最短路徑上的充電站時(shí)直接選擇在此站點(diǎn)充電,而不論該站點(diǎn)當(dāng)前時(shí)刻的排隊(duì)情況如何。最終得到的最優(yōu)位置為14和13以及14和19,其等待時(shí)間分別為1449和1314分鐘,均大于有充電規(guī)則時(shí)TSLM模型的等待時(shí)間(表2)。因此,可以認(rèn)為TSLM模型的充電規(guī)則確保了系統(tǒng)最優(yōu),同時(shí)上述結(jié)果證明了14和19節(jié)點(diǎn)的充電組合略優(yōu)于14和13節(jié)點(diǎn)充電組合,而FCLM無法給出判斷依據(jù)。5出行模型的研究本文強(qiáng)調(diào)了較長(zhǎng)充電時(shí)間和充電站有限容量的矛盾,從出發(fā)時(shí)刻分布、出發(fā)時(shí)剩余電量、充