小区居民电动汽车有序充电方法探究——基于启发式算法求解的混合整数规划

Study on the Orderly Charging Method of Residential Electric Vehicles —To Solve the Mixed Integer Programming Based on Heuristic Algorithm

摘要: 为探究小区居民电动汽车的最佳充电方式，本文对比分析了有序充电中连续充电与不连续充电两种模式。以最小化充电成本以及最大程度满足居民用户充电的需求量为目标函数，充电负荷等作为约束条件建立了连续与不连续充电的混合整数规划模型。根据设定情景采用蒙特卡罗模拟法模拟小区充电站1天内电动汽车的充电需求，并优化启发式算法中的贪心算法对模型进行求解。研究结果表明：与连续充电模式相比，不连续充电模式具有降低充电商经营成本、最大满足用户需求以及降低小区电网负荷的优点。

Abstract: In order to explore the best way of charging electric vehicles in residential areas, this paper compares and analyzes two modes of continuous charging and discontinuous charging in orderly charging. The mixed integer programming models of continuous and discontinuous charging was established with the objective function of minimizing the charging cost and maximizing the charging demand of residential users and the constraint conditions of charging load and so on. The Monte Carlo simulation method was used to simulate the charging demand of electric vehicles within one day of the charging station in the community according to the set scenario, and the greedy algorithm of the heuristic algorithm was optimized to solve the model. The results show that, compared with the continuous charging mode, the discontinuous charging mode has the advantages of reducing the operating cost of the charger, maximizing the demand of the user and reducing the load of the community grid.

1. 引言

近年来，为建设环境友好型社会，具有节约燃油能源、减少废气排放等作用的新能源汽车被大力推广，2020年11月，国务院办公厅印发《新能源汽车产业发展规划(2021~2035年)》，要求深入实施发展新能源汽车国家战略，推动中国新能源汽车产业高质量可持续发展，加快建设汽车强国 [1]。人们也积极响应这一号召，购买新能源汽车的需求日趋强烈，2022年4月19日，国务院新闻办公室举行新闻发布会，工信部运行监测协调局局长罗俊杰介绍，我国新能源汽车产业发展取得了积极成效，已经累计推广1033万辆，突破了一千万辆的大关，成为引领全球汽车产业电动化转型的一个重要力量。在新能源汽车中，应用最广泛的充电式电动汽车是一种可以通过外界电源充电的机动车。随着电动汽车产业的蓬勃发展，大规模集中式的充电站模式得到广泛应用，截至2021年4月，全国已累计建设充电站6.5万座、换电站644座，各类充电桩187万个，建成覆盖176个城市、超过5万公里的高速公路快充网络 [2]。因此在充电式电动汽车日益普及的今天，实现居民小区内优质高效的充电站控制策略不仅可以提高用户满意度，促进电动汽车的进一步推广，而且可以节约充电成本，充分利用资源。

文献 [3] 提出了一种价格与激励联合需求响应下电动汽车长时间尺度充放电调度策略，仿真结果表明，该篇所提调度策略能够在长时间宏观尺度上提升电动汽车聚合商净收益，减小负荷波动以及降低电动汽车调度成本。文献 [4] 提出考虑降损条件约束的电动汽车有序充电控制模型，实现符合电动汽车充电需求发展的可靠性控制。实验分析得知，该方法进行电动汽车降损有序充电控制的输出稳定性较高，增益较大，误差较小。文献 [5] 以电动汽车充放电电价、电动汽车充放电状态和充放电功率为决策变量，构建了以电动汽车充放电成本最小、电动汽车接入造成的网络损耗最小和节点电压偏差最小为优化目标的电动汽车充放电调度数学模型，结果表明，动态分时电价克服了传统峰谷分时电价下的弊端，能够根据电动汽车的动态特性来调整电价。所提调度策略融合了灵敏度分析方法，可大幅缩短调度过程中潮流计算的时间，并能有效降低电动汽车的充放电成本以及电动汽车接入对网络损耗和节点电压的影响。文献 [3] [4] [5] 从电路稳定和商家的成本与收益角度进行考虑，缺乏对需求端的兼顾。文献 [6] 首先搭建电动汽车充电模型，在MATLAB中采用蒙特卡洛法模拟电动汽车无序充电情况；其次，所提出的新的基于分时电价的电动汽车多目标有序充电控制策略，不仅可以有效地减小电网的峰谷差，还可以降低电动汽车用户的充电费用，充分验证了该策略的有效性与合理性，但该结果并未将对用户的充电需求满足纳入考虑范围内。

