【论文笔记】Demand-Aware Charger Plann

一.introduction

理想的充电基础设施规划应该有以下两点特点
（i）确保普遍覆盖，以便电动车（EV）驾驶员可以达到尽可能多的POI（他们感兴趣的地方，或者说司机要去的地方）
（ii）在每个充电站提供足够数量的充电器，因为本地充电需求可能会在不同的POI发生显着变化。

EV平台的主要问题就是在有限的预算中如何选择充电站的位置和合适的充电器的数目以满足尽可能多的充电的需求。

先前的工作：

之前的很多研究的前提是为政府做的城市规划，政府的基础设施主要是为了满足市民的充电需求。然而一方面公司没有足够的资源和预算去满足所有的需求，另一方面，产生最大利润的规划可能不一定涵盖所有的充电需求。还有一些工作集中于最大化满足区域不同粗粒度的需求。

本文为EV-共享平台提出了EVCP问题

本文的贡献contributions：

• 格式化EVCP问题，优化EV充电器的分布来最大化POI覆盖率和本地充电需求的平衡函数。并且证明了EVCP问题是NP-hard
• 分析了EVCP问题的子模块，并且设计了一个竞争率为1-1/e其时间复杂度为O(M**2n)的近似算法。m为充电站的数目，n为POI的数目。
• 在真实的数据集上做扩展实验。

二.问题格式化

2.1前提

定义2.1 道路网络：

道路网路是一个无向图G = (V , E)，V中的每个顶点是一个POI 或者一个充电站候选地点wj 。其中POI 中vi ∈ {v1,v2, · · · ,vn }，n为POI的数目候选地点 wj ∈ W = {w1,w2, · · · ,wm },m为候选地点的数目。每条边都要一个代表两个顶点之间距离的权值。

定义2.2 候选站（Candidate Station）：

cj = (wj,dj,rj )，wj为V中的候选地点，代表cj的位置；dj表示cj的本地充电需求 量；rj表示POI距离cj不超过rj的时候可以被cj覆盖，即rj表示的为cj覆盖的范围。c1 =c2表示w1 = w2即表示位置重合

估计候选站cj的本地充电需求dj不是重点。 一种简单实用的方法是将返回候选站的EV数量用作粗略估计。 因此，我们假设dj在我们的论文中是一个非负整数

定义2.3 选择selection

sj = (cj，nj)表示将nj个充电器部署到候选站cj中。果两个选择的位置重合的cj1 =cj2，那么说明sj1和sj2是同一个。

定义2.4 EV充电器规划（EV Charger Plan）

是选择selection的集合。给定一组候选站C，其中每个候选站cj都只出现在S的一个选择中。, S = {sj |sj = (cj,nj ),nj ∈ Z∗, j = 1, 2, · · · ,m}
定义S的size为S中所有EV充电器的数目

2.2 满足充电需求的奖励：

1. POI覆盖范围的奖励。
   如果POI位于一个拥有至少一个充电器的selection 的候选站的覆盖范围之内，那么这个POI被覆盖了。P（sj）表示被selection sj 覆盖的POI节点集，P（S)表示被被EV充电器规划 S 覆盖的POI节点的集合，

   
   

   被S覆盖的POI节点总数目作为S的POI覆盖范围的奖励。即奖励为覆盖的POI的个数。
   Rc (S) = |P(S)|

2. 本地充电需求的奖励。
   用u表示单个充电器在一段时间内（如一周）可以满足的本地充电需求的比率。
   那么selection sj的本地充电需求的数目是
   Rd (sj ) = min(dj,u · nj ).即为sj的需求量和sj能提供的充电的次数的最小值。
   plan 规划S可以从所有选择的充电站的本地充电需求获得的奖励为：

   
   

2.3.问题声明

定义2.5 EVCP问题

给定道路网络G =（V，E），候选站集合C，一个充电器能满足的本地充电需求的比率u,可调参数α和充电器总数的预算B，EVCP问题 找到一个大小不超过B的计划S，使总奖励R（S）为：

与决定是否在每个候选地点建站的传统设施位置问题不同，EVCP进一步考虑了每个站的充电器数量以及当地充电需求的满意度

2.4EVCP问题的NP-难分析

定理2.7：EVCP问题时NP-难问题
该问题可以转化为求决策最大覆盖问题，决策最大覆盖问题是一个NP-hard问题

三.方法

3.1 基于充电器的贪婪算法

sj+表示在同一候选站中比sj增加一个充电器。

S+j表示在规划S中的cj中增加一个充电器之后的EV充电器规划。

ΔRj(S) 表示在规划S的候选站cj中增加一个充电器之后增加的奖励。

同理增加的POI奖励和增加的当地需求奖励为：

伪代码：
在每次迭代中，算法都贪婪的选择增大增长奖励的候选站，然后更新规划。直到最大增加奖励减少到0的时候，这个算法终止。

3.2算法分析

CG算法的竞争比为1-1/e

3.3加速技术

3.3.1 observation：

• 在规划S上向nj≥1的站cj添加一个充电器之后，任何站的POI覆盖的增加的奖励保持不变。即如果S上的一个站已经有充电器了，那么他覆盖的POI就不会变了。

  
  
  

• 在计划S上向充电站cj添加一个充电器之后，任何其他站的本地充电需求的增加的奖励保持不变。即在S上的一个充电站加充电器，并不会增加或者减少其他站需求的满足。

  
  

其中cj本地的充电器需求奖励的增加计算方式如下：

而其他站的增加量不变。

对于每一个充电站cj，可以最多部署

个充电器。

3.2.2伪代码

3.2.3时间复杂度分析：

因为line5最多可能执行三次，一次为nj从0到1，第二次为1到 [dj/u ]的最小正整数，第三次为 [dj/u ]到 [dj/u ]+1.所以5~15行最多可能执行3m次,即O（m)。计算line5的时间复杂度为O(m) 所以line5的总的时间复杂度为O( M² ) .第十行的时间复杂度为O(m²n)所以该行数的时间复杂度为O(m²n)。则总的时间复杂度为：O(m²n)

四.实验结果

基线算法：将EVCP问题表示为整数规划问题，然后使用简单分支边界约束的方法[16]来近似实现解决方案。
fast-GG的结果和GG的相同，但是运行速度要快很多。

五.相关工作

1. 充电需求作为约束：
   i)本文的目标是为EV共享平台提供一个EV充电计划而不是为城市规划。目标是通过有限的预算最大限度地满足充电求，以实现proft。
   ii) 之前的很多研究不仅优化了充电器的部署，而且还优化了充电需求的变化，本文工作对EV驾驶员的运动没有任何假设或要求
2. 充电需求作为目标：
   我们的工作与[4]不同，考虑了每个充电站的覆盖范围和本地需求。 与[6]和[9]相比，优化了不同地区的充电器部署，本文通过为每个地点规划充电器部署来实现细化。 提供具有理论保证的解决方案。

六 .思考

这篇文章整体是一个使用贪婪策略的近似算法，每次选取能带来最大利益的充电站加入充电器。而在优化的时候考虑到只要有一个充电站有充电器那么司机能到达的地点范围就不会变了，也就是POI的覆盖就不会变了。而且在某一个充电站增加充电器，不会给别的充电站带来奖励，以此来减少时间复杂度。
这个近似算法的竞争比算出来有点不明白。后续再 写一篇来说。

七 参考文献

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