可壓縮網絡流的輸送策略研究

劉 煒，吳瑞明

(上海交通大學 安泰經濟與管理學院，上海 200030)

1 引言

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

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

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

同時，研究者們也在嘗試運用啟發式算法來解決網絡輸運的相關問題。郎茂祥&胡思繼(2002)將爬山算法與遺傳算法相結合，構造了解決物流路徑優化問題的混合遺傳算法，在一定程度上啟發了現實生活中的物流管理。沐士光(2010)基于電信網絡的運行情況，運用改進的遺傳算法，在充分節省優化費用的基礎上降低了網絡拓撲路徑的總長度，并在網絡的時效性與應用的智能性方面取得了一定的成果。

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

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

2 問題描述

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

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

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

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

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

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

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

圖1 天然氣網絡輸送問題抽象模型

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

3 模型求解與策略分析

3.1 模型轉化

運籌學已經解決了傳統流的最小費用最大流問題，其具體模型如圖2所示：

圖2 傳統流的最小費用最大流模型

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

顯然，傳統流的最小費用最大流模型與可壓縮流的最小費用最大流模型有諸多不同，主要表現在：

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

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

以數學符號來表示，假設流量為F，對任一點Vi，其輸出流量為SCvi，輸入流量為SRvi，則

在傳統網絡流模型中，

在改進的網絡流模型中，

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

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

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

這樣做的原因如下：

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

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

在經過以上處理后，模型中所有節點的性質都與傳統流的最小費用最大流模型無異，即可壓縮流的最小費用最大流模型轉化為了傳統模型。

3.2 模型求解與策略分析

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

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

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

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

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

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

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

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

4 案例分析

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

支線1：B1-A8

支線2：B20-A14

支線3：B22-A16

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

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

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

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

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

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

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

5 結論與展望

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

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

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

[ 2 ] 林振智, 文福拴. 基于加權復雜網絡模型的恢復路徑優化方法[J]. 電力系統自動化, 2009, 33(6):11-15.

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

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

[ 5 ] 蔣洋. 多式聯運服務網絡優化建模方法研究[D]. 北京：北京交通大學, 2014.

[ 6 ] 張鵬程. 基于改進遺傳算法的冷鏈物流路徑優化研究[D]. 淮南：安徽理工大學, 2016.

[ 7 ] 許星. 物流配送路徑優化問題的研究[D]. 杭州：浙江大學, 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.