梁　濤　李衛(wèi)東　徐愛東

1(山東電力工程咨詢院有限公司　山東 濟南 250013)2(華能西寧熱電有限責(zé)任公司　青海 西寧 810000)

?

考慮容量約束的電纜敷設(shè)變鄰域搜索優(yōu)化算法

梁濤1李衛(wèi)東2徐愛東1

1(山東電力工程咨詢院有限公司山東 濟南 250013)2(華能西寧熱電有限責(zé)任公司青海 西寧 810000)

摘要針對一類考慮容量約束的電纜敷設(shè)優(yōu)化問題，提出一種新的變鄰域搜索優(yōu)化算法。首先，分析電纜敷設(shè)問題的優(yōu)化要求，基于圖論給出具有容量約束的電纜敷設(shè)優(yōu)化問題的數(shù)學(xué)描述；然后，結(jié)合問題特征提出基于Dijkstra算法的初始解生成策略，構(gòu)建依據(jù)解間距離的鄰域結(jié)構(gòu)和局部啟發(fā)式搜索策略，在此基礎(chǔ)上給出電纜敷設(shè)變鄰域搜索優(yōu)化算法；最后通過實例求解結(jié)果表明，該算法能在短時間內(nèi)獲得問題的最優(yōu)解或近優(yōu)解，驗證了算法的有效性和優(yōu)越性。

關(guān)鍵詞電纜敷設(shè)變鄰域搜索優(yōu)化算法

0引言

電纜敷設(shè)是發(fā)電廠工程建設(shè)中一項復(fù)雜且重要的工作內(nèi)容。合理的敷設(shè)優(yōu)化不但能減少電纜和周圍環(huán)境相互干擾而引起的事故概率，而且能夠顯著節(jié)約電纜及橋架使用量。同時電纜長度的減少可明顯降低電纜施工的工程量，無疑為電廠的投資帶來可觀的經(jīng)濟效益。另一方面，電纜的敷設(shè)優(yōu)化又受到工藝系統(tǒng)布置、橋架容量和不同電壓等級電纜電磁干擾等諸多因素影響，導(dǎo)致電纜敷設(shè)優(yōu)化問題成為一類典型的NP-Hard問題。因而，引起了科學(xué)研究和工程設(shè)計領(lǐng)域的普遍關(guān)注[1,2]。

現(xiàn)階段，在國內(nèi)工程設(shè)計中應(yīng)用的電纜敷設(shè)優(yōu)化工具主要有從法國引進的PERICLES和國產(chǎn)的AUTOLAY軟件等[3,4]。這些軟件大多采用Dijkstra算法或Floyd算法。這兩種算法作為經(jīng)典的最短路徑算法，對于無容量約束的最短路徑問題具有較高的求解效率，但較難用于具有容量約束的路徑優(yōu)化問題。另外，文獻[5]在其設(shè)計的電廠電纜敷設(shè)計算機輔助設(shè)計與管理系統(tǒng)(CADMCL)中提出了應(yīng)用人工智能方法來解決電纜路徑尋優(yōu)問題；文獻[6]針對電纜敷設(shè)設(shè)計問題，引入了一種樹狀或網(wǎng)狀優(yōu)化算法，用于提高設(shè)計水平，并將其應(yīng)用于脫硫改造工程施工。這些方法本質(zhì)上屬于基于規(guī)則的啟發(fā)式方法，求解過程簡單快速，但對于大規(guī)模優(yōu)化問題較難保證求解的優(yōu)化性。目前，考慮容量約束的電纜敷設(shè)優(yōu)化問題仍是工程設(shè)計優(yōu)化研究中面臨的一個難題。

變鄰域搜索VNS(VariableNeighborhoodSearch)作為一種新興的智能優(yōu)化算法，從1997年被首次提出[7]，至今經(jīng)過十多年的研究和擴展，已被成功應(yīng)用于旅行商問題、圖著色、車輛調(diào)度等問題中。在解決優(yōu)化問題，尤其是大規(guī)模組合優(yōu)化問題上體現(xiàn)出了良好性能[8-10]。但是，此算法的尋優(yōu)能力很大程度上依賴于鄰域構(gòu)建的合理性和局部搜索策略的有效性。本文針對具有容量約束的電纜敷設(shè)問題特點，在分析鄰域結(jié)構(gòu)與局部搜索策略構(gòu)建方法的基礎(chǔ)上，提出一種新的電纜敷設(shè)變鄰域搜索優(yōu)化算法，并應(yīng)用實例驗證了該方法的有效性和優(yōu)越性。

