可壓縮網(wǎng)絡(luò)流的輸送策略研究

劉 煒，吳瑞明

(上海交通大學(xué) 安泰經(jīng)濟(jì)與管理學(xué)院，上海 200030)

1 引言

流是一個被廣泛使用的概念，在數(shù)學(xué)、工程學(xué)、力學(xué)、計算機(jī)科學(xué)等領(lǐng)域均有涉及。在網(wǎng)絡(luò)輸送問題中，無論實際上輸送的是何種物質(zhì)，都可以被視為是流的輸送。例如，水管輸送的是水，電路輸送的是電，以天然氣為代表的氣體也可以通過管道運送，而在做數(shù)理研究時，這些都可以被抽象為流，而忽略其本身物理性質(zhì)的不同。

在傳統(tǒng)的流模型中，當(dāng)一個流或多個流流入一個節(jié)點時，節(jié)點不會對流的總量有任何影響，即不論流入節(jié)點的流量為多少，流出節(jié)點時的流量均與流入節(jié)點時的流量相同，除非流進(jìn)入該節(jié)點后不再流出。而在現(xiàn)實生活中，許多流并不會滿足這樣的性質(zhì)。例如，河道中的水流流經(jīng)水壩時，由于水壩能夠攔截水流以及調(diào)節(jié)流量，因此水流流出水壩時，其流量將很有可能與流入水壩時不同；同樣，天然氣流進(jìn)入輸氣站時，由于輸氣站及周邊用戶通常有用氣需求，流出輸氣站的天然氣量也會與流入輸氣站時不同。因此，傳統(tǒng)的流模型在研究這種性質(zhì)的流輸送問題時變得不再適用，我們需要一個新的模型及算法來解決擁有這種性質(zhì)的流的運輸問題，而擁有這種性質(zhì)的流通常就被稱為可壓縮流。

在之前的研究中，蔣洋(2014)研究了交通運輸中的網(wǎng)絡(luò)流問題，建立了若干個交通運輸網(wǎng)絡(luò)流模型，涵蓋了不同情況下的交通狀況分析，取得了一定的成果。孫華燦等(2008)從貨運生產(chǎn)實踐出發(fā)，研究了運輸過程中的路徑優(yōu)化與成本節(jié)約問題，并提出了一個適用于特定條件的數(shù)學(xué)模型。而林振智&文福拴(2009)通過研究電力系統(tǒng)輸電過程的運行特點，提出了若干適合輸電系統(tǒng)的運行策略，并將其運用于實踐，促進(jìn)了一些地區(qū)輸電網(wǎng)絡(luò)的更新與發(fā)展。

同時，研究者們也在嘗試運用啟發(fā)式算法來解決網(wǎng)絡(luò)輸運的相關(guān)問題。郎茂祥&胡思繼(2002)將爬山算法與遺傳算法相結(jié)合，構(gòu)造了解決物流路徑優(yōu)化問題的混合遺傳算法，在一定程度上啟發(fā)了現(xiàn)實生活中的物流管理。沐士光(2010)基于電信網(wǎng)絡(luò)的運行情況，運用改進(jìn)的遺傳算法，在充分節(jié)省優(yōu)化費用的基礎(chǔ)上降低了網(wǎng)絡(luò)拓?fù)渎窂降目傞L度，并在網(wǎng)絡(luò)的時效性與應(yīng)用的智能性方面取得了一定的成果。

在管道輸運問題方面，Dandy G C等(1996)通過研究水管網(wǎng)絡(luò)的運行，找到了適合的效用函數(shù)，有效提升了紐約水管網(wǎng)的運行效率，引起了一定的社會反響。

但是，關(guān)于可壓縮流的網(wǎng)絡(luò)輸送尚無系統(tǒng)的研究成果，因此本文嘗試通過研究可壓縮流的相關(guān)性質(zhì)，提出系統(tǒng)解決這一問題的模型及算法，具有一定的理論與實用價值。

2 問題描述

以天然氣網(wǎng)絡(luò)輸送為例。天然氣的輸送通常有若干條線路，每條線路上有若干個輸氣站，每個輸氣站有一定的天然氣需求，用于維護(hù)輸氣站自身的正常運轉(zhuǎn)以及售賣天然氣給輸氣站周邊的用戶以獲取一定利益。在輸氣時，起點輸氣站將一定量的天然氣流裝進(jìn)管道，經(jīng)過管道的輸送到達(dá)相鄰的下游輸氣站。下游輸氣站根據(jù)需求取用后將剩余天然氣裝進(jìn)管道繼續(xù)輸送至下一個輸氣站。氣流最終經(jīng)過每一個輸氣站并由于各站點的取用持續(xù)減少，最終到達(dá)終點輸氣站，一次天然氣輸運就此結(jié)束。

