非均衡空間下考慮性能退化的充電設(shè)施聯(lián)合檢修路徑

諶微微，許茂增，邢青松

(重慶交通大學(xué)經(jīng)濟(jì)與管理學(xué)院，重慶400074)

《節(jié)能與新能源汽車產(chǎn)業(yè)發(fā)展規(guī)劃(2012—2020年)》和《汽車產(chǎn)業(yè)中長期發(fā)展規(guī)劃》中明確了中國以純電驅(qū)動為主的新能源汽車產(chǎn)業(yè)發(fā)展戰(zhàn)略[1-2]，實施該戰(zhàn)略的重要保障便是充電基礎(chǔ)設(shè)施建設(shè)，而充電便利性是充電基礎(chǔ)設(shè)施建設(shè)的重要指標(biāo)，亦是影響新能源汽車推廣的首要和最重要因素。伴隨新能源汽車產(chǎn)業(yè)的發(fā)展，以充電樁為代表的充電設(shè)施網(wǎng)絡(luò)快速擴(kuò)展，據(jù)權(quán)威數(shù)據(jù)統(tǒng)計，目前中國充電樁總量已達(dá)到45萬個，公共充電樁達(dá)到21萬個，成為充電樁保有量最多的國家。不過，在充電設(shè)施建設(shè)時運營商主要從運營成本[3]、充電需求[4-5]、場地[6]等方面考慮，導(dǎo)致充電設(shè)施分布出現(xiàn)低覆蓋度、布局疏密非均衡性等現(xiàn)象。即使在建設(shè)時考慮了充電需求分布，但在運營中由于充電設(shè)施固有的性能退化屬性及缺乏專業(yè)的設(shè)施檢修導(dǎo)致出現(xiàn)了局部冗長排隊與“死樁”并存的利用率極度不平衡等現(xiàn)象。而目前對充電設(shè)施的研究多集中于充電設(shè)施規(guī)劃布局[7-8]、運營成本[9]、合作機(jī)制[10]等方面，鮮有涉及充電設(shè)施檢修方案的研究。

然而，對于成熟生產(chǎn)運營系統(tǒng)，預(yù)防性維護(hù)、修理等一系列檢修活動通常是定期安排的。李二霞等[11]、卞建鵬等[12]、Wang等[13]、劉志文等[14]優(yōu)化了電力設(shè)施檢修方案，使其維護(hù)成本最低；劉增民[15]、吳晨愷等[16]研究了動車組在各項標(biāo)準(zhǔn)限值約束下檢修的最佳間隔周期。對于以上性能退化屬性較為明確的運營系統(tǒng)，其檢修方案優(yōu)化主要從降低成本、調(diào)整周期等方面開展研究，而對于充電設(shè)施這類性能退化規(guī)律尚待明確的新興運營系統(tǒng)，還未建立有效的檢修計劃和機(jī)制，其研究重點存在較大差異。由于在技術(shù)上的退化規(guī)律尚不明確，而導(dǎo)致充電設(shè)施不能像智能電網(wǎng)等成熟運營系統(tǒng)一樣進(jìn)行定點檢修，設(shè)計檢修方案和制定間隔周期便成為研究難題。非均衡分布[17]狀態(tài)下，充電需求量大或充電便捷度高的充電設(shè)施更為頻繁使用，更易出現(xiàn)故障，前期新能源汽車用戶的使用體驗對持觀望態(tài)度中的消費者有較大的影響，因而在眾多充電設(shè)施品類技術(shù)退化規(guī)律尚不明確的情況下保證全域范圍內(nèi)充電設(shè)施良好的運行狀態(tài)對新能源汽車進(jìn)一步推廣具有重要意義。故而，建立非均衡空間下考慮性能退化的充電設(shè)施檢修機(jī)制是其首要任務(wù)，可使所有充電設(shè)施在合理間隔周期內(nèi)都能接受檢修，恢復(fù)最優(yōu)或接近最優(yōu)性能的狀態(tài)。