本文在已知未来一段时间内所有充电车辆到达和离开充电站的时间、到达和离开充电站时各车辆的电池荷电状态(即电动汽车当前电池容量占电池总容量的比值)等信息的基础上，根据小区居民充电的实际情景，用户出于方便与减少电池损耗的目的，一般在充电过程中不会更换充电机，因此本文建立了充电过程中不可更换充电机的数学模型，并同时考虑连续充电和不连续充电两种模式，适用于不同的应用情景。使用MATLAB调用启发式算法中的贪心算法，得到局部最优解，最终形成连续充电模式与不连续充电模式的对比，在实际应用中可以降低充电成本、满足用户需求并减少电网负荷。由此本文通过连续充电模型的建立以及其与不连续充电模型的对比，在已有研究上实现了创新与进一步完善。

本文的结构安排如下：首先对有序充电过程中所需的变量以及参数进行定义并规定衡量标准，包括序充电的目标与输入信息、基于分时电价的时间处理、决策矩阵的定义与用户充电程度的衡量。基于此建立有序充电中建立连续与不连续两种混合整数规划模型，选择利用启发式算法中的贪心算法思想对模型进行求解。在对模型求解过程中的对充电收益的衡量以及求解过程的处理两个关键问题进行说明后，根据参数设定的分布利用蒙特卡罗模拟法生成随机数作为实际场景中可能出现的情况，模型最终的结果以两种模型的成本、负荷等结果对比的形式来呈现。

2. 有序充电控制策略变量定义过程

2.1. 有序充电的目标与输入信息

作为小区内充电机设施的供应商，首要应最大可能满足小区内居民的电动汽车充电需求，然后根据合理安排使电费成本降低，利用向供电局所交电费与向居民用户收取的充电服务费之间的价差获得收益。基于此，本节同时考虑充电服务商与小区居民的充电需求，设计充电站有序充电策略。

首先假设小区内共有M台充电机，并且假设每台充电机充电过程中的充电功率恒定为P (单位为kW) [7]。有序充电的实施过程的关键是要记录电动汽车充电始末的状态数据：一旦居民将电动汽车停入充电机前，充电站的充电管理系统便会自动记录第n ( $n=1,2,\cdots ,N$ )辆电动汽车的电池总容量B_n (单位为kW∙h)，并准确生成进站时间t_n0、车辆电池的初始荷电状态C_n0的记录。将车停靠完毕，居民用户需要向充电站充电管理系统输入预计的第n辆电动汽车取车时间t_n1以及取车时期望的电池荷电状态C_n1。当充电站无法满足居民在特定时间段内的充电需求时，居民用户可以选择重新向充电管理系统输入充电需求信息，也可以默认服从系统调剂，系统将以最大程度满足或接近用户充电期望的原则，按照用户指定的取车时间安排充电计划。

2.2. 基于分时电价的时间处理

由于不同时间段对应的电价不同，需要将一天中的时段进行区分。由于电价具有不易波动、稳定性强的特性，因此本文的分时电价的制定借鉴了北京市电网峰谷分时销售电价表(夏季) [8]，下表1展示了充电站从电网的购电价格采用分时电价的具体数值形式：

Table 1. Time-of-use electricity price

表1. 分时电价

根据变压器对负荷预测的限制，将1天平均分成96个时间段，每个时间段的时长为T = 15 min [7]，由于记录居民用户的时间数据为时点，因此需要将其转换为分钟数以此来对应一天中的时段，定义第n辆电动汽车最早开始充电与最后允许充电的时间段分别为：

$T_{n,early}=\left[\frac{minute\left(t_{n0}\right)}{T}\right]+2$ (1)

$T_{n,late}=\left[\frac{minute\left(t_{n1}\right)}{T}\right]$ (2)

其中，用[x]表示不超过x的最大整数；minute (t)表示把时间转换为分钟数，例如当居民电动汽车在06:19到达小区充电机，则最早可以在06:30进行充电，根据公式(1)有 $T_{n,early}=\left[\left(6\times 60+30\right)/15\right]+2=27$，此时对应一天中第27个时段；同理，若用户设定的离开时间为13:10，可以充电时间最迟到13:00，转换为时间段即 $T_{n,late}=\left[\left(13\times 60\right)/15\right]=52$，允许充电时间段最迟为第52个时间段。

定义第i ( $i=1,2,\cdots ,I$ )个时间段的电网电价为P_i，基于分时电价来进行充电策略的安排，同样基于在满足居民用户充电需求的基础上，再利用不同时段的电价差异，合理安排充电计划，最终达到在尽量满足用户需求的前提下降低运营成本，实现有序充电控制的效果。

