Iterative Double Auction Algorithm for Wireless Electric Vehicle Charging Market

图 1给出智能电网中电动汽车无线充电市场的示意图。汇集商管理一片区域内的无线充电设施，能够实时获取到区域内电动汽车的航线和充电需求信息^[4]，并在市场中购买电能来满足车的充电需求。分布式能源可以是可再生能源，也可以是火力发电，作为电能卖方。代理商作为拍卖师，跟买卖方交换信息，达到优化双方总效益的目的。考虑到电动汽车的快速移动性和航线的不确定性，该无线充电市场应该对电能进行预售，事先确定电能交易量和价格。如现在是5:55，市场对6:00-6:05时段进行电能预售(PJM电力市场中实时电能调度时间间隔是5 min^[7]）。电动汽车需要保证在该时段内始终与充电设施(动态或静态)连接，汇集商才会接受它的充电请求。不能保证这一点的其他电动汽车将不能参与此次电能预售，它们可以通过其他方式(如主电网)获得电能。

对某一个时段进行分析。用$i \in [A]$标记汇集商，其中集合[A]定义为$[A] \buildrel \Delta \over = \{ 1,2, \cdots ,A\} $，表示汇集商的集合。用$[{V_i}] \buildrel \Delta \over = \{ 1,2, \cdots ,{V_i}\} $表示汇集商i中允许充电的电动汽车的集合。用$d_{ik}^{\min }$和$d_{ik}^{\max }$分别表示电动汽车$k \in [{V_i}]$的充电需求的最小值和最大值。汇集商i必须满足$ \ge d_{ik}^{\min }$，否则电动汽车将有可能由于电力不足而无法行驶。$d_{ik}^{\max }$由每辆车的最大充电功率决定。用$j \in [G]$标记分布式能源，$[G] \buildrel \Delta \over = \{ 1,2, \cdots ,G\} $表示分布式能源的集合。用d_ij表示汇集商i对能源j的电能需求量，故汇集商i的需求向量表示为${\mathit{\boldsymbol{d}}_i} \buildrel \Delta \over = \{ {d_{ij}}|j \in [G]\} $，所有汇集商的需求表示为$\mathit{\boldsymbol{d}} \buildrel \Delta \over = \{ {\mathit{\boldsymbol{d}}_i}|i \in [A]\} $。汇集商i中电动汽车的满意度函数表示为：

式中，r_i为常数；ξ为电动汽车无线充电效率。由式(1)可知，只有当汇集商i所提供的充电电量大于电动汽车最小需求量时，满意度才能得到提升。

用s_ij表示分布式能源j对汇集商i的电能供应量，故能源j的供应向量表示为${\mathit{\boldsymbol{s}}_j} \buildrel \Delta \over = \{ {s_{ij}}|i \in [A]\} $，所有能源的供应表示为$\mathit{\boldsymbol{s}} \buildrel \Delta \over = \{ {\mathit{\boldsymbol{s}}_j}|j \in [G]\} $ 。分布式能源j的成本函数^[4]表示为：

式中，c_{1, j}、c_{2, j}、c_{3, j}为常数，且c_{1, j}＞0。

汇集商和分布式能源之间是非合作的关系，且它们的目标往往是矛盾的。汇集商希望获得更多电能来提升电动汽车的满意度，而分布式能源却希望尽量减少发电成本。因此，它们需要一个代理商来协调电能分配。这里考虑代理商需要最大化双方的总效益，即社会福利(social welfare, SW)。通过求解下面的SW问题，可以得到最优的d^*和s^*：

式中， $s_j^{\max }$ 为分布式能源j的最大发电量。式(6)表示电能的供需平衡。SW问题是典型的约束优化问题，可以通过计算KKT(Karush-Kuhn-Tucker)条件求解，而且其目标函数是凹的，故可以得到全局最优解。对约束式(4)~式(6)进行松弛，SW问题的Lagrange函数表示为：

式中，$\mathit{\boldsymbol{\lambda }} \buildrel \Delta \over = \{ {\lambda _j}|j \in [G]\} $；$\mathit{\boldsymbol{\mu }} \buildrel \Delta \over = \{ {\mu _{ij}}|i \in [A],j \in [G]\} $； $\mathit{\boldsymbol{\alpha }} \buildrel \Delta \over = \{ {\alpha _i}|i \in [A]\} ;\mathit{\boldsymbol{\beta }} \buildrel \Delta \over = \{ {\beta _i}|i \in [A]\} $ 。SW问题的最优解满足如下KKT条件：

代理商在求解SW问题时，需要知道汇集商的满意度函数和分布式能源的成本函数。但由于隐私或欺骗等问题，代理商不一定能获得真实的函数信息。这时直接求解SW问题就变得不可行。

把双边拍卖机制应用到电动汽车充电市场中，汇集商(买方)和分布式能源(卖方)对电能进行出价，代理商(拍卖师)根据出价来确定电能交易量以及交易价格。这样可避免买卖方直接披露隐私信息。

用b_ij表示汇集商i对能源j的电能买入价(bid price)，故汇集商i出价向量表示为${\mathit{\boldsymbol{b}}_i} \buildrel \Delta \over = \{ {b_{ij}}|j \in [G]\} $，所有汇集商的出价表示为$\mathit{\boldsymbol{b}} \buildrel \Delta \over = \{ {\mathit{\boldsymbol{b}}_i}|i \in [A]\} $。汇集商i需要求解下面的买方(buyer, B)问题，从而确定最优的买入价为：

式中，P_i(b_i)为买方的支付函数，由拍卖师决定。

用a_ij表示分布式能源j对汇集商i的电能卖出价(ask price)，故分布式能源j的出价向量表示为${\mathit{\boldsymbol{a}}_j} \buildrel \Delta \over = \{ {a_{ij}}|i \in [A]\} $，所有分布式能源的出价表示为$\mathit{\boldsymbol{a}} \buildrel \Delta \over = \{ {\mathit{\boldsymbol{a}}_j}|j \in [G]\} $。分布式能源j需要求解下面的卖方(seller, S)问题，从而确定最优的卖出价为：

式中，R_j(a_j)为卖方的收益函数，由拍卖师决定。

汇集商和分布式能源把出价提交给代理商，代理商需要求解下面的拍卖师(auctioneer, A)问题^[8-9]，从而计算出电能的交易量为：

式(13)中目标函数的构建与买卖方(满意度和成本)函数的凹凸性有关。因为汇集商的满意度函数是凹的，故增添一个凹成分(对数运算)来获取其函数的凹特征。类似地，增添一个凸成分(平方运算)来获取分布式能源成本函数的凸特性。由式(13)可知，代理商求解A问题时只需要知道买卖方的出价。A问题与SW问题有同样的约束条件，且目标函数也是凹的，所以也可以通过计算KKT条件求解。A问题的Lagrange函数为：

A问题的最优解满足如下KKT条件：

为了使得A问题的最优解也是SW问题的最优解，需要保证它们的KKT条件是一致的。由式(9)、式(10)、式(15)、式(16)可得：

这意味着，当买方和卖方的出价分别满足式(17)和式(18)时，A问题的最优解就是SW问题的最优解。

代理商需要确定买方支付金额和卖方出售金额。买方支付函数和卖方收益函数分别表示为：

定理 1  由式(19)和式(20)给定的定价规则可以使得A问题的最优解与SW问题的最优解一致。

证明：由式(11)可知，汇集商的最优买入价应该满足：

由式(15)可得：

把式(19)和式(22)代入式(21)可得：

可见式(23)与式(17)一致。由式(12)可知，分布式能源的最优卖出价应该满足：

由式(16)可得：

把式(20)和式(25)代入式(24)可得：

可见式(26)与式(18)一致。

因此，由式(19)和式(20)给定的定价规则可以使得最优买入价满足式(17)，也使得最优卖出价满足式(18)。所以，代理商A问题的最优解与SW问题的最优解一致。证毕

由以上双边拍卖机制可知，汇集商和分布式能源分别求解B问题和S问题时，需要代理商提供的电能供需信息d和s；代理商求解A问题时，需要买卖方提交的出价信息b和a。因此，B、S、A问题的求解需要通过迭代的方式进行。迭代过程中，代理商与买卖方不断交换信息，直到拍卖结果不再改变。算法1给出迭代双边拍卖算法的具体步骤。

算法1：迭代双边拍卖算法

1) 初始化：d⁽⁰⁾, s⁽⁰⁾, λ⁽⁰⁾, μ⁽⁰⁾, ε；

