多品種流中特定品種在結點上的流量有要求的最大流算法設計

丁 振 寇瑋華 崔皓瑩

0 引 言

最大流問題是圖論的核心問題之一，傳統的最大流算法只能對單一品種的流量進行分配[1-4]。而對于多品種問題，雖然可以通過按品種拆分結點重構網絡來求解最大流，但是，這種解法經常使得運算過程很繁瑣[5,6]。多品種流交通網絡中，特定品種在結點上的流量有要求的問題，類似于運輸問題中的多品種問題，在實際交通網絡中頻繁出現，而在圖論中暫時沒有很好的求解方法。本文先對求解最大流的 Ford-Fulkerson算法進行改進，構造求解多品種問題最大流的算法，然后在這個基礎上構造了特定品種在結點上的流量有要求的交通網絡最大流算法。

1 基于多品種問題的Ford-Fulkerson算法描述

1.1 多品種流的交通網絡特性分析

多品種流可以定義為在交通網絡中存在的多股相互獨立的流。

傳統的交通網絡中，只針對單一品種流進行分析，而實際的交通網絡常常涉及多品種流的輸送。多品種流網絡具有以下幾個特點：

（1）獨立性。除非有特別說明，否則各品種流之間不能相互代替，具有獨立性。

（2）結點的準入特性。與一般交通網絡不同，多品種流交通網絡上每個結點對流的進入有品種限制。

（3）發出點與接收點。多品種流交通網絡有特定的一個或多個發出點與接收點。

目前求網絡最大流主流的算法有 Ford-Fulkerson算法等，而為求多品種流網絡的最大流勢必要對原有算法進行改進。

通過對多品種流交通網絡特性的分析，基于多品種問題的 Ford-Fulkerson算法與一般 Ford-Fulkerson算法的區別主要有以下幾個方面：

（1）結點的標記。多品種問題中有發出點與接收點，本文用xi、yj分別表示交通網絡中發出點和接收點。為了運算方便，定義一個總源點x和總匯點y，其他中間點用vi來表示。

（2）網絡中邊上流量的表示。一般Ford-Fulkerson算法用一個數值表示邊上的流量，而基于多品種問題的Ford-Fulkerson算法用集合f(fk)=( f1, f2,…, fk, …, fq)表示該邊上每一種品種的流量。

（3）在一條增流鏈上，基于多品種問題的Ford-Fulkerson算法只能對一個品種的流量進行調整。

（4）由于結點的準入特性，在增流時，多品種問題需要確認下一個結點是否能接收該品種的流量。

1.2 多品種流交通網絡描述

根據以上描述，對基于多品種問題的Ford-Fulkerson算法可以定義如下：

（1）交通網絡圖用G=( X,Y, V, E,C,F)來表示。

（2）集合X={x,xi|i=1,2,…,n1}, x為圖G的源，xi為發出點；集合Y={y,yj|j=1,2,…,n2}，y為圖G的匯，yj為接收點；中間結點集合 V={vi|i=1,2,…,n3}。其中X、Y和V只能接收或發出特定品種的流量；邊集合E={e(x,xi),e(xi,vi),e(vi,vj),e(vj,yi),e(yi,y),e(xi,yj)|x,xi∈X;vi,vj∈V;yi,y∈Y}；C為邊的容量的集合；

（3）F為邊的流量的集合，假設k為圖G中的第k個品種（k=1,2,…,q），fkuv為邊（u,v）上品種k的流量，fuv(fk)=(f1, f2,…,fq)表示邊（u,v）上各品種的流量，并且f1+f2+…+fq=f(u,v)，f(u,v)為該邊上所有品種流量之和。

圖G中滿足以下條件的一組流可以稱為可行流：

①容量限制條件，對任意邊e=(u,v)∈E有

其中，c為(u,v)的容量，fkuv為該邊上品種k的流量。

②結點流量平衡條件：

對于結點u≠x,y，有

以上條件保證結點上每個品種的流量守恒，同時保證了結點上所有品種的流量之和的守恒。

用v(fk)表示從x到y的品種k的可行流的流量，v(f)表示從x到y的可行流流量的總和。對于結點u=x或y，有

1.3 算法步驟

基于多品種問題的Ford-Fulkerson算法步驟如下[7]：

第一步：給圖 G一個初始流（一般為平凡的可行流）。給初始流的過程中要滿足以下規則：

