配網(wǎng)帶電作業(yè)車輛路徑優(yōu)化模型研究

李士動，陳　綱，金云奎，王　林

（國網(wǎng)山東省電力公司泰安供電公司，山東　泰安　271000）

0　引言

帶電作業(yè)是指在不停電狀態(tài)下對電網(wǎng)各電壓等級線路、設(shè)備進(jìn)行維護(hù)、檢修或改造，對于提升供電企業(yè)服務(wù)水平和經(jīng)濟(jì)效益、降低用戶停電損失有著十分重要的意義[1]。近年來，隨用戶供電可靠性要求的逐步提高，帶電作業(yè)以其能夠縮短停電時間甚至不需要停電的優(yōu)勢已發(fā)展成為配網(wǎng)檢修及維護(hù)的重要技術(shù)手段。以山東某一線城市為例，城區(qū)配網(wǎng)年帶電作業(yè)次數(shù)可達(dá)4000余次。

目前，對于配網(wǎng)帶電作業(yè)的研究主要集中在提升現(xiàn)場作業(yè)安全水平的新技術(shù)、新方法及新裝置[2-6]，而具體針對如何提升實(shí)際作業(yè)效率的研究，尚未見報道，隨著當(dāng)前配網(wǎng)帶電作業(yè)規(guī)模的不斷擴(kuò)大，這一問題的重要性愈發(fā)凸顯?，F(xiàn)實(shí)工作中，為了增強(qiáng)配網(wǎng)帶電作業(yè)的計劃性與可控性，保證工作順利開展，作業(yè)人員必須提前制訂下一個作業(yè)周期內(nèi)的工作計劃，一般以周為時間尺度，將眾多的工作任務(wù)分解至下一周的每一個工作日，同時確定每個工作日的作業(yè)車次與作業(yè)路徑。目前，工作計劃往往由作業(yè)人員根據(jù)自身經(jīng)驗(yàn)進(jìn)行“合理”的編制，然而基于人工的信息獲取、處理和計算能力畢竟是有限的，隨問題規(guī)模的增大，這一傳統(tǒng)方法便無法實(shí)現(xiàn)工作計劃的最優(yōu)化，導(dǎo)致大量時間與費(fèi)用的浪費(fèi)，大大降低了工作效率。尤其，絕緣斗臂車作為開展配網(wǎng)帶電作業(yè)的專用絕緣承載工具與交通工具，其油耗巨大，不合理的路徑選擇所帶來的行駛成本十分顯著。

帶電作業(yè)工作計劃要求車輛從作業(yè)中心出發(fā)后依次前往不同工作地點(diǎn)，完成相應(yīng)工作后返回，本質(zhì)上屬于車輛路徑問題（Vehicle Routing Problem，VRP）[7-11]，該問題起源于物流配送行業(yè)。 VRP 是多約束組合優(yōu)化問題，已被證明是NP完全問題，關(guān)于VRP的求解，目前主要存在精確法、啟發(fā)式算法和智能算法[7-11]。精確法包括動態(tài)規(guī)劃法和分支定界法，適合于小規(guī)模問題的求解；啟發(fā)式算法包括構(gòu)造法和兩階段法，求解效率較高，卻難以獲得最優(yōu)解；智能算法包括粒子群優(yōu)化算法、遺傳算法和蟻群算法等，具有應(yīng)用簡單、搜索速度快的優(yōu)點(diǎn)，已成為路徑優(yōu)化的主要方法。

通過優(yōu)化工作計劃提升作業(yè)效率與效益一直被忽視，為此本文將車輛路徑問題引入配網(wǎng)帶電作業(yè)領(lǐng)域，針對配網(wǎng)帶電作業(yè)工作特性建立路徑優(yōu)化模型，并采用改進(jìn)粒子群優(yōu)化算法進(jìn)行求解，最后通過兩個算例驗(yàn)證了所建模型的有效性。

1　配網(wǎng)帶電作業(yè)路徑優(yōu)化模型建立

