基于改进遗传算法的充电桩检测调度优化

李晶晶，张永敏，田桂林，崔胜胜，严 洁

（国网青海省电力公司营销服务中心，电能计量设备检定检测技术实验室，青海 西宁 810000）

随着我国双碳目标的提出，快速发展的新能源电动汽车已经作为解决能源短缺和环境污染的有效途径之一。充电桩作为电动汽车的主要设施，扮演着越来越重要的角色。充电桩是否安全可靠对电动汽车的推广和发展，以及对新能源产品用户是否拥有良好的体验感和信任度都至关重要。相应的，对充电桩进行必要的检测，提高充电桩检测效率也成为充电桩研究领域的重中之重。

在充电桩检测方面，目前主要有人工检测与系统自动检测 2 种方式。对于传统的人工检测方式，接线、拆线等项目均采用同一套检测设备，检测一台充电桩往往需要大量时间。同时，人工检测主观误差较大，且检测设备不够稳定。这些问题严重制约了充电桩检测的效率和精度。

针对人工检测速度慢等问题，学者们着力研发充电桩自动测试系统。例如，钟劲松等[1]研发了一套充电桩检定系统，为电动汽车充电桩相关试验提供了测试环境和方法的参考。姜立标等[2]研发了一种基于LabVIEW 的电动汽车直流充电桩检测系统，该系统操作方便快捷，提高了充电桩的检测效率。朱彬等[3]研究了供电设备与电动汽车之间的互操作性测试，并设计了一种充电桩检测平台[4]，实现了对充电桩进行互操作性和电性能测试，预防了人为读数误差，提高了检测的准确性。

随着现代新能源产业的蓬勃发展，关于充电桩检测领域研究的相关理论也逐渐丰富。王斌[5]从新能源充电桩的检测技术入手，对智能感应在其中的应用进行了分析，提出了充电桩模拟检测方案，拓展性地丰富了新能源汽车充电桩检验检测相关理论和方法。丁建顺等[6]以电动汽车交直流充电桩技术为基础，提出了一种基于区块链技术的电动汽车充电桩共享检测方案，保证了无源状态下的数据存储与通信安全。上述研究表明，系统自动检测充电桩的方式实质性地提高了检测的准确率和工作效率，但优秀的检测平台必须考虑兼容性与可扩展性，需要支持不同厂家、不同型号产品的检测[7]；因此，对检测平台提出了非常高的要求。

为了进一步提高充电桩检测效率，本文在已有自动检测系统平台的基础上，结合车间调度问题的特点，对充电桩检测调度优化问题进行研究。车间调度问题是指M台机器，加工N个作业，其中作业i包含工序数为Li，各工序的加工时间已确定，每个作业必须按照工序的先后顺序进行加工。在对多个充电桩同时进行检测时，会因选择不同的调度方案而直接影响整体的检测效率，还需要对多个项目一一检测才能确认其性能是否真正安全可靠。因此，充电桩检测问题亦属于柔性开放车间调度问题，是一种典型的NP-Hard 问题。在车间调度优化领域，国内外学者已经做了研究，取得了一些成果。Bai 等[8]以最长完工时间为目标，分别研究了柔性开放车间调度问题的静态和动态问题，利用有界性假设证明了广义密集调度算法的渐近最优性。文献[9]提出了一种粒子群算法，通过将其应用于分层多目标框架来解决具有不确定加工时间和灵活交货期的多目标开放车间产生的调度问题。文献[10]介绍了一种改进人工蜂群算法，用序列对问题的解进行编码，其计算结果表明，该算法能在大规模问题中取得最佳的求解效果，但不能在小范围问题中提供精确解。针对在车间调度过程中工件的选择优先级规则对其调度结果有较大影响[11]的问题，王秋莲等[12]提出了一种改进的多目标候鸟优化算法，用于求解高维多目标问题，算例和实例验证了该算法在实际加工中能够给予决策者更好的选择。

此外，还有采用基于多智能体的深度强化学习算法[13]、结合模拟退火的多目标COOT 算法[14]和遗传算法等对柔性车间调度的多目标优化问题求解。因遗传算法具有全局搜索快的优点特性，王冠等[15]针对非支配排序遗传算法进行自适应改进，采用独立的交叉和变异操作对工序与设备进行排序及分配的调整，其结果表明采用该改进算法，最大完工时间、加工能耗、加工设备总负载和延期时间均得到显著改善，有效提高了生产管理效率。田志强等[16]提出了一种基于改进非支配排序遗传算法的柔性作业车间多目标节能分批调度方法，解决了无方向性生成初始解导致算法收敛精度低、速度慢的问题，使初始解的生成具有方向性。上述研究表明，基于遗传算法的求解方法虽改善了诸多问题，但易早熟收敛，易陷于局部最优。