規則1：輸送給結點的某品種的流量必須滿足該結點對品種類別的要求。

規則2：各個品種之間的流量應該區分開來。

交通網絡 G上各邊對容量和流量的描述應遵從多品種流特點，用[c,( f1,f2,…,fq)]表示。同時給結點x標號。

第二步：尋找源x到匯y的增流鏈Q的方法：

尋找增流鏈首先必須滿足下列規則：

規則3：一條增流鏈上只能對一個品種的流量進行調整。當對某個品種在增流鏈上進行流量調整時，不管是前向邊還是后向邊，在該增流鏈上只能對該品種的流量進行調整。

（1）與結點v相關的邊上某一品種能否增流的條件：

①基于規則1，即結點v能否接收該品種的流。

當邊e=(u,v)為后向邊時，有邊(u,v)上品種k的流量＞ 0 。

（2）對滿足以上條件的結點 v進行標記（u，邊的方向和調整的品種，lk(v)）。其中u為標記點v的前一個結點；v為終點時邊的方向，用+表示；v為始點時邊的方向，用-表示；邊的方向和調整的品種表示如下：+k或者-k；lk(v)表示品種k的調整量。v為終點時lk(v)=min{lk(u),C(u,v)-f(u,v)}，v為始點時lk(v)=min{lk(u),fuvk}，其中 f(u,v)為(u,v)上所有品種流量之和。

第三步：按照標號的第一項，從匯y進行反向追蹤，可得到增流鏈Q以及品種k的調整量lk(Q)=lk(y)。

第四步：利用修改流性質進行調整：

（1）增流鏈Q的前向邊，品種k的流量加上調整量 lk(Q)。

（2）增流鏈Q的后向邊，品種k的流量減去調整量 lk(Q)。

（3）非增流鏈Q的邊的調整量不變。

第五步：返回第二步，不斷循環，直到不能找到增流鏈為止。

為了引用方便，在這里假設用 MV-Ford-Fulkerson(G)表示基于多品種的Ford-Fulkerson算法，其中G表示交通網絡圖。

2 對特定品種在結點上的流量有要求的幾種情況

為了描述圖 G中對特定品種在結點上的流量有要求的約束條件[8]，將基于多品種流的Ford-Fulkerson算法的描述形式采用MV-Ford-Fulkerson{G,MAXFlow|(A)}來表示，其中MAXFlow|(A)表示在約束條件A下的最大流量。若A=?，即對特定品種沒有約束條件的MV-Ford-Fulkerson算法用MV-Ford-Fulkerson{G,MAXFlow|(?)}表示。本文討論的對特定品種的流量有要求的4種情況描述如下：

（1）某發出點發出某一品種的流量有最低限制

假設交通網絡圖中有 q個品種，要求發出點 xi發出品種 k的流量至少為 Z。用 MV-Ford-Fulkerson{G,MAXFlow|(Flow(xi)k≥Z,)}來描述此約束條件。

（2）某接收點接收某一品種的流量有最低限制

假設交通網絡圖中有 q個品種，要求接收點 yj接收品種 k的流量至少為 Z。用 MV-Ford-Fulkerson{G,MAXFlow|(Flow(yj)k≥Z,)}來描述此約束條件。

（3）某發出點發出某一品種的流量有最高限制

假設交通網絡圖中有 q個品種，要求發出點 xi發出品種 k的流量最多為 Z。用 MV-Ford-Fulkerson{G,MAXFlow|(Flow(xi)k≤Z,)}來描述此約束條件。

（4）某接收點接收某一品種的流量有最高限制

假設交通網絡圖中有 q個品種，要求接收點 yj接收品種 k的流量最多為 Z。用 MS-Ford-Fulkerson{G,MAXFlow|(Flow(yj)k≤Z,)}來描述此約束條件。

3 多品種流中對特定品種在結點上的流量有要求的最大流算法

3.1 某發出點發出的某一品種的流量有最低限制的算法

（1）算法思想[9]

由于輸送流量給發出點xi的邊僅有一條，因此該約束可以轉換為要求邊(x,xi)上的品種k的流量至少為Z。在計算過程中，先利用增流鏈方法將圖G中在x與xi之間品種k的流量調整到限制值，在此基礎上進行流量分配。但(x,xi)之間的流量須滿足以下規則：

