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

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

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

?

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

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

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

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

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

0引言

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

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

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

1問題描述

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

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

若選擇電纜敷設總長度最短作為優(yōu)化目標，則考慮通道容量約束的電纜敷設問題就等價于在一個敷設圖L中，求其所有待敷設路徑敷設長度和的最小值。該優(yōu)化問題也可表示為如下數(shù)學規(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為表示敷設路徑k是否從頂點i到頂點j經(jīng)過邊(i,j)的決策變量，1表示是，0表示否；dij為邊(i,j)的長度，K為待敷設路徑集合，sk、fk分別代表敷設路徑k的起點和終點，cij為邊(i,j)的容量。若存在特殊類型電纜的專用路徑，例如某橋架為動力電纜橋架，不允許控制和信號電纜通過，只需將約束條件式(7)增加到上述模型中，其中E1為動力電纜橋架對應的邊集，K2、K3分別為控制和信號電纜對應的敷設路徑集合。其他電纜專用路徑同理。

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

(7)

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

2變鄰域搜索算法

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

2.1初始解的構造

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

2.2鄰域結構的構建

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

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

δ(x1,x2)=k

(8)

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

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

(9)

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

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

2.3局部搜索策略

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

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

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

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

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

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

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

Step3設置k=1。

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

Step7若k≤M，則轉至Step4；否則，算法結束。

3實例求解與分析

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

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

表1　實例求解結果比較表

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

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

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

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

4結語

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

參考文獻

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

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

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

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

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

[6] 羅建國,韋思亮.基于樹狀、網(wǎ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)仿真學報,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。梁濤，工程師，主研領域：復雜系統(tǒng)建模與優(yōu)化，電力系統(tǒng)運行與控制技術。李衛(wèi)東，高工。徐愛東，教授級高工。

中圖分類號TP391.9TM621

文獻標識碼A

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