基于满意优化的电动汽车充电站选址

贾永基， 邢芳芳

(东华大学 旭日工商管理学院， 上海 200051)

基于满意优化的电动汽车充电站选址

贾永基， 邢芳芳

(东华大学 旭日工商管理学院， 上海 200051)

充电站选址是当前电动汽车推广中面临的首要问题. 基于满意优化理论，提出了电动汽车用户满意度评价函数；通过引入充电站等级概念，以平均电动汽车用户满意度最大为目标函数，建立了多等级电动汽车充电站选址的混合整数规划模型，并提出了基于免疫算法的模型求解算法. 测试结果表明，该模型可以有效地确定充电站的位置、等级及服务区域，并且其求解算法是快速、有效的.

满意优化； 电动汽车； 充电站选址； 免疫算法

受能源危机和环境压力的双重影响，具有能源利用效率高、零污染、低噪声等优点的电动汽车，正在受到世界各国的广泛关注.然而，电动汽车充电站网络的建设远远滞后于电动汽车的发展.虽然国内已经建成较多充电桩，但大都处于居民小区内部，充电速度慢，且仅服务于单个电动汽车用户；现有的部分公共充电站，也处于技术验证及示范阶段，无法满足电动汽车用户的日常充电需求，从而降低电动汽车潜在用户的购买意愿.充电站选址问题已经成为制约我国电动汽车普及的关键因素之一.

目前，电动汽车充电站选址问题已经成为一项研究热点.文献[1]根据区域交通流量守恒定理，研究了电动汽车充电站的布局和定容问题，建立了综合费用最小模型，并对成都市充电站建设提出了解决方案.文献[2]考虑了地理环境和服务半径两个因素，构造了电动汽车充电站最优规划的数学模型，并采用改进的原对偶点法来求解.文献[3]考虑了充电站具有城市交通公共服务设施以及普通用电设施的双重属性，以俘获的交通流量最大、配电系统网络损耗最小以及节点电压偏移最小为目标，建立了充电站选址的多目标决策模型.文献[4-6]对台湾澎湖列岛旅游景区内的电动汽车充电站布局问题进行了一系列研究，从单目标集合覆盖问题到最大覆盖问题逐步深入研究，建立了多目标混合整数规划模型，并对结果进行了灵敏度分析，研究表明，使用多等级混合充电站可实现最佳布局.文献[7]构建了预算费用限制下的最大覆盖模型，并提出了混合启发式算法，用以确定充电站的位置和类型.文献[8]综合考虑了充电站建设运营成本和顾客充电成本，针对充电站规划的多目标性，提出了一种新的多种群混合遗传算法.文献[9]探讨了带容量限制的电动汽车电池交换站选址-路径问题，同时确定电池交换站的选址策略和电动汽车的最优行驶路径，并提出两个启发式算法(SIGALNS和TS-MCWS)用于求解该问题.

免疫算法是通过模拟生物免疫系统的智能行为而提出的仿生算法，是一种确定性和随机性相结合的启发式算法.自文献[10]于1974年首次提出免疫系统的模型之后，免疫算法已成为继遗传算法和神经网络之后的一个研究热点，其研究成果已经广泛应用于车辆调度、机器学习、图像处理和设施选址等诸多领域.文献[11]将免疫算法与遗传算法相结合，提出了一种新的免疫遗传算法并用于求解具有75个城市的旅行商问题，仿真结果表明，该算法的收敛速度显著提高.文献[12]概述了免疫算法的产生、发展和作用机理，比较了不同免疫算法的设计方法及其优劣.文献[13]讨论了几种典型的免疫算法及其应用情况，展望了今后的研究重点和发展趋势.文献[14]综述了免疫算法的基本模型、原理，并讨论了免疫算法的种类及最新应用成果.文献[15]将免疫算法用于分布式电源选址与定容问题的求解.文献[16]提出了多目标优化量子免疫算法，并用于通信基站选址问题的求解.文献[17]将免疫算法用于带权值的物流配送中心选址问题的求解.