規則4：如果新的增流鏈包括(x,xi)，且為前向邊，那么該邊上的該品種的流量調整量為容量減去所有品種流量之和。

規則5：如果新的增流鏈包括(x,xi)，且為后向邊，那么該邊上的該品種的流量調整量為該品種的流量減去最低限值Z。

（2）算法過程

發出點xi發出品種k的流量不能低于限制值Z，步驟如下：

第一步：如果邊(x,xi)上的品種k的流量fkxxi小于限制值Z，進行以下過程：

（1）按照標記法先找從發出點xi到匯y品種k的不飽和鏈Q1，尋找增流鏈的時候必須滿足規則1、2和3。

（2）確定增流鏈(x,xi)+Q1上的品種k的調整量：lk((x,xi)+Q1)=min{lk(Q1),C(x,xi)-f(x,xi)}。

（3）對增流鏈(x,xi)+Q1按照修改流性質進行流量調整，如果(x,xi)之間fkxxi大于等于限制值Z，停止。否則，返回第（1）個過程。

第二步：對圖G調用MV-Ford-Fulkerson(G)，尋找增流鏈。如果增流鏈 Q包括(x,xi)，并對品種 k進行流量調整，根據規則4和5，增流鏈的調整量如下所示：

當邊(x,xi)為前向邊時，lk(Q)=min{lk(Q1),C(x,xi)-f(x,xi)}；當邊(x,xi)為后向邊時，lk(Q)=min{lk(Q1),fkxxi-Z}；第三步：返回第二步，不斷循環，直到不能找到增流鏈為止。

在以上的算法中，邊(x,xi)是不可能出現后向邊的，本文寫出后向邊的目的是為了能夠拓展到對多品種問題任意一條邊的流量有限制的情況。本文的算法對多品種網絡上任意一條邊上某品種的流量有限制的情況同樣適用。

3.2 某接收點接收某一品種的流量有最低限制的算法

（1）算法思想

同理，該約束可以轉換為要求邊(yj,y)上的品種k的流量至少為Z。在計算過程中，先利用增流鏈方法將圖G中在yj與y之間品種k的流量調整到最低限制值，在此基礎上進行流量分配。規則與前述相似。

（2）算法過程與3.1相似。

3.3 某發出點發出某一品種的流量有最高限制的算法

（1）算法思想

限制邊(x,xi)上的品種k的流量最高為Z。只需在進行流量分配和流量調整時，使邊(x,xi)上的品種k的流量不要超過限制值即可。

（2）算法步驟

調用MV-Ford-Fulkerson(G)。

第一步：給圖G一個初始流。若(x,xi)上fkxxi≤Z，則進行下一步，否則重新分配流量。

第二步：尋找源x到匯y的增流鏈Q。

（1）檢查增流鏈上是否包含邊(x,xi)，并且對品種k進行了流量調整。否則，進行第三步。

（2）當增流鏈 Q上有邊(x,xi)，并且調整的是品種k的流量，則確認調整后fkxxi是否小于等于Z，若是則進行下一步，否則重新調整 lk(Q)的值或者重新尋找增流鏈。

第三步：返回第二步，不斷循環，直到不能找到增流鏈為止。

3.4 某接收點接收某一品種的流量有最高限制的算法

（1）算法思想

限制邊(yj,y)上的品種 k的流量最高為 Z。只需在進行流量分配和流量調整時，使邊(yj,y)上的品種k的流量不要超過限制值即可。

（2）算法步驟

算法過程與3.3相似。

4 示 例

已知某交通網絡有3個品種Ⅰ、Ⅱ和Ⅲ的貨物需要輸送，各結點關系如圖1所示，圖中數值表示邊的容量。表 1表示各結點所能接收的品種。要求結點x1發出品種Ⅱ的數量至少為4，y2接收品種Ⅰ的數量至少為 5，x3發出品種Ⅱ的數量最多為 3，y3接收品種Ⅱ的數量最多為4，請分配最大流。

圖1 運輸網絡結構Fig.1 Configuration of traffic network

表1 各結點所能接收的品種類型Tab.1 Types of the varieties each node can receive

該題是多品種流的問題，同時對特定的品種有條件要求，因此不能直接采用Ford-Fulkerson算法。針對題中的約束條件，可以采用本文相關的一些算法。由于篇幅限制，省略掉尋找增流鏈的過程，解題過程如下：

