枝狀管網(wǎng)布局優(yōu)化中的3類問題

商冠琪

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

目前，針對(duì)集輸管網(wǎng)的優(yōu)化設(shè)計(jì)問題多采用分級(jí)優(yōu)化的策略，根據(jù)不同的管網(wǎng)形態(tài)將系統(tǒng)優(yōu)化分為多個(gè)子問題來處理，比如，星枝管網(wǎng)的優(yōu)化設(shè)計(jì)[1]，通過分級(jí)優(yōu)化將氣田星枝狀地面集輸系統(tǒng)優(yōu)化分為井組最優(yōu)劃分、星式管網(wǎng)布局優(yōu)化、干支管網(wǎng)布局優(yōu)化和管網(wǎng)參數(shù)優(yōu)化4個(gè)子問題進(jìn)行研究。干支管網(wǎng)布局優(yōu)化是進(jìn)行站點(diǎn)位置的合理布置，可分為3方面的內(nèi)容，一是無向圖枝狀結(jié)構(gòu)，二是枝狀結(jié)構(gòu)中心點(diǎn)，三是有向圖的枝狀連接。

1 無向枝狀結(jié)構(gòu)連接

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

1.1 模型的建立

求解無向圖最小生成樹的數(shù)學(xué)模型為：

(1)

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

W(e)——邊e的權(quán)值。

在求解最小生成樹時(shí)，不僅要使枝狀管網(wǎng)的管線總長(zhǎng)度最短，還要考慮各節(jié)點(diǎn)氣量不同而造成的管徑差異，但是流向未知，可對(duì)頂點(diǎn)加權(quán)，得到求解枝狀管網(wǎng)最優(yōu)連接方式的數(shù)學(xué)模型如下：

(2)

其約束條件為：

(3)

(4)

(5)

Aij=0,1

(6)

式中Aij——0～1決策變量，當(dāng)節(jié)點(diǎn)i、j間有管線連接時(shí)，Aij為1，當(dāng)節(jié)點(diǎn)i與j不相連時(shí)，Aij為0；

Lij——第i節(jié)點(diǎn)到第j節(jié)點(diǎn)間的管線長(zhǎng)度；

m——節(jié)點(diǎn)的總數(shù)；

qi——第i節(jié)點(diǎn)的集氣量。

1.2 求解算法

求解算法主要包括Kruskai、 Prim和SI生成樹算法。這3種方法是圖論中的經(jīng)典算法，算法運(yùn)行穩(wěn)定，是集輸系統(tǒng)枝狀結(jié)構(gòu)布局普遍采用的方式。

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

學(xué)者李書文首次對(duì)3種算法在枝狀管網(wǎng)布局優(yōu)化研究中進(jìn)行了論述[2]；康正凌和袁宗明采用Kruskai算法確定枝狀管網(wǎng)連接關(guān)系[3]；李征用Prim算法確定枝狀天然氣管網(wǎng)連接關(guān)系[4]；鄭清高等都采用了SI算法來確定氣田集輸管網(wǎng)最優(yōu)網(wǎng)絡(luò)布局[5～7]。

2 枝狀結(jié)構(gòu)中心點(diǎn)的確定

枝狀結(jié)構(gòu)中心點(diǎn)問題是在確定了枝狀結(jié)構(gòu)連接關(guān)系時(shí)，在給定的生成樹結(jié)構(gòu)中選取合理節(jié)點(diǎn)作為站點(diǎn)。中心點(diǎn)作為整個(gè)枝狀管網(wǎng)系統(tǒng)的中心，它的位置決定了干支管網(wǎng)各管段流量的流向和分布，從而直接影響到枝狀管網(wǎng)中集氣管線直徑和長(zhǎng)度的變化。中心點(diǎn)選址問題就可以轉(zhuǎn)化為圖論中求解連通圖的加權(quán)中心問題，即選擇連通圖的某個(gè)頂點(diǎn)，使得其他所有頂點(diǎn)到該頂點(diǎn)的距離和最小，則該頂點(diǎn)就稱為此連通圖的加權(quán)中心，也就是優(yōu)化確定的中心站點(diǎn)位置。

2.1 模型的建立

在連通圖中，從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)間的加權(quán)路徑最短，要找到這條途徑，在圖論中稱為最短路徑問題。若整個(gè)管網(wǎng)有m個(gè)節(jié)點(diǎn)，分別對(duì)每個(gè)節(jié)點(diǎn)到其他所有節(jié)點(diǎn)之間求解最短路徑，并將各個(gè)最短路徑求和，最小值對(duì)應(yīng)的節(jié)點(diǎn)即為中心節(jié)點(diǎn)位置。