1問題描述

實際工程中的電纜敷設(shè)問題是將幾千甚至幾萬根的動力電纜、控制電纜和信號電纜通過由橋架、電纜溝等組成的電纜通道從起點設(shè)備連接至終端設(shè)備。該問題的關(guān)鍵在于在電纜各通道都有其固定容量的前提下，數(shù)量如此龐大的電纜分別走哪條路徑才能使整個系統(tǒng)更穩(wěn)定、更經(jīng)濟。為更好地描述該問題，首先給出以下定義：

定義1設(shè)G=(V,E)為一個無向圖，V為非空的頂點集，E為邊集，若滿足：

① 在G的邊集E上定義非負實值函數(shù)d，稱為長度函數(shù)，對任意e∈E，稱d(e)為邊e的長度。

② 在G的邊集E上定義非負整值函數(shù)c，稱為容量函數(shù)，對任意e∈E，稱c(e)為邊e的容量。

③S與F是兩個長度為M的非空頂點序列；對任意s∈S，f∈F，均有s∈V，f∈V。

則稱圖G為一個敷設(shè)圖，簡記為L=(V,E,d,c,S,F)。其中，由序列S、F中頂點構(gòu)成的頂點對(s1,f1),…,(sM,fM)表示待敷設(shè)的路徑。在圖G中從路徑的起點s到終點f找出一條連通的途徑，稱為路徑的敷設(shè)，且將其上敷設(shè)路徑數(shù)達到其最大容量的邊稱之為滿邊。

若選擇電纜敷設(shè)總長度最短作為優(yōu)化目標(biāo)，則考慮通道容量約束的電纜敷設(shè)問題就等價于在一個敷設(shè)圖L中，求其所有待敷設(shè)路徑敷設(shè)長度和的最小值。該優(yōu)化問題也可表示為如下數(shù)學(xué)規(guī)劃模型：

Minz=∑k∈K∑(i,j)∈Edijxijk

(1)

s.t.

∑(i,j)∈Exijk=∑(i,j)∈Exjikk∈K,i≠sk,i≠fk

(2)

∑(i,j)∈Exijk=1k∈K,i∈skorj=fk

(3)

∑(i,j)∈Exjik=0k∈K,i∈skorj=fk

(4)

∑(i,j)∈E(xijk+xjik)≤cijk∈K,i>j

(5)

xjik=0 or 1

(6)

其中，xijk為表示敷設(shè)路徑k是否從頂點i到頂點j經(jīng)過邊(i,j)的決策變量，1表示是，0表示否；dij為邊(i,j)的長度，K為待敷設(shè)路徑集合，sk、fk分別代表敷設(shè)路徑k的起點和終點，cij為邊(i,j)的容量。若存在特殊類型電纜的專用路徑，例如某橋架為動力電纜橋架，不允許控制和信號電纜通過，只需將約束條件式(7)增加到上述模型中，其中E1為動力電纜橋架對應(yīng)的邊集，K2、K3分別為控制和信號電纜對應(yīng)的敷設(shè)路徑集合。其他電纜專用路徑同理。

xijk=0,(i,j)∈E1,k∈K2∪K3

(7)

電纜敷設(shè)優(yōu)化的目標(biāo)也可以是電纜投資最省，即電纜總費用最少，只需將優(yōu)化目標(biāo)式(1)中各類不同價格的電纜長度相加之前乘以其單位價格即可。

2變鄰域搜索算法

變鄰域搜索算法(VNS)的基本思想是從一個初始可行解出發(fā)，在搜索過程中通過多次系統(tǒng)地改變鄰域結(jié)構(gòu)集來拓展搜索范圍，不斷地從一個局部最優(yōu)解移向另一個更優(yōu)的局部最優(yōu)解。應(yīng)用VNS求解優(yōu)化問題，首先需要給出一個初始可行解。另外，根據(jù)應(yīng)用問題特征，構(gòu)建合適的鄰域結(jié)構(gòu)和局部搜索策略是實現(xiàn)算法優(yōu)越性能的關(guān)鍵。

2.1初始解的構(gòu)造