1.1　問題分析

假設(shè)有多項帶電作業(yè)工作任務(wù)，最大可用作業(yè)車次已知，所有作業(yè)地點(diǎn)（包括帶電作業(yè)中心）之間的路徑距離、行駛用時和工作作業(yè)用時也為已知，現(xiàn)實(shí)中上述距離及時間數(shù)據(jù)可以通過配網(wǎng)地理信息系統(tǒng)（GIS）結(jié)合網(wǎng)絡(luò)地圖獲取。每車次車輛從作業(yè)中心出發(fā)，依次經(jīng)過位于其行駛路徑上的作業(yè)點(diǎn)并完成該點(diǎn)工作后返回中心，結(jié)束該車次當(dāng)日工作。路徑優(yōu)化的目標(biāo)就是找到最優(yōu)作業(yè)車次數(shù)與每車次最優(yōu)行駛路徑使總成本（行駛距離或時間）達(dá)到最小化，同時需要滿足如下約束條件：

1）完成計劃時間尺度內(nèi)的全部工作任務(wù)需求。

2）每車次路徑上的總作業(yè)用時不超過人員日最大勞動強(qiáng)度。帶電作業(yè)屬兼具“體力型”與“技能型”的高危工作，該約束的目的是通過限制勞動強(qiáng)度來提升作業(yè)人員的安全性。

3）每車次路徑上的總用時（包括總行駛用時和總作業(yè)用時）不超過日最大工時。

4）每車次路徑上的總油耗（包括總行駛油耗及總作業(yè)油耗）不超過車輛最大載油量。

5）每個作業(yè)點(diǎn)的工作只能由1輛車次完成，調(diào)用的車次不超過最大可用車次。

需要指出的是，最大可用作業(yè)車次等于計劃時間尺度內(nèi)的工作日數(shù)乘以作業(yè)車輛數(shù)。

1.2　路徑優(yōu)化數(shù)學(xué)模型

以全部作業(yè)車次的總行駛里程最小為目標(biāo)，建立如下路徑優(yōu)化模型：

約束條件

式中：K為最大可用作業(yè)車次數(shù)；nk為車次k完成的作業(yè)點(diǎn)數(shù)，nk為0則表示車次k沒有參與作業(yè)；為車次k中作業(yè)順序?yàn)閕的作業(yè)點(diǎn)兩作業(yè)順序相鄰點(diǎn)的距離；ti為作業(yè)點(diǎn)i的作業(yè)用時；Tmax1為日最大勞動時間；兩相鄰點(diǎn)的行駛用時；Tmax2為日最大工時；兩相鄰點(diǎn)行駛油耗；ci為作業(yè)點(diǎn)i的作業(yè)油耗；Cmax為車輛最大載油量；Rk1、Rk2分別為車次 k1、k2的作業(yè)點(diǎn)集合；M 為計劃周期內(nèi)的作業(yè)任務(wù)數(shù)。

式（3）～（5）分別表示每車次人員勞動強(qiáng)度約束、工時約束及車輛油耗限制，式（6）表示每項作業(yè)任務(wù)只能由1輛車次完成，式（7）～（8）表示完成計劃周期內(nèi)的作業(yè)任務(wù)需求。

2　混沌粒子群優(yōu)化算法

粒子群優(yōu)化（Particles Swarm Optimization，PSO）是一種基于群體智能的隨機(jī)尋優(yōu)算法[8-9]，由心理學(xué)家Kennedy博士和電氣工程師Eberhart博士根據(jù)鳥群的集體協(xié)作覓食行為而提出，具有概念簡明、收斂速度快、參數(shù)設(shè)置少的優(yōu)點(diǎn)。

PSO采用速度—位移模型，在適應(yīng)值函數(shù)的引導(dǎo)下實(shí)現(xiàn)個體與群體的全局最優(yōu)搜索。速度—位置更新的向量表達(dá)為

