非均衡空间下考虑性能退化的充电设施联合检修路径

谌微微，许茂增，邢青松

(重庆交通大学经济与管理学院，重庆400074)

《节能与新能源汽车产业发展规划(2012—2020年)》和《汽车产业中长期发展规划》中明确了中国以纯电驱动为主的新能源汽车产业发展战略[1-2]，实施该战略的重要保障便是充电基础设施建设，而充电便利性是充电基础设施建设的重要指标，亦是影响新能源汽车推广的首要和最重要因素。伴随新能源汽车产业的发展，以充电桩为代表的充电设施网络快速扩展，据权威数据统计，目前中国充电桩总量已达到45万个，公共充电桩达到21万个，成为充电桩保有量最多的国家。不过，在充电设施建设时运营商主要从运营成本[3]、充电需求[4-5]、场地[6]等方面考虑，导致充电设施分布出现低覆盖度、布局疏密非均衡性等现象。即使在建设时考虑了充电需求分布，但在运营中由于充电设施固有的性能退化属性及缺乏专业的设施检修导致出现了局部冗长排队与“死桩”并存的利用率极度不平衡等现象。而目前对充电设施的研究多集中于充电设施规划布局[7-8]、运营成本[9]、合作机制[10]等方面，鲜有涉及充电设施检修方案的研究。

然而，对于成熟生产运营系统，预防性维护、修理等一系列检修活动通常是定期安排的。李二霞等[11]、卞建鹏等[12]、Wang等[13]、刘志文等[14]优化了电力设施检修方案，使其维护成本最低；刘增民[15]、吴晨恺等[16]研究了动车组在各项标准限值约束下检修的最佳间隔周期。对于以上性能退化属性较为明确的运营系统，其检修方案优化主要从降低成本、调整周期等方面开展研究，而对于充电设施这类性能退化规律尚待明确的新兴运营系统，还未建立有效的检修计划和机制，其研究重点存在较大差异。由于在技术上的退化规律尚不明确，而导致充电设施不能像智能电网等成熟运营系统一样进行定点检修，设计检修方案和制定间隔周期便成为研究难题。非均衡分布[17]状态下，充电需求量大或充电便捷度高的充电设施更为频繁使用，更易出现故障，前期新能源汽车用户的使用体验对持观望态度中的消费者有较大的影响，因而在众多充电设施品类技术退化规律尚不明确的情况下保证全域范围内充电设施良好的运行状态对新能源汽车进一步推广具有重要意义。故而，建立非均衡空间下考虑性能退化的充电设施检修机制是其首要任务，可使所有充电设施在合理间隔周期内都能接受检修，恢复最优或接近最优性能的状态。

针对充电设施多运营商、低覆盖度、布局疏密不均、性能退化规律不明等问题，通过联合组建专业维护团队定期对区域内所有充电设施进行故障排查、检修是较为有效的途径，既有利于提高新能源汽车充电便利性，又能较快掌握充电设施性能退化规律以促进技术进步。鉴于此，针对区域内非均衡分布且性能退化规律尚不明确的充电设施，首先提出通过制定各运营商联合检修机制确保充电设施性能可满足新能源汽车用户充电需求；接着，建立充电设施联合检修路径模型；然后，采用基于密度的聚类算法(density-based spatial clustering of applications with noise，DBSCAN)将区域内充电设施按照分布密度进行聚类，设置充电设施虚拟检修点；最后，以虚拟检修点的地址位置信息为基础，运用遗传禁忌搜索算法对联合检修路径进行研究，以使维护团队单次检修的总路程最短。

1 非均衡空间下充电设施性能退化问题描述

受运营成本、充电需求、场地等实际条件的限制，运营中的充电设施分布出现低覆盖度、布局疏密不均、各充电运营商的充电设施性能不尽相同、充电设施可靠性参差不齐等现象。当呈现出这种非均衡分布状态时，可能导致充电需求量大或充电便捷度高的充电设施更为频繁出现故障，而各类充电设施技术退化属性尚不明确，加之各运营商之间充电设施状态未实现信息互联互通及自动故障申告，无法进行定点检修，因而现阶段进行全域范围内充电设施进行检修需求更为迫切，以期提高新能源汽车充电便利性、加快掌握各类充电设施性能退化规律。各充电设施使用过程中固有的性能退化属性仍然存在，若没有外界力量及时进行检修，其性能退化量快速增加，一旦达到某一临界值时，充电设施丧失充电功能属性而发生失效，过程如图1所示，图中Ls为充电设施性能失效阈值，X(t)为充电设施性能退化量。在不进行检修的情况下，充电设施性能退化量X(t)随着时间t的延长而递增，当工作到T时刻时，其性能退化量达到阈值Ls，充电设施失效。

图1 充电设施性能退化过程Fig.1 Performance degradation process of charging facilities

