李晶晶，張永敏，田桂林，崔勝勝，嚴 潔

（國網青海省電力公司營銷服務中心，電能計量設備檢定檢測技術實驗室，青海 西寧 810000）

隨著我國雙碳目標的提出，快速發(fā)展的新能源電動汽車已經作為解決能源短缺和環(huán)境污染的有效途徑之一。充電樁作為電動汽車的主要設施，扮演著越來越重要的角色。充電樁是否安全可靠對電動汽車的推廣和發(fā)展，以及對新能源產品用戶是否擁有良好的體驗感和信任度都至關重要。相應的，對充電樁進行必要的檢測，提高充電樁檢測效率也成為充電樁研究領域的重中之重。

在充電樁檢測方面，目前主要有人工檢測與系統(tǒng)自動檢測 2 種方式。對于傳統(tǒng)的人工檢測方式，接線、拆線等項目均采用同一套檢測設備，檢測一臺充電樁往往需要大量時間。同時，人工檢測主觀誤差較大，且檢測設備不夠穩(wěn)定。這些問題嚴重制約了充電樁檢測的效率和精度。

針對人工檢測速度慢等問題，學者們著力研發(fā)充電樁自動測試系統(tǒng)。例如，鐘勁松等[1]研發(fā)了一套充電樁檢定系統(tǒng)，為電動汽車充電樁相關試驗提供了測試環(huán)境和方法的參考。姜立標等[2]研發(fā)了一種基于LabVIEW 的電動汽車直流充電樁檢測系統(tǒng)，該系統(tǒng)操作方便快捷，提高了充電樁的檢測效率。朱彬等[3]研究了供電設備與電動汽車之間的互操作性測試，并設計了一種充電樁檢測平臺[4]，實現了對充電樁進行互操作性和電性能測試，預防了人為讀數誤差，提高了檢測的準確性。

隨著現代新能源產業(yè)的蓬勃發(fā)展，關于充電樁檢測領域研究的相關理論也逐漸豐富。王斌[5]從新能源充電樁的檢測技術入手，對智能感應在其中的應用進行了分析，提出了充電樁模擬檢測方案，拓展性地豐富了新能源汽車充電樁檢驗檢測相關理論和方法。丁建順等[6]以電動汽車交直流充電樁技術為基礎，提出了一種基于區(qū)塊鏈技術的電動汽車充電樁共享檢測方案，保證了無源狀態(tài)下的數據存儲與通信安全。上述研究表明，系統(tǒng)自動檢測充電樁的方式實質性地提高了檢測的準確率和工作效率，但優(yōu)秀的檢測平臺必須考慮兼容性與可擴展性，需要支持不同廠家、不同型號產品的檢測[7]；因此，對檢測平臺提出了非常高的要求。

為了進一步提高充電樁檢測效率，本文在已有自動檢測系統(tǒng)平臺的基礎上，結合車間調度問題的特點，對充電樁檢測調度優(yōu)化問題進行研究。車間調度問題是指M臺機器，加工N個作業(yè)，其中作業(yè)i包含工序數為Li，各工序的加工時間已確定，每個作業(yè)必須按照工序的先后順序進行加工。在對多個充電樁同時進行檢測時，會因選擇不同的調度方案而直接影響整體的檢測效率，還需要對多個項目一一檢測才能確認其性能是否真正安全可靠。因此，充電樁檢測問題亦屬于柔性開放車間調度問題，是一種典型的NP-Hard 問題。在車間調度優(yōu)化領域，國內外學者已經做了研究，取得了一些成果。Bai 等[8]以最長完工時間為目標，分別研究了柔性開放車間調度問題的靜態(tài)和動態(tài)問題，利用有界性假設證明了廣義密集調度算法的漸近最優(yōu)性。文獻[9]提出了一種粒子群算法，通過將其應用于分層多目標框架來解決具有不確定加工時間和靈活交貨期的多目標開放車間產生的調度問題。文獻[10]介紹了一種改進人工蜂群算法，用序列對問題的解進行編碼，其計算結果表明，該算法能在大規(guī)模問題中取得最佳的求解效果，但不能在小范圍問題中提供精確解。針對在車間調度過程中工件的選擇優(yōu)先級規(guī)則對其調度結果有較大影響[11]的問題，王秋蓮等[12]提出了一種改進的多目標候鳥優(yōu)化算法，用于求解高維多目標問題，算例和實例驗證了該算法在實際加工中能夠給予決策者更好的選擇。

