崔皓瑩 寇瑋華 丁 振

0 引 言

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

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

1 多品種流交通網(wǎng)絡(luò)的引例

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

圖1 交通網(wǎng)絡(luò)的引例Fig.1 An example of transportation network

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

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

2 多品種交通網(wǎng)絡(luò)的最大流分配研究

2.1 多品種交通網(wǎng)絡(luò)最大流問題分析

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

針對多品種交通網(wǎng)絡(luò)圖，邊(vi,vj)要遵從兩個(gè)約束條件：

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

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

2.2 最大流算法思路

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

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

2.3 最大流算法步驟

算法步驟如下：

第一步 將 G轉(zhuǎn)換為單源單匯的結(jié)構(gòu)形式，構(gòu)建新的網(wǎng)絡(luò)圖Gn：

（1）單源的構(gòu)建

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

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

（2）單匯的構(gòu)建

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

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

第二步 設(shè)集合 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 }，并給定網(wǎng)絡(luò)圖Gn一個(gè)初始流(一般為零流)，即初始的均為，設(shè)源x的增流量l(x)= +∞，可以對源x標(biāo)號為(0,+,+∞)。

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

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

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

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

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

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

① 當(dāng) vj∈yi時(shí)，設(shè) vm為 yi的前一個(gè)頂點(diǎn)，判斷邊(vm，yi)是否為增流鏈中的邊，方法同上。

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

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

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

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

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

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

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

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

2.4 示例求解

為了更好地解釋說明多品種交通網(wǎng)絡(luò)的最大流分配問題，下面對引例進(jìn)行求解。

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

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

第三步 反復(fù)迭代尋找增流鏈，對其對應(yīng)品種進(jìn)行流量調(diào)整，其余步驟省略，最終的結(jié)果如圖4所示。

圖2 交通網(wǎng)絡(luò)的初始流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è)品種的具體方案。交通網(wǎng)G的最大流 max z=8+3+3+9+3+4＝30，同時(shí)可知 x1發(fā)出Ⅰ品種7 t、Ⅲ品種4 t；x2發(fā)出Ⅱ品種5 t、Ⅲ品種7 t，x3發(fā)出Ⅰ品種5 t、Ⅱ品種2 t。

3 結(jié)束語

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

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

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

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

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

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

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

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

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

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

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