式中：Vi為第i個粒子的速度；Xi為第i個粒子的位置；Pi為第i個粒子的個體最優(yōu)位置；Pg為全局最優(yōu)位置；k為迭代次數(shù)；w為慣性權(quán)重；c1、c2為學(xué)習(xí)因子；r1、r2為[0，1]內(nèi)隨機(jī)數(shù)。

與其他智能算法類似，PSO在優(yōu)化復(fù)雜函數(shù)時也存在陷入局部最優(yōu)的問題，其根本原因?yàn)榱Ｗ佣鄻有缘娜狈εc喪失。為此，考慮利用混沌序列的隨機(jī)性與遍歷性來增強(qiáng)算法搜索的多樣性[12]：采用混沌序列生成初始粒子位置，保證初始粒子在解空間內(nèi)均勻分布；當(dāng)檢測到算法陷入局部最優(yōu)后，對最優(yōu)解進(jìn)行混沌變異，擾亂粒子當(dāng)前的搜索軌跡，以跳出局部最優(yōu)。

首先，對處于D維空間的n個粒子產(chǎn)生n個初始值 zk（1），并將 zk（1）代入 Logistic 映射經(jīng) D 次迭代，映射得到n條混沌序列。

其中，用于產(chǎn)生混沌序列的Logistic映射為

式中：μ為常數(shù)，μ∈[3.56，4]。

將得到的混沌序列代入式（12）逆映射得到粒子的初始位置：

式中：k=1，…，n；i=1，…，D；Lmax，i、Lmin，i分別為粒子第 i維取值的上、下限。

其次，當(dāng)檢測到算法搜索停滯時，對全局最優(yōu)解Pg=（xg，1，xg，2，…，xg，D） 進(jìn)行混沌變異，將 Pg代入式（13）映射到解空間作為混沌迭代的初值：

將 zg，i作為初值代入式（11）進(jìn)行若干次迭代產(chǎn)生混沌序列 z′g，i，再將 該序列 按式 （14）返回原解空間：

最終得到新的全局最優(yōu)解：

3　路徑優(yōu)化的混沌粒子群優(yōu)化算法

PSO適用于求解連續(xù)型變量問題，而VRP則是離散型組合優(yōu)化問題，為此構(gòu)造以下編碼與解碼方式，實(shí)現(xiàn)粒子位置與解的對應(yīng)。對于M個作業(yè)點(diǎn)與K輛車次的路徑優(yōu)化問題，以0代表作業(yè)中心，以正整數(shù)i表示第i個作業(yè)點(diǎn)，隨機(jī)生成作業(yè)點(diǎn)序列，并在序列中插入M-1個0，這樣就把作業(yè)點(diǎn)序列分為M段，每一段代表某車次的行駛路徑。每個粒子為K+M-1維向量。

例如，作業(yè)點(diǎn)數(shù)目為6、可用車次數(shù)為3，某粒子位置向量為[5 3 0 6 1 4 0 2]，則第1輛車的行駛路徑為0→5→3→0，第2輛的行駛路徑為0→6→1→4→0，第3輛車行駛路徑為0→2→0。采用這一編碼／解碼方式即可實(shí)現(xiàn)粒子群優(yōu)化算法對VRP問題的求解。

基于上述編碼／解碼方式，采用混沌PSO算法求解路徑優(yōu)化問題，步驟為：

1）算法初始化。設(shè)置PSO算法參數(shù)，輸入可用車次數(shù)及作業(yè)點(diǎn)之間的距離與時間矩陣。

2）通過混沌優(yōu)化生成初始種群。粒子位置向量每一維取值范圍為1～（K+M-1），速度向量每一維取值范圍為-（K+M-2）～（K+M-2）。

3）根據(jù)粒子編碼與解碼方式形成路徑方案。

4）計算粒子的適應(yīng)度函數(shù)值。若滿足約束條件，直接以目標(biāo)函數(shù)做為適應(yīng)度函數(shù)，若不滿足，采用罰函數(shù)方法處理。