由于电动汽车用户需求分布不均匀，单一等级的充电站网络不能低成本地满足所有用户的充电需求，因此，建立不同等级和不同服务能力的充电站网络可以提高充电站运营商和电动汽车用户的整体利益.2010年7月，标准化指导性技术文件——《电动汽车充电站电能供给与保障技术规范：充电站》出台，该文件将电动汽车充电站分为4个等级，各等级充电站动力蓄电池存储能、单路配电容量、日服务车辆数目等各不相同，如表1所示.

表1 电动汽车充电站等级Table 1 Glades of electric vehicle recharging stations

目前，对电动汽车充电站选址问题的优化主要是从充电站的运营成本、建设成本或充电服务获利的角度考虑，很少考虑电动汽车用户对充电服务的满意度问题. 电动汽车现在正处于推广阶段，政府出台了一系列促进充电站建设的补贴政策.为了迅速提高电动汽车使用的便利性，促进更多潜在用户购买电动汽车，成本不再是建设充电站的首要考虑因素，而用户充电的便利性，即用户对充电服务的满意度，已经成为充电站建设的首要目标. 因此，在当前推广阶段，应该从电动汽车用户满意度的角度考虑充电站的选址问题，通过不同等级充电站的合理布局，使得电动汽车用户的充电需求得到最大可能的满足，从而推动电动汽车的广泛普及.

本文首先建立了一个多等级电动汽车充电站选址问题的混合整数规划模型，该模型可以决策充电站的建站位置、等级及服务区域等问题；然后，提出了求解该模型的改进免疫算法，并通过一个算例来说明模型和算法的有效性.

1 电动汽车用户满意度评价函数

电动汽车用户满意度评价函数是一个反映用户实际体验的变量取值(客观)与用户心理状态(主观)之间关系的数学函数. 现有文献中的充电站选址模型主要是通过优化充电站的位置，使电动汽车用户与充电站之间的距离之和最短，没有考虑电动汽车用户充电的满意度，也可以认为电动汽车用户满意度是恒定不变的，跟抵达充电站的行驶距离无关，如图1(a)所示. 但在许多实际问题中，电动汽车用户满意度随着需求点与充电站的距离变大而降低，因为用户更加愿意充电站建设在自己的“家门口”，如图1(b)所示的用户满意度曲线，可以很好地表达电动汽车用户的这种偏好.

(a) 恒定的用户满意度 (b) 变化的用户满意度 图1 用户满意度曲线Fig.1 Curves of customer satisfaction

式(1)是图1(b)所示的电动汽车用户满意度函数的数学表达[18].

(1)

式中：dij为需求点i到充电站j的距离；F(dij)为需求点i的电动汽车用户的充电满意度；Li和Ui为需求点i的用户满意度变化的临界值，用户满意度在临界值Li和Ui附近的变化较小，在曲线中间部分的变化较大.F(dij)与dij的关系如下：

(1)dij在区间[0，Li]时，用户满意度最大为100%；

(2)dij在区间(Li，Ui]时，用户满意度为0到100%的非负数；

(3)dij在区间(Ui， +∞)时，用户不能接受，满意度为0.

2 电动汽车充电站选址模型

2.1 基本假设

基于满意优化的电动汽车充电站选址模型的基本假设如下：

(1) 每个需求点代表一个小型区域，其需求量是在该区域内有充电需求的电动汽车用户的总和；

(2) 每个需求点处的电动汽车用户只能到同一个充电站进行充电；

(3) 电动汽车行驶速度不受路况影响，保持恒定；

(4) 车辆类型、电池类型均相同.

2.2 符号说明

假设i为电动汽车用户所在的需求点，其数量为n，I为需求点的集合，i∈I；j为充电站候选点，其数量为m，J为候选点的集合，j∈J；hi为需求点i的需求量，即需要充电的电动汽车数量；k={1， 2， 3， 4}为电动汽车充电站等级；sk为k等级充电站的服务能力；p为需要建设的充电站数量；dij为需求点i到候选点j的距离.

Xjk为0-1决策变量，如果在候选点j处建立等级为k的充电站时，取值为1；其他情况取值为0.Yij也为0-1决策变量，如果需求点i的用户到候选点j处充电，取值为1；其他情况取值为0.

2.3 目标函数与约束条件