2.3. 决策矩阵的定义与用户充电程度的衡量

为表示电动汽车在某一时间段内的充电情况，定义0-1矩阵F_M×J×N表示N辆电动汽车充电决策矩阵，其元素 $f_{i,m}^n$ 定义如下：当第n辆电动汽车第i个时间段在充电机m充电时， $f_{i,m}^n=1$ ；否则 $f_{i,m}^n=0$。为了对不可更换充电机这一条件做出限制，定义0-1矩阵E_M×N表示车辆被分配到固定的充电机上充电的分配矩阵，其中的元素 $e_{n,m}$ 定义如下：当第n辆电动汽车被分配到充电机m充电时， $e_{n,m}=1$ ；否则 $e_{n,m}=0$。

居民使用充电机的体验感首要取决于要求的电量是否满足，把未能满足居民用户所要求的电量的缺失值部分定义为每辆电动汽车的不满意度，并采用S_n表示，由于S_n本质上是缺失值，因此定义S_n本身的值非负。但是在实际应用场景中，电量的缺失值的产生会受到很多因素的影响，从而形成了不同程度的不满意度。因此为了增强系统决策的公平性与合理性，为每一辆电动汽车的S_n设置相对应的足够大的惩罚系数Φ_n。Φ_n的值应当由两部分构成：一方面，由于充电机的服务能力有限，原则上遵循“先来后到”，导致每辆电动汽车的惩罚系数Φ_n的值会根据车到达的先后顺序，即车的序号n来设置，为了尽可能满足先来的车辆，先来的电动汽车(n较小)的惩罚系数要比后来的电动汽车的惩罚系数大，使得存在的欠缺量尽量是后来的电动汽车的欠缺量，此时的惩罚系数记为Φ_1n。另一方面，在先后“先来后到”原则的基础上，用户对充电的急切程度也应当在考虑范围内，记此时的惩罚系数记为Φ_2n。例如居民A先于居民B到达，但居民A的电动汽车预计三天后使用而居民B的汽车将在电量充足后立马投入使用。在此规定用户预计使用时间作为急切程度的判断依据，与先后原则同理，急切程度大的居民用户的Φ_2n的值应当大于急切程度小的居民用户。

3. 数学模型的建立与求解

供电系统在进行供电时会遵循一套智能判断的基于分时电价的有序充电策略，有序充电又分为两种模式，第一种为不连续充电模式，即电价高的时候降低功率，停止充电，电价低的时候相对提高充电功率继续充电，此种模式可以减少电网负荷，提高安全性。而连续充电模式的功率不会发生变化，每台电动汽车充电过程中不可中断，直接达到所能达到发充电范围，可以减少充电中断带来的损耗。

3.1. 不连续充电数学模型的建立

目标应当使得充电机供应商的电费和居民用户的不满意值之和最小。第i个时间段内充电站的电费成本C_i为：

$C_i=P_{i}P\frac{T}{60}{\displaystyle \underset{m=1}{\overset{M}{\sum }}{\displaystyle \underset{n=1}{\overset{N}{\sum }}{f}_{i,m}^n}}$ (3)

这样，充电机有序充电问题可以通过求解决策矩阵来得到最少运营成本与最大程度满足用户充电量的问题，目标函数为：

$\underset{F_{N\times I\times M},E_{N\times M},S}{\min }={\displaystyle \underset{i=1}{\overset{I}{\sum }}{C}_i}+{\displaystyle \underset{n=1}{\overset{N}{\sum }}\left({\Phi }_{1n}+{\Phi }_{2n}\right)S_n}$ (4)

下面给出约束条件：

