多品種流交通網絡的最大流算法研究

崔皓瑩 寇瑋華 丁 振

0 引 言

交通網絡中的最大流量的分配問題，通常是針對單一品種的流量分配，在保持流量約束與守恒的條件下，一般選擇基于Ford-Fulkerson算法對流量進行調整，以達到交通網絡的最大流狀態(tài)[1-10]。但在實際應用中，多品種流的最大流分配常常會在交通網絡中出現(xiàn)，但是，針對于多品種流的研究成果卻很少，因此，本文在借鑒傳統(tǒng)的網絡流理論及算法的基礎上，構建了可行的多品種流交通網絡最大流分配算法。

本文首先介紹多品種流交通網絡問題并對其進行分析，在保證流量約束的條件下，基于 Ford-Fulkerson算法的思路，構造多品種流交通網絡的最大流算法，在保證網絡流量分配為最大流的狀態(tài)下，明確每一個品種在網絡中的流量分配。

1 多品種流交通網絡的引例

為了解釋說明交通網絡的多品種流問題，也為了清晰地闡述多品種流交通網絡最大流分配的算法研究，先給出多品種流交通網絡的一個引例。

圖1 交通網絡的引例Fig.1 An example of transportation network

引例 有交通網絡如圖1所示，它分別給出了運送能力和運送費用，即邊的容量、費用。其中 x1生產Ⅰ和Ⅲ兩種產品，數(shù)量分別為7 t和4 t；x2生產Ⅱ和Ⅲ兩種產品，數(shù)量分別為5 t和8 t；x3生產Ⅰ和Ⅱ兩種產品，數(shù)量分別為 6 t和 3 t。y1、y2、y3分別為三個需求地，y1需要Ⅰ和Ⅲ兩種產品，需求量分別為6 t和7 t；y2需要Ⅱ和Ⅲ兩種產品，需求量分別為 3 t和9 t；y3需要Ⅰ和Ⅱ兩種產品，需求量分別為7 t和8 t。

針對此引例，傳統(tǒng)的交通網絡最大流分配算法就不能完全適用于多品種交通網絡的流量分配問題，所以，有必要研究多品種流交通網絡的最大流分配算法。

2 多品種交通網絡的最大流分配研究

2.1 多品種交通網絡最大流問題分析

給定交通網絡 G=(V,E,C,F,W,X,Y )，其中V=(v1,v2,…,vn)，E=(e1,e2,…,em)。對頂點集合 V 取定兩個非空子集X、Y。X為只發(fā)出流量的頂點集合，Y為只接收流量的頂點集合，且X∩Y=?。把X中的頂點xi稱為網絡G的源，Y中的頂點yi稱為網絡G的匯。針對邊ei賦予兩個非負的整數(shù)參數(shù)cij、fij，分別為邊(vi,vj)的容量、流量。設頂點vi?X、Y，即vi為中間點，用f+(vi)表示頂點vi發(fā)出的流量之和，f-(vi)表示頂點vi接收的流量之和。設k為多品種流中的第k個品種流，其中k=1,2,…,q。fijk為第k個品種流在邊(vi,vj)上的流量，f+(vik)表示頂點vi發(fā)出第k個品種流的流量之和，f-(vik)表示頂點vik接收第k個品種流的流量之和。

針對多品種交通網絡圖，邊(vi,vj)要遵從兩個約束條件：

（2）所有中間點vi都要遵從流量守恒條件，即在保證所有品種的總流量守恒的同時，也要保證每一個品種的分流量守恒，則有：

基于以上分析，多品種交通網絡的最大流分配模型如模型(1)所示：

2.2 最大流算法思路

基于Ford-Fulkerson算法的思路，本文針對于多品種交通網絡問題設計了其最大流算法。先將多源多匯的交通網絡圖G，化為單源單匯形式的網絡圖Gn，邊（vi，vj）的屬性為容量、流量，設表現(xiàn)形式如下，，式中，fij表示邊（vi，vj）的總流量；fijk表示各品種的分流量。再給定網絡圖Gn一個初始的可行流 f（也可以是零流），對結點進行標號，判斷和尋找是否存在增流鏈，如果不存在，則當前網絡已為最大流，算法停止；如果存在增流鏈，再根據其調整值，調整網絡，直至沒有贈流鏈，算法停止。