5）根據(jù)粒子適應(yīng)度值更新粒子個體最優(yōu)值及全局最優(yōu)值，同時更新粒子的速度與位置。

6）判斷算法是否陷入停滯，若停滯則對最優(yōu)解進(jìn)行混沌優(yōu)化。

7）判斷是否滿足終止條件，若滿足則輸出求解結(jié)果；否則，返回步驟3）。

4　算例分析

4.1　算例1

以Matlab 2012b作為優(yōu)化平臺編制求解本文模型的混沌PSO算法程序，粒子個數(shù)為1 000，最大迭代次數(shù)為 300，wmax、wmin分別取 0.9、0.4，c1、c2 分別取0.9、0.7。假設(shè)需優(yōu)化29項工作任務(wù)，每項工作的地理位置坐標(biāo)在100 km×100 km的范圍內(nèi)隨機(jī)生成，作業(yè)中心的坐標(biāo)為（50，50），每項工作的作業(yè)用時在[30 min，90 min]范圍內(nèi)隨機(jī)取值，以作業(yè)點(diǎn)之間的直線距離模擬路徑距離，可用車次為10輛，車輛行駛速度為30km／h，作業(yè)人員單日最大勞動強(qiáng)度為4 h，單日最大工作時間6 h。

圖1為算法改進(jìn)前后求解過程的迭代曲線，可以看出混沌PSO算法能夠有效克服基本PSO算法的局部收斂問題。

圖1　算法迭代曲線

圖2為路徑優(yōu)化結(jié)果。對于該規(guī)模為30個作業(yè)點(diǎn)的問題，最優(yōu)路徑方案所需車次數(shù)為7輛，總行駛里程為760 km，總行駛時間為1 520 min，由圖2中的作業(yè)路徑優(yōu)化分布結(jié)果可以看出，混沌PSO算法能夠?qū)崿F(xiàn)配網(wǎng)帶電作業(yè)車輛路徑的最優(yōu)選擇。

圖2　路徑優(yōu)化結(jié)果

4.2　算例2

以山東泰安地區(qū)某典型周實(shí)際帶電作業(yè)工作計劃為例進(jìn)行分析，該典型周需安排16項工作計劃，各作業(yè)點(diǎn)之間的路程距離及時間數(shù)據(jù)通過網(wǎng)絡(luò)地圖定位獲取，該作業(yè)點(diǎn)工作用時參考具體工作標(biāo)準(zhǔn)作業(yè)用時，可用車次為15輛，作業(yè)人員單日最大勞動強(qiáng)度為4 h，單日最大工作時間6 h。

首先，采用傳統(tǒng)方法即由作業(yè)人員根據(jù)自身經(jīng)驗(yàn)編制工作計劃，具體結(jié)果如表1所示。由表1知，基于傳統(tǒng)經(jīng)驗(yàn)的工作計劃編制方法，共安排10輛作業(yè)車次，全部車次所需總工時為1 528 min，其中總作業(yè)時間為810 min，占比53%，總行駛用時為718 min，占比47%，總行駛距離為302.7 km?？梢钥闯觯渚W(wǎng)帶電作業(yè)工作用時近半數(shù)為路程行駛用時。

表1　傳統(tǒng)方法優(yōu)化結(jié)果

采用路徑優(yōu)化模型對工作計劃進(jìn)行路徑優(yōu)化，優(yōu)化結(jié)果如表2所示。

表2　本文方法優(yōu)化結(jié)果

分析表2，采用路徑優(yōu)化模型，完成該周計劃需5輛作業(yè)車次，總工時為1296 min，其中總作業(yè)時間為810 min，占比62.5%，總行駛用時為486 min，占比37.5%。相比于傳統(tǒng)方法，行駛用時減少232 min，使總工時縮短15.2%，總行駛用時縮短32.3%，總行駛距離為214.5 km，減少88.2 km，使車輛行駛成本降低29.1%。

