基于K-means算法的电动汽车充电站在线能量管理

王琛焱， 徐珑婷

(东华大学 信息科学与技术学院， 上海 201620)

社会经济发展所引发的交通危机和能源危机使得消费需求和能源有限性之间的矛盾日益增长。电动汽车(electric vehicles，EV)[1-2]因以清洁可再生能源为燃料，在交通运输领域得到越来越广泛的应用[3]，但在行驶过程中电动汽车存在电量耗尽的风险。

目前已有许多学者针对电动汽车的电量供给问题以及充分利用可再生资源进行发电的问题进行研究。Huang等[4]研究指出，利用建筑物和电动汽车中电池的能量共享可提高电动汽车充电时的协调控制能力。Chellaswamy等[5]提出一种基于可再生能源的电动汽车充电机制，并将可再生能源应用于电动汽车的自动充电。Han等[6]提出一种公寓级电动汽车充电协调方案，降低了电动汽车的峰值负荷，并在保证公寓级电网稳定性的同时实现收费的最小化。Limmer[7]研究指出，时变定价有利于激发电动汽车用户的潜在灵活性，反过来又促进了未来电动汽车和可再生能源资源与电网的整合。Prajapati等[8]通过减少场景数，以最小化发电成本、重新安排成本和电动汽车成本为目标对可再生能源联合电力系统进行拥塞管理，提出的拥堵管理问题考虑了一天中风能、太阳能、电动汽车数量和负荷状况的不确定性。Alhelou等[9]提出一种储能系统与电动汽车的发电技术相结合的方法，为电力系统提供了更大的灵活性。

上述研究倾向于从内部增强电力系统的可靠性，以提升能量的利用率和充电负荷，较少探讨完整的充电方案。本文提出一种电动汽车充电站系统结构，该系统中充电站的电量来源于风能发电站及电网，太阳能为电动汽车直接提供电力。基于该系统结构模型，考虑在电价低的时刻买入电力，从而使系统充电成本趋于最小化，提出一种在线能量管理算法。基于电价、风能和太阳能的随机统计信息，首先采用遗传算法解决期望成本最小化的随机规划问题，再通过K-means聚类算法分析所有充电策略，以实现最小化电价的目标。

1 电动汽车充电站系统模型

1.1 模型概述

根据电动汽车的充电需求，构建电动汽车电池充电模型与充电站能量供给模型，电动汽车充电站系统的结构模型如图1所示。通过风能发电和电网供电为充电站供能，再将获得的电能供给电动汽车；同时，在电动汽车上配备太阳能电池，进行太阳能充电，以确保电动汽车电量的充足。t表示时隙，t=1,2,…,T。1辆电动汽车需要在有限的T个时隙内充满电。由于电价以及风能和太阳能随机变化，充电站可根据这些信息调整充电量以降低充电站向电网购买电力的成本。图1中：QS(t)为电动汽车电池组在第t个时隙内利用太阳能发电获得的电量；QC(t)为充电站第t个时隙给电动汽车充入的电量；QW(t)为第t个时隙充电站从风能发电站获取的电量；QG(t)为充电站在第t个时隙内从电网获取的电能。

图1 电动汽车充电站系统结构

1.2 充电站能量供给模型

充电站能量供给模型中，电动汽车充电站与本地的风能发电厂相连。由于风力发电是不连续和不规则的，式(1)中的QW(t)是一个随机变量，满足独立同分布。

0≤QW(t)≤maxQW

(1)

由于风电场无法保证所有时隙的电能供给，因此该充电站可从电网购买电力。通常情况下，电动汽车所需的电能大于等于风能发电供应的电能，当风能能够完全保证供给时，充电站在t个时隙内从电网获取的电能QG=0。而充电站从电网购买的电量是有限的，最大购买电量为maxQG，约束表达式为

0≤QG(t)≤maxQG

(2)

风能是绿色能源，不存在购买成本，但是当可再生能源不足以满足用户需求时，充电站需要从电网获取电量，此过程中会产生购买成本。CG(t)为充电站从电网获取电能的电价，由于电价是随机变化的，因此CG(t)是一个独立同分布的随机变量。充电站在每个时隙开始获取当前时隙的电价信息并决定购买电量与电动汽车的充电电量。

1.3 电动汽车充电模型

日益增加的电动汽车分布在城市的各个角落，因此对能源的需求越来越大。为满足需求的同时充分利用可再生资源，在电动汽车上配置太阳能充电板，将太阳能转化为电能从而为电动汽车供能。太阳能充电板发电存在最大值maxQS，约束表达式为

0≤QS(t)≤maxQS

(3)

在获取太阳能的同时，电动汽车从充电站获取电量。充电站第t个时隙给电动汽车充入电量的最大充电量为maxQC。QC(t)的不等式约束条件如式(4)所示，该约束条件保证了充电量为正值且不会超出最大充电量限制。

0≤QC(t)≤maxQC

(4)

电动汽车在充电站充电时，电动汽车相当于负载。当电动汽车停留在充电站时，设定电动汽车的电池需要在t=1～T内完全充满。因此，电池的电量等于t=1～T时各个时隙内充电量的求和与太阳能的总电量，建立如式(5)所示的约束表达式