針對充電設(shè)施多運營商、低覆蓋度、布局疏密不均、性能退化規(guī)律不明等問題，通過聯(lián)合組建專業(yè)維護(hù)團(tuán)隊定期對區(qū)域內(nèi)所有充電設(shè)施進(jìn)行故障排查、檢修是較為有效的途徑，既有利于提高新能源汽車充電便利性，又能較快掌握充電設(shè)施性能退化規(guī)律以促進(jìn)技術(shù)進(jìn)步。鑒于此，針對區(qū)域內(nèi)非均衡分布且性能退化規(guī)律尚不明確的充電設(shè)施，首先提出通過制定各運營商聯(lián)合檢修機(jī)制確保充電設(shè)施性能可滿足新能源汽車用戶充電需求；接著，建立充電設(shè)施聯(lián)合檢修路徑模型；然后，采用基于密度的聚類算法(density-based spatial clustering of applications with noise，DBSCAN)將區(qū)域內(nèi)充電設(shè)施按照分布密度進(jìn)行聚類，設(shè)置充電設(shè)施虛擬檢修點；最后，以虛擬檢修點的地址位置信息為基礎(chǔ)，運用遺傳禁忌搜索算法對聯(lián)合檢修路徑進(jìn)行研究，以使維護(hù)團(tuán)隊單次檢修的總路程最短。

1 非均衡空間下充電設(shè)施性能退化問題描述

受運營成本、充電需求、場地等實際條件的限制，運營中的充電設(shè)施分布出現(xiàn)低覆蓋度、布局疏密不均、各充電運營商的充電設(shè)施性能不盡相同、充電設(shè)施可靠性參差不齊等現(xiàn)象。當(dāng)呈現(xiàn)出這種非均衡分布狀態(tài)時，可能導(dǎo)致充電需求量大或充電便捷度高的充電設(shè)施更為頻繁出現(xiàn)故障，而各類充電設(shè)施技術(shù)退化屬性尚不明確，加之各運營商之間充電設(shè)施狀態(tài)未實現(xiàn)信息互聯(lián)互通及自動故障申告，無法進(jìn)行定點檢修，因而現(xiàn)階段進(jìn)行全域范圍內(nèi)充電設(shè)施進(jìn)行檢修需求更為迫切，以期提高新能源汽車充電便利性、加快掌握各類充電設(shè)施性能退化規(guī)律。各充電設(shè)施使用過程中固有的性能退化屬性仍然存在，若沒有外界力量及時進(jìn)行檢修，其性能退化量快速增加，一旦達(dá)到某一臨界值時，充電設(shè)施喪失充電功能屬性而發(fā)生失效，過程如圖1所示，圖中Ls為充電設(shè)施性能失效閾值，X(t)為充電設(shè)施性能退化量。在不進(jìn)行檢修的情況下，充電設(shè)施性能退化量X(t)隨著時間t的延長而遞增，當(dāng)工作到T時刻時，其性能退化量達(dá)到閾值Ls，充電設(shè)施失效。

圖1 充電設(shè)施性能退化過程Fig.1 Performance degradation process of charging facilities

當(dāng)加入檢修活動后充電設(shè)施的性能退化狀態(tài)如圖2所示。在有維護(hù)活動時，充電設(shè)施性能退化量X(t)會在檢修時刻ti(i∈N+)被恢復(fù)到最小值，然后恢復(fù)原有工作狀態(tài)。與圖1進(jìn)行對比，圖2的充電設(shè)施性能退化呈現(xiàn)兩個特點，即間斷性和突變性。充電設(shè)施性能退量因檢修而恢復(fù)到最小值，在檢修時刻出現(xiàn)間斷點，但隨著檢修次數(shù)的增加，每次檢修后充電設(shè)施的性能退化量增加幅度越來越大。檢修活動雖不能無限制延長充電設(shè)施使用壽命，但在一定程度上有利于延緩其性能退化過程并及時恢復(fù)原有工作狀態(tài)，提高充電用戶的便利性。

圖2 檢修條件下充電設(shè)施性能退化過程Fig.2 Degradation of charging facility performance under maintenance conditions

針對充電設(shè)施這種固有的性能退化屬性及技術(shù)上的退化規(guī)律尚不明確的問題，提出通過聯(lián)合各充電設(shè)施運營商建立充電設(shè)施檢修機(jī)制，在一定間隔周期對區(qū)域內(nèi)充電設(shè)施進(jìn)行全面檢修，確保充電設(shè)施保持良好工作狀態(tài)以滿足新能源汽車用戶充電需求。然而，在現(xiàn)階段不能明確其技術(shù)性能退化規(guī)律的情況下，無法從檢修周期及總體檢修時間方面開展研究，聯(lián)合檢修路徑規(guī)劃則成為降低檢修成本的關(guān)鍵途徑。

