基于双蚁群优化算法的电动汽车充电基础设施规划方法

摘要

本发明公开了基于双蚁群优化算法的电动汽车充电基础设施规划方法，本方法基于双蚁群算法实现。该算法使用两个蚁群分别求解CIPL的两个子问题。在每次迭代中，上层蚁群搜索最佳充电站选址，最大化充电需求，下层蚁群搜索每个确定充电站的最佳充电桩数量，最小化经济成本。应用两种信息传输策略平衡充电需求和经济成本。信息素增强策略是根据上层蚁群的解来增强下层蚁群的信息素，以加速下层蚁群的收敛。全局信息素更新策略通过综合考虑两个目标函数来确定最优解，并据此解对上层蚁群的信息素进行更新。

说明书

技术领域

本发明涉及进化算法技术领域，针对电动汽车充电基础设施规划问题(CIPL)，设计了一种双蚁群算法来解决CIPL中的充电站选址和充电桩分配。

背景技术

一般来说，CIPL涉及两个子问题:(1)充电站选址问题，通过考虑一些因素来确定一些地点建设充电站。(2)充电桩配置问题，通过考虑一些因素来确定每个充电站的充电桩数量。这两个问题本质上是组合优化问题。据我们所知，对CIPL的研究始于2011年，在过去的十年里，有许多关于CIPL的研究。总体而言，现有的研究大多只关注充电站选址问题，而最近的一些研究开始同时关注这两个问题。根据实现机制，充电站选址问题的所有方法可分为整数线性规划(ILP)和启发式算法两大类。ILP方法将充电站选址问题建模为整数线性优化问题，利用传统的确定性优化方法确定充电站选址。ILP方法可以快速解决充电站选址问题，但仅适用于备选充电站选址较少的小规模问题。而且，这类方法要求优化模型的优化目标和约束函数必须是线性的。随着充电基础设施和电动汽车的发展，充电站选址问题需要考虑的因素越来越多。充电站选址问题的优化模型可能是大规模的，涉及更多的充电站候选站点，可能不再满足线性要求。面对这样的情况，ILP方法是无能为力的。启发式算法是随机优化算法中的一类，以其对优化模型的尺度和性质要求小而著称。正因为如此，它被广泛应用于解决各种复杂的优化问题，也有研究人员采用启发式算法求解充电站选址问题。

近年来的研究开始采用启发式算法同时解决充电站选址问题和充电桩分配问题。例如，快速贪心算法通过充电需求最大化来解决充电站选址问题，然后利用M/M/N/N排队理论，通过最小化电动汽车排队概率来解决充电桩分配问题。上升启发式算法AHA通过确定充电站选址，使利润最大化，然后为每个充电站分配充电桩，使需求损失率最小。这些方法虽然同时提供了充电站选址问题和充电桩配置问题的求解方法，但它们是独立处理这两个问题的，忽略了这两个问题的相互联系和影响。换句话说，这两个问题之间可能存在冲突。在一个目标的给定情况下，通常无法得到另一个目标的最优情况。如果能系统、全面地考虑这两个问题，CIPL的合理性可能会更好。

发明内容

本发明尝试用蚁群算法解决CIPL问题，提出了一种双蚁群算法DACO-CIPL。该算法使用两个蚁群分别求解CIPL的两个子问题。在每次迭代中，上层蚁群搜索最佳充电站选址，最大化充电需求，下层蚁群搜索每个确定充电站的最佳充电桩数量，最小化经济成本。应用两种信息传输策略平衡充电需求和经济成本。信息素增强策略是根据上层蚁群的解来增强下层蚁群的信息素，以加速下层蚁群的收敛。全局信息素更新策略通过综合考虑两个目标函数来确定最优解，并据此解对上层蚁群的信息素进行更新。