由上述分析可以看出，車輛路程行駛用時占據(jù)了帶電作業(yè)工作大部分時間，路徑優(yōu)化方法則能夠通過合理組合作業(yè)計劃以及作業(yè)路徑，減少無謂的行駛時間及距離的浪費(fèi)，從而顯著提升帶電作業(yè)工作效率、降低車輛行駛成本。需要指出的是，問題規(guī)模越大，則優(yōu)化空間越大，優(yōu)化效果也越明顯。

5　結(jié)語

隨用戶側(cè)供電可靠性要求的逐步提高，配網(wǎng)帶電作業(yè)規(guī)模不斷擴(kuò)大，已成為配網(wǎng)檢修的重要技術(shù)手段，如何提高作業(yè)效率則成為配網(wǎng)帶電作業(yè)發(fā)展的關(guān)鍵問題。

作業(yè)路徑的選擇存在較大優(yōu)化空間，為此在考慮配網(wǎng)帶電作業(yè)工作特性的基礎(chǔ)上建立了車輛路徑優(yōu)化模型，并采混沌粒子群優(yōu)化算法進(jìn)行求解，取得了理想效果。

配網(wǎng)帶電作業(yè)路徑優(yōu)化模型有效縮短了現(xiàn)場作業(yè)時間，降低了車輛行駛費(fèi)用，經(jīng)濟(jì)效益顯著。

[1]胡毅，劉凱，彭勇，等.帶電作業(yè)關(guān)鍵技術(shù)研究進(jìn)展與趨勢[J].高電壓技術(shù)，2014，40（7）：1 921-1 931.

[2]黃旭，周文濤，李鵬，等.35 kV輸電線路實(shí)施中間電位帶電作業(yè)安全方法的研究[J].電氣應(yīng)用，2015，34（20）：58-61.

[3]李華鵬，楊忠，李興斗，等.基于絕緣平臺的綜合帶電作業(yè)新技術(shù)研究及應(yīng)用[J].現(xiàn)代電子技術(shù)，2016，39（9）：153-155，159.

[4]高旭啟，方書博，周明杰，等.10 kV配網(wǎng)耐張絕緣子遮蔽罩設(shè)計[J].電瓷避雷器，2014（3）：23-26，31.

[5]孫占功，林冬晧，王輝云，等.一種新型10 kV配電線路地電位帶電作業(yè)絕緣隔離工具[J].山東電力技術(shù)，2016，43（11）：47-50.

[6]劉夏清，牛捷，楊琪，等.10 kV環(huán)網(wǎng)柜完全不停電作業(yè)方法[J].電力科學(xué)與技術(shù)學(xué)報，2016，31（2）：109-114.

[7]蔣國清，潘勇，胡飛躍.兩階段式的物流配送路徑優(yōu)化方法[J].計算機(jī)工程與應(yīng)用，2015，51（2）：255-258，264.

[8]張勇.基于改進(jìn)蟻群算法物流配送路徑優(yōu)化的研究[J].控制工程，2015，22（2）：252-256.

[9]鄧先瑞，于曉慧，李春艷，等.基于種群分類粒子群算法的物流車輛調(diào)度優(yōu)化 [J]. 計算機(jī)工程與應(yīng)用，2016，52 （10）：237-240，258.

[10]戴昕.基于反向?qū)W習(xí)策略粒子群的物流配送路徑優(yōu)化研究[J].物流技術(shù)，2014，33（7）：291-294.

[11]侯玉梅，賈震環(huán)，田歆，等.帶軟時間窗整車物流配送路徑優(yōu)化研究[J].系統(tǒng)工程學(xué)報，2015，30（2）：240-250.

[12]于佳，任建文，周明.基于機(jī)會約束規(guī)劃的風(fēng)-蓄聯(lián)合動態(tài)經(jīng)濟(jì)調(diào)度[J].電網(wǎng)技術(shù)，2013，37（8）：2 116-2 122.