在實際情況中，不同線路上的某些站點也有若干條支線相連接，因此形成了天然氣輸送網(wǎng)絡(luò)。在網(wǎng)絡(luò)中，每一段線路都對應(yīng)兩個參數(shù)，即單位成本與輸氣容量。單位成本指在該段線路上每輸送一個單位天然氣所需要付出的成本，輸氣容量指該段線路所能通過的最大天然氣量。這兩個參數(shù)決定了一定數(shù)量的天然氣通過一段線路所需要付出的成本，而一次天然氣輸運所需要的總成本即為每段線路的輸送成本之和。

顯然，一次天然氣輸送的最優(yōu)情況滿足以下兩個條件，即：

(1) 每個站點及周邊用戶的需求得到滿足；

(2) 本次輸送的總成本降到最低。

如果每一次天然氣輸送都能滿足上述條件，那么從長期的角度來看，運營者可以節(jié)省的費用將十分可觀，同時輸氣線路的效率也將顯著提升。

將以上問題抽象化可以得到如圖1所示的模型：

圖1 天然氣網(wǎng)絡(luò)輸送問題抽象模型

在模型中，Vs1-Vt1與Vs2-Vt2分別為兩條輸送線路，Vs1，Vs2分別為兩條線路的起點，Vt1，Vt2分別為兩條線路的終點。V1，V2，V3，V4是Vs1-Vt1線路上的中間節(jié)點(線路上仍有其他節(jié)點，僅列舉一部分，下同)，V5，V6，V7，V8是Vs2-Vt2線路上的中間節(jié)點，不同線路上的若干節(jié)點間可以連通，箭頭揭示了流運動的方向。每段線路上的參數(shù)為該段線路所對應(yīng)的單位成本(括號中左邊數(shù)值)以及輸送容量(括號中右邊數(shù)值)，每個節(jié)點上的參數(shù)為該節(jié)點的需求量。問題的目標(biāo)就是以最小的費用輸送滿足所有節(jié)點需求量的可壓縮流。

3 模型求解與策略分析

3.1 模型轉(zhuǎn)化

運籌學(xué)已經(jīng)解決了傳統(tǒng)流的最小費用最大流問題，其具體模型如圖2所示：

圖2 傳統(tǒng)流的最小費用最大流模型

在傳統(tǒng)流的最小費用最大流模型中，Vs為線路的起點，Vt為線路的終點。V1，V2，V3，V4，V5是Vs-Vt線路上的中間節(jié)點，箭頭揭示了流運動的方向。每段線路上的參數(shù)為該段線路所對應(yīng)的單位成本(括號中左邊數(shù)值)以及輸送容量(括號中右邊數(shù)值)。

顯然，傳統(tǒng)流的最小費用最大流模型與可壓縮流的最小費用最大流模型有諸多不同，主要表現(xiàn)在：

(1) 傳統(tǒng)模型只有一個起點和一個終點，而可壓縮流模型有多個起點和多個終點；

(2) 傳統(tǒng)模型的中間節(jié)點及終點均沒有需求量，而可壓縮流模型的中間節(jié)點及終點均有需求量。

以數(shù)學(xué)符號來表示，假設(shè)流量為F，對任一點Vi，其輸出流量為SCvi，輸入流量為SRvi，則

在傳統(tǒng)網(wǎng)絡(luò)流模型中，

在改進(jìn)的網(wǎng)絡(luò)流模型中，

因此，可壓縮流的最小費用最大流模型并不能用傳統(tǒng)流的最小費用最大流模型的解法直接求解。然而，由于可壓縮流模型與傳統(tǒng)模型仍有許多相似之處，如果能將可壓縮流的最小費用最大流模型轉(zhuǎn)化為傳統(tǒng)流的最小費用最大流模型，則可以使用已有的解法求解。具體的轉(zhuǎn)化過程如下：

(1) 新增一虛擬點Vs，并將該點用虛擬線路連接至所有的起點。同時，新增一虛擬點Vt，將所有的終點用虛擬線路連接至該點。在成本方面，所有新增虛擬線路的單位成本均視為0。在容量方面，Vs至各起點的容量視為無窮大，各終點到Vt的容量視為各終點的需求量。

(2) 將所有的中間節(jié)點用虛擬線路連接至Vt。在成本方面，所有新增虛擬線路的單位成本均視為0。在容量方面，各中間節(jié)點到Vt的容量視為各中間節(jié)點的需求量。

這樣做的原因如下：