当加入检修活动后充电设施的性能退化状态如图2所示。在有维护活动时，充电设施性能退化量X(t)会在检修时刻ti(i∈N+)被恢复到最小值，然后恢复原有工作状态。与图1进行对比，图2的充电设施性能退化呈现两个特点，即间断性和突变性。充电设施性能退量因检修而恢复到最小值，在检修时刻出现间断点，但随着检修次数的增加，每次检修后充电设施的性能退化量增加幅度越来越大。检修活动虽不能无限制延长充电设施使用寿命，但在一定程度上有利于延缓其性能退化过程并及时恢复原有工作状态，提高充电用户的便利性。

图2 检修条件下充电设施性能退化过程Fig.2 Degradation of charging facility performance under maintenance conditions

针对充电设施这种固有的性能退化属性及技术上的退化规律尚不明确的问题，提出通过联合各充电设施运营商建立充电设施检修机制，在一定间隔周期对区域内充电设施进行全面检修，确保充电设施保持良好工作状态以满足新能源汽车用户充电需求。然而，在现阶段不能明确其技术性能退化规律的情况下，无法从检修周期及总体检修时间方面开展研究，联合检修路径规划则成为降低检修成本的关键途径。

2 充电设施联合检修路径模型

2.1 定义变量

通过一个有向图G=(V,A)来定义被检修的充电设施及所需经过路径形成的网络。其中，A表示所有可行路径的集合，V表示充电设施检修节点集合。

充电设施检修点为1，2，3，…，m，…，n，工作人员从检修点m出发，经过检修点m+1，m+2，…，m-1各一次后再返回检修点m。设检修点i和j间的距离为dij(i≠j)。

2.2 模型建立

设xij为检修路径决策变量，则

(1)

在考虑总检修路径最短的情况下可设定目标函数为

(2)

约束条件为

(3)

(4)

此外，还需要满足

xij=0, 1；i,j=1,…,n

(5)

(6)

3 联合检修路径优化算法

3.1 充电设施检修点聚类

一定区域范围内充电设施数据较大，若以每一个实际充电设施为节点将不便于进行数据处理，且没有必要将距离非常接近的充电设施分开来研究，因此考虑设置虚拟检修点，即以充电设施的实际位置为依据，将实际距离接近的充电设施聚集成一个检修点，并以最终聚类成的虚拟检修点地理位置为依据建立表示各虚拟检修点间车行距离的邻接矩阵。对于非均质分布的区域，采用基于分布密度的DBSCAN算法将区域内充电设施进行聚类，形成充电设施虚拟检修点。

3.1.1 算法定义

E领域：给定检修点半径为E内的区域都为该检修点E的领域。

核心对象：若给定检修点E领域的充电设施数量或服务能力大于等于领域密度minPts，则该检修点为核心对象。

直接密度可达：对于检修点集合D，如果检修点q在检修点p的E领域内，且p为核心对象，那么检修点q从检修点p直接密度可达。

密度可达：对于检修点集合D，给定一串检修点p1，p2，…，pn，p=p1，q=pn，若检修点pi从pi-1直接密度可达，那么检修点q从检修点p密度可达。

密度相连：存在检修点集合D中的一点，如果检修点o到检修点p和检修点q都是密度可达的，那么检修点q和检修点p密度相联。

3.1.2 算法步骤

步骤1：根据实际检修能力，确定E领域及领域密度minPts的取值。

步骤2：标记所有检修点为unvisited。

步骤3：随机选择其中一个unvisited作为检修点p。

步骤4：标记检修点p为visited。

步骤5：判断检修点p领域中检修点个数。若检修点p的E领域至少有minPts个检修点，创建一个新簇C。

步骤6：令N为检修点p的E领域中的对象集合，检查集合N中的每个检修点p。若p是unvisited，则重新标记为visited；若p的E领域至少有minPts个检修点，则把这些检修点统统添加到集合N中；若p还不是任何簇的成员，则把p添加到C；停止检查，输出簇C；否则标记p为噪声；转到步骤4。

步骤7：直到没有标记为unvisited的检修点为止。

3.2 联合检修路径优化算法

遗传算法(genetic algorithm, GA)可以从解空间的多点出发进行自我学习式广泛探索，能求解大规模多目标函数的全局优化问题。禁忌搜索算法(tabu search, TS)则使用禁忌准则避免无效循环计算，并采用藐视准则接受差解，以保证不同范围有效路径的探测，能实现路径的全局逐步寻优。综合遗传算法较强的全局寻优能力和禁忌搜索算法较强的局部搜索能力，遗传禁忌搜索算法(GA-TS)更加适用于求解充电设施联合检修的路径优化问题。它包含7个核心元素。

邻域：变换初始路径中途径点的位置，产生的新路径集合称为初始路径的邻域。依次采用交叉、变异构建初始路径邻域。

移动：初始路径转移到它的邻域中的最优回路，称为一次移动。被采纳的移动即为下一次迭代过程的初始回路。

候选解集：初始回路的邻域子集。遗传算法的选择算子能引导算法朝着搜索空间中可能的最优区域进行探测。选用精英选择法来加快禁忌搜索速度，从初始回路的邻域中挑选出最优的10个回路构成候选解集，参与禁忌搜索。