可见，粒子群算法、人工蜂群算法和遗传算法等虽然已经应用于解决一些开放式车间调度问题，但是仍然存在不能在小范围内提供精确解，以及缺少对实际应用中因选择不同检测项目机器、检测项目之间的先后顺序和检测调度方案等的研究而严重影响整体检测效率的问题。因此，本文以充电桩检测完成时间最短为目标，建立充电桩检测优化模型，并采用改进遗传算法对其进行求解，以此提高充电桩检测效率。

1 充电桩检测调度优化问题建模

1.1 调度决策变量

调度决策主要为：充电桩检测设备的选择决策xijk、检测设备上充电桩检测的顺序决策yil jk和充电桩检测项的顺序决策zijg。其对应的表达式为：

式中：ji(i=1,2,3,···,n)为第i个充电桩；Mjk为第j项检测的第k台检测设备。

1.2 目标函数

在进行充电桩检测时，希望所有充电桩检测完毕用时最短，因此目标函数为充电桩的最大检测完成时间Cmax，为

式中：n为充电桩总数目；Ci为第i个充电桩的检测完成时间；i的取值范围为1,···,n。

1.3 约束条件

1) 充电桩检测设备约束。

用Oij表示充电桩Ji的第j项检测，且充电桩检测项只能分配给一台检测设备。

式中xijk表示第i个充电桩选择检测设备Mjk；Mjk表示第j项检测的第k台检测设备。

2) 检测设备上充电桩检测顺序约束。

检测设备Mjk检测的任意充电桩Jl至多有一个先于它或后于它的检测充电桩。

式中：yil jk表示检测设备Mjk上，充电桩Ji在充电桩Jl前一个检测；ylijk表示检测设备Mjk上，充电桩Jl在充电桩Ji前一个检测。

3) 充电桩检测顺序约束。

在充电桩Ji的检测过程中任意一项检测至多有一项检测先于该项或后于该项检测。

式中：zijg表示充电桩Ji的第j项检测为第g项检测的前项检测；zigj表示充电桩Ji的第g项检测为第j项检测的前项检测；m为充电桩检测项目种类数。

4) 检测设备同时刻检测充电桩数量约束。

一台检测设备同一时刻至多检测一个充电桩。

式中：Cij表示第i个充电桩的第j项检测的检测结束时间；tl j表示第l个充电桩的第j项检测的检测用时。

5) 决策变量取值。

2 基于改进的遗传算法的求解

充电桩检测调度属于柔性开放车间调度问题，不仅涉及到各检测项目顺序之间的柔性，还涉及到设备选择的柔性问题，为NP-Hard 难题。因此，本文采用以仿自然体算法为主的启发式算法进行求解。在启发式算法中，被应用较多的遗传算法具有强大的全局搜索能力，且易于与其他算法相结合，同时，搜索从群体出发时可进行多个个体同时比较，具备信息处理的并行性和操作的简明性，是一种具有良好适应性和可规模化求解的方法。为此，本文结合充电桩检测会因选择检测项目、机器间先后顺序的不同而有不同结果的实际特点，设计了双变异算子，对遗传算法的迭代过程进行改进。在此基础上添加初始化因子和精英策略，对标准遗传算法[17]在求解充电桩检测调度优化问题时存在局部搜索能力差和容易过早收敛等问题进行改进，采用改进的遗传算法对所建立模型进行求解。

2.1 基于标准遗传算法的充电桩检测调度优化

采用标准遗传算法求解充电桩检测调度优化问题的流程图如图1 所示，主要步骤描述如下。

图1 基于标准遗传算法的充电桩检测调度优化流程图Fig.1 Flow chart of charging pile detection scheduling optimization method based on standard genetic algorithm

第1 步，输入充电桩、检测设备和检测项目时间等数据。

第2 步，随机初始化各充电桩检测工序顺序和检测设备顺序，并将检测顺序与检测设备分别进行编码，构造初始种群P(t)。

第3 步，将所有充电桩最大检测完成时间设为目标函数，对初始种群P(t)进行适应度计算。然后，评价个体适应度值，检测时间越短，适应度越高。

第4 步，采用轮盘赌策略选择种群中适应度较高的个体进入下一代种群。轮盘赌选择的基本思想是各个个体被选中的概率与其适应度大小成正比，将种群中所有个体的适应度值进行累加然后归一化，最后随机对落在区域对应的个体进行选取。

第5 步，对选择出的个体进行交叉和变异操作，生成新的子代个体。

第6 步，将新的种群个体带入目标函数中进行计算，在多次迭代方案中选出检测用时最少的个体，得到最优调度方案。

2.2 基于改进的遗传算法的充电桩检测调度优化