首先，可壓縮流模型有多個起點和多個終點，經(jīng)過以上處理后可以回歸到一個起點和一個終點。在容量方面，Vs至各起點的容量視為無窮大，是因為不論最后從各起點輸入多少流量，都必須得到滿足，而Vs至各起點的線路實際上是不存在的，因此不可能限制容量。同樣，各終點到Vt的容量也可以視為無窮大，但在實際情況中，由于流量流至終點時一般來說只剩下滿足終點周邊需求的量(終點不再傳輸流)，各終點到Vt的容量通常不會超過各終點的需求量(若超過需求量則所求的流并不是最小費用流)。因此，也可將各終點到Vt的容量視為各終點的需求量。

其次，對于中間節(jié)點，SCvi-SRvi=-需求量，稍加變形即可得到SCvi-SRvi+需求量=0，而右邊為0滿足傳統(tǒng)模型。因此，只需將左邊變?yōu)檩敵隽髁繙p去輸入流量即可。實際上，觀察式子左邊可以得到SCvi-SRvi+需求量=SCvi+需求量-SRvi。也就是說，當(dāng)輸入流量為SRvi時，若輸出流量為SCvi+需求量，則將滿足傳統(tǒng)模型。SCvi為原有的輸出流量，因此考慮增加一條輸出虛擬線路至某一點，其輸出流量即為需求量，單位成本為0，這樣就可以滿足傳統(tǒng)模型。此時我們可以觀察到，所有終點連接至虛擬點Vt的線路的容量即為各終點的需求量，而將要新增的中間點到某一點的輸出流量也為需求量，因此不妨將中間點接出的虛擬線路也連接到虛擬終點Vt，這樣可以避免點的數(shù)量再增加。

在經(jīng)過以上處理后，模型中所有節(jié)點的性質(zhì)都與傳統(tǒng)流的最小費用最大流模型無異，即可壓縮流的最小費用最大流模型轉(zhuǎn)化為了傳統(tǒng)模型。

3.2 模型求解與策略分析

傳統(tǒng)流的最小費用最大流模型可用多種方法求解，其中，貪心算法是效率較高的一種。貪心算法是一種求局部最優(yōu)解的方法。在這一問題中，所有局部最優(yōu)解的累積就成為全局最優(yōu)解，因為這一問題屬于特殊的最短路徑問題，而最短路徑問題的全局最優(yōu)解即為所有局部最優(yōu)解的累積。

貪心算法最重要的步驟是貪心策略的選擇，只有選擇正確而高效的貪心策略，才能夠根據(jù)這一策略求局部最優(yōu)解以及全局最優(yōu)解。本問題的貪心策略是總選擇起點到終點單位成本最低的路徑，這是因為系統(tǒng)的總成本只與每一段路徑的單位成本和流過這一段路徑的流量有關(guān)，而一個流從起點流向終點時，無論流量大小，都需要流過路徑上的每一段，因此貪心策略的主體就是每一段路徑單位成本的總和，而其他因素不在考慮范圍之內(nèi)。

貪心算法的具體步驟如下：

(1)找到一條從起點到達(dá)終點的距離最短的路徑，距離使用該路徑上的邊的單位費用之和來衡量，最短距離記為m(Vs,Vt)；

(2)然后找出這條路徑上的邊的容量的最小值b，則當(dāng)前最大流增加b，同時當(dāng)前最小費用增加b*m(Vs,Vt)；

(3)將這條路徑上的每條正向邊的容量都減少b，每條反向邊的容量都增加b；

(4)重復(fù)以上步驟直到無法找到從源點到達(dá)匯點的路徑。

由于在轉(zhuǎn)化過程中，所有的中間節(jié)點和終點都被連接到一個虛擬終點Vt，所以算法開始時，從起點到終點的路徑有許多條。通過以上的步驟，貪心算法每次找出一條路徑，也就為一個節(jié)點找到了最小費用流。當(dāng)所有節(jié)點的最小費用流都被找到時，根據(jù)貪心算法的性質(zhì)，將所有的結(jié)果累加即為全局最優(yōu)解，即整個系統(tǒng)的最小費用最大流。

4 案例分析

以某公司的天然氣輸送網(wǎng)絡(luò)為例，該公司擁有兩條輸送線路，分別為線路A與線路B。線路A有18個輸氣站，從上游到下游分別編號為A1，A2，…，A18，線路B有24個輸氣站,從上游到下游分別編號為B1，B2，…，B24。同時，兩條線路中都有若干站點與另一條線路的站點相連，天然氣可在這些站點間雙向流動，具體如下：

支線1：B1-A8

支線2：B20-A14

支線3：B22-A16

天然氣輸送網(wǎng)絡(luò)的參數(shù)包含單位成本表(表1)、容量表(表2)以及需求量表(表3)(A18與B24為終點，不考慮輸氣單位成本；A1與B1為起點，不考慮需求量)。