在電纜敷設(shè)問題對應(yīng)的敷設(shè)圖L中，所有待敷設(shè)路徑的一次成功敷設(shè)，就形成了該問題的一個解。若敷設(shè)后，對于任意e∈E，其上經(jīng)過的路徑數(shù)cr都滿足cr≤c(e)，則該解即為電纜敷設(shè)問題的一個可行解。由此可見，初始可行解可以通過在合適的順序下逐條進行路徑的敷設(shè)來獲得。為保證初始解的局部優(yōu)化性，減少搜索時間，可以在考慮各邊容量的基礎(chǔ)上應(yīng)用Dijkstra算法獲得各路徑的敷設(shè)，即每次應(yīng)用Dijkstra算法時所用的邊集E′為當(dāng)前的可用邊集，需從邊集E中去除當(dāng)前的滿邊以及與當(dāng)前待敷設(shè)路徑電纜類型不匹配通道的對應(yīng)邊。這樣既保證了獲得解的可行性，又兼顧了獲得解在當(dāng)前敷設(shè)順序下的最優(yōu)性。路徑的敷設(shè)順序可以采用賭輪法生成，若一次敷設(shè)無法獲得可行解，則需要變更敷設(shè)順序或重新生成新的敷設(shè)順序。

2.2鄰域結(jié)構(gòu)的構(gòu)建

首先針對電纜敷設(shè)問題特點，給出兩個解之間距離的定義：

定義2設(shè)x1,x2為電纜敷設(shè)問題的兩個可行解，若x1中所有路徑的敷設(shè)存在k條路徑與x2中不同，而其他M-k條路徑的敷設(shè)相同，則稱解x1,x2之間的距離為k，記為：

δ(x1,x2)=k

(8)

由以上定義，本文依據(jù)不同解之間距離的遠近來定義解的鄰域結(jié)構(gòu)。換句話說，將與解x距離為k的解的集合定義為解x的鄰域Nk，即：

Nk={x′|δ(x,x′)=k}k=1,2,…,M

(9)

對于考慮容量約束的電纜敷設(shè)問題，這樣定義鄰域結(jié)構(gòu)的好處在于可以直觀地進行鄰域內(nèi)搜索和搜索范圍拓展。

進行鄰域內(nèi)搜索時，由解x獲得鄰域Nk內(nèi)的另一個解x′，只需隨機選擇k條路徑變換敷設(shè)即可。變換敷設(shè)時，先在敷設(shè)圖L中將選中路徑的敷設(shè)刪除，將原路徑其中一條邊設(shè)置為不可用，然后應(yīng)用Dijkstra算法在可用邊范圍內(nèi)重新敷設(shè)該路徑。如此既保證了獲得的解x′∈Nk，又兼顧了解的優(yōu)化性。

2.3局部搜索策略

局部搜索的目的是在可行解附近的局部區(qū)域內(nèi)獲得更優(yōu)解。局部搜索策略的好壞很大程度上決定著局部搜索過程中解是否能夠被改進。本文采用在解x′的鄰域Nm2內(nèi)進行啟發(fā)式搜索的策略：

針對圖中一條滿邊定義兩個路徑集合KA和KB，分別表示途經(jīng)該邊的路徑集和不途經(jīng)該邊的路徑集。通過隨機互換KA中某條路徑和KB中某條路徑的敷設(shè)順序來搜索更優(yōu)解。

經(jīng)過簡單分析可知，考慮容量約束的電纜敷設(shè)問題無法應(yīng)用Dijkstra算法直接求解是因為進行路徑敷設(shè)時存在滿邊，而決定解是否優(yōu)化的關(guān)鍵在于滿邊上敷設(shè)哪些路徑。換言之，應(yīng)用Dijkstra算法直接求解可能導(dǎo)致某邊e上敷設(shè)的路徑數(shù)cr超出其容量約束，產(chǎn)生不可行解。在考慮容量約束的條件下，此cr條路徑中哪些路徑能夠途經(jīng)邊e很大程度上決定著對應(yīng)解的可行性和優(yōu)化性，而前者又取決于這些路徑的敷設(shè)順序。由此可見，通過互換可行解中兩條路徑的敷設(shè)順序可以達到局部搜索尋優(yōu)的目的。然而，若互換敷設(shè)順序的兩條路徑均不途經(jīng)滿邊或者均途經(jīng)相同的滿邊，難以實現(xiàn)解的實質(zhì)性改進。因此，通過上述啟發(fā)式搜索策略，更容易發(fā)現(xiàn)由于路徑敷設(shè)順序隨機導(dǎo)致的解的次優(yōu)點，從而進行修正。局部搜索的次數(shù)可根據(jù)問題的規(guī)模確定，無經(jīng)驗的情況下，推薦選擇區(qū)間[10,50]內(nèi)的一個整數(shù)。