對(duì)于節(jié)點(diǎn)j至i的加權(quán)距離，計(jì)算式為：

(7)

則求解中心節(jié)點(diǎn)的目標(biāo)函數(shù)為：

(8)

其中，qj為節(jié)點(diǎn)j的集氣量。

2.2 求解算法

計(jì)算任意兩頂點(diǎn)之間的最短路徑，在圖論中應(yīng)用較普遍的有Dijkstra算法及Floyd算法等。

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

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

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

3 有向枝狀連接結(jié)構(gòu)布置

有向枝狀結(jié)構(gòu)連接關(guān)系。把無向樹轉(zhuǎn)化為有向樹后，在無向圖中確定的連接方式，不一定是有向圖的最優(yōu)連接方式，所得到的管網(wǎng)最小流量長(zhǎng)度和也不一定是有向樹的最小流量長(zhǎng)度和。從數(shù)學(xué)模型來看，有向圖布局優(yōu)化的數(shù)學(xué)模型與無向圖相同，但優(yōu)化算法來看，徐國(guó)棟和梁政首先采用了無向枝狀結(jié)構(gòu)連接確定連接關(guān)系，然后確定管網(wǎng)的中心點(diǎn)，在此基礎(chǔ)上一管網(wǎng)的流量長(zhǎng)度之和最小原則，調(diào)整中心站的位置，最終確定枝狀管網(wǎng)的布局[8]。陳坤明等采用單親遺傳算和深度優(yōu)先搜索混合算法對(duì)該問題進(jìn)行了求解[9]。有向圖枝狀連接結(jié)構(gòu)布置，由于問題的復(fù)制性，目前無較成熟和被廣泛認(rèn)可的求解方法。

4 結(jié)束語

枝狀管網(wǎng)作為集輸系統(tǒng)普遍采用的結(jié)構(gòu)之一，將管網(wǎng)布局轉(zhuǎn)變?yōu)闊o向枝狀布局和中心點(diǎn)位置優(yōu)化問題是當(dāng)前優(yōu)化設(shè)計(jì)普遍采用的方式，其優(yōu)化算法簡(jiǎn)便且穩(wěn)定，已得到廣泛應(yīng)用。但集輸系統(tǒng)枝狀結(jié)構(gòu)布局優(yōu)化區(qū)別于一般圖的連接關(guān)系是管道中流體的存在，在布局優(yōu)化設(shè)計(jì)方案中考慮流體方向，也是枝狀管網(wǎng)布局研究的難點(diǎn)。無向連接關(guān)系布局是對(duì)此問題的簡(jiǎn)化處理，優(yōu)化結(jié)果無法保證最優(yōu)性。目前雖有學(xué)者對(duì)此問題進(jìn)行了研究，但效果有待提高，需研究者繼續(xù)努力。

[1] 潘紅麗，楊鴻雁.氣田地面集輸管網(wǎng)系統(tǒng)的優(yōu)化設(shè)計(jì)[J]. 油氣儲(chǔ)運(yùn)，2002，21(4)：14～18.

[2] 李書文.氣田網(wǎng)絡(luò)優(yōu)化布局初探[J].天然氣工業(yè)，1989，9(5)：68～72.

[3] 康正凌，袁宗明.樹枝狀天然氣管網(wǎng)優(yōu)化設(shè)計(jì)[J].天然氣工業(yè)，2001，21(3)：76～78，2.

[4] 李征.天然氣集輸管網(wǎng)優(yōu)化設(shè)計(jì)方法研究[J].內(nèi)蒙古石油化工，2009，34(6)：19～21.

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

[6] 孟榮章，李書文，湯林.大型氣田集輸管網(wǎng)布局優(yōu)化[J].石油規(guī)劃設(shè)計(jì)，1998，9(2)：20～22，4.

[7] 姚麟昱，駱彬，孟慶華，等.川西高壓高產(chǎn)氣田集輸管網(wǎng)規(guī)劃設(shè)計(jì)[J].石油規(guī)劃設(shè)計(jì)，2010，21(6)：21～24，54.

[8] 徐國(guó)棟，梁政.氣田集輸管網(wǎng)布局優(yōu)化研究[J].石油規(guī)劃設(shè)計(jì)，2004，15(6)：18～21.

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