枝狀管網布局優化中的3類問題

商冠琪

(中國石油化工股份有限公司)

目前，針對集輸管網的優化設計問題多采用分級優化的策略，根據不同的管網形態將系統優化分為多個子問題來處理，比如，星枝管網的優化設計[1]，通過分級優化將氣田星枝狀地面集輸系統優化分為井組最優劃分、星式管網布局優化、干支管網布局優化和管網參數優化4個子問題進行研究。干支管網布局優化是進行站點位置的合理布置，可分為3方面的內容，一是無向圖枝狀結構，二是枝狀結構中心點，三是有向圖的枝狀連接。

1 無向枝狀結構連接

無向枝狀結構連接關系，多采用圖論的最小生成樹算法確定無向圖的連接關系。根據圖論的知識，管網中的站點和管段可以抽象為圖中的節點和邊，對于任意兩個節點間，理論上都可能存在一條管線相連，任意兩點存在邊則構成了一個完備圖。n個節點的完備圖存在Cn2=n(n-1)/2條邊，在這些邊中，選擇n-1條邊就可以得到枝狀管網的連接方式，而這n-1條管線也就構成了這個完備圖的一棵生成樹。一個完備圖的生成樹有很多，可能的枝狀管網的連接方式也就有很多，沒有考慮到流向的問題，可將枝狀管網連接方式的優化問題轉變成求無向圖中的最小生成樹問題。

1.1 模型的建立

求解無向圖最小生成樹的數學模型為：

(1)

式中E——圖中所有邊的集合；

W(e)——邊e的權值。

在求解最小生成樹時，不僅要使枝狀管網的管線總長度最短，還要考慮各節點氣量不同而造成的管徑差異，但是流向未知，可對頂點加權，得到求解枝狀管網最優連接方式的數學模型如下：

(2)

其約束條件為：

(3)

(4)

(5)

Aij=0,1

(6)

式中Aij——0～1決策變量，當節點i、j間有管線連接時，Aij為1，當節點i與j不相連時，Aij為0；

Lij——第i節點到第j節點間的管線長度；

m——節點的總數；

qi——第i節點的集氣量。

1.2 求解算法

求解算法主要包括Kruskai、 Prim和SI生成樹算法。這3種方法是圖論中的經典算法，算法運行穩定，是集輸系統枝狀結構布局普遍采用的方式。

Prime算法的時間復雜度為O(n2)，n為圖中頂點的個數，由于Prime算法與邊的數目無關，適合求解邊稠密的網絡圖的最小生成樹；Kruskal算法的時間復雜度為O(lg2k+2klg2n+n)，n為頂點個數，k為邊的個數，由于Kruskal算法的時間復雜度主要取決于邊的數目，適合求解邊稀疏的網絡圖的最小生成樹；SI算法在管網結構中加入了額外點，其優化結果優于其他兩種算法，但運行效率不高。

學者李書文首次對3種算法在枝狀管網布局優化研究中進行了論述[2]；康正凌和袁宗明采用Kruskai算法確定枝狀管網連接關系[3]；李征用Prim算法確定枝狀天然氣管網連接關系[4]；鄭清高等都采用了SI算法來確定氣田集輸管網最優網絡布局[5～7]。

2 枝狀結構中心點的確定

枝狀結構中心點問題是在確定了枝狀結構連接關系時，在給定的生成樹結構中選取合理節點作為站點。中心點作為整個枝狀管網系統的中心，它的位置決定了干支管網各管段流量的流向和分布，從而直接影響到枝狀管網中集氣管線直徑和長度的變化。中心點選址問題就可以轉化為圖論中求解連通圖的加權中心問題，即選擇連通圖的某個頂點，使得其他所有頂點到該頂點的距離和最小，則該頂點就稱為此連通圖的加權中心，也就是優化確定的中心站點位置。

2.1 模型的建立

在連通圖中，從一個頂點到另一個頂點間的加權路徑最短，要找到這條途徑，在圖論中稱為最短路徑問題。若整個管網有m個節點，分別對每個節點到其他所有節點之間求解最短路徑，并將各個最短路徑求和，最小值對應的節點即為中心節點位置。