$\{\begin{array}{ll}P{\displaystyle \underset{m=1}{\overset{M}{\sum }}{\displaystyle \underset{n=1}{\overset{N}{\sum }}{f}_{i,m}^n}}\le Q_i\forall i\hfill & (5)\hfill \\ {\displaystyle \underset{n=1}{\overset{N}{\sum }}{f}_{i,m}^n}\le 1\forall i,m\hfill & (6)\hfill \\ {\displaystyle \underset{m=1}{\overset{M}{\sum }}{e}_{n,m}}=1\forall n\hfill & (7)\hfill \\ {\displaystyle \underset{i=1}{\overset{I}{\sum }}{f}_{i,m}^n}\le 1\forall i,m\hfill & (8)\hfill \\ B_n\left(t_{n0}-t_{n1}\right)-S_n\le {\displaystyle \underset{m=1}{\overset{M}{\sum }}{\displaystyle \underset{i=T_{n,early}}{\overset{T_{n,early}}{\sum }}P\frac{T}{60}{f}_{i,m}^n}}\hfill & (9)\hfill \\ S_n\ge 0\forall n\hfill & (\; 10\; )\hfill \end{array}$

式(5)表示对负载进行限制的约束条件，其中，Q_i为第i个时间段充电站允许给电动汽车充电的功率最大值；式(6)与式(7)是对充电机分配及充电的约束：式(6)表示在任意充电机的任意时间段内最多只能有一辆电动汽车在充电，即一台充电机不能同时为多台充电汽车充电；式(7)表示任意电动汽车都必然分配到唯一一台充电机，即整个充电过程中都有且只有一台充电机为该电动汽车充电，是不可更换充电机条件的限制；式(8)表示任意电动汽车只在被分配到的充电机上充电。式(9)是充电电量的约束，表示电动汽车实际充电量不小于需求量与不满意值之差，即满足缺失部分的电量只能是不满意值；式(10)是不满意值的非负约束，表示所有不满意值必须非负。

3.2. 连续充电数学模型的建立

连续充电模型的目标函数与其余约束条件都与不连续充电模型相同，只增加用来限制连续的约束条件：

$f_{i,m}^{n+1}-f_{i,m}^n\le 1$ (11)

式(11)表示充电的时间段必须是连续的，即相邻两个充电时间段的时间间隔不能超过1。

3.3. 不连续与连续充电数学模型的求解

本文对不连续与连续模型的求解基于启发式算法中的贪心算法，贪心算法(greedy algorithm，又称贪婪算法)是一种对某些求最优解问题的更简单、更迅速的设计技术。在对问题求解时，把要求解的问题分成若干个子问题，不断迭代得到子问题的局部最优解，因此总是做出在当前看来是最好的选择，不去考虑整体的最优解，省去了为找最优解要穷尽所有可能而必须耗费的大量时间 [9]。

在本文的实际求解过程中，将贪心算法进行改进，根据整数规划模型进行模拟仿真，首先对待充电的车辆根据优先级进行排序，排序的原则根据惩罚系数Φ_1n和Φ_2n的设定，即同时考虑“先来后到”原则的基础以及用户对充电的急切程度，将排序好的电动汽车依次遍历M台充电机，分别计算电动汽车在每台充电机上目标函数的值，首先满足用户的不满意值最小，在此基础上选择充电成本最小的充电机。利用此种求解方法可求得不同时间段内不同电动汽车的具体充电效果。

3.4. 模型与求解中几个关键问题的说明

3.4.1. 对充电收益的衡量

本文计算时购电成本参考北京市电网峰谷分时销售电价表(夏季)，但是充电商向用户收费的定价，是依据市场行情而定，例如，在充电的峰时段为了提高利润把定价定的更高，相反在谷时段，定价可能与成本十分接近。因此充电商的收益具有不确定性，在计算时不予以考虑。

3.4.2. 求解过程的处理

为了计算方便在求解模型时采用双目标规划中的目标分层法将模型分成两步求解：

第一步，求得使总不满意值最小的解。模型中的约束条件不变，将目标函数改为 $\min {\displaystyle {\sum }_{n=1}^N{S}_n}$，首先求得使得总不满意值最小的解，将该解记为S。

第二步，在第一步的基础上求使总成本最小的解。将目标函数改为 $\min {\displaystyle {\sum }_{i=1}^I{C}_i}$，并且添加约束条件： ${\displaystyle {\sum }_{n=1}^N{S}_n}=S$，得到在总不满意值最小的方案中，使充电站总电费成本最小的充电方案。

4. 模拟仿真计算与分析

4.1. 参数设置

模拟仿真的部分原始数据来源于文献 [7]，数据设定参考文献 [10]，并对原始数据做了必要的调整。假设随机生成的案例中充电站共有充电机20台，待充电的充电汽车300辆；每台充电机的充电功率为5 kW，每辆电动汽车的电池总容量均为30 kW∙h。每辆电动汽车充电需求信息设定如表2：

Table 2. Setting information for EV charging demand

表2. 电动汽车充电需求信息设定

注：参数的设定仅考虑测试案例来验证模型的正确性与可行性这一原则。

在求解案例的过程中，根据表2中设定的分布，利用蒙特卡罗随机生成电动汽车到达时间、充电等待时间、初始荷电状态、离开荷电状态的数据，带入模型进行求解。

4.2. 仿真结果说明与分析

1) 居民用户充电需求量的满足情况