2.4電纜敷設(shè)變鄰域搜索優(yōu)化算法

基于2.1節(jié)-2.3節(jié)的分析，考慮通道容量約束的電纜敷設(shè)變鄰域搜索優(yōu)化算法描述如下：

Step1在考慮容量約束的基礎(chǔ)上，應(yīng)用Dijkstra算法逐條路徑敷設(shè)，從而獲得一個初始可行解x。

Step2定義x的鄰域結(jié)構(gòu)Nk={x′|δ(x,x′)=k}(k=1,2,…,M)。

Step3設(shè)置k=1。

Step6若獲得的局部最優(yōu)解x′優(yōu)于當(dāng)前最優(yōu)解x，則更新當(dāng)前最優(yōu)解x=x′，轉(zhuǎn)至Step3；否則，設(shè)置k=k+1。

Step7若k≤M，則轉(zhuǎn)至Step4；否則，算法結(jié)束。

3實例求解與分析

為了驗證電纜敷設(shè)變鄰域搜索優(yōu)化算法的有效性，本文對五個不同規(guī)模的實例進行了建模和求解。算法采用C++進行編程實現(xiàn)，在CPU為2.66GHz、內(nèi)存為1GB的PC機上進行求解。實例1-實例5均為隨機實例，其電纜通道的連接方式、各段長度與容量以及需要敷設(shè)的電纜集均為隨機生成。由于實際三維空間中各通道交點上連接的通道一般不超過六個方向，為保持實例與實際問題的一致性，在保證敷設(shè)圖中所有頂點間均存在連通途徑的基礎(chǔ)上，每個頂點上連接的邊數(shù)均不大于六。

應(yīng)用本文算法對實例1-實例5進行優(yōu)化求解的結(jié)果如表1所示。作為比較，表1中同時給出了基于第1節(jié)中數(shù)學(xué)規(guī)劃模型應(yīng)用數(shù)學(xué)優(yōu)化求解器LINDOAPI5.0對五個實例在同一配置PC機上進行優(yōu)化求解的結(jié)果。從表1中可以看出，對于規(guī)模較小的實例1和實例2，兩種方法均能找到問題的最優(yōu)解，而本文方法的所用的求解時間比LINDO的求解時間要少得多。隨著問題規(guī)模的增大，最優(yōu)解越來越難被找到。對于較大規(guī)模的實例3-實例5，基于數(shù)學(xué)規(guī)劃模型利用求解器LINDO在規(guī)定的時間內(nèi)只能找到問題的近優(yōu)解。甚至由于模型規(guī)模巨大出現(xiàn)內(nèi)存不足錯誤，而本文方法則可以在更短的時間內(nèi)獲得更優(yōu)的可行解。這主要歸功于算法中鄰域結(jié)構(gòu)和局部啟發(fā)式搜索策略構(gòu)建的有效性，特別是局部啟發(fā)式搜索策略。表2中給出了在同一初始解的情況下利用局部隨機搜索策略和局部啟發(fā)式搜索策略求解結(jié)果的比較，同時給出了對應(yīng)無容量限制電纜敷設(shè)問題的最優(yōu)解作為下限值提供參考。從表2中可以看出，相對于局部隨機搜索策略，本文提出的局部啟發(fā)式搜索策略對初始解的改進效果明顯，獲得的結(jié)果與參考下限之間的距離均小于2%?？紤]到容量約束條件使最優(yōu)解與參考下限之間可能的偏離距離，由此可見本文方法的優(yōu)越性。

表1　實例求解結(jié)果比較表

注：aNv/NE/M表示實例的節(jié)點數(shù)/邊數(shù)/電纜數(shù)；

b經(jīng)過相應(yīng)的時間結(jié)束計算，將最佳可行解作為優(yōu)化結(jié)果；

c由于模型規(guī)模太大，無法完成計算過程

表2　局部搜索策略效果比較表

4結(jié)語

