一.introduction

理想的充電基礎(chǔ)設(shè)施規(guī)劃應(yīng)該有以下兩點(diǎn)特點(diǎn)
（i）確保普遍覆蓋，以便電動(dòng)車(chē)（EV）駕駛員可以達(dá)到盡可能多的POI（他們感興趣的地方，或者說(shuō)司機(jī)要去的地方）
（ii）在每個(gè)充電站提供足夠數(shù)量的充電器，因?yàn)楸镜爻潆娦枨罂赡軙?huì)在不同的POI發(fā)生顯著變化。

EV平臺(tái)的主要問(wèn)題就是在有限的預(yù)算中如何選擇充電站的位置和合適的充電器的數(shù)目以滿(mǎn)足盡可能多的充電的需求。

先前的工作：

之前的很多研究的前提是為政府做的城市規(guī)劃，政府的基礎(chǔ)設(shè)施主要是為了滿(mǎn)足市民的充電需求。然而一方面公司沒(méi)有足夠的資源和預(yù)算去滿(mǎn)足所有的需求，另一方面，產(chǎn)生最大利潤(rùn)的規(guī)劃可能不一定涵蓋所有的充電需求。還有一些工作集中于最大化滿(mǎn)足區(qū)域不同粗粒度的需求。

本文為EV-共享平臺(tái)提出了EVCP問(wèn)題

本文的貢獻(xiàn)contributions：

• 格式化EVCP問(wèn)題，優(yōu)化EV充電器的分布來(lái)最大化POI覆蓋率和本地充電需求的平衡函數(shù)。并且證明了EVCP問(wèn)題是NP-hard
• 分析了EVCP問(wèn)題的子模塊，并且設(shè)計(jì)了一個(gè)競(jìng)爭(zhēng)率為1-1/e其時(shí)間復(fù)雜度為O(M**2n)的近似算法。m為充電站的數(shù)目，n為POI的數(shù)目。
• 在真實(shí)的數(shù)據(jù)集上做擴(kuò)展實(shí)驗(yàn)。

二.問(wèn)題格式化

2.1前提

定義2.1 道路網(wǎng)絡(luò)：

道路網(wǎng)路是一個(gè)無(wú)向圖G = (V , E)，V中的每個(gè)頂點(diǎn)是一個(gè)POI 或者一個(gè)充電站候選地點(diǎn)wj 。其中POI 中vi ∈ {v1,v2, · · · ,vn }，n為POI的數(shù)目候選地點(diǎn) wj ∈ W = {w1,w2, · · · ,wm },m為候選地點(diǎn)的數(shù)目。每條邊都要一個(gè)代表兩個(gè)頂點(diǎn)之間距離的權(quán)值。

定義2.2 候選站（Candidate Station）：

cj = (wj,dj,rj )，wj為V中的候選地點(diǎn)，代表cj的位置；dj表示cj的本地充電需求 量；rj表示POI距離cj不超過(guò)rj的時(shí)候可以被cj覆蓋，即rj表示的為cj覆蓋的范圍。c1 =c2表示w1 = w2即表示位置重合

估計(jì)候選站cj的本地充電需求dj不是重點(diǎn)。 一種簡(jiǎn)單實(shí)用的方法是將返回候選站的EV數(shù)量用作粗略估計(jì)。 因此，我們假設(shè)dj在我們的論文中是一個(gè)非負(fù)整數(shù)

定義2.3 選擇selection

sj = (cj，nj)表示將nj個(gè)充電器部署到候選站cj中。果兩個(gè)選擇的位置重合的cj1 =cj2，那么說(shuō)明sj1和sj2是同一個(gè)。

定義2.4 EV充電器規(guī)劃（EV Charger Plan）

是選擇selection的集合。給定一組候選站C，其中每個(gè)候選站cj都只出現(xiàn)在S的一個(gè)選擇中。, S = {sj |sj = (cj,nj ),nj ∈ Z?, j = 1, 2, · · · ,m}
定義S的size為S中所有EV充電器的數(shù)目

2.2 滿(mǎn)足充電需求的獎(jiǎng)勵(lì)：

1. POI覆蓋范圍的獎(jiǎng)勵(lì)。
   如果POI位于一個(gè)擁有至少一個(gè)充電器的selection 的候選站的覆蓋范圍之內(nèi)，那么這個(gè)POI被覆蓋了。P（sj）表示被selection sj 覆蓋的POI節(jié)點(diǎn)集，P（S)表示被被EV充電器規(guī)劃 S 覆蓋的POI節(jié)點(diǎn)的集合，

   
   

   被S覆蓋的POI節(jié)點(diǎn)總數(shù)目作為S的POI覆蓋范圍的獎(jiǎng)勵(lì)。即獎(jiǎng)勵(lì)為覆蓋的POI的個(gè)數(shù)。
   Rc (S) = |P(S)|

2. 本地充電需求的獎(jiǎng)勵(lì)。
   用u表示單個(gè)充電器在一段時(shí)間內(nèi)（如一周）可以滿(mǎn)足的本地充電需求的比率。
   那么selection sj的本地充電需求的數(shù)目是
   Rd (sj ) = min(dj,u · nj ).即為sj的需求量和sj能提供的充電的次數(shù)的最小值。
   plan 規(guī)劃S可以從所有選擇的充電站的本地充電需求獲得的獎(jiǎng)勵(lì)為：

   
   

2.3.問(wèn)題聲明

定義2.5 EVCP問(wèn)題