此外，還有采用基于多智能體的深度強化學習算法[13]、結合模擬退火的多目標COOT 算法[14]和遺傳算法等對柔性車間調度的多目標優(yōu)化問題求解。因遺傳算法具有全局搜索快的優(yōu)點特性，王冠等[15]針對非支配排序遺傳算法進行自適應改進，采用獨立的交叉和變異操作對工序與設備進行排序及分配的調整，其結果表明采用該改進算法，最大完工時間、加工能耗、加工設備總負載和延期時間均得到顯著改善，有效提高了生產管理效率。田志強等[16]提出了一種基于改進非支配排序遺傳算法的柔性作業(yè)車間多目標節(jié)能分批調度方法，解決了無方向性生成初始解導致算法收斂精度低、速度慢的問題，使初始解的生成具有方向性。上述研究表明，基于遺傳算法的求解方法雖改善了諸多問題，但易早熟收斂，易陷于局部最優(yōu)。

可見，粒子群算法、人工蜂群算法和遺傳算法等雖然已經應用于解決一些開放式車間調度問題，但是仍然存在不能在小范圍內提供精確解，以及缺少對實際應用中因選擇不同檢測項目機器、檢測項目之間的先后順序和檢測調度方案等的研究而嚴重影響整體檢測效率的問題。因此，本文以充電樁檢測完成時間最短為目標，建立充電樁檢測優(yōu)化模型，并采用改進遺傳算法對其進行求解，以此提高充電樁檢測效率。

1 充電樁檢測調度優(yōu)化問題建模

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 難題。因此，本文采用以仿自然體算法為主的啟發(fā)式算法進行求解。在啟發(fā)式算法中，被應用較多的遺傳算法具有強大的全局搜索能力，且易于與其他算法相結合，同時，搜索從群體出發(fā)時可進行多個個體同時比較，具備信息處理的并行性和操作的簡明性，是一種具有良好適應性和可規(guī)?；蠼獾姆椒?。為此，本文結合充電樁檢測會因選擇檢測項目、機器間先后順序的不同而有不同結果的實際特點，設計了雙變異算子，對遺傳算法的迭代過程進行改進。在此基礎上添加初始化因子和精英策略，對標準遺傳算法[17]在求解充電樁檢測調度優(yōu)化問題時存在局部搜索能力差和容易過早收斂等問題進行改進，采用改進的遺傳算法對所建立模型進行求解。

2.1 基于標準遺傳算法的充電樁檢測調度優(yōu)化

采用標準遺傳算法求解充電樁檢測調度優(yōu)化問題的流程圖如圖1 所示，主要步驟描述如下。

圖1 基于標準遺傳算法的充電樁檢測調度優(yōu)化流程圖Fig.1 Flow chart of charging pile detection scheduling optimization method based on standard genetic algorithm

第1 步，輸入充電樁、檢測設備和檢測項目時間等數據。

第2 步，隨機初始化各充電樁檢測工序順序和檢測設備順序，并將檢測順序與檢測設備分別進行編碼，構造初始種群P(t)。

第3 步，將所有充電樁最大檢測完成時間設為目標函數，對初始種群P(t)進行適應度計算。然后，評價個體適應度值，檢測時間越短，適應度越高。

第4 步，采用輪盤賭策略選擇種群中適應度較高的個體進入下一代種群。輪盤賭選擇的基本思想是各個個體被選中的概率與其適應度大小成正比，將種群中所有個體的適應度值進行累加然后歸一化，最后隨機對落在區(qū)域對應的個體進行選取。

第5 步，對選擇出的個體進行交叉和變異操作，生成新的子代個體。

第6 步，將新的種群個體帶入目標函數中進行計算，在多次迭代方案中選出檢測用時最少的個體，得到最優(yōu)調度方案。

2.2 基于改進的遺傳算法的充電樁檢測調度優(yōu)化

上述標準遺傳算法具有良好的適應性和可規(guī)?；蠼獾膬?yōu)點，但其局部搜索能力差和容易過早收斂等問題未得到解決。因此，本文采用改進的遺傳算法求解充電樁檢測調度優(yōu)化，其流程圖如圖2所示，主要步驟描述如下。