目标函数(式(2))表示电动汽车用户平均满意度最大；式(3)表示任一需求点的电动汽车用户只能到一个充电站接受服务；式(4)表示在一个候选点至多只能建设一个充电站；式(5)表示只有在候选点处建设了充电站，用户才能到该充电站接受服务；式(6)表示充电站等级必须满足所分配的所有需求点的充电需求；式(7)表示需要建设充电站的总数量；式(8)和(9)表示0-1决策变量.

(2)

(3)

(4)

(5)

(6)

(7)

Xjk∈{0， 1} ∀j∈J

(8)

Yij∈{0， 1} ∀i∈I，j∈J

(9)

3 基于免疫算法的模型求解算法

电动汽车充电站选址问题属于NP(non-deterministic polynomial)难问题，无法得到精确的最优解，因而只有采用启发式算法来求得满意解[19-22].

近年来，随着免疫算法研究的不断深入，人们逐渐认识到免疫算法具有保持解群分布多样性的特征，从而克服了一般寻优过程易陷入局部最优解的缺点. 在抗原的选择下，抗体与抗原的亲和力呈现不断增加的趋势，最终能够产生对付抗原的最有效的抗体. 从问题求解的角度而言，如果将抗体看作问题的解，免疫优化的过程就是一个不断寻求最大亲和力解的过程. 免疫算法被大量应用于求解各类选址问题[15-17]，但还没有将其应用于求解电动汽车充电站选址问题.

本文引入免疫算法思想并加以改进，使其适合电动汽车充电站选址问题的求解，算法流程图如图2所示. 如果将免疫算法与电动汽车充电站选址问题的一般搜索算法相比较，那么抗原、抗体、抗原和抗体的亲和力分别对应于目标函数和约束、可行解、可行解与目标函数的匹配度.

图2 改进免疫算法流程图Fig.2 Flow chart of improved immune algorithm

3.1 编码与初始抗体产生

每个选址方案可形成一个长度为p的抗体，每个抗体代表被选为充电站的候选点序列. 例如，考虑m个候选点选取p个点的充电站选址问题，假设1， 2， …，m代表候选点的序号，那么抗体[i1，i2， …，ip]代表一个可行选址方案，它表示[i1，i2， …，ip]被选为充电站，其中i1，i2， …，ip代表1， 2， …，n中不重复的p个序号.为增加抗体的多样性，初始抗体通过洗牌方式随机产生.

3.2 亲和力计算

亲和力包括抗体与抗原的亲和力Av以及抗体与抗体的亲和力Sv， s.

(1) 抗体与抗原亲和力Av表示抗体与抗原的匹配程度. 对于电动汽车充电站选址问题而言：

(10)

式中：Fv为目标函数，其取值范围为[0， 1]，因此Av的取值范围也为[0， 1].Av值越小，抗体与抗原的匹配程度越高；反之，Av值越大，抗体与抗原的匹配程度越低.

(2) 抗体与抗体的亲和力Sv， s表示抗体之间的相似程度，以百分比表示. 对电动汽车充电站选址问题来而言

(11)

式中：kv， s为抗体v和抗体s中相同候选点的个数；p为抗体长度.

3.3 抗体浓度计算与记忆细胞库更新

抗体浓度cv是指群体中相似抗体所占的百分数，即

(12)

在计算过程中，当一种抗体的浓度cv超过设定的阈值T时，表明该抗体在群体中占据了较大优势，到达了一个局部最优解，这时生成一个记忆细胞来记录此局部最优解. 如果记忆细胞库已满，则与抗原亲和力最低的记忆细胞被新产生的具有较高亲和力的记忆细胞取代. 记忆细胞同时也是抑制细胞，对那些与记忆细胞有较高亲和力的抗体产生抑制作用，使其生存力降低，以保证免疫算法不会陷入局部最优解.

3.4 期望繁殖概率计算

抗体与抗原间亲和力Av和抗体浓度cv共同决定了种群中每个个体的期望繁殖概率，即

(13)

其中，a为[0， 1]之间的常数.式(13)说明，个体亲和力越高、浓度越低，则被选择繁殖的概率越大；反之，个体亲和力越低、浓度越高，则被选择繁殖的概率越小.

3.5 变异算子

与标准免疫算法不同，变异算子是改进免疫算法的核心算子. 本文设计了两个变异算子：变异算子1和2.

图3 变异算子1Fig.3 Mutation operator 1