本发明采用的技术方案为基于双蚁群优化算法的电动汽车充电基础设施规划方法，充电站负责为区域内的电动汽车提供充电服务。在一个区域内，电动汽车轨迹用整数编号。所有的电动汽车(EV)轨迹号组成T＝{1,2,...,t,...,m}，其中t表示任意轨迹编号，m表示区域内轨迹总数。所有候选充电站站点号组成集合{1,2,...,i,...,n}，其中i表示任意候选充电站站点编号，n表示候选充电站站点总数。所有候选充电站的坐标构成集合{c

根据两个问题的解定义两个目标函数，充电站选址的目标函数为最大化充电需求，其定义为：

其中s(x

充电桩分配的目的是最小化经济成本，但是为了反应充电桩分配结果与充电站选址的关系，其目标函数定义为最大化单位经济成本所能满足的充电需求：

其中F

F

其中ω(x

求解算法中解的编码形式，在上层蚁群中，每只蚂蚁都表示为充电站选址问题的一个候选解，其形式为集合{1,2，...，n}的N元排列，其中n为候选位置的数量，N为待建设充电站的数量。在下层蚁群中，每只蚂蚁都表示为充电桩分配问题的一个候选解，其形式为集合{1,2，...，r

在算法中，每个蚁群的搜索空间是一个搜索图。两个蚁群的搜索图分别用G

首先，随机选取一定数量的轨道起始坐标和结束坐标作为充电站候选站点。然后初始化与每个蚁群搜索图相关的启发式信息(H

其中，τ

初始化后，开始搜索过程。在每次迭代中，上层蚁群和下层蚁群通过在各自的搜索图上行走，依次构造充电站选址问题和充电桩配置问题的解。对于两个蚁群中的所有蚂蚁，根据启发式信息和信息素信息，通过状态转换规则确定其行走轨迹，以上层蚁群为例，假设一只蚂蚁在图G

其中P

其中v

每走一步，就执行一次局部信息素更新策略，以修改它们刚刚经过的顶点上的信息素值，更新规则如下：

P

其中ρ∈(0,1)为信息素的挥发率，是预先设定的参数。

当两个蚁群的蚂蚁在一次迭代中全部完成行走时，对两个蚁群最佳解行走轨迹中存在的顶点进行全局信息素更新策略，规则如下：

其中

当上层蚁群在每次迭代中完成构建解的过程时，将其解传递给下层蚁群，这可以增强下层蚁群的信息素，加速下层蚁群的收敛，规则如下：

其中

两个蚁群通过迭代重复上述构造解的过程，直到满足预先设定的迭代次数上限，此时，输出两个蚁群最终的历史最优解。

与现有技术相比较，蚁群优化(ACO)是一种受蚂蚁觅食行为启发的元启发式优化方法。在实践中，蚁群算法使用一组人工蚂蚁来构造解。蚂蚁通过一种叫做信息素的化学物质将食物来源分享给同伴。当蚂蚁成功找到食物时，它们会在返回巢穴的路上沉积信息素。其他蚂蚁选择一条信息素更多的路径，概率更大。通过重复这个觅食过程，所有的蚂蚁都被引导到具有大量信息素的最佳路径。我们将ACO应用于CIPL有以下两个优点:(1)ACO作为一种启发式算法，以其能够解决不同规模的组合优化问题而闻名，并在不同的现实应用中得到了应用。如前所述，充电站选址和充电桩配置问题本质上都是组合优化问题。因此，我们认为ACO适合于进行CIPL。(2)蚁群算法中，信息素的正反馈机制是获得优解的关键。这一点启发我们，信息素或许能够在充电站选址问题和充电桩分配问题之间起到平衡调整作用。这样，我们就可以系统、全面地考虑这两个问题，从而为CIPL提供更好的决策。

与现有方法相比，本发明具有以下明显的优势和创新：

1)本发明首次考虑充电站选址问题和充电桩配置问题的相互联系和影响。2)提出了一种双蚁群优化算法，通过信息传递平衡充电站选址问题和充电桩配置问题的目标函数。3)提出了一种新的信息素增强策略，将解的信息从上层蚁群传递到下层蚁群，以加速下层蚁群的收敛。4)在实际车辆轨迹数据集上，将所提算法与其他算法进行了比较，结果表明所提算法能得到更合理的充电基础设施规划。

附图说明

图1：CIPL实例。

图2：算法流程图。

图3：真实地图上的对比结果。

具体实施方式

为了进一步解释本发明的技术方案，首先介绍CIPL的两个子问题的数学模型。

图1是一个简化的CIPL示例，充电站负责为区域内的电动汽车提供充电服务。在一个区域内，电动汽车轨迹用整数编号。所有的电动汽车(EV)轨迹号组成T＝{1,2,...,t,...,m}，其中t表示任意轨迹编号，m表示区域内轨迹总数。所有候选充电站站点号组成集合{1,2,...,i,...,n}，其中i表示任意候选充电站站点编号，n表示候选充电站站点总数。所有候选充电站的坐标构成集合{c

根据两个问题的解定义两个目标函数，充电站选址的目标函数为最大化充电需求，其定义为：

其中s(x

充电桩分配的目的是最小化经济成本，但是为了反应充电桩分配结果与充电站选址的关系，其目标函数定义为最大化单位经济成本所能满足的充电需求：

其中F

F

其中ω(x

接下来介绍求解算法中解的编码形式，在上层蚁群中，每只蚂蚁都表示为充电站选址问题的一个候选解，其形式为集合{1,2，…，n}的N元排列，其中n为候选位置的数量，N为待建设充电站的数量。在下层蚁群中，每只蚂蚁都表示为充电桩分配问题的一个候选解，其形式为集合{1，2，...，r

在算法中，每个蚁群的搜索空间是一个搜索图。两个蚁群的搜索图分别用G

算法流程如图2所示，首先，随机选取一定数量的轨道起始坐标和结束坐标作为充电站候选站点。然后初始化与每个蚁群搜索图相关的启发式信息(H

/>

其中，τ

初始化后，开始搜索过程。在每次迭代中，上层蚁群和下层蚁群通过在各自的搜索图上行走，依次构造充电站选址问题和充电桩配置问题的解。对于两个蚁群中的所有蚂蚁，根据启发式信息和信息素信息，通过状态转换规则确定其行走轨迹，以上层蚁群为例，假设一只蚂蚁在图G

其中P

其中v

每走一步，就执行一次局部信息素更新策略，以修改它们刚刚经过的顶点上的信息素值，更新规则如下：

P

其中ρ∈(0,1)为信息素的挥发率，是预先设定的参数。

当两个蚁群的蚂蚁在一次迭代中全部完成行走时，对两个蚁群最佳解行走轨迹中存在的顶点进行全局信息素更新策略，规则如下：

其中

当上层蚁群在每次迭代中完成构建解的过程时，将其解传递给下层蚁群，这可以增强下层蚁群的信息素，加速下层蚁群的收敛，规则如下：

其中

两个蚁群通过迭代重复上述构造解的过程，直到满足预先设定的迭代次数上限，此时，输出两个蚁群最终的历史最优解。

本方法采用华盛顿的出租车轨迹数据集。该数据集包括2017年10万份完整的出租车轨迹。每个轨道包含关于每个轨道的起始坐标和结束坐标的信息。使用了三种不同规模(SC1，SC2和SC3)的测试数据集，表1提供了三种不同规模的测试数据集的详细信息，其中m、n、N和r

表1测试实例设置

表2本发明所提方法与其他算法比较的性能对比

/>

将用于在每个测试实例上比较算法的最佳解。如表2所示，与GA-CIPL、PSO-CIPL和AHA相比，在SC1和SC2的5个测试实例中，有3个DACO-CIPL的BEST高于其他算法。当测试实例规模达到SC3时，DACO-CIPL的BEST是所有测试实例中最好的。随着充电站候选站点数量的增加，DACO-CIPL具有更好的性能。这表明DAOC-CIPL算法在中小型数据集上并不弱于比较算法，在大规模数据集上具有优势。除此之外，在13个测试实例中，DACO-CIPL的均值表现很好，证明了DACO-CIPL的稳定性更好。另一方面，在所有的测试实例中，DACO-CIPL的CPU时间比3种比较算法最短。结果表明，DACO-CIPL通常能在更短的时间内获得更好的解。为了验证算法的规划能力，在地图上展示了测试实例SC2-2、SC1-2和SC1-3上的DACO-CIPL和GA-CIPL的最佳充电站站点。因为相较于其他对比算法GA-CIPL表现最好。GA-CIPL可以代表其他比较算法。图3中，为DACO-CIPL充电站站点和GA-CIPL充电站站点，以及两种算法都确定的充电站位置。在地图上，标出了通常产生更多充电需求的繁华区域。所覆盖的繁华区域数量可以反映充电站站点的充电需求。在图(a)中，DACO-CIPL选择了杜邦环岛、华盛顿联合车站、里根国家机场和国家动物园，而GA-CIPL只选择了其中一个地点。在图(b)中，除了杜邦环岛，DACO-CIPL还选择了邦克山。在图(c)中，GA-CIPL选择了更繁华的区域，包括乔治敦大学，国家动物园和唐人街。真实充电站站点覆盖的繁华区域与表1中的充电需求一致。算法覆盖的繁忙区域越多，充电需求就越高。以上结果证明，CIPL的目标函数能够准确反映站点的收费需求。此外，也可以证明DACO-CIPL在实际CIPL中具有较好的应用价值。