給定初始流為零流，如圖2所示。

圖2 初始化的運輸網絡結構Fig.2 Initialization of the transportation network configuration

針對約束條件，結點 x1發出品種Ⅱ的數量至少為4，即要求（x,x1）上的品種Ⅱ的流量至少為4。尋找 x1到 y，品種Ⅱ不飽和鏈 Q1：x1→v1→v2→y3→y，調整量：

增流鏈(x,x1)+Q1品種Ⅱ的調整量：lⅡ((x,x1)+Q1)=min{C(x,x1)-f(x,x1), lⅡ(Q2)}=min{8-0,4}=4。利用修改流性質進行調整，fkxx1=4。同時，由于限制了y3接收品種Ⅱ的數量最多為4，增流鏈上有邊(y3,y)，并對品種Ⅱ增流，檢查(y3,y)上流量。品種Ⅱ流量小于等于4，該結果是滿足限制條件的，結果如圖3所示。

圖3 基于修改流的分配方案1Fig.3 Scheme 1 of flow distribution based on modification

同理，針對約束條件 y2接收品種Ⅰ的數量至少為5，即要求(y2,y)上的品種Ⅰ的流量至少為5。尋找x到 y2，品種Ⅰ不飽和鏈 Q2：x→x2→v1→y2，調整量：lⅠ(Q2)=6。增流鏈 Q2+(y2,y)品種Ⅰ的調整量：lⅠ(Q2+(y2,y))=6。利用修改流性質進行調整，結果如圖4所示。

圖4 基于修改流的分配方案2Fig.4 Scheme 2 of flow distribution based on modification

第三步：尋找增流鏈。Q3：x→x1→y1→y，對品種Ⅰ進行流量調整，lⅠ(Q3)=4，結果如圖5所示。同理，尋找增流鏈 Q4：x→x2→v2→y3→y，對品種Ⅲ進行流量調整，lⅢ(Q4)=4，結果如圖6所示。尋找增流鏈 Q5：x→x3→v2→v1→y2→y，對品種Ⅱ進行流量調整，lⅡ(Q5)=3，結果如圖 7所示。尋找增流鏈 Q6：x→x3→v2→y3→y，對品種Ⅲ進行流量調整，lⅢ(Q6)=4，結果如圖8所示。

在圖4中再無法尋找到增流鏈，最終方案如圖8所示。

圖5 基于修改流的分配方案3Fig.5 Scheme 3 of flow distribution based on modification

圖6 基于修改流的分配方案4Fig.6 Scheme 4 of flow distributing based on modification

圖8 基于修改流的最終方案Fig.8 Scheme of flow distribution based on modification

5 結束語

本文研究的算法，是在Ford-Fulkerson算法基礎上，解決多品種流中結點上對特定品種的流量有要求的交通網絡最大流問題，本文的算法對多品種網絡上任意一條邊的某品種的流量有限制的情況同樣適用。對于特別復雜的情況，本文的標號方法和各品種流量表示不是很明晰，應加以改進。本文研究對象針對的是發出點與接收點，而針對其他中間結點某品種流量的限制還沒有研究，應繼續研究相應的算法。

[1] 寇瑋華.運籌學[M].成都：西南交通大學出版社，2013.

[2] 徐周波,古天龍,趙嶺忠.網絡最大流問題求解的符號ADD 增廣路徑算法[J].計算機科學，2005,32(10)∶38-54.

[3] 寇瑋華,李宗平. 運輸網絡中有流量需求的轉運結點最大流分配算法[J]. 西南交通大學學報，2009,44(1)∶118-121

[4] Daiheng Ni. Determining Traffic-Flow Characteristics by Definition for Application in ITS [J]. IEEE Transactions on Intelligent Transportation Systems,2007, 8(2)∶ 181-187.

[5] 焦永蘭.管理運籌學[M].北京∶中國鐵道出版社,2005.

[6] 甘愛英等. 運籌學[M].北京∶清華大學出版社,2002.

[7] 孫澤宇,丁國強,程志謙. 網絡最大流求解算法的研究[J]. 微計算機信息, 2010,(03)∶143-145.

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

[9] 寇瑋華,朱雪麗,張聰聰. 交通網絡兩個相鄰結點之間有流量約束的最大流分配算法[J].交通運輸工程與信息學報, 2010,8(1)∶7-13.