图4 变异算子2Fig.4 Mutation operator 2

4 测试与分析

4.1 测试实例

本文设计了电动汽车充电站选址问题的测试实例. 所有需求点的位置在[0， 50 km]×[0， 50 km]的平面内随机产生，其具体坐标和充电需求量如表2所示.其中，需求点的数量是60个，可以建设充电站的候选点的数量为55个. 现实中的充电站选址，除了考虑用户充电需求之外，还要考虑实施条件的可能性，例如，符合城市总体规划和路网规划、足够面积的可用土地以及电力负荷等，因此不可能所有候选点都适合建设充电站.为了使测试实例更符合现实情况，从60个需求点中随机产生5个不适宜建设充电站的点，即坐标(8.13， 26.99)、 (20.87， 41.78)、 (29.10， 30.69)、 (25.66， 28.79)和(25.99， 17.03).要求从候选点中选择p个点建设充电站，以满足所有需求点的充电需求，并确定充电站的等级和服务区域.

表2 测试实例数据Table 2 Data of test instance

(续 表)

4.2 测试结果分析

利用Matlab 2014a编写改进免疫算法来求解电动汽车充电站选址测试实例.参数设置：种群规模为50，迭代次数为100次，变异概率为0.5，电动汽车用户满意度临界值Li=3，Ui=15，亲和力阈值T=70%.对每个测试结果都是独立运行30次，取平均值.

不同充电站建设数量对电动汽车用户平均满意度的影响如表3所示.从表3中可以看出，随着充电站建设数量的增加，平均用户满意度也在增加，当然充电站的建设成本也会随着增加.选择合适的充电站数量，需要同时考虑财政预算和用户满意度，不同的决策者会得出不同的结论.本文中，选择建设9个电动汽车充电站，此时的平均用户满意度是85.25%， 充电站建站位置、等级及服务区域如表4和图5所示.

表3 充电站数量与平均用户满意度Table 3 Quantity of recharging stations and the average users’ satisfaction

表4 充电站建站位置、等级及服务区域Table 4 Locations， grades and service regions of recharging stations

图5 充电站建站位置及服务区域Fig.5 Locations and service regions of recharging stations

标准免疫算法和改进免疫算法的收敛曲线图如图6所示.从图6可以看出，改进免疫算法优于标准免疫算法.标准免疫算法在60次迭代之后才收敛到最优解，而改进免疫算法在30多次迭代之后就收敛到最优解，且收敛结果更好.对比结果表明，改进免疫算法既保持了标准免疫算法全局搜索性的特点，又增加了局部搜索能力，使其能够更好、更快地找到最优解.

(a) 标准免疫算法

(b) 改进免疫算法 图6 标准免疫算法和改进免疫算法收敛曲线Fig.6 Convergent curves based on immune algorithm and improved immune algorithm

5 结 语

本文研究了基于满意优化的电动汽车充电站选址问题，引入了充电站等级概念，提出了电动汽车用户满意度评价函数，建立了以用户满意度为目标函数的电动汽车充电站选址问题的混合整数规划模型. 为了求解该模型，提出了基于免疫算法的求解算法，设计了新的变异算子，既可以使解群中优势个体得以保留并快速收敛于最优解，又可以产生差异较大的新个体，保持解群中的个体多样性，防止出现早熟现象. 测试结果表明，本文提出的模型求解算法具有良好的寻优能力及收敛性能，能够满足实际电动汽车充电站选址问题的应用需求.

[1] WANG H， HUANG Q， ZHANG C， et al. A novel approach for the layout of electric vehicle charging station[C]// International Conference on Apperceiving Computing and Intelligence Analysis. IEEE， 2010：64-70.

[2] 刘志鹏，文福拴，薛禹胜，等.电动汽车充电站的最优选址和定容[J].电力系统自动化，2012， 36(3)：54-59.

[3] 王辉，王贵斌，赵俊华，等.考虑交通网络流量的电动汽车充电站规划[J].电力系统自动化，2013，37(13)：63-69.

[4] WANG Y W， WANG C R. Locating passenger vehicle refueling stations[J]. Transportation Research Part E， 2010， 46(5)：791-801.