(5)

式中：B为电池电量。

1.4 问题建立

根据充电站能源供给模型和电动汽车充电模型，充电站在每个时隙内从风电场与主电网获得电力并将能量供给电动汽车，建立如式(6)所示的供需平衡约束条件。该约束条件保证了每个时隙充电站的供应量和需求量保持相同。此处假设在传输过程中电量未发生损耗。

QW(t)+QG(t)=QC(t)

(6)

通常可再生能源发电的边际成本被认为是零，充电站的成本即是从电网购买电力的成本。用C(t)表示t个时隙充电站成本，即从电网购入的单位买入电价和购入电量的乘积，约束表达式如式(7)所示。

C(t)=CG(t)QG(t)

(7)

充电站可以根据不同时刻的电价和可再生能源发电量调整电动汽车的充电量，并且与电动汽车利用太阳能发电搭配作用以充分利用可再生能源。图 1所示的电动汽车充电站系统旨在满足电动汽车充电需求的同时最大程度降低运营平均成本。因此，平均成本最小化问题可表达为式(8)中的优化问题P1。

(8)

该问题的目标是求解所有T的成本函数期望的时间平均值最小值。若充电过程中可以知道所有时隙的信息，则该问题为一个典型的线性规划问题，求解的结果即为每个时隙充电站需要购买的电量以及该时隙的充电量。因此，试验首先假设将来所有的信息是可以获取的，可采用遗传算法搜索优化问题P1的全局最优解。

2 基于遗传算法的离线算法

2.1 算法概述

假设从t=1～T所有电价和可再生能源发电量是已知的。当T很大时，直接求解P1会带来很高的计算复杂度。为减少计算量，利用遗传算法(genetic algorithm，GA)搜索问题的全局最优解。

遗传算法[10-11]是一种自适应全局优化搜索算法，本质是一种并行、高效、全局搜索的方法，遗传算法使用群体搜索技术，用种群代表一组问题解，通过对当前种群施加选择、交叉和变异等一系列遗传操作来产生新一代的种群，逐步使种群进化到包含近似最优解的状态。基于遗传算法，提出充电站电力管理离线算法求解目标函数的全局最优解，得到最优解样本集合。

2.2 算法设计

2.2.1 编码方式

遗传算法采用浮点数编码，即直接采取变量的真实值进行运算。由于价格和能量都是连续变量，采取浮点数编码有利于系统精确收敛到最小值，因此应用连续值参与适应度函数的计算。

2.2.2 适应度函数

用来对种群中个体的适应性进行度量的函数即为适应度函数。研究中的个体是指充电策略，度量的适应性是充电站的运营成本。适应度函数的构建选择用轮盘赌，需要寻找能映射到非负空间的映射。式(8)的目标优化问题P1是一个非负函数，设计的适应度函数基于越高的适应度代表越小的成本原则，因此适应度函数定义如下：

(9)

式中：Fi为个体适应度函数；fi为目标函数值；E为最大目标函数估计值。

2.2.3 遗传算子

遗传算子分为选择算子、交叉算子和变异算子。选用轮盘赌确定选择算子，用pi(x)表示选择概率，如式(10)所示。

(10)

2.2.4 离线算法设计

算法中假设所有的信息包括未来的电价、风能和太阳能发电量已知，因此该算法是一个离线算法。在随机产生初始种群后，通过选择、交叉、变异操作后可以得到新种群。经过计算新种群的适应度函数可以判断算法达到最优解，重复这些步骤，最终设计出基于遗传算法的离线全局最优解搜索方法。算法流程如下：

算法1基于遗传算法的离线充电管理算法

(1)随机生成M个个体初始化群体。

(2)根据式(9)计算个体适应度。

(3)根据式(10)选择下一代。

(4)执行交叉运算，将变异算子作用于群体。

(5)当种群遗传数小于最大进化代数时，循环往复步骤(2)～(4)；当种群遗传数大于等于最大进化代数时，将具有最大适应度的个体作为最优解输出，即可获得使模型成本最小的解。

为查找P1的全局最优解，遗传算法需要所有时隙的系统信息，但是实际电价、太阳能及风能发电量是随机分布的，电动汽车无法在每个时隙开始获得随机变化的信息。因此，提出仅依赖当前信息的充电策略集，该策略集有助于设计一种在线算法来控制充电站的充电量输出并最小化系统成本。

3 基于K-means聚类算法的在线算法

采用基于K-means[12]的聚类算法对遗传算法获得的结果进行聚类分析，得到不同价格区间的电动汽车充电策略，最后提出一种基于电价的在线能量管理算法。

3.1 方法概述

K-means聚类算法使用距离描述相似度。现有两个样本x1和x2，两者之间的相似度d(x1,x2)如式(11)所示。

(11)

式中：N为样本的维度。

若样本有K个分类，用Mk表示第k个聚类中心，k=1,2,…,K。先在样本中选择K个点作为质心，然后计算其他点与聚类中心之间的相似度，并将其分成K个集群，用ck表示。最后，根据式(12)重新计算新的聚类中心。