2 充電設(shè)施聯(lián)合檢修路徑模型

2.1 定義變量

通過一個有向圖G=(V,A)來定義被檢修的充電設(shè)施及所需經(jīng)過路徑形成的網(wǎng)絡(luò)。其中，A表示所有可行路徑的集合，V表示充電設(shè)施檢修節(jié)點集合。

充電設(shè)施檢修點為1，2，3，…，m，…，n，工作人員從檢修點m出發(fā)，經(jīng)過檢修點m+1，m+2，…，m-1各一次后再返回檢修點m。設(shè)檢修點i和j間的距離為dij(i≠j)。

2.2 模型建立

設(shè)xij為檢修路徑?jīng)Q策變量，則

(1)

在考慮總檢修路徑最短的情況下可設(shè)定目標(biāo)函數(shù)為

(2)

約束條件為

(3)

(4)

此外，還需要滿足

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

(5)

(6)

3 聯(lián)合檢修路徑優(yōu)化算法

3.1 充電設(shè)施檢修點聚類

一定區(qū)域范圍內(nèi)充電設(shè)施數(shù)據(jù)較大，若以每一個實際充電設(shè)施為節(jié)點將不便于進(jìn)行數(shù)據(jù)處理，且沒有必要將距離非常接近的充電設(shè)施分開來研究，因此考慮設(shè)置虛擬檢修點，即以充電設(shè)施的實際位置為依據(jù)，將實際距離接近的充電設(shè)施聚集成一個檢修點，并以最終聚類成的虛擬檢修點地理位置為依據(jù)建立表示各虛擬檢修點間車行距離的鄰接矩陣。對于非均質(zhì)分布的區(qū)域，采用基于分布密度的DBSCAN算法將區(qū)域內(nèi)充電設(shè)施進(jìn)行聚類，形成充電設(shè)施虛擬檢修點。

3.1.1 算法定義

E領(lǐng)域：給定檢修點半徑為E內(nèi)的區(qū)域都為該檢修點E的領(lǐng)域。

核心對象：若給定檢修點E領(lǐng)域的充電設(shè)施數(shù)量或服務(wù)能力大于等于領(lǐng)域密度minPts，則該檢修點為核心對象。

直接密度可達(dá)：對于檢修點集合D，如果檢修點q在檢修點p的E領(lǐng)域內(nèi)，且p為核心對象，那么檢修點q從檢修點p直接密度可達(dá)。

密度可達(dá)：對于檢修點集合D，給定一串檢修點p1，p2，…，pn，p=p1，q=pn，若檢修點pi從pi-1直接密度可達(dá)，那么檢修點q從檢修點p密度可達(dá)。

密度相連：存在檢修點集合D中的一點，如果檢修點o到檢修點p和檢修點q都是密度可達(dá)的，那么檢修點q和檢修點p密度相聯(lián)。

3.1.2 算法步驟

步驟1：根據(jù)實際檢修能力，確定E領(lǐng)域及領(lǐng)域密度minPts的取值。

步驟2：標(biāo)記所有檢修點為unvisited。

步驟3：隨機(jī)選擇其中一個unvisited作為檢修點p。

步驟4：標(biāo)記檢修點p為visited。

步驟5：判斷檢修點p領(lǐng)域中檢修點個數(shù)。若檢修點p的E領(lǐng)域至少有minPts個檢修點，創(chuàng)建一個新簇C。

步驟6：令N為檢修點p的E領(lǐng)域中的對象集合，檢查集合N中的每個檢修點p。若p是unvisited，則重新標(biāo)記為visited；若p的E領(lǐng)域至少有minPts個檢修點，則把這些檢修點統(tǒng)統(tǒng)添加到集合N中；若p還不是任何簇的成員，則把p添加到C；停止檢查，輸出簇C；否則標(biāo)記p為噪聲；轉(zhuǎn)到步驟4。

步驟7：直到?jīng)]有標(biāo)記為unvisited的檢修點為止。