禁忌表：一种存放禁忌对象的数据结构。一般情况下，禁忌表中的对象不能被选作为产生邻域的新解，以防止出现循环搜索和陷入局部最优解。

藐视准则：当候选解集中的最优对象比历史最优解好时，即使该对象被禁忌，仍可以替代历史最优解，作为下一次迭代过程的初始解，即特赦该禁忌对象。还有一种特赦情况是，若候选解集中的所有对象都被禁忌，则特赦最优候选解。

终止条件：算法达到预设的迭代次数，或者在固定周期内连续求得的最优解不变，二者满足其一即可终止计算过程，其中固定周期设置为算法迭代次数的0.6倍。

具体算法实现过程如图3 所示。

图3 遗传禁忌搜索算法过程Fig.3 Genetic tabusearch algorithm

4 案例分析

4.1 数据处理

重庆是重要的汽车产业基地，近年来也着力推广新能源汽车。为了支持新能源汽车产业的发展，截至2018年9月，重庆市主城八区已建成并投入使用的公共充电设施共计3 592个。使用Lenovo台式电脑，CPU主频为3.70 GHz的Inter Core i3-6100，操作系统为Windows10(64位)，以现有充电设施的地理位置信息为基础，应用PYTHON语言编写DBSCAN算法将充电设施聚集成若干个虚拟检修点，并以聚类结果作为输入，用MATLAB对联合检修路径模型求解。按照DBSCAN算法，设置E领域为100 m、领域密度阈值minPts为20，将3 592个充电设施聚类得到194个虚拟检修点，将虚拟检修点用ARCGIS10.2进行可视化显现，如图4所示。因此，可将各虚拟检修点进行标号，分别为1、2、…、194，并将虚拟检修点间的车行距离建立了194×194的邻接矩阵。

图4 虚拟检修点聚类图Fig.4 Clustering of virtual maintenance points

4.2 结果分析

用3种算法分别运行10次，对虚拟检修点构建的194×194车行距离矩阵最短路径模型进行求解，记录最短检修路径长度。具体结果如表1所示。

表1 最短路径模型求解结果Table 1 Solution of shortest path model

从解的稳定性和计算效率两方面对算法解的质量进行比较[18]。解的稳定性用相对最好解百分比g表示，计算公式为

(7)

式(7)中：S为3种算法各自的最短检修路径长度；B为所有算法中的最短路径长度；g为不小于0的值，g值越小，解的稳定性越高。计算效率用平均计算时间表示，时间越短，计算效率越高。解的质量比较如表2所示。

表2 解的质量比较Table 2 Quality comparison of results

根据3种算法求解结果及解的质量比较，遗传算法(GA)解的稳定性优于禁忌搜索算法(TS)，但计算效率方面存在一定的局限性；禁忌搜索算法(TS)计算效率最高，但解的稳定性方面不太理想；遗传禁忌搜索算法(GA-TS)所得到的检修路径长度最短，解的稳定性最好，由于在其求解过程中变异算子是一个搜索过程，增加了计算时间，使得计算效率方面无法体现优势，然而在一定群体规模下增加的计算时间是可以接受的，且从解决实际问题的角度来看，通常更为关注解的稳定性。因此，采用GA-TS所求解的最短检修路径作为联合检修的依据，检修路径如图5所示。图5中涵盖了所有虚拟检修点，且每次检修只经过一次，减少了因无检修路径规划造成的无效往返，可有效节约维修团队的有限资源，各运营商现有充电设施性能都能满足新能源汽车用户的充电需求，对提升其充电便利性作用显著。

图5 联合检修路径Fig.5 Path for joint maintenance

5 结论

基于充电设施呈现的非均质分布状态，结合目前运营中由于充电设施固有性能退化属性导致的局部冗长排队与“死桩”并存的利用率极度不平衡等现象，为满足新能源汽车用户的充电需求，在充电设施技术上的性能退化规律不明的情况下，提出组建专业维护团队对区域内所辖的所有充电设施进行联合检修。在建立充电设施联合检修路径模型的基础上，根据DBSCAN聚类算法，将重庆市主城八区截至2018年9月已建成运营的充电设施聚类为194个虚拟检修点，依据各虚拟检修点的地理位置数据，基于联合检修最短路程策略，构建194×194的车行距离矩阵，并采用3种算法对最短路径模型进行求解，结果显示遗传禁忌搜索算法的路径最优。通过制定检修机制，可逐步认识充电设施性能退化规律，进一步可不断优化检修周期和定点检修方案。此外，在以下方面可继续深入研究：基于现阶段充电设施分布，后期可引入不同区域的动态充电需求，进一步对充电设施进行布局优化；或充电设施数量进一步增加，布局基本稳定，可将大区域进一步分割为若干个小区域，寻求更优的检修路径；或待理清充电设施性能退化规律后可将其作为一个参数加入联合检修计划中，可提升检修效率。