(12)

式中：|ck|表示集合ck中的元素个数。

在此过程中，K-means聚类算法不断重新分类和更新质心的坐标，并在迭代达到最大限制或目标函数小于阈值时结束。目标函数为

(13)

3.2 在线算法设计

将每个样本定义为所有遗传算法得到的第t个时隙下电价与充电量的组合，表示为

X={xt|xt|=[CG(t),QG(t)],1≤t≤T}

(14)

根据上述分析，提出基于K-means聚类算法的在线能量管理算法，算法流程如下：

算法2基于K-means算法的在线能量管理算法

(1)根据式(14)初始化数据样本，得到K个聚类中心；

(2)根据式(11)计算样本间的距离；

(3)当低于最大迭代次数时，利用式(12)计算新的聚类中心；

(4)达到最大迭代次数时迭代结束，获取并保存成本最低的充电策略Ψ*。

根据在线能量管理算法得到的成本最低的充电策略Ψ*，可知第t个时隙从电网获取电量QG(t)和充电站电动汽车充入的电量QC(t)。

4 仿真结果与分析

4.1 参数设置

仿真使用的电价轨迹和风能轨迹如图2和3所示。电价为0.002 2～0.061 2元/(kW·h)，平均值为0.024 2元/(kW·h)；风能为0～0.587 1 kW·h，平均值为0.25 kW·h;太阳能随机分布在[0.054 7，0.267 5] kW·h内，平均值为0.124 3 kW·h。由图3可以看出，风能是断断续续且不确定的。试验中，将每个时隙设置为15 min。1个充电循环的时间长度T=32，这意味着电动汽车必须在8 h内充满电。电动汽车的电池容量为40 kW·h。此外，设定maxQG=100 kW·h，maxQC=1.75 kW·h。

图2 电价随时间的变化曲线

图3 风能发电量随时间的变化曲线

仿真过程：首先，假设电动汽车在t=1时开始充电，在t=32时停止充电；然后，让电动汽车在t=2时开始充电，并在t=33时停止充电；依此类推。因此，试验总共对系统进行了368次仿真，并使用了所有400个时隙的数据。

4.2 评价方法

采用式(8)所示成本函数期望的时间平均值来评估算法，用平均成本表示成本函数期望的时间平均值。为评估基于K-means在线能量管理算法的平均成本，将其与每个时隙充入固定电量的平均成本、基于遗传算法离线能量管理算法的平均成本进行比较。用“平均算法”表示在每个时隙充入固定电量的充电策略；用“GA离线算法”表示基于遗传算法的离线能量管理算法；用“K-means在线算法”表示基于K-means的在线能量管理算法。

4.3 仿真结果

平均算法、GA离线算法和K-means在线算法的平均成本如图4所示。由图4可知，仿真显示K-means在线算法在t>30时实现从波动到收敛稳定，表明基于K-means在线算法的电动汽车充电站系统在长期运行时具有稳定性和可实施性。第4.1节提及“使用了所有400个时隙的数据，进行了368次仿真”，因此，GA离线算法和K-means在线算法都有368个仿真结果；而平均算法的仿真结果个数和时隙个数一致，为400。GA离线算法和K-means在线算法的充电站平均成本在t>30时都低于平均算法控制下的平均成本；在时隙t=30～130时间段，GA离线算法优于K-means在线算法；但在t=130～330时间段，这两种算法的结果几乎没有差异；而在t>330时间段，K-means在线算法获得比GA离线算法更优的平均成本，且仿真表明K-means在线算法收敛速度更快。

图4 不同算法下的平均成本随时间的变化曲线对比

为了更加直观展示基于K-means聚类的能量管理在线算法，给出如图5所示的聚类结果。其中遗传算法的所有样本被分为6类，每种颜色代表不同的类别，“×”代表最终迭代得到的质心。通过集合，K-means在线算法可以根据实时电价得到充电策略，并最小化成本。

图5 K-means算法的聚类结果

电动汽车电量随时间变化的曲线如图6所示。由图6(a)可知，GA离线算法与K-means在线算法的充电量随时隙的变化情况相似，电池电量最终趋于40 kW·h，证实了这两种算法在实践中的有效性。由图6(b)和(c)可知，时隙t=12～18时，GA离线算法停止购买电力，这是因为在离线算法中已知所有电力价格，可以预知即将到来的更低价格，而K-means在线算法无法提前获取价格信息，因此在时隙t=12～18时继续根据电价购买相同电力。

图6 基于GA离线算法和K-means在线算法的不同时隙电动汽车电池充电情况

5 结 语

为满足日益增长的能源需求，构建以可再生能源发电和电网供电的电动汽车充电系统，可在满足电动汽车充电需求的同时最大程度地降低运营成本。对比电动汽车充电站能量管理的平均算法、GA离线算法、K-means在线算法，通过仿真试验验证了K-means在线算法的有效性。结果表明，基于K-means在线算法的能量管理可在未知电价的情况下控制成本，在实际应用中使充电系统更加稳定。