案例中两个模型的结果的不满意值如表3所示，从仿真结果可以看出在不连续充电模式下，居民用户的不满意度明显小于连续充电模式，即不连续充电模式能更好地满足用户所需的充电量。

Table 3. Dissatisfaction of discontinuous and continuous charging

表3. 不连续与连续充电的不满意度

造成这一差异的原因，是因为在低负荷使用的时候，不连续充电允许使用更大的功率来充电，来增大充电量；而连续充电是恒定功率，并未具有这一优化性。

2) 充电成本的对比

表4展示了有序充电模式下在一天内不连续充电和连续充电的总成本，显然在节约成本方面不连续充电明显优于连续充电，该结论基于分时电价的设定。

Table 4. Charging cost of discontinuous and continuous charging

表4. 不连续与连续充电的充电成本

利用MATLAB绘制不同车辆在连续与不连续两种情况下的成本比较图(见图1)：

Figure 1. Comparison of charging costs

图1. 充电成本对比

由于随着充电时间的增加，必然会带来充电成本的增加，因此图1中充电成本的中高段，可认为是充电的中长时间段，充电成本相对较低的时段则对应短时间段。可根据图1得出结论：不连续充电在中长时间段内的充电成本低于连续充电成本；但是在短时间充电，不连续充电与连续充电成本差距较小，甚至一些情况下不连续充电成本高于连续充电成本。

3) 负荷曲线的绘制与说明

Figure 2. Curve of charging load

图2. 充电负荷曲线

充电负荷曲线的对比可以体现不同时间段的一个负荷，其中初始负荷状态为前一天最后一个时间段的负荷。根据图2可以很明显地看到，连续充电在后半段，即在晚间充电高峰期，由于充电的人数增加导致充电负荷压力很大，使用不连续充电模式可以减小该种情况的负荷。同时不连续充电一天中的负荷效果比较均衡，可以保证这个充电过程的总负荷不会超标，不会出现连续充电模式下负荷波动较大、供电不足的情况。

4) 两种模式下的小区总负荷

最后观察在引入了有序充电系统后，小区的总负荷的变化情况。

由图3可知，在小区居民用电较少原始负荷比较低的时候，不连续充电的总负荷会相对提高，达到提高充电机的利用率的目的。而在小区的原始负荷在比较高的时候，不连续充电发挥其充电的不连续性，使得负荷增加相比与连续充电增加较少，降低该时段小区用电的总功率，避免出现小区居民用电负荷过载的情况。

Figure 3. The total load curve of the residential areas

图3. 小区总负荷曲线

5. 结论

本文利用蒙特卡罗模拟法随机生成案例，将数值带入到所建立的混合整数规划模型中，应用启发式算法中贪心算法的思想，对每一种可能的情形进行遍历，对比分析得到有序充电中不连续充电与连续充电的效果：

1) 不连续充电可通过其对功率的调控更大程度地满足居民用户的充电需求，降低用户的不满意度；

2) 应用不连续充电模式总体上可以大大降低充电运营商的经营成本，但是这种降低效果会受充电时长的影响，不连续充电在中长时间段内的充电成本低于连续充电成本，相反在短时间内充电，甚至会出现不连续充电成本高于连续充电成本的情况。说明在实际应用过程中，要根据小区总体的充电时长来确定应用何种充电方式；

3) 正因为不连续充电的调控充电功率的特性，可以平衡一天过程中充电负荷，减小充电站电荷波动，防止用电高峰的出现；

4) 相比连续充电，不连续充电可以平衡小区的总负荷，在小区总负荷低的时段采用高功率模式，总负荷高的时段则采用低功率模式，使得大型充电站的引入不至于使得小区总负荷引起较大波动从而造成负载的现象；

5) 事实上，如果选择不连续的充电模式，随之也会承担由于充电中断对电池带来的损伤。例如，在充电时，如果长时间插枪停放，或许会因为电池电量下降而频繁触发充电模式，并导致电池热失控 [11]，在一定程度可能导致电池失火事故的发生。

总之，随着绿色出行方式的普及，充电式汽车在未来将会得到更广泛的应用，本文所建立的连续与不连续充电模型可根据实际应用场景中的具体应用进行选择，但本文尚存在需要完善的地方，通过对算法的进一步学习，在未来可采用更加精确的算法并结合实际的数据给出不同充电方式的具体方案，探究更多可供选择的充电方式，来完善本文所研究的问题。

NOTES

^*第一作者。

^#通讯作者。