3.2 聯(lián)合檢修路徑優(yōu)化算法

遺傳算法(genetic algorithm, GA)可以從解空間的多點出發(fā)進(jìn)行自我學(xué)習(xí)式廣泛探索，能求解大規(guī)模多目標(biāo)函數(shù)的全局優(yōu)化問題。禁忌搜索算法(tabu search, TS)則使用禁忌準(zhǔn)則避免無效循環(huán)計算，并采用藐視準(zhǔn)則接受差解，以保證不同范圍有效路徑的探測，能實現(xiàn)路徑的全局逐步尋優(yōu)。綜合遺傳算法較強(qiáng)的全局尋優(yōu)能力和禁忌搜索算法較強(qiáng)的局部搜索能力，遺傳禁忌搜索算法(GA-TS)更加適用于求解充電設(shè)施聯(lián)合檢修的路徑優(yōu)化問題。它包含7個核心元素。

鄰域：變換初始路徑中途徑點的位置，產(chǎn)生的新路徑集合稱為初始路徑的鄰域。依次采用交叉、變異構(gòu)建初始路徑鄰域。

移動：初始路徑轉(zhuǎn)移到它的鄰域中的最優(yōu)回路，稱為一次移動。被采納的移動即為下一次迭代過程的初始回路。

候選解集：初始回路的鄰域子集。遺傳算法的選擇算子能引導(dǎo)算法朝著搜索空間中可能的最優(yōu)區(qū)域進(jìn)行探測。選用精英選擇法來加快禁忌搜索速度，從初始回路的鄰域中挑選出最優(yōu)的10個回路構(gòu)成候選解集，參與禁忌搜索。

禁忌表：一種存放禁忌對象的數(shù)據(jù)結(jié)構(gòu)。一般情況下，禁忌表中的對象不能被選作為產(chǎn)生鄰域的新解，以防止出現(xiàn)循環(huán)搜索和陷入局部最優(yōu)解。

藐視準(zhǔn)則：當(dāng)候選解集中的最優(yōu)對象比歷史最優(yōu)解好時，即使該對象被禁忌，仍可以替代歷史最優(yōu)解，作為下一次迭代過程的初始解，即特赦該禁忌對象。還有一種特赦情況是，若候選解集中的所有對象都被禁忌，則特赦最優(yōu)候選解。

終止條件：算法達(dá)到預(yù)設(shè)的迭代次數(shù)，或者在固定周期內(nèi)連續(xù)求得的最優(yōu)解不變，二者滿足其一即可終止計算過程，其中固定周期設(shè)置為算法迭代次數(shù)的0.6倍。

具體算法實現(xiàn)過程如圖3 所示。

圖3 遺傳禁忌搜索算法過程Fig.3 Genetic tabusearch algorithm

4 案例分析

4.1 數(shù)據(jù)處理

重慶是重要的汽車產(chǎn)業(yè)基地，近年來也著力推廣新能源汽車。為了支持新能源汽車產(chǎn)業(yè)的發(fā)展，截至2018年9月，重慶市主城八區(qū)已建成并投入使用的公共充電設(shè)施共計3 592個。使用Lenovo臺式電腦，CPU主頻為3.70 GHz的Inter Core i3-6100，操作系統(tǒng)為Windows10(64位)，以現(xiàn)有充電設(shè)施的地理位置信息為基礎(chǔ)，應(yīng)用PYTHON語言編寫DBSCAN算法將充電設(shè)施聚集成若干個虛擬檢修點，并以聚類結(jié)果作為輸入，用MATLAB對聯(lián)合檢修路徑模型求解。按照DBSCAN算法，設(shè)置E領(lǐng)域為100 m、領(lǐng)域密度閾值minPts為20，將3 592個充電設(shè)施聚類得到194個虛擬檢修點，將虛擬檢修點用ARCGIS10.2進(jìn)行可視化顯現(xiàn)，如圖4所示。因此，可將各虛擬檢修點進(jìn)行標(biāo)號，分別為1、2、…、194，并將虛擬檢修點間的車行距離建立了194×194的鄰接矩陣。

圖4 虛擬檢修點聚類圖Fig.4 Clustering of virtual maintenance points

4.2 結(jié)果分析