圖2 基于改進遺傳算法的充電樁檢測調度優(yōu)化流程圖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 步，啟發(fā)式生成檢測項目排序串、檢測設備串和檢測時間。改進算法的可行解由待檢測充電樁的工件生成工序串、檢測項目串、檢測設備串和檢測時間串共同組成的一條染色體串來表示。

第3 步，采用輪盤賭算子選擇種群中適應度較高的個體進入下一代進行迭代。因每個部分被選中的概率與其適應度值成比例，本文直接選取所有充電樁的最大檢測完成時間為目標函數，Cmax作為適應度函數來計算群體中個體的適應度值。因此，適應度函數的數學表達式如公式（4）所示。

第4 步，隨機選擇2 個父代染色體進行優(yōu)先操作交叉(precedence peration crossover，POX)，生成新個體。交叉是遺傳算法最重要的操作，決定著遺傳算法的全局搜索能力。遺傳算法假定，若一個個體的適應度較好，那么基因鏈碼中的某些相鄰關系片段是好的，并且由這些鏈碼所構成的其他個體的適應度也較好。本文選用POX 作為交叉算子[18]，它相對于基于作業(yè)的順序交叉(job-based order crossover，JOX)算子、子序列交換交叉(subse-quence exchange crossover，SXX)算子、設置分區(qū)交叉(setpartition crossover，SPX)算子、優(yōu)先級保留交叉(precedence preservation crossover，PPX)算子能夠更好地繼承父代優(yōu)良特征并且其子代總是可行的。

第5 步，采用基于工序變異和設備變異的雙變異算子生成新個體。對于工序編碼變異來說，其過程為從父代個體中隨機選擇一個關鍵工序，在滿足內部順序約束的條件下，將選擇的工序插到其最近的關鍵工序之前。設備變異則通過單點變異的方式進行。本文考慮到問題的復雜性，設計了基于工序變異和基于設備變異的雙變異算子，來保持種群的多樣性，提高算法的全局搜索能力。

第6 步，采用初始化方法生成部分新個體，以提高算法的全局搜索能力。初始化時首先確定各充電樁檢測工序之間的排序，然后隨機確定各充電樁檢測工序對應的檢測項目，最后根據檢測項目隨機化確定各充電樁檢測工序對應的檢測設備和檢測時間。

第7 步，采用精英策略，篩選父代種群和新一代種群中適應度較高的個體作為新一代種群，以提升算法的收斂速度。精英策略是利用種群精英個體信息來改進算法性能，將群體進化過程中出現的最好個體不進行配對交叉而直接復制到下一代中。本文為了保持群體的規(guī)模不變，若精英個體被加入到新一代群體中，則將新一代群體中適應度值最小的個體被淘汰。

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 臺進行檢測。本文將根據以上設置的各參數信息，做人工現場檢測、標準遺傳算法求解優(yōu)化和改進遺傳算法求解優(yōu)化3 組試驗，對比其檢測時間，以驗證所提改進遺傳算法的可行性、有效性和優(yōu)越性。

3.1 人工現場檢測結果

截至目前，人工現場檢測仍然是充電樁檢測的主要方式[20]。本文通過現場查勘檢測人員檢測5 臺充電樁的各個操作環(huán)節(jié)，統(tǒng)計其工序及時間，得到調度結果甘特圖如圖3 所示。由圖3 可知，采用人工現場檢測同時檢測5 個充電樁的最短完工時間為46 min。圖3 中同一充電樁用相同的顏色表示，并標出了對應的充電樁序號和檢測順序工序號。以藍色代表的第3 個充電樁工作流程為例進行解釋：3-1 表示第3 個充電樁的第1 道工序，加工設備為S4，檢測項目為3 號絕緣性能試驗，加工時間為2.2 min，之后的檢測循序進行。在人工檢測過程中檢測項目和設備的選擇都需檢測人員自定，需要檢測人員根據豐富的工作經驗和扎實的理論基礎，綜合性地分析問題，并采取針對性的方案去解決問題[21]。若檢測人員經驗不足或是主觀判斷錯誤，就會嚴重影響檢測正確率，就會出現3-4 這種已經結束上一項檢測但因為選擇下一項檢測設備與其他正在檢測的充電樁沖突而浪費過長時間等待的情況。