針對最大流算法，設計結點vj的標號形式如下：[vi,邊的方向,lk(vj)]，其中，vi表示被標號點 vj的前一個頂點；邊的方向通過“+”或“-”表示前向邊或后向邊；lk(vj)表示增流鏈中針對于k品種的調整量。

2.3 最大流算法步驟

算法步驟如下：

第一步 將 G轉換為單源單匯的結構形式，構建新的網絡圖Gn：

（1）單源的構建

① 基于所有源xi共有的品種數(shù)q，在G中設定q個新源xk，同時將頂點xk與生產k品種的頂點xi相連，構建出邊(xk,xi)。該邊的容量c(xk,xi)等于網絡G的源xi所生產的第k個品種的數(shù)量。

② 設定 x作為單源，同時構建邊(x,xk)，該邊的容量 c(x,xk)=∑c(xk,xi)。

（2）單匯的構建

① 基于所有匯 yi共需要的品種數(shù) q，在 G中設定 q個新匯 yk，同時將接收 k品種的頂點 yi與頂點yk相連，構建出邊(yi, yk)。該邊的容量c(yi, yk)等于交通網絡G的匯yi所需要的第k個品種的數(shù)量。

② 設定y作為單匯，同時構建邊(yk, y)，該邊的容量 c(yk, y)=∑c(yi, yk)。

第二步 設集合 X={x, xk, xi︱k=1,2,…,q;i=1,2,…,n}、V={vi︱i=1,2,…,n}、Y={yi, yk, y︱k=1,2,…,q;i=1,2,…,n }，并給定網絡圖Gn一個初始流(一般為零流)，即初始的均為，設源x的增流量l(x)= +∞，可以對源x標號為(0,+,+∞)。

第三步 對與x有直接連線的頂點xk標號，其中邊(x, xk)為前向邊。若fxk=cxk，此時該邊流量不能增加，那么不對xk標號，即不能對k品種進行流量調整；若fxk＜cxk，此時流量能增加，存在 lk(vx)=min{l(x),cxkfxk}，那么，頂點xk標號為[x,+,lk(vx)]，可判斷出此時是對該路徑的k品種進行流量調整。

第四步 繼續(xù)檢查，判斷之后的邊(vi,vj)能否成為增流鏈的邊，邊（vi,vj）成為增流鏈中的邊必須滿足如下條件：

（1）當vj∈X,V時，判斷邊（vi, vj）是否為增流鏈中的邊，分以下兩種情況：

① 當邊(vi, vj)為前向邊時：若 fij＜cij，則該邊流量可以增加，邊(vi,vj)為增流鏈中的邊，那么，lk(vj)=min{lk(vi),cij-fij}，且頂點 vj標號為[vi,+,lk(vj)]；若 fij=cij，則該邊流量不可以增加，即不對頂點 vj標號。

② 當邊(vi, vj)為后向邊時：若fij＞0，則該邊流量可以減少，邊(vi,vj)為增流鏈中的邊，那么，lk(vj)=min{lk(vi), fij, fijk}，且頂點 vj標號為[vi, -, lk(vj)]；若fij=0，則該邊流量不可以減少，即不對頂點vj標號。

（2）當 vj∈Y時，判斷邊(vi, vj)是否為增流鏈中的邊，分以下情況：

① 當 vj∈yi時，設 vm為 yi的前一個頂點，判斷邊(vm，yi)是否為增流鏈中的邊，方法同上。

② 當 vi∈yi，vj∈yk時，判斷邊(yi，yk)是否為增流鏈中的邊，分以下兩種情況：

? 頂點 yi與頂點 yk有直接連線，則判斷邊(yi，yk)能否成為為增流鏈中的邊，若邊(yi，yk)為增流鏈中的邊，那么對頂點 yk標號，若邊(yi，yk)不為增流鏈中的邊，那么不對頂點yk標號。具體方法同上。

? 頂點 yi與頂點 yk沒有直接連線，則邊(yi，yk)不為增流鏈中的邊，那么不對頂點yk標號。

若頂點 yk被標號，則轉第五步；若頂點 yk沒被標號，說明此路徑無法找到一條增流鏈，返回第三步重新尋找增流鏈。

第五步 當匯y被標號，那么說明存在增流鏈，此時，按照標號方式的第一項，從匯y進行反向追蹤，可得到增流鏈Q，以及調整量lk(Q)=lk(y)。流量的調整按照以下規(guī)則進行：