2) t ←0；flag_conv ←0；

3) while flag_conv=0 do

4) t ←t+1；

5) 汇集商求解B问题，提交买入价b^(t)；

6) 分布式能源求解S问题，提交卖出价a^(t)；

7) 拍卖师求解A问题，得到d^(t)，s^(t)，并广播定价规则的参数λ^(t)，μ^(t)；

8) if $\left| {\frac{{b_{ij}^{(t)} - b_{ij}^{(t - 1)}}}{{b_{ij}^{(t)}}}} \right| ＜ \varepsilon $且 $\left| {\frac{{a_{ij}^{(t)} - a_{ij}^{(t - 1)}}}{{a_{ij}^{(t)}}}} \right| ＜ \varepsilon $ ， $\forall i \in [A],\forall j \in [G]$ then

9) flag_conv ←1；

10) end if

11) end while

12)输出： ${\mathit{\boldsymbol{d}}^*},{\mathit{\boldsymbol{s}}^*},{\mathit{\boldsymbol{\lambda }}^*},{\mathit{\boldsymbol{\mu }}^*},P({\mathit{\boldsymbol{b}}^*}),R({\mathit{\boldsymbol{a}}^*})$ 。

算法中，ε为一个极小的常数，用于判定算法收敛。

该算法的特点在于，把集中式的SW问题拆分成汇集商的B问题、分布式能源的S问题、代理商的A问题。它们分别独立求解自身的最优化问题，然后交换计算结果。这种机制更加适用于电动汽车充电市场，代理商无需知道买卖方的隐私信息(满意度函数和成本函数)，仅根据买卖方的出价就能使得A问题的解收敛至SW问题的解，从而优化双方总效益。