對于節點j至i的加權距離，計算式為：

(7)

則求解中心節點的目標函數為：

(8)

其中，qj為節點j的集氣量。

2.2 求解算法

計算任意兩頂點之間的最短路徑，在圖論中應用較普遍的有Dijkstra算法及Floyd算法等。

Dijkstra算法又叫做標號法，應用一次的時間復雜度為O(m2)，它每次只能求出圖中一個特定頂點到其他各頂點的最短路，如果要計算像煤層氣集輸管網這種具有m個頂點的無向圖中任意兩個頂點間的最短路徑，需要將圖中每一個頂點依次視為起始點，然后反復應用Dijkstra算法計算。因此，應用Dijkstra算法求解該問題的時間復雜度為O(m3)。

Floyd算法又叫做插點法，在計算時從任意一條單邊路徑開始，對于每一對頂點u和v，看是否存在一個頂點w使得從u到w再到v比己知路徑的加權距離更短，如果存在就更新它，如此循環，直到得出最短路徑。Floyd算法求解該問題最短路徑的時間復雜性也是O(m3)。

徐國棟和梁政針對海上邊際油田和陸上氣田，研究了枝狀管網的中心站址選擇問題[8]。

3 有向枝狀連接結構布置

有向枝狀結構連接關系。把無向樹轉化為有向樹后，在無向圖中確定的連接方式，不一定是有向圖的最優連接方式，所得到的管網最小流量長度和也不一定是有向樹的最小流量長度和。從數學模型來看，有向圖布局優化的數學模型與無向圖相同，但優化算法來看，徐國棟和梁政首先采用了無向枝狀結構連接確定連接關系，然后確定管網的中心點，在此基礎上一管網的流量長度之和最小原則，調整中心站的位置，最終確定枝狀管網的布局[8]。陳坤明等采用單親遺傳算和深度優先搜索混合算法對該問題進行了求解[9]。有向圖枝狀連接結構布置，由于問題的復制性，目前無較成熟和被廣泛認可的求解方法。

4 結束語

枝狀管網作為集輸系統普遍采用的結構之一，將管網布局轉變為無向枝狀布局和中心點位置優化問題是當前優化設計普遍采用的方式，其優化算法簡便且穩定，已得到廣泛應用。但集輸系統枝狀結構布局優化區別于一般圖的連接關系是管道中流體的存在，在布局優化設計方案中考慮流體方向，也是枝狀管網布局研究的難點。無向連接關系布局是對此問題的簡化處理，優化結果無法保證最優性。目前雖有學者對此問題進行了研究，但效果有待提高，需研究者繼續努力。

[1] 潘紅麗，楊鴻雁.氣田地面集輸管網系統的優化設計[J]. 油氣儲運，2002，21(4)：14～18.

[2] 李書文.氣田網絡優化布局初探[J].天然氣工業，1989，9(5)：68～72.

[3] 康正凌，袁宗明.樹枝狀天然氣管網優化設計[J].天然氣工業，2001，21(3)：76～78，2.

[4] 李征.天然氣集輸管網優化設計方法研究[J].內蒙古石油化工，2009，34(6)：19～21.

[5] 鄭清高.油氣集輸管網幾何布局的研究[J].石油學報，1995，(1)：139～143.

[6] 孟榮章，李書文，湯林.大型氣田集輸管網布局優化[J].石油規劃設計，1998，9(2)：20～22，4.

[7] 姚麟昱，駱彬，孟慶華，等.川西高壓高產氣田集輸管網規劃設計[J].石油規劃設計，2010，21(6)：21～24，54.

[8] 徐國棟，梁政.氣田集輸管網布局優化研究[J].石油規劃設計，2004，15(6)：18～21.

[9] 陳坤明，簡朝陽，劉松泉，等.單親遺傳和深度優先搜索算法的集輸管網優化[J].油氣田地面工程，2012，31(8)：34～35.