用3種算法分別運行10次，對虛擬檢修點構(gòu)建的194×194車行距離矩陣最短路徑模型進(jìn)行求解，記錄最短檢修路徑長度。具體結(jié)果如表1所示。

表1 最短路徑模型求解結(jié)果Table 1 Solution of shortest path model

從解的穩(wěn)定性和計算效率兩方面對算法解的質(zhì)量進(jìn)行比較[18]。解的穩(wěn)定性用相對最好解百分比g表示，計算公式為

(7)

式(7)中：S為3種算法各自的最短檢修路徑長度；B為所有算法中的最短路徑長度；g為不小于0的值，g值越小，解的穩(wěn)定性越高。計算效率用平均計算時間表示，時間越短，計算效率越高。解的質(zhì)量比較如表2所示。

表2 解的質(zhì)量比較Table 2 Quality comparison of results

根據(jù)3種算法求解結(jié)果及解的質(zhì)量比較，遺傳算法(GA)解的穩(wěn)定性優(yōu)于禁忌搜索算法(TS)，但計算效率方面存在一定的局限性；禁忌搜索算法(TS)計算效率最高，但解的穩(wěn)定性方面不太理想；遺傳禁忌搜索算法(GA-TS)所得到的檢修路徑長度最短，解的穩(wěn)定性最好，由于在其求解過程中變異算子是一個搜索過程，增加了計算時間，使得計算效率方面無法體現(xiàn)優(yōu)勢，然而在一定群體規(guī)模下增加的計算時間是可以接受的，且從解決實際問題的角度來看，通常更為關(guān)注解的穩(wěn)定性。因此，采用GA-TS所求解的最短檢修路徑作為聯(lián)合檢修的依據(jù)，檢修路徑如圖5所示。圖5中涵蓋了所有虛擬檢修點，且每次檢修只經(jīng)過一次，減少了因無檢修路徑規(guī)劃造成的無效往返，可有效節(jié)約維修團(tuán)隊的有限資源，各運營商現(xiàn)有充電設(shè)施性能都能滿足新能源汽車用戶的充電需求，對提升其充電便利性作用顯著。

圖5 聯(lián)合檢修路徑Fig.5 Path for joint maintenance

5 結(jié)論

基于充電設(shè)施呈現(xiàn)的非均質(zhì)分布狀態(tài)，結(jié)合目前運營中由于充電設(shè)施固有性能退化屬性導(dǎo)致的局部冗長排隊與“死樁”并存的利用率極度不平衡等現(xiàn)象，為滿足新能源汽車用戶的充電需求，在充電設(shè)施技術(shù)上的性能退化規(guī)律不明的情況下，提出組建專業(yè)維護(hù)團(tuán)隊對區(qū)域內(nèi)所轄的所有充電設(shè)施進(jìn)行聯(lián)合檢修。在建立充電設(shè)施聯(lián)合檢修路徑模型的基礎(chǔ)上，根據(jù)DBSCAN聚類算法，將重慶市主城八區(qū)截至2018年9月已建成運營的充電設(shè)施聚類為194個虛擬檢修點，依據(jù)各虛擬檢修點的地理位置數(shù)據(jù)，基于聯(lián)合檢修最短路程策略，構(gòu)建194×194的車行距離矩陣，并采用3種算法對最短路徑模型進(jìn)行求解，結(jié)果顯示遺傳禁忌搜索算法的路徑最優(yōu)。通過制定檢修機(jī)制，可逐步認(rèn)識充電設(shè)施性能退化規(guī)律，進(jìn)一步可不斷優(yōu)化檢修周期和定點檢修方案。此外，在以下方面可繼續(xù)深入研究：基于現(xiàn)階段充電設(shè)施分布，后期可引入不同區(qū)域的動態(tài)充電需求，進(jìn)一步對充電設(shè)施進(jìn)行布局優(yōu)化；或充電設(shè)施數(shù)量進(jìn)一步增加，布局基本穩(wěn)定，可將大區(qū)域進(jìn)一步分割為若干個小區(qū)域，尋求更優(yōu)的檢修路徑；或待理清充電設(shè)施性能退化規(guī)律后可將其作為一個參數(shù)加入聯(lián)合檢修計劃中，可提升檢修效率。