考慮容量約束的電纜敷設(shè)優(yōu)化問題是目前工程設(shè)計優(yōu)化領(lǐng)域面臨的難題之一。本文針對具有通道容量約束的電纜敷設(shè)問題特點，提出了敷設(shè)圖的概念，在此基礎(chǔ)上給出了一種新的適合電纜敷設(shè)優(yōu)化問題的變鄰域搜索算法。該算法鄰域結(jié)構(gòu)構(gòu)建簡單、直觀，局部啟發(fā)式搜索策略合理、有效，較好地保證了搜索過程的快速趨優(yōu)性。實例計算結(jié)果驗證了該算法不但具有較快的求解速度，而且具有較好的尋優(yōu)性能。特別是對于較大規(guī)模問題，該算法優(yōu)勢明顯，在解決電纜敷設(shè)優(yōu)化設(shè)計問題領(lǐng)域具有較好的應(yīng)用前景和推廣價值。

參考文獻

[1] 王鋮.火力發(fā)電廠電纜敷設(shè)路徑優(yōu)化研究[J].紹興文理學(xué)院學(xué)報,2011,31(10):58-62.

[2] 王愛梅,張悅,郭曉玲.發(fā)電廠電纜敷設(shè)優(yōu)化方式探討[J].山西電力,2013,33(2):70-72.

[3] 陳智,游建偉.秦山核電二期工程核島電纜敷設(shè)設(shè)計實踐[J].核動力工程,2003,24(2):201-203.

[4] 安慶敏,徐愛東,陳志強,等.火力發(fā)電廠熱控電纜敷設(shè)軟件的開發(fā)與應(yīng)用[J].工業(yè)儀表與自動化裝置,2011,41(6):64-66.

[5] 王明海.電廠電纜敷設(shè)設(shè)計與工程管理系統(tǒng)的研究[D].華北電力大學(xué),2004.

[6] 羅建國,韋思亮.基于樹狀、網(wǎng)狀搜索算法的電纜敷設(shè)設(shè)計與應(yīng)用[J].熱力發(fā)電,2013,42(3):103-105.

[7]MladenovicN,HansenP.Variableneighborhoodsearch[J].Computers&OperationsResearch,1997,24(11):1097-1100.

[8]AvanthayC,HertzA,ZuffereyN.Avariableneighborhoodsearchforgraphcoloring[J].EuropeanJournalofOperationsResearch,2003,151(2):379-388.

[9] 張則強,譚思捷,黃玉真,等.求解單行布局問題的一種變鄰域搜索算法[J].中國機械工程,2013,24(20):2791-2796.

[10] 陳萍,黃厚寬,董興業(yè).求解多車型車輛路徑問題的變鄰域搜索算法[J].系統(tǒng)仿真學(xué)報,2011,23(9):1945-1950.

A VARIABLE NEIGHBOURHOOD SEARCH ALGORITHM FOR CABLE LAYOUTPROBLEMSWITHCAPACITYCONSTRAINTS

Liang Tao1Li Weidong2Xu Aidong1

1(Shandong Electric Power Engineering Consulting Institute Co., Ltd., Jinan 250013,Shandong,China)2(Huaneng Xining Thermal Power Co., Ltd., Xining 810000,Qinghai,China)

AbstractWe presented a new optimised variable neighbourhood search algorithm for a kind of cable layout optimisation problem with capacity constraints. First, we analysed the optimisation demands of cable layout problems, and presented based on graph theory the mathematical description of cable layout optimisation problem with capacity constraints. Then in combination with the problem features, we introduced an initial solution generation strategy using Dijkstra algorithm, and built up a solution-distance-based neighbourhood structure and a local heuristic search strategy. On this basis, we proposed the optimised variable neighbourhood search algorithm for cable layout. Finally, it was demonstrated through the example of solving results that the presented algorithm could obtain optimal solutions or near-optimal solutions in a short time, which verified the effectiveness and superiority of the algorithm.

KeywordsCable layoutVariable neighbourhood searchOptimisation algorithm

收稿日期：2014-11-17。梁濤，工程師，主研領(lǐng)域：復(fù)雜系統(tǒng)建模與優(yōu)化，電力系統(tǒng)運行與控制技術(shù)。李衛(wèi)東，高工。徐愛東，教授級高工。

中圖分類號TP391.9TM621

文獻標(biāo)識碼A

DOI:10.3969/j.issn.1000-386x.2016.06.069