非均衡空間下考慮性能退化的充電設施聯合檢修路徑

諶微微，許茂增，邢青松

(重慶交通大學經濟與管理學院，重慶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種算法對最短路徑模型進行求解，結果顯示遺傳禁忌搜索算法的路徑最優。通過制定檢修機制，可逐步認識充電設施性能退化規律，進一步可不斷優化檢修周期和定點檢修方案。此外，在以下方面可繼續深入研究：基于現階段充電設施分布，后期可引入不同區域的動態充電需求，進一步對充電設施進行布局優化；或充電設施數量進一步增加，布局基本穩定，可將大區域進一步分割為若干個小區域，尋求更優的檢修路徑；或待理清充電設施性能退化規律后可將其作為一個參數加入聯合檢修計劃中，可提升檢修效率。