[5] WANG Y W. Locating flow-recharging stations at tourist destinations to serve recreational travelers[J]. International Journal of Sustainable Transportation， 2011， 5(3)：153-171.

[6] WANG Y W， LIN C C. Locating multiple types of recharging stations for battery-powered electric vehicle transport[J]. Transportation Research Part E：Logistics and Transportation Review， 2013， 58(16)：76-87.

[7] YOU P S， HSIEH Y C. A hybrid heuristic approach to the problem of the location of vehicle charging stations[J]. Computers & Industrial Engineering， 2014，70(2)：195-204.

[8] 冯超，周步祥，林楠，等.电动汽车充电站规划的多种群混合遗传算法[J].电力系统及其自动化学报，2013，25(6)：123-129.

[9] YANG J， SUN H. Battery swap station location-routing problem with capacitated electric vehicles[J]. Computers & Operations Research， 2015， 55：217-232.

[10] JERNE N K. Towards a network theory of the immune system[J]. Annual Immunology， 1974， 125(1/2)：373-389.

[11] 王磊，潘进，焦李成.免疫算法[J].电子学报，2000，28(7)：74-78.

[12] 蔡自兴，龚涛.免疫算法研究的进展[J].控制与决策，2004，19(8)：841-846.

[13] 谢克明，郭红波，谢刚，等.人工免疫算法及其应用[J].计算机工程与应用，2005，41(20)：77-80.

[14] DASGUPTA D， YU S H， NINO F. Recent advances in artificial immune systems： models and applications[J]. Applied Soft Computing， 2011(11)：1574-1587.

[15] MA J J， WANG Y L， LIU Y. Size and location of distributed generation in distribution system based on immune algorithm[J]. Systems Engineering Procedia， 2012(4)： 124-132.

[16] 朱思峰，陈国强，张新刚，等.多目标优化量子免疫算法求解基站选址问题[J].华中科技大学学报(自然科学版)，2012，40(1)：49-53.

[17] 淦艳，魏延，杨有.免疫算法在带权值的物流配送中心选址中的应用[J].重庆师范大学学报(自然科学版)，2015，32(5)：107-113.

[18] 马云峰，杨超，张敏，等.基于时间满意的最大覆盖选址问题[J].中国管理科学，2006，14(2)：45-51.

[19] 李菱，李燕青，姚玉海，等.基于遗传算法的电动汽车充电站的布局规划[J].华东电力，2011，39(6)：1004-1006.

[20] 刘自发，张伟，王泽黎.基于量子粒子群优化算法的城市电动汽车充电站优化布局[J].中国电机工程学报，2012， 32(22)：39-45.

[21] 加鹤萍，谢胜利，邵翔，等.基于模拟退火算法的城市电动汽车充电站优化布局[J].山西电子技术，2013(3)：26-27.

[22] 赵书强，李志伟.基于差分进化粒子群算法的城市电动汽车充电站最优规划[J].华北电力大学学报(自然科学版)，2015，42(2)：1-7.

LocationofElectricVehicleRechargingStationsBasedonSatisfactoryOptimization

JIAYongji，XINGFangfang

(Glorious Sun School of Business and Management， Donghua University， Shanghai 200051， China)

Location of electric vehicle recharging stations is the primary issue to promote the usage of electric vehicles. Based on satisfactory optimization theory， the evaluation function of electric vehicle users’ satisfaction is proposed. By introducing the conception of multi-grade of recharging stations， a mixed integer programming model on location of multi-grade electric vehicle recharging stations is developed， and its objective function is to maximize the average electric vehicle users’ satisfaction. And an algorithm based on immune algorithm is proposed to solve this model. The test results show that the proposed model can effectively determine the locations， grades and the service regions of the recharging stations， and the algorithm is quick and effective.

satisfactory optimization； electric vehicle； recharging stations location； immune algorithm

1671-0444(2017)05-0739-07

2016-06-29

国家自然科学基金资助项目(71371045)；教育部人文社科青年基金资助项目(13YJC630159)；中央高校基本科研业务费专项资金资助项目(16D110815)

贾永基(1976—)，男，山东烟台人，副教授，博士，研究方向为物流系统建模与优化.E-mail：yjjia@dhu.edu.cn

U 469.72

A

(责任编辑：杨静)