仿真场景基于文献[4]中的无线充电系统设计，其中汇集商能够实时获取车的航线信息并控制车的充电。仿真中，主要分析单个时段内算法的性能。为了便于分析，首先考虑A = 2和G = 2的情况，即两个汇集商和两个分布式能源。令V₁ = 300和V₂ = 200，即汇集商1和2分别有300和200辆电动汽车需要充电。对于$\forall i \in [A],\forall k \in [{V_i}],\forall j \in [G]$，有如下参数设置： $d_{ik}^{\max } = 1,d_{1k}^{\min } = 0.3,d_{2k}^{\min } = 0.4$ ， $s_1^{\max } = 500,s_2^{\max } = 600$ ，${r_1} = {r_2} = 500$， ${c_{1,1}} = 0.01,{c_{1,2}} = 0.02,{c_{2,j}} = {c_{3,j}} = 0$ ， $\xi = 0.8$ 。

图 2给出迭代双边拍卖算法的收敛性能。图 2a中虚线表示通过直接求解SW问题得到的总效益最优值，但这种方案需要买卖方的隐私信息。可见，本方双边拍卖算法的总效益在第5次迭代后可以稳定在最优值上，收敛速度快，且无需隐私信息。图 2b给出本文算法的电能需求量和供应量的收敛情况。因为约束条件式(6)，所以需求量与供应量相等。

接下来分析汇集商和分布式能源的数量对收敛速度的影响。参数设置如下，对于 $\forall i \in [A],\forall k \in ,\forall j \in [G]$ ，有 $d_{ik}^{\min } = [0.3,0.4]$ ， $s_j^{\max } = [500,600]$ ， ${c_{1,j}} = [0.01,0.02]$ ，即参数的取值为其区间内的均匀分布。其余参数设置与之前相同。仿真结果表明，本文算法的收敛迭代次数不会随着买卖方数量增加而增加。通常，第5次迭代后的总效益就收敛至最优值。但由于买卖方数量增加，代理商求解A问题的时间会增加。图 3给出总效益收敛至最优值所用的时间。

最后分析电动汽车数量对电能交易结果的影响。考虑两个汇集商和两个分布式能源的情况。设汇集商1和2分别最多可同时服务300和200辆电动汽车。电动汽车服务率等于当前服务车数与最大服务车数的比值。由图 4a可见，汇集商1在0.5服务率后购电成本大幅增长，此时其服务车数为300 ×0.5=150。汇集商2在0.7服务率后也有类似的增长，此时其服务车数为200×0.7=140。可见，当总充电车数大约为290后，分布式能源的发电成本将大大增加，使得汇集商购电成本也随之增加。图 4b表明，购电成本大幅增加后，汇集商会减少电能获取量的增量。图 4c中，总效益前半段上升的主要原因是电动汽车满意度的提升，而总效益后半段下降的原因主要来自于分布式能源发电成本的上升。

针对电动汽车无线充电市场，采用迭代双边拍卖算法进行电能供需匹配。汇集商和分布式能源按照自身效益最大化原则进行出价，代理商无需买卖方的隐私信息，仅根据他们的出价进行电能分配和定价。仿真结果表明，本文算法可以使得最终的买卖双方总效益收敛至最优值，而且有较快的收敛速度，能保证电动汽车无线充电市场中电能分配的高效性。