劉 煒，吳瑞明

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

1 引言

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

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

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

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

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

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

2 問題描述

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

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

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

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

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

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

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

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

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

3 模型求解與策略分析

3.1 模型轉(zhuǎn)化

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

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

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

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

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

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

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

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

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

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

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

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

這樣做的原因如下：

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

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

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

3.2 模型求解與策略分析

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

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

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

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

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

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

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

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

4 案例分析

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

支線1：B1-A8

支線2：B20-A14

支線3：B22-A16

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

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

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

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

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

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

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

5 結(jié)論與展望

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

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

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

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

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

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

[ 5 ] 蔣洋. 多式聯(lián)運(yù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.