圖3 最優(yōu)調度方案甘特圖Fig.3 The gantt chart for optimal scheduling scheme

3.2 標準遺傳算法求解優(yōu)化調度結果

通過標準遺傳算法得到的最優(yōu)解收斂曲線如圖4 所示。由圖4 可知，標準遺傳算法在迭代大概7 次后求解結果趨于穩(wěn)定，檢測完成時間大約為35.6 min。種群均值在迭代16 次左右后整體趨于較小擾動的穩(wěn)定狀態(tài)。

圖4 標準遺傳算法最優(yōu)解收斂曲線Fig.4 The optimal convergence curve

基于標準遺傳算法的充電樁檢測調度結果甘特圖如圖5 所示。由圖5 可知，采用經典遺傳算法同時檢測5 個充電樁的最短完工時間為36.05 min；只有在進行3-7、4-5、5-3、5-6 的項目檢測時需等待，但即使需要等待，等待時間也不會很長。

圖5 最優(yōu)調度方案甘特圖Fig.5 The gantt chart for optimal scheduling scheme

3.3 改進遺傳算法求解優(yōu)化調度結果

通過改進遺傳算法得到的最優(yōu)解收斂曲線如圖6 所示。由圖6 可知，改進遺傳算法在迭代大概7 次后求解結果趨于穩(wěn)定，檢測完成時間大概為30.67 min。種群均值在迭代20 次后整體趨于穩(wěn)定狀態(tài)。可見，改進遺傳算法具有較快的收斂速度，很適合求解充電樁檢測調度問題。

圖6 改進遺傳算法最優(yōu)解收斂曲線Fig.6 The optimal convergence curve

基于改進遺傳算法的充電樁檢測調度結果甘特圖如圖7 所示。由圖7 可知，采用改進算法求解，同時檢測5 個充電樁的最短完工時間為30.7 min；其檢測流程緊密，僅僅在進行3-3 和1-5 的項目檢測時需等待，且等待時間很短，在換檢測項目的過程中沒有浪費時間。

圖7 最優(yōu)調度方案甘特圖Fig.7 The gantt chart for optimal scheduling scheme

3.4 對比分析

對比采用人工檢測、標準遺傳算法和改進遺傳算法得到的3 組結果，可知：在相同設備條件下，人工安排充電樁檢測的用時為46 min，采用標準遺傳算法調度優(yōu)化后，檢測時間縮短為36.05 min，總檢測時間較人工檢測降低了約21.6%；通過改進遺傳算法調度優(yōu)化后，檢測時間縮短為30.7 min，總檢測時間較人工檢測降低了約33.26%，較標準遺傳算法降低了約14.8%。此外，通過多次調度優(yōu)化求解，選取傳統(tǒng)遺傳算法和改進遺傳算法多組種群均值變化數據的最大值、最小值及平均值，對穩(wěn)定性進行了分析，其結果如表3 所示，可以發(fā)現改進遺傳算法有著比標準遺傳算法更好的穩(wěn)定性和收斂性，降低了由于人工主觀判斷而造成的檢測錯誤率，減少檢測人員的工作壓力?？梢姡ㄟ^改進遺傳算法對充電樁進行檢測，可提高充電樁的檢測效率。

表3 傳統(tǒng)、改進遺傳算法均值數據統(tǒng)計表Tab.3 Traditional and improved genetic algorithm mean data statistical table

4 結束語

本文以充電樁總檢測完成時間為目標函數，將充電樁的檢測設備、檢測設備的檢測順序、充電樁的檢測順序和同時刻檢測的充電樁數量等諸多基本信息作為約束條件，建立了充電樁檢測調度優(yōu)化模型。通過采用輪盤賭算子選擇出適應度較高的個體進入下一代群體，以POX 為交叉算子，設計了基于工序變異和設備變異的雙變異算子，并添加初始化因子和精英策略對遺傳算法進行了改進，進而對充電樁檢測調度優(yōu)化問題進行求解。優(yōu)化后的結果表明，總檢測時間大大降低，有效降低了人工成本，減少了人工的主觀選擇錯誤，進而提升了充電樁檢測效率。本文對充電樁檢測優(yōu)化調度問題進行了求解，將來可拓展的工作包括考慮調度過程中的經濟成本[22]、考慮充電樁最優(yōu)檢測時段等。