上述标准遗传算法具有良好的适应性和可规模化求解的优点，但其局部搜索能力差和容易过早收敛等问题未得到解决。因此，本文采用改进的遗传算法求解充电桩检测调度优化，其流程图如图2所示，主要步骤描述如下。

图2 基于改进遗传算法的充电桩检测调度优化流程图Fig.2 Flow chart of improved genetic algorithm

第1 步，随机初始化各充电桩工序编码信息。本文采用多层染色体编码方式：第1 层表示各充电桩之间的工序排序；第2 层表示充电桩各工序对应的检测项目；第3 层表示选择的机器编号；第4 层表示充电桩各工序的检测用时。例如，假设有2 个充电桩需要检测，检测工序简化为3 个，其对应的编码方案如表1 所示。

表1 染色体编码示意信息Tab.1 The information of chromosome coding

第2 步，启发式生成检测项目排序串、检测设备串和检测时间。改进算法的可行解由待检测充电桩的工件生成工序串、检测项目串、检测设备串和检测时间串共同组成的一条染色体串来表示。

第3 步，采用轮盘赌算子选择种群中适应度较高的个体进入下一代进行迭代。因每个部分被选中的概率与其适应度值成比例，本文直接选取所有充电桩的最大检测完成时间为目标函数，Cmax作为适应度函数来计算群体中个体的适应度值。因此，适应度函数的数学表达式如公式（4）所示。

第4 步，随机选择2 个父代染色体进行优先操作交叉(precedence peration crossover，POX)，生成新个体。交叉是遗传算法最重要的操作，决定着遗传算法的全局搜索能力。遗传算法假定，若一个个体的适应度较好，那么基因链码中的某些相邻关系片段是好的，并且由这些链码所构成的其他个体的适应度也较好。本文选用POX 作为交叉算子[18]，它相对于基于作业的顺序交叉(job-based order crossover，JOX)算子、子序列交换交叉(subse-quence exchange crossover，SXX)算子、设置分区交叉(setpartition crossover，SPX)算子、优先级保留交叉(precedence preservation crossover，PPX)算子能够更好地继承父代优良特征并且其子代总是可行的。

第5 步，采用基于工序变异和设备变异的双变异算子生成新个体。对于工序编码变异来说，其过程为从父代个体中随机选择一个关键工序，在满足内部顺序约束的条件下，将选择的工序插到其最近的关键工序之前。设备变异则通过单点变异的方式进行。本文考虑到问题的复杂性，设计了基于工序变异和基于设备变异的双变异算子，来保持种群的多样性，提高算法的全局搜索能力。

第6 步，采用初始化方法生成部分新个体，以提高算法的全局搜索能力。初始化时首先确定各充电桩检测工序之间的排序，然后随机确定各充电桩检测工序对应的检测项目，最后根据检测项目随机化确定各充电桩检测工序对应的检测设备和检测时间。

第7 步，采用精英策略，筛选父代种群和新一代种群中适应度较高的个体作为新一代种群，以提升算法的收敛速度。精英策略是利用种群精英个体信息来改进算法性能，将群体进化过程中出现的最好个体不进行配对交叉而直接复制到下一代中。本文为了保持群体的规模不变，若精英个体被加入到新一代群体中，则将新一代群体中适应度值最小的个体被淘汰。

3 结果与对比分析

为了验证改进遗传算法在提高充电桩检测效率方面的可行性和有效性，本文在充电桩检测应用实例中对人工检测、标准遗传算法和改进遗传算法的测试结果进行对比分析。该实例共需检测5 个充电桩，各充电桩都包含表2 所示的10 项检测项目。遗传算法参数的具体设置如下：种群个数为50，迭代次数为100[19]，选择概率为0.8，交叉概率为0.6，变异概率为0.5。

表2 充电桩检测项目相关信息Tab.2 The information about charging pile detection project

为了保证2 种算法求解结果的准确性，对标准遗传算法和改进遗传算法进行了多次迭代求解，最后取平均值作为最终解。充电桩的数量和各检测项目可选择的检测设备及检测所需时间如表2 所示，其中各试验项目均为兼容性试验。

由表2 可知，充电桩的不同检测项目对应的检测设备不同，有的检测项目有多个可选设备，例如充电输出试验、谐波电流试验和功能检查项目都可用具有相同功能同种设备进行检测。S5/S6/S7 表示充电输出试验检测项目可选择3 台设备中任意空闲的1 台进行检测。本文将根据以上设置的各参数信息，做人工现场检测、标准遗传算法求解优化和改进遗传算法求解优化3 组试验，对比其检测时间，以验证所提改进遗传算法的可行性、有效性和优越性。

3.1 人工现场检测结果

