多品種流中特定品種在結(jié)點(diǎn)上的流量有要求的最大流算法設(shè)計(jì)

丁 振 寇瑋華 崔皓瑩

0 引 言

最大流問題是圖論的核心問題之一，傳統(tǒng)的最大流算法只能對單一品種的流量進(jìn)行分配[1-4]。而對于多品種問題，雖然可以通過按品種拆分結(jié)點(diǎn)重構(gòu)網(wǎng)絡(luò)來求解最大流，但是，這種解法經(jīng)常使得運(yùn)算過程很繁瑣[5,6]。多品種流交通網(wǎng)絡(luò)中，特定品種在結(jié)點(diǎn)上的流量有要求的問題，類似于運(yùn)輸問題中的多品種問題，在實(shí)際交通網(wǎng)絡(luò)中頻繁出現(xiàn)，而在圖論中暫時(shí)沒有很好的求解方法。本文先對求解最大流的 Ford-Fulkerson算法進(jìn)行改進(jìn)，構(gòu)造求解多品種問題最大流的算法，然后在這個(gè)基礎(chǔ)上構(gòu)造了特定品種在結(jié)點(diǎn)上的流量有要求的交通網(wǎng)絡(luò)最大流算法。

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

1.1 多品種流的交通網(wǎng)絡(luò)特性分析

多品種流可以定義為在交通網(wǎng)絡(luò)中存在的多股相互獨(dú)立的流。

傳統(tǒng)的交通網(wǎng)絡(luò)中，只針對單一品種流進(jìn)行分析，而實(shí)際的交通網(wǎng)絡(luò)常常涉及多品種流的輸送。多品種流網(wǎng)絡(luò)具有以下幾個(gè)特點(diǎn)：

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

（2）結(jié)點(diǎn)的準(zhǔn)入特性。與一般交通網(wǎng)絡(luò)不同，多品種流交通網(wǎng)絡(luò)上每個(gè)結(jié)點(diǎn)對流的進(jìn)入有品種限制。

（3）發(fā)出點(diǎn)與接收點(diǎn)。多品種流交通網(wǎng)絡(luò)有特定的一個(gè)或多個(gè)發(fā)出點(diǎn)與接收點(diǎn)。

目前求網(wǎng)絡(luò)最大流主流的算法有 Ford-Fulkerson算法等，而為求多品種流網(wǎng)絡(luò)的最大流勢必要對原有算法進(jìn)行改進(jìn)。

通過對多品種流交通網(wǎng)絡(luò)特性的分析，基于多品種問題的 Ford-Fulkerson算法與一般 Ford-Fulkerson算法的區(qū)別主要有以下幾個(gè)方面：

（1）結(jié)點(diǎn)的標(biāo)記。多品種問題中有發(fā)出點(diǎn)與接收點(diǎn)，本文用xi、yj分別表示交通網(wǎng)絡(luò)中發(fā)出點(diǎn)和接收點(diǎn)。為了運(yùn)算方便，定義一個(gè)總源點(diǎn)x和總匯點(diǎn)y，其他中間點(diǎn)用vi來表示。

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

（3）在一條增流鏈上，基于多品種問題的Ford-Fulkerson算法只能對一個(gè)品種的流量進(jìn)行調(diào)整。

（4）由于結(jié)點(diǎn)的準(zhǔn)入特性，在增流時(shí)，多品種問題需要確認(rèn)下一個(gè)結(jié)點(diǎn)是否能接收該品種的流量。

1.2 多品種流交通網(wǎng)絡(luò)描述

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

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

（2）集合X={x,xi|i=1,2,…,n1}, x為圖G的源，xi為發(fā)出點(diǎn)；集合Y={y,yj|j=1,2,…,n2}，y為圖G的匯，yj為接收點(diǎn)；中間結(jié)點(diǎn)集合 V={vi|i=1,2,…,n3}。其中X、Y和V只能接收或發(fā)出特定品種的流量；邊集合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為邊的流量的集合，假設(shè)k為圖G中的第k個(gè)品種（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的流量。

②結(jié)點(diǎn)流量平衡條件：

對于結(jié)點(diǎn)u≠x,y，有

以上條件保證結(jié)點(diǎn)上每個(gè)品種的流量守恒，同時(shí)保證了結(jié)點(diǎn)上所有品種的流量之和的守恒。

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

1.3 算法步驟

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

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

規(guī)則1：輸送給結(jié)點(diǎn)的某品種的流量必須滿足該結(jié)點(diǎn)對品種類別的要求。

規(guī)則2：各個(gè)品種之間的流量應(yīng)該區(qū)分開來。

交通網(wǎng)絡(luò) G上各邊對容量和流量的描述應(yīng)遵從多品種流特點(diǎn)，用[c,( f1,f2,…,fq)]表示。同時(shí)給結(jié)點(diǎn)x標(biāo)號。

第二步：尋找源x到匯y的增流鏈Q(jìng)的方法：

尋找增流鏈?zhǔn)紫缺仨殱M足下列規(guī)則：

規(guī)則3：一條增流鏈上只能對一個(gè)品種的流量進(jìn)行調(diào)整。當(dāng)對某個(gè)品種在增流鏈上進(jìn)行流量調(diào)整時(shí)，不管是前向邊還是后向邊，在該增流鏈上只能對該品種的流量進(jìn)行調(diào)整。

（1）與結(jié)點(diǎn)v相關(guān)的邊上某一品種能否增流的條件：

①基于規(guī)則1，即結(jié)點(diǎn)v能否接收該品種的流。

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

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

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

第四步：利用修改流性質(zhì)進(jìn)行調(diào)整：

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

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

（3）非增流鏈Q(jìng)的邊的調(diào)整量不變。

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

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