給定道路網(wǎng)絡(luò)G =（V，E），候選站集合C，一個(gè)充電器能滿(mǎn)足的本地充電需求的比率u,可調(diào)參數(shù)α和充電器總數(shù)的預(yù)算B，EVCP問(wèn)題 找到一個(gè)大小不超過(guò)B的計(jì)劃S，使總獎(jiǎng)勵(lì)R（S）為：

與決定是否在每個(gè)候選地點(diǎn)建站的傳統(tǒng)設(shè)施位置問(wèn)題不同，EVCP進(jìn)一步考慮了每個(gè)站的充電器數(shù)量以及當(dāng)?shù)爻潆娦枨蟮臐M(mǎn)意度

2.4EVCP問(wèn)題的NP-難分析

定理2.7：EVCP問(wèn)題時(shí)NP-難問(wèn)題
該問(wèn)題可以轉(zhuǎn)化為求決策最大覆蓋問(wèn)題，決策最大覆蓋問(wèn)題是一個(gè)NP-hard問(wèn)題

三.方法

3.1 基于充電器的貪婪算法

sj+表示在同一候選站中比sj增加一個(gè)充電器。

S+j表示在規(guī)劃S中的cj中增加一個(gè)充電器之后的EV充電器規(guī)劃。

同理增加的POI獎(jiǎng)勵(lì)和增加的當(dāng)?shù)匦枨螵?jiǎng)勵(lì)為：

3.2算法分析

CG算法的競(jìng)爭(zhēng)比為1-1/e

3.3加速技術(shù)

3.3.1 observation：

• 在規(guī)劃S上向nj≥1的站cj添加一個(gè)充電器之后，任何站的POI覆蓋的增加的獎(jiǎng)勵(lì)保持不變。即如果S上的一個(gè)站已經(jīng)有充電器了，那么他覆蓋的POI就不會(huì)變了。

  
  
  
  

• 在計(jì)劃S上向充電站cj添加一個(gè)充電器之后，任何其他站的本地充電需求的增加的獎(jiǎng)勵(lì)保持不變。即在S上的一個(gè)充電站加充電器，并不會(huì)增加或者減少其他站需求的滿(mǎn)足。

  
  

其中cj本地的充電器需求獎(jiǎng)勵(lì)的增加計(jì)算方式如下：

而其他站的增加量不變。

對(duì)于每一個(gè)充電站cj，可以最多部署

個(gè)充電器。

3.2.2偽代碼

3.2.3時(shí)間復(fù)雜度分析：

因?yàn)閘ine5最多可能執(zhí)行三次，一次為nj從0到1，第二次為1到 [dj/u ]的最小正整數(shù)，第三次為 [dj/u ]到 [dj/u ]+1.所以5~15行最多可能執(zhí)行3m次,即O（m)。計(jì)算line5的時(shí)間復(fù)雜度為O(m) 所以line5的總的時(shí)間復(fù)雜度為O( M² ) .第十行的時(shí)間復(fù)雜度為O(m²n)所以該行數(shù)的時(shí)間復(fù)雜度為O(m²n)。則總的時(shí)間復(fù)雜度為：O(m²n)

四.實(shí)驗(yàn)結(jié)果

基線(xiàn)算法：將EVCP問(wèn)題表示為整數(shù)規(guī)劃問(wèn)題，然后使用簡(jiǎn)單分支邊界約束的方法[16]來(lái)近似實(shí)現(xiàn)解決方案。
fast-GG的結(jié)果和GG的相同，但是運(yùn)行速度要快很多。

五.相關(guān)工作

1. 充電需求作為約束：
   i)本文的目標(biāo)是為EV共享平臺(tái)提供一個(gè)EV充電計(jì)劃而不是為城市規(guī)劃。目標(biāo)是通過(guò)有限的預(yù)算最大限度地滿(mǎn)足充電求，以實(shí)現(xiàn)proft。
   ii) 之前的很多研究不僅優(yōu)化了充電器的部署，而且還優(yōu)化了充電需求的變化，本文工作對(duì)EV駕駛員的運(yùn)動(dòng)沒(méi)有任何假設(shè)或要求
2. 充電需求作為目標(biāo)：
   我們的工作與[4]不同，考慮了每個(gè)充電站的覆蓋范圍和本地需求。 與[6]和[9]相比，優(yōu)化了不同地區(qū)的充電器部署，本文通過(guò)為每個(gè)地點(diǎn)規(guī)劃充電器部署來(lái)實(shí)現(xiàn)細(xì)化。 提供具有理論保證的解決方案。

六 .思考

這篇文章整體是一個(gè)使用貪婪策略的近似算法，每次選取能帶來(lái)最大利益的充電站加入充電器。而在優(yōu)化的時(shí)候考慮到只要有一個(gè)充電站有充電器那么司機(jī)能到達(dá)的地點(diǎn)范圍就不會(huì)變了，也就是POI的覆蓋就不會(huì)變了。而且在某一個(gè)充電站增加充電器，不會(huì)給別的充電站帶來(lái)獎(jiǎng)勵(lì)，以此來(lái)減少時(shí)間復(fù)雜度。
這個(gè)近似算法的競(jìng)爭(zhēng)比算出來(lái)有點(diǎn)不明白。后續(xù)再 寫(xiě)一篇來(lái)說(shuō)。

七 參考文獻(xiàn)

Demand-Aware Charger Planning for Electric Vehicle Sharing Bowen Du ，Yongxin Tong?，Zimu Zhou，Qian Tao，Wenjun Zhou