根據(jù)以上數(shù)據(jù)，運用算法，可以得出從起點到每一點的滿足需求的最小費用路徑，如表4所示。

表1 某公司天然氣輸送網(wǎng)絡(luò)線路單位成本(以每段線路起點為標(biāo)志，單位：元/立方米)

表2 某公司天然氣輸送網(wǎng)絡(luò)線路容量(以每段線路起點為標(biāo)志，單位：萬立方米)

表3 某公司天然氣輸送網(wǎng)絡(luò)站點需求量(單位：萬立方米)

表4 某公司天然氣輸送網(wǎng)絡(luò)輸送路徑(以鄰接方式表示)

表4中，某一點的上一站表示從起點到該點的最小費用路徑中該點的上一站，而起點到上一站的最小費用路徑與上一站到該站的直接路徑結(jié)合即為起點到該站的最小費用路徑。因此，結(jié)合起點到每一站點的最小費用流即可得到整個系統(tǒng)運行的最小費用最大流。

5 結(jié)論與展望

可壓縮流是流的一種特殊形式。但是，在現(xiàn)實生活中，可壓縮流卻有十分廣泛的應(yīng)用。無論是河流、石油、天然氣或其他物質(zhì)，在以流的形式運動時都會具有一些可壓縮流的性質(zhì)與特征，因而可壓縮流網(wǎng)絡(luò)輸送的模型與算法無疑具有極強(qiáng)的現(xiàn)實意義。本文通過對特定模型性質(zhì)的研究，揭示了可壓縮流網(wǎng)絡(luò)輸送的一般規(guī)律，并提出了較為高效的算法來解決這一問題，較好地達(dá)到了預(yù)期的目標(biāo)。在某公司的案例中，運用該算法所得的成本比該公司目前運營的實際成本減少了15%左右，獲得了明顯的效果，而這一算法對現(xiàn)實生活中其他可壓縮流的輸送問題將提供較為可行的解決方案。

當(dāng)然，這一模型也有許多改進(jìn)的空間。例如，當(dāng)線路的容量不能滿足所有節(jié)點的需求量時，其結(jié)果將會產(chǎn)生一定的變化。同樣，如果各站點之間具有優(yōu)先級的不同，這一情況也將改變模型的設(shè)置，使得解決方案更為復(fù)雜。因此，算法本身仍可以持續(xù)改進(jìn)，以適應(yīng)不同的需求，相信未來的研究將使模型本身與算法都越來越完善。

[ 1 ] 孫華燦, 李旭宏, 陳大偉,等. 綜合運輸網(wǎng)絡(luò)中合理路徑優(yōu)化模型[J]. 東南大學(xué)學(xué)報(自然科學(xué)版), 2008, 38(5):873-877.

[ 2 ] 林振智, 文福拴. 基于加權(quán)復(fù)雜網(wǎng)絡(luò)模型的恢復(fù)路徑優(yōu)化方法[J]. 電力系統(tǒng)自動化, 2009, 33(6):11-15.

[ 3 ] 郎茂祥, 胡思繼. 用混合遺傳算法求解物流配送路徑優(yōu)化問題的研究[J]. 中國管理科學(xué), 2002, 10(5):51-56.

[ 4 ] 沐士光. 遺傳算法在網(wǎng)絡(luò)優(yōu)化問題中的研究與應(yīng)用[J]. 計算機(jī)仿真, 2010, 27(5):128-131.

[ 5 ] 蔣洋. 多式聯(lián)運服務(wù)網(wǎng)絡(luò)優(yōu)化建模方法研究[D]. 北京：北京交通大學(xué), 2014.

[ 6 ] 張鵬程. 基于改進(jìn)遺傳算法的冷鏈物流路徑優(yōu)化研究[D]. 淮南：安徽理工大學(xué), 2016.

[ 7 ] 許星. 物流配送路徑優(yōu)化問題的研究[D]. 杭州：浙江大學(xué), 2006.

[ 8 ] BAIR E S. Applied Ggroundwater modeling—simulation of flow and advective transport[J]. Groundwater, 2016(54).

[ 9 ] DANDY G C, SIMPSON A R, MURPHY L J. An improved genetic algorithm for pipe network optimization[J]. Water Resources Research, 1996, 32(2):449-458.

[10] WANG N, HO K, PAVLOU G, et al. An overview of routing optimization for internet traffic engineering[J]. IEEE Communications Surveys & Tutorials, 2008, 10(1):36-56.

[11] YAN B, WANG Y, KILLOUGH J E. Beyond dual-porosity modeling for the simulation of complex flow mechanisms in shale reservoirs[J]. Computational Geosciences, 2016, 20(1):69-91.