2 對特定品種在結(jié)點(diǎn)上的流量有要求的幾種情況

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

（1）某發(fā)出點(diǎn)發(fā)出某一品種的流量有最低限制

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

（2）某接收點(diǎn)接收某一品種的流量有最低限制

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

（3）某發(fā)出點(diǎn)發(fā)出某一品種的流量有最高限制

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

（4）某接收點(diǎn)接收某一品種的流量有最高限制

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

3 多品種流中對特定品種在結(jié)點(diǎn)上的流量有要求的最大流算法

3.1 某發(fā)出點(diǎn)發(fā)出的某一品種的流量有最低限制的算法

（1）算法思想[9]

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

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

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

（2）算法過程

發(fā)出點(diǎn)xi發(fā)出品種k的流量不能低于限制值Z，步驟如下：

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

（1）按照標(biāo)記法先找從發(fā)出點(diǎn)xi到匯y品種k的不飽和鏈Q(jìng)1，尋找增流鏈的時(shí)候必須滿足規(guī)則1、2和3。

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

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

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

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

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

3.2 某接收點(diǎn)接收某一品種的流量有最低限制的算法

（1）算法思想

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

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

3.3 某發(fā)出點(diǎn)發(fā)出某一品種的流量有最高限制的算法

（1）算法思想

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

（2）算法步驟

調(diào)用MV-Ford-Fulkerson(G)。

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

第二步：尋找源x到匯y的增流鏈Q(jìng)。

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

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

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

3.4 某接收點(diǎn)接收某一品種的流量有最高限制的算法

（1）算法思想

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

（2）算法步驟

算法過程與3.3相似。

4 示 例

已知某交通網(wǎng)絡(luò)有3個(gè)品種Ⅰ、Ⅱ和Ⅲ的貨物需要輸送，各結(jié)點(diǎn)關(guān)系如圖1所示，圖中數(shù)值表示邊的容量。表 1表示各結(jié)點(diǎn)所能接收的品種。要求結(jié)點(diǎn)x1發(fā)出品種Ⅱ的數(shù)量至少為4，y2接收品種Ⅰ的數(shù)量至少為 5，x3發(fā)出品種Ⅱ的數(shù)量最多為 3，y3接收品種Ⅱ的數(shù)量最多為4，請分配最大流。

圖1 運(yùn)輸網(wǎng)絡(luò)結(jié)構(gòu)Fig.1 Configuration of traffic network

表1 各結(jié)點(diǎn)所能接收的品種類型Tab.1 Types of the varieties each node can receive

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

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

圖2 初始化的運(yùn)輸網(wǎng)絡(luò)結(jié)構(gòu)Fig.2 Initialization of the transportation network configuration

針對約束條件，結(jié)點(diǎn) x1發(fā)出品種Ⅱ的數(shù)量至少為4，即要求（x,x1）上的品種Ⅱ的流量至少為4。尋找 x1到 y，品種Ⅱ不飽和鏈 Q1：x1→v1→v2→y3→y，調(diào)整量：

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

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

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

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

第三步：尋找增流鏈。Q3：x→x1→y1→y，對品種Ⅰ進(jìn)行流量調(diào)整，lⅠ(Q3)=4，結(jié)果如圖5所示。同理，尋找增流鏈 Q4：x→x2→v2→y3→y，對品種Ⅲ進(jìn)行流量調(diào)整，lⅢ(Q4)=4，結(jié)果如圖6所示。尋找增流鏈 Q5：x→x3→v2→v1→y2→y，對品種Ⅱ進(jìn)行流量調(diào)整，lⅡ(Q5)=3，結(jié)果如圖 7所示。尋找增流鏈 Q6：x→x3→v2→y3→y，對品種Ⅲ進(jìn)行流量調(diào)整，lⅢ(Q6)=4，結(jié)果如圖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 結(jié)束語

本文研究的算法，是在Ford-Fulkerson算法基礎(chǔ)上，解決多品種流中結(jié)點(diǎn)上對特定品種的流量有要求的交通網(wǎng)絡(luò)最大流問題，本文的算法對多品種網(wǎng)絡(luò)上任意一條邊的某品種的流量有限制的情況同樣適用。對于特別復(fù)雜的情況，本文的標(biāo)號方法和各品種流量表示不是很明晰，應(yīng)加以改進(jìn)。本文研究對象針對的是發(fā)出點(diǎn)與接收點(diǎn)，而針對其他中間結(jié)點(diǎn)某品種流量的限制還沒有研究，應(yīng)繼續(xù)研究相應(yīng)的算法。

[1] 寇瑋華.運(yùn)籌學(xué)[M].成都：西南交通大學(xué)出版社，2013.

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

[3] 寇瑋華,李宗平. 運(yùn)輸網(wǎng)絡(luò)中有流量需求的轉(zhuǎn)運(yùn)結(jié)點(diǎn)最大流分配算法[J]. 西南交通大學(xué)學(xué)報(bào)，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] 焦永蘭.管理運(yùn)籌學(xué)[M].北京∶中國鐵道出版社,2005.

[6] 甘愛英等. 運(yùn)籌學(xué)[M].北京∶清華大學(xué)出版社,2002.

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

[8] 寇瑋華,董雪,呂林劍.交通運(yùn)輸網(wǎng)絡(luò)中兩個(gè)結(jié)點(diǎn)間有流量約束的最小費(fèi)用最大流算法[J].蘭州交通大學(xué)學(xué)報(bào), 2009,28(6)∶104-109

[9] 寇瑋華,朱雪麗,張聰聰. 交通網(wǎng)絡(luò)兩個(gè)相鄰結(jié)點(diǎn)之間有流量約束的最大流分配算法[J].交通運(yùn)輸工程與信息學(xué)報(bào), 2010,8(1)∶7-13.