截至目前，人工现场检测仍然是充电桩检测的主要方式[20]。本文通过现场查勘检测人员检测5 台充电桩的各个操作环节，统计其工序及时间，得到调度结果甘特图如图3 所示。由图3 可知，采用人工现场检测同时检测5 个充电桩的最短完工时间为46 min。图3 中同一充电桩用相同的颜色表示，并标出了对应的充电桩序号和检测顺序工序号。以蓝色代表的第3 个充电桩工作流程为例进行解释：3-1 表示第3 个充电桩的第1 道工序，加工设备为S4，检测项目为3 号绝缘性能试验，加工时间为2.2 min，之后的检测循序进行。在人工检测过程中检测项目和设备的选择都需检测人员自定，需要检测人员根据丰富的工作经验和扎实的理论基础，综合性地分析问题，并采取针对性的方案去解决问题[21]。若检测人员经验不足或是主观判断错误，就会严重影响检测正确率，就会出现3-4 这种已经结束上一项检测但因为选择下一项检测设备与其他正在检测的充电桩冲突而浪费过长时间等待的情况。

图3 最优调度方案甘特图Fig.3 The gantt chart for optimal scheduling scheme

3.2 标准遗传算法求解优化调度结果

通过标准遗传算法得到的最优解收敛曲线如图4 所示。由图4 可知，标准遗传算法在迭代大概7 次后求解结果趋于稳定，检测完成时间大约为35.6 min。种群均值在迭代16 次左右后整体趋于较小扰动的稳定状态。

图4 标准遗传算法最优解收敛曲线Fig.4 The optimal convergence curve

基于标准遗传算法的充电桩检测调度结果甘特图如图5 所示。由图5 可知，采用经典遗传算法同时检测5 个充电桩的最短完工时间为36.05 min；只有在进行3-7、4-5、5-3、5-6 的项目检测时需等待，但即使需要等待，等待时间也不会很长。

图5 最优调度方案甘特图Fig.5 The gantt chart for optimal scheduling scheme

3.3 改进遗传算法求解优化调度结果

通过改进遗传算法得到的最优解收敛曲线如图6 所示。由图6 可知，改进遗传算法在迭代大概7 次后求解结果趋于稳定，检测完成时间大概为30.67 min。种群均值在迭代20 次后整体趋于稳定状态。可见，改进遗传算法具有较快的收敛速度，很适合求解充电桩检测调度问题。

图6 改进遗传算法最优解收敛曲线Fig.6 The optimal convergence curve

基于改进遗传算法的充电桩检测调度结果甘特图如图7 所示。由图7 可知，采用改进算法求解，同时检测5 个充电桩的最短完工时间为30.7 min；其检测流程紧密，仅仅在进行3-3 和1-5 的项目检测时需等待，且等待时间很短，在换检测项目的过程中没有浪费时间。

图7 最优调度方案甘特图Fig.7 The gantt chart for optimal scheduling scheme

3.4 对比分析

对比采用人工检测、标准遗传算法和改进遗传算法得到的3 组结果，可知：在相同设备条件下，人工安排充电桩检测的用时为46 min，采用标准遗传算法调度优化后，检测时间缩短为36.05 min，总检测时间较人工检测降低了约21.6%；通过改进遗传算法调度优化后，检测时间缩短为30.7 min，总检测时间较人工检测降低了约33.26%，较标准遗传算法降低了约14.8%。此外，通过多次调度优化求解，选取传统遗传算法和改进遗传算法多组种群均值变化数据的最大值、最小值及平均值，对稳定性进行了分析，其结果如表3 所示，可以发现改进遗传算法有着比标准遗传算法更好的稳定性和收敛性，降低了由于人工主观判断而造成的检测错误率，减少检测人员的工作压力。可见，通过改进遗传算法对充电桩进行检测，可提高充电桩的检测效率。

表3 传统、改进遗传算法均值数据统计表Tab.3 Traditional and improved genetic algorithm mean data statistical table

4 结束语

本文以充电桩总检测完成时间为目标函数，将充电桩的检测设备、检测设备的检测顺序、充电桩的检测顺序和同时刻检测的充电桩数量等诸多基本信息作为约束条件，建立了充电桩检测调度优化模型。通过采用轮盘赌算子选择出适应度较高的个体进入下一代群体，以POX 为交叉算子，设计了基于工序变异和设备变异的双变异算子，并添加初始化因子和精英策略对遗传算法进行了改进，进而对充电桩检测调度优化问题进行求解。优化后的结果表明，总检测时间大大降低，有效降低了人工成本，减少了人工的主观选择错误，进而提升了充电桩检测效率。本文对充电桩检测优化调度问题进行了求解，将来可拓展的工作包括考虑调度过程中的经济成本[22]、考虑充电桩最优检测时段等。