（1）邊(vi, vj)在增流鏈中為前向邊時，邊的流量調整為，其余品種的流量保持不變。

（2）邊(vi, vj)在增流鏈中為后向邊時，邊的流量調整為，其余品種的流量保持不變。

第六步 返回第三步，不斷循環(huán)，直到不能找到增流鏈為止，即此時網絡已為最大流，同時可確定多品種流交通網絡 Gn在最大流情況下，各品種的流量分配方案。

2.4 示例求解

為了更好地解釋說明多品種交通網絡的最大流分配問題，下面對引例進行求解。

第一步 將圖 1的交通網絡轉換為單源單匯的網絡圖Gn，并給Gn一個初始流，給定源x標號(0,+,+∞)，如圖2所示，邊旁數(shù)據依次表示容量、流量。

第二步 利用標號法尋找從源x到匯y的一條增流鏈 x→xI→x1→v1→ y1→y，lI(Q)=min{13,7,8,3,6,13}=3，該增流鏈包含邊(x，xI)，因此是對I品種增流，按照 Ford-Fulkerson算法的思路調整流量，如圖 3所示。

第三步 反復迭代尋找增流鏈，對其對應品種進行流量調整，其余步驟省略，最終的結果如圖4所示。

圖2 交通網絡的初始流Fig.2 Initialization flow of the transportation network

圖3 第一次流量分配Fig.3 First flow distributing of the transportation network

圖4 最大流分配方案Fig.4 Maximum flow distribution scheme

通過以上步驟，由圖4可以知道該引例的總體方案，也可以知道該引例各個品種的具體方案。交通網G的最大流 max z=8+3+3+9+3+4＝30，同時可知 x1發(fā)出Ⅰ品種7 t、Ⅲ品種4 t；x2發(fā)出Ⅱ品種5 t、Ⅲ品種7 t，x3發(fā)出Ⅰ品種5 t、Ⅱ品種2 t。

3 結束語

本文通過對多品種交通網絡進行分析，并將多源多匯網絡圖構建成單源單匯的網絡圖形式，再基于Ford-Fulkerson算法在交通網絡中尋找增流鏈以及流量調整的思路，設計了適合于多品種交通網絡的最大流算法，并通過示例對算法進行了驗證。然而，在交通網絡中，仍然存在許多問題需要研究。一個多品種交通網絡的最大流的流值是一定，但分布的狀態(tài)不同，因此，最大流的分配方案是多種多樣的，那么，也許就會存在特定的產地或銷地有著具體的流量要求的情況下，求解多品種交通網絡的流量分配問題，又或者在多品種交通網絡中的中間點有截流的情況下，對該網絡進行流量分配，這些問題都有待以后的研究。

[1] 寇瑋華 編著, 李宗平 主審. 運籌學[M]. 成都：西南交通大學出版社，2013.

[2] 甘愛英等. 運籌學[M]. 北京：清華大學出版社，2002.

[3] 寇瑋華，崔皓瑩. 滿足交通網絡流量增長態(tài)勢的擴能優(yōu)化研究[J]. 交通運輸工程與信息學報，2012，10(4)：19-25.

[4] 寇瑋華，董 雪，呂林劍. 交通運輸網絡中兩個結點間有流量約束的最小費用最大流算法[J]. 蘭州交通大學學報，2009，28(6)：104-109.

[5] Network Optimization.麻省理工學院開放課件[EB/OL]. http∶//www.core.org.cn/OcwWeb/index.htm,2003.

[6] Transportation Flow System.麻省理工學院開放課件[EB/OL]. http∶//www.core.org.cn/OcwWeb/index.htm,2002.

[7] 謝 政,湯澤瀅. 帶模糊約束的最小費用流問題[J].模糊系統(tǒng)與數(shù)學,1999,13(2)∶ 90-941.

[8] 程 琳，王 煒. Dial交通量分配模型和選擇率問題的研究[J]. 交通運輸系統(tǒng)工程與信息，2002，2(3)：29-32.

[9] 陳光亞. 帶有向量值費用函數(shù)的交通網絡平衡問題——模型與分析[J]. 交通運輸系統(tǒng)工程與信息，2006，6(5)：56-58.

[10] 任 剛，王 煒. 可直接計算轉向流量的改進型Dial交通分配算法[J]. 中國公路學報，2005，18(4)：83-86.