寇瑋華，崔皓瑩

(西南交通大學交通運輸與物流學院，610031成都)

最小費用流問題是網絡與流的核心問題之一，最基本的算法是Ford-Fulkerson算法，其他的算法還有網絡單純形算法(graph simplex algorithm)、松弛算法(relaxation algorithm)、消圈算法(cycle-canceling algorithm)、瑕疵算法(out-ofkilter algorithm)等等［1-8］，這些算法都可以解決單一品種流的最小費用流分配問題.在實際的交通網絡應用中，普遍出現了多品種流問題，所以有了流變換、流分解、組合應用、多品種流及預流推進等新的理論和方法［9-13］，但這些算法都沒有徹底解決多品種流的最小費用流分配問題.針對交通運輸領域出現的多品種流交通網絡，有必要對其最小費用流分配問題作進一步研究，并在其他算法的基礎上，構造可行的最小費用流分配算法.

本文主要對運送費用無差異的多品種流交通網絡相關問題進行分析，再基于連續(xù)最短路算法(successive shortestpath algorithm)和 Ford-Fulkerson算法的思路，構造相應的多品種流交通網絡的最小費用流算法.

1 運送費用無差異的多品種流交通網絡分析

1.1 運送費用無差異的多品種流的交通網絡引例

為了解運送費用無差異的多品種流交通網絡最小費用流問題，也為清晰地闡述相關算法的研究，先給出運送費用無差異的多品種流交通網絡的一個引例.

引例 有一交通網絡如圖1所示，圖中的邊分別給出了運送能力和運送量，即邊的容量、流量(零流)、費用.其中x1有Ⅰ、Ⅱ兩種產品，質量分別為18、8 t;x2有Ⅱ、Ⅲ兩種產品，質量分別為6、19 t．y1、y2、y3為3 個需求地，y1需要Ⅰ、Ⅱ 兩種產品，需求量分別為6、7 t;y2需要Ⅱ、Ⅲ兩種產品，需求量分別為4、9 t;y3需要Ⅰ、Ⅲ兩種產品，需求量分別為8、13 t．現在需要設計的方案是在滿足總運送費用最少的前提下，將盡可能多的產品運送到需求地．

圖1 多品種流交通網絡圖

針對此引例，再利用傳統(tǒng)的最小費用流算法，就不能設計出可行的最小費用流分配方案，所以有必要研究此類多品種流交通網絡的最小費用流問題.

1.2 運送費用無差異的多品種流交通網絡問題分析

先給定單一品種流的交通網絡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中的頂點x稱為網絡G的源，Y中的頂點y稱為網絡G的匯．針對邊(vi，vj)賦予 3 個非負的整數參數cij、fij、wij，分別為容量、流量、費用．設頂點vi?X、Y，即vi為轉運點，用f+(vi)表示頂點vi發(fā)出的流量之和，f-(vi)表示頂點vi接收的流量之和．設分配目標流的流值為A，fA為流值為A的網絡流，即Valf=A．

以上給出的交通網絡描述，是針對運送費用無差異的單一品種流，在實際的交通網絡中，在同一個階段不同品種流運送費用相同的多品種流現象普遍存在，下面對運送費用無差異的多品種流交通網絡特點進行分析.

設r為q個多品種中的第r個品種，其中r=1，2，…，q．fijr為第r個品種在邊(vi，vj)上的流量，f+(vir)表示頂點vi發(fā)出第r個品種的流量之和，f-(vir)表示頂點vir接收第r個品種的流量之和．wij為所有品種在邊(vi，vj)上的運送費用．邊(vi，vj)也要遵從容量約束條件，即所有品種的流量之和要小于該邊的容量，則有所有轉運頂點vi也都要遵從流量守恒條件，而這里所謂的流量守恒是，既要保證所有品種的流量總和守恒，也要保證每一個單一品種的分量之和守恒，則有

基于以上分析，運送費用無差異的多品種流交通網絡最小費用流分配的線性規(guī)劃模型如模型(1)所示.針對模型(1)所刻畫的多品種流交通網絡，需要設計特定的最小費用流分配算法.

2 運送費用無差異的多品種流交通網絡最小費用流算法設計

單一品種流最小費用流Ford-Fulkerson算法，是通過構造增流網絡，在增流網絡中尋找關于費用代數和最低的路徑，再針對此路徑所對應原網絡中的增流鏈進行流量調整.

針對運送費用無差異的多品種流交通網絡，再構造增流網絡，勢必會造成增流網絡的結構變得龐大而且復雜，同時計算過程更為繁瑣，所以直接利用Ford-Fulkerson算法可行但不是優(yōu)化的方法.

2.1 算法思想

本文在借鑒連續(xù)最短路算法和Ford-Fulkerson算法的基礎上，將網絡圖中邊的屬性設計為復合參數的形式，再針對流量分配構建復合指標，從而建立運送費用無差異的多品種流交通網絡最小費用流算法.

2.1.1 復合參數及復合指標的設定

復合參數．費用沒有差異的單一品種流交通網絡中，邊(vi，vj)的屬性參數為(cij，fij，wij)．針對運送費用無差異的多品種流，本文把邊(vi，vj)的屬性設計為復合參數形式，即為［cij，fij(fij1，…，fijr，…，fijq)，wij］，其中fij(fij1，…，fijr，…，fijq)表示邊(vi，vj)的總流量fij中，每個品種的分流量的多少．

復合指標．在連續(xù)最短路算法中，頂點vj的指標為(l(vj)，vi)，其中l(wèi)(vj)表示從起點經過頂點vi到頂點vj關于費用的最短路長度，vi表示vj的前一個頂點．在Ford-Fulkerson算法中，針對流量調整，頂點vj的指標為(u，邊的方向，δ)，其中u表示被標識點vj的前一個頂點;邊的方向通過“+”或“-”來標識是前向邊還是后向邊;δ表示流量的調整量．針對多品種流交通網絡，既要考慮最短路指標和流量調整指標，還要考慮多品種問題，所以本文構建了復合指標，其形式為(l(vj)，vi，邊的方向)|［λ(λ1，…，λr…，λp)］．其中l(wèi)(vj)表示第r個品種從起點經過前一個頂點vi到頂點vj，關于運送費用最低的最短路長度;vi表示頂點vj的前一個頂點;邊的方向表明邊(vi，vj)是前向邊還是后向邊，即(vi，vj)的流量是增加還是減少;λ表示在關于運送費用最低的當前鏈路中，針對總流量fij的調整量;λr表示在當前鏈路中，針對第r個品種分流量fijr的最大可能調整量．

2.1.2 復合指標中相關指標的計算規(guī)則

規(guī)則1 若邊(vi，vj)為前向邊且fij＜cij時，l(vj)=min{l(vj)，l(vi)+Wij}，λ=min{λ，cijfij}．因為此時總流量只能增加，而每個品種的分流量都有增加的可能性，所以λr=λ，其中r=1，2，…，q．

規(guī)則2 若邊(vi，vj)為后向邊且fij＞0，l(vj)=min{l(vj)，l(vi)-Wij}，λ=min{λ，fij}．因為此時總流量只能減小，每個品種的分流量都有減小的可能性，但每個品種的分流量不能減小為小于0，所以λr=min{λ，fijr}，其中r=1，2，…，q．

規(guī)則1、2基于連續(xù)最短路算法給出了當前最短路的長度l(vj);基于Ford-Fulkerson算法給出了當前鏈路中針對總流量fij的調整量λ;基于前面的容量約束條件，給出了當前鏈路中針對第r個品種分流量fijr的最大可能調整量λr．

2.1.3 增流鏈的流量調整量確定規(guī)則

盡管規(guī)則1、規(guī)則2計算了當前鏈路的相關指標，但針對第r個品種的分流量fijr，只給出了最大可能的調整量，那么針對從源到匯的增流鏈，總流量fij的調整量以及各個品種分量fijr的調整量還沒有最終確定．

設針對增流鏈總流量fij的調整量為δ，基于Ford-Fulkerson算法可知δ=min{λ，A-Valf}．

設針對增流鏈品種分量fijr的調整量為δr，下面給出確定δr的規(guī)則3和規(guī)則4．

規(guī)則3 若至少存在一個品種的最大可能調整量與總流量調整量相等，即有 max{λ1，…，λr…，λp}=δ，則任取其中一個最大的關于品種k的λk，令δk=λk=δ，此時增流鏈的總流量以及分流量的調整量即為 δ(0，…，δk，…，0)．

規(guī)則4 若不存在任意一個品種的最大可能調整量與總流量調整量相等，即 max{λ1，…，λr…，λp}＜δ，則任取其中一個最大的λk，令δk=λk．此時針對分流量的調整幅度還剩余δ=δδk，再任取其余一個最大的 λm，即 λm=max{λ1，…，λr…，λp;其中不包含 λk}，那么 δm=min{δ，λm}．此時針對分流量還剩余δ=δ-δm，依次如上類推，直到δ=0為止．沒有被確認的分流量的調整量λi=0．此時增流鏈的總流量以及分流量的調整量即為 δ(0，…，δk，…，δm，…，0)．

規(guī)則3、規(guī)則4是在所有品種流量之和要小于該邊容量的基礎上，對分流量調整幅度最大的品種來優(yōu)先增加流量，目的是在運送費用最低的增流鏈上，盡可能多的增加分流量.

2.1.4 增流鏈的流量調整規(guī)則

基于Ford-Fulkerson算法，將關于運送費用最低的增流鏈的流量進行調整，即增流鏈中的邊(vi，vj)的復合參數按照如下規(guī)則修改．

規(guī)則5 若(vi，vj)為前向邊，其復合參數修改為［cij，fij+δ(fij1+δ1，…，fijr+δr，…，fijq+δq)，wij］;若(vi，vj)為后向邊，其復合參數修改為［cij，fij-δ(fij1-δ1，…，fijr-δr，…，fijq-δq)，wij］．

2.2 算法步驟

基于給出的復合參數、復合指標以及相應的規(guī)則，本文算法的思路是，隨著所求最短路的延伸，同時消除非增流邊，這樣既杜絕了二次求解問題，也避免了全枚舉的問題，算法步驟如下.第1～3步為初始化過程，第4～8步為尋找費用最低的增流鏈過程，第9～11步為流量調整過程.

第1 步 設源 X={x1，…，xi，…，xn}，轉運點 V={v1，…，vi，…，vn}，匯 yi={y1，…，yi，…，yn}．設源xi具有第r品種的數量為sir，匯yi需要第r品種的數量為．設λ=λr=+∞，設集合S=?，集合 T={x1，…，xi，…，xn，v1，…，vi，…，vn，y1，…，yi，…，yn}．

第2步 對運送費用無差異的多品種流交通網絡，在零流(平凡流)基礎上，利用給出的容量、費用，把邊的屬性設為復合參數形式，即［cij，fij(fij1，…，fijr，…，fijq)，wij］， 此 時 初 始 的 流 量fij(fij1，…，fijr，…，fijq)均為 0(0，…，0，…，0)，即有Valf=0．

第3步 設l(xi)=0，對起點xi賦予復合指標(0，0，+)|［+∞(+∞，…，+∞…，+∞)］;設其余頂點的l(vi)=+∞、l(yi)=+∞，那么其余頂點均可以賦予復合指標(+∞，0，+)|［+∞(+∞，…，+∞，…，+∞)］．

第4步 選擇起點xi檢查，將起點xi復合指標標上*，表示頂點vi已被檢查．同時設集合S={xi}，xi? T．

第5步 若xi與其他頂點沒有直接連線，其他頂點的復合指標保持不變;若有直接連線，則計算其他頂點的復合指標值，計算方法如下:1)(xi，vj)為前向邊．若fij=cij，此時流量不能增加，即邊(xi，vj)不能成為增流鏈中的邊，那么最短路也就不能經過該邊，此時頂點vj的復合指標保持不變．若fij＜cij，此時流量可以增加，即邊(xi，vj)可以成為增流鏈中的邊，那么最短路也就可以經過該邊．復合指標中的各個指標計算如下:按照規(guī)則1可知l(vj)=min{l(vj)，l(xi)+Wij}，如果l(vj)值來自第1項l(vj)，頂點vj的復合指標保持不變．如果l(vj)值來自第2項l(xi)+Wij，總流量調整量λ=min{λ，cij-fij，A-Valf}．當vj∈V時，所有品種的最大可能調整量λr=λ．當vj∈Y時，若-f+(xik)=0或-f-(yjk)=0，則k品種的最大可能調整量λk=0，其余品種的最大可能調整量λr=min{λ，tjk-f-(yjk)};否則，所有品種的最大可能調整量λr=min{λ，tjk-f-(yjk)}．此時需要將頂點vj復合指標修改為(l(vj)，xi，邊的方向)|［λ(λ1，…，λr…，λp)］．2)(xi，vj)為后向邊．若fij=0，此時流量不能減少，即邊(xi，vj)不能成為增流鏈中的邊，那么最短路也就不能經過該邊，此時頂點vj的復合指標保持不變．若fij＞0，此時流量可以減少，即邊(xi，vj)可以成為增流鏈中的邊，那么最短路也就可以經過該邊．復合指標中的各個指標計算如下:按照規(guī)則2可知l(vj)=min{l(vj)，l(xi)-Wij}，如果l(vj)值來自第1項l(vj)，頂點vj復合指標保持不變．如果l(vj)值來自第2項l(xi)-Wij，總流量的調整量 λ=min{λ，fij，A-Valf}．當vj∈ V 時，所有品種的最大可能調整量λr=min{λ，fijr}．當vj∈Y時，若-f+(xik)=0或-f-(yjk)=0，則k品種的最大可能調整量λk=0，其余品種的最大可能調整量λr=min{λ，fijr，tjk-f-(yjk)};否則，所有品種的 最 大 可 能 調 整 量 λr=min{λ，fijr，tjk-f-(yjk)}．此時需要將頂點vj復合指標修改為(l(vj)，xi，邊的方向)|［λ(λ1，…，λr…，λp)］．

第6步 針對頂點vj，計算l(vj)*=min{l(vj);其中j=1，2，…，n;vj? S}．將頂點vj的復合指標標上*，表示頂點vj已被檢查，設集合S={xi，…，vj}，vj?T．當vj∈Y時，轉第9 步，否則轉第7步．

第7步 從頂點vj出發(fā)，求其他頂點vk的復合指標．若頂點vj與頂點vk沒有直接連線，頂點vk的復合指標保持不變;若有直接連線，則計算頂點vk的復合指標值，計算方法如下:1)(vj，vk)為前向邊．若fjk=cjk，此時流量不能增加，即邊(vj，vk)不能成為增流鏈中的邊，那么最短路也就不能經過該邊，此時頂點vk的復合指標保持不變．若fjk＜cjk，此時流量可以增加，即邊(vj，vk)可以成為增流鏈中的邊，那么最短路也就可以經過該邊．復合指標中的各個指標計算如下:按照規(guī)則1可知l(vk)=min{l(vk)，l(vj)+Wjk}，如果l(vk)值來自第1項l(vk)，頂點vk的復合指標保持不變．如果l(vk)值來自第2項l(vj)+Wjk，總流量的調整量λ=min{λ，cjk-fjk，A-Valf}．當vk∈ V 時，所有品種的最大可能調整量λr=λ．當vk∈Y時，若-f-(yjk)=0，則k品種的最大可能調整量λk=0，其余品種的最大可能調整量-f-(yjk)};否則，所有品種的最大可能調整量λr=min{λ，tjk-f-(yjk)}．此時需要將頂點vk復合指標修改為(l(vk)，vj，邊的方向)|［λ(λ1，…，λr，…，λp)］．2)(vj，vk)為后向邊．若fjk=0，此時流量不能減少，即邊(vj，vk)不能成為增流鏈中的邊，那么最短路也就不能經過該邊，此時頂點vk的復合指標保持不變．若fjk＞0，此時流量可以減少，即邊(vj，vk)可以成為增流鏈中的邊，那么最短路也就可以經過該邊．復合指標中的各個指標計算如下:按照規(guī)則2可知l(vk)=min{l(vk)，l(vj)-Wjk}，如果l(vk)值來自第1項l(vk)，頂點vk復合指標保持不變．如果l(vk)值來自第2項l(vj)-Wjk，總流量的調整量 λ=min{λ，fjk，AValf}．當vk∈V時，所有品種的最大可能調整量λr=min{λ，fjkr}．當vk∈Y時，若tjk-f-(yjk)=0，則k品種的最大可能調整量λk=0，其余品種的最 大 可 能 調 整 量 λr=min{λ，fjkr，tjk-f-(yjk)};否則，所有品種的最大可能調整量λr=min{λ，fjkr，tjk-f-(yjk)}．此時需要將頂點vk復合指標修改為(l(vk)，vj，邊的方向)|［λ(λ1，…，λr…，λp)］．

第8步 針對頂點vk，計算l(vk)*=min{l(vk);其中j=1，2，…，n;vk? S}．將頂點vk復合指標標上*，表示頂點vk已被檢查，設集合S={xi，…，vk}，vk? T．當vk∈ Y 時，轉第9 步．

第9步 當yi?S時，自匯yi逆向追蹤，沿著每個頂點復合指標中第1個子指標組的vi即可得出運送費用最低的增流鏈，路長為l(yi)，總流量的調整量δ=λ．再按照規(guī)則3、4，即可確定出增流鏈中每個品種的分流量的調整量δr．

第10步 按照規(guī)則5，對增流量的總流量及分流量進行調整.

第11步 轉到第3步，反復進行，直到找不到關于運送費用最低的增流鏈為止.

3 示例求解

為了說明本文算法，下面對引例進行最小費用最大流分配，最小費用最大流的目標流是最大流，此時將算法中總流量調整量λ公式中的AValf去掉即可.由于圖顯示空間的局限，不對頂點進行復合指標的標號;另外，因篇幅限制，將相應的計算過程省略.

第1步 設集合S=?，集合T={x1，x2，v1，v2，v3，y1，y2，y3}．此時初始的流量fij(fij1，fij2，fij3)均為 0(0，0，0)．此問題涉及 I、II、III 3 個品種，這里用1、2、3序號來標識．對起點xi均賦予復合指標(0，0，+)|［+∞(+∞，+∞，+∞)］;對其余各個頂點均可以賦予復合指標(+∞，0，+)|［+∞(+∞，+∞，+∞)］．圖2為求解時流量調整以后某一過程的狀態(tài)圖．

圖2 某一過程流量調整后的狀態(tài)圖

第2步 對圖2繼續(xù)尋找關于運送費用最低的增流鏈．表1為分別從源x1、x2出發(fā)的復合指標計算結果表(此計算過程省略)．

表1 復合指標結果

針對表1取l(vj)*=min{l(vj);vj?S}=min{15，23}=15=l(v1)* ，將表1中頂點v1的指標標記* ，此時 S={x1，x2，v1}，集合T={v2，v3，y1，y2，y3}．從頂點v1出發(fā)，繼續(xù)求復合指標，頂點v1與頂點v2、v3、y1、y2有直接連線，只需計算這4個頂點的復合指標即可，其余頂點復合參數保持不變，詳細計算過程如下:1)(v1，v2)為后向邊，同時f12=3＞0，此邊可以成為增流鏈中的邊，則l(v2)=min{l(v2)，l(v1)-W12}=min{+∞，10}=10，l(v2)值來自第2項，總流量的調整量λ=min{λ，f12}=min{9，3}=3，v2∈V，各個品種的最大調整量分別為λ1=3，λ2=λ3=0．2)(v1，v3)為前向邊，同時f13=2＜c13=6，此邊可以成為增流鏈中的邊，則l(v3)=min{l(v3)，l(v1)+W13}=min{+∞，23}=23，l(v2)值來自第2項，總流量的調整量 λ=min{λ，c13-f13}=min{9，6-2}=4，此時v3∈V，各個品種的最大調整量分別為λ1=λ2=λ3=4．3)(v1，y1)為前向邊，此時f11=8=c11=8，此時總流量不能增加，即邊不可以成為增流鏈中的邊，那么最短路也就不能經過該邊，此時頂點y1的復合指標保持不變．4)(v1，y2)為前向邊，同時f12=0＜c12=5，此邊可以成為增流鏈中的邊，則l(y2)=min{l(y2)，l(v1)+W12}=min{+∞，28}=28，l(y2)值來自第2項，總流量的調整量λ=min{λ，c12-f12}=min{9，5-0}=5．匯y2不需要第I品種，則第I品種的最大可能調整量λ1=0;針對第II品種有λ2=min{λ，t22-f-(y22)}=min{5，4-0}=4;對第Ⅲ品種有λ3=min{λ，t23-f-(y23)}=min{5，9-6}=3．修改后的復合指標如表2所示．

表2 復合指標結果

針對表2取l(vj)*=min{l(vj);vj?S}=min{10，23，23，28}=10=l(v2)* ，將表 2 中頂點v2的指標標記 *．此時 S={x1，x2，v1，v2}，集合 T={v3，y1，y2，y3}．從頂點v2出發(fā)，繼續(xù)求復合指標，頂點v2與頂點v3、y3有直接連線．但由于在前向邊(v2，v3)上，f23=8=c23=8，此時流量不能增加，即邊(v2，v3)不能成為增流鏈中的邊，那么最短路也就不能經過該邊，此時頂點v3的復合指標保持不變;同理，在前向邊(v2，y3)上由于f23=5=c23=5，流量不能增加，此時頂點y3的復合指標保持不變．此種情況說明，無法通過頂點v2找到一條到達匯的增流鏈，此時需要返回到前一個頂點v1，通過與頂點v1有直接連線的其他頂點來尋找最短路．針對表2取l(vj)*=min{l(vj);vj? S}=min{23，23，28}=23=l(y1)=l(v3)*，這里選擇頂點v3作為標記點，即將表2中頂點v3的指標標記 *．此時 S={x1，x2，v1，v2，v3}，集合 T={y1，y2，y3}．

從頂點v3出發(fā)，繼續(xù)求復合指標，頂點v3與頂點y1、y2、y3有直接連線，只需要計算這3個頂點的復合指標即可，其余頂點復合參數保持不變，詳細計算過程如下:1)(v3，y1)為前向邊，此時f31=0＜c31=4，此邊可以成為增流鏈中的邊，則l(y1)=min{l(y1)，l(v3)+W31}=min{23，26}=23，l(y1)值來自第1項，頂點y1的復合指標保持不變．2)(v3，y2)為前向邊，此時f32=c32=6，此時流量不能增加，即邊(v3，y2)不能成為增流鏈中的邊，那么最短路也就不能經過該邊，頂點y2的復合指標保持不變．3)(v3，y3)為前向邊，此時f33=4＜c33=6，此邊可以成為增流鏈中的邊．則l(y3)=min{l(y3)，l(v3)+W33}=min{+∞，30}=30，l(y3)值來自第2項，總流量的調整量λ=min{λ，c33-f33}=min{4，6-4}=2，此時針對第I品種有=8-(5+2)=1，則第I品種的最大可能調整量 λ1=minf-(y31)}=min{2，1}=1;針對第Ⅱ品種有-f-(y32)=0，則第Ⅱ品種的最大可能調整量λ2=0;針對第Ⅲ品種有=13-(0+2+7)=4，則第Ⅲ品種的最大可能調整量λ3=min{λ，t33-f-(y33)}=min{2，4}=2．修改后的復合指標如表3所示．

表3 復合指標結果

針對表3取l(vj)*=min{l(vj);vj?S}=min{23，28，30}=23=l(y1)*．由此可知關于費用的最短路的增流鏈應為x1→y1，但由于匯y1需要的第I、II品種已全部滿足，其流量無法增加，此時需要選擇包含匯的次最短路．針對表3取l(vj)*=min{l(vj);vj?S}=min{28，30}=28=l(y2)*．將表3中頂點y2的指標標記*，此時S={x1，x2，v1，v2，v3，y2}，集合T={y1，y3}．因為y2?S，說明已經找到關于運送費用最低的增流鏈．

自匯y2，沿著每個頂點復合指標中第1個子指標組的第2個指標逆向追蹤，可得出關于費用的最短路為x2→v1→y2，路長為28，總流量調整量 δ=5．因為 max{λ1，λ2，λ3}=max{0，4，3}≤δ=5，則任取其中一個最大的λ2=4，令δ2=λ2=4．此時針對分流量的調整幅度還剩余δ=δ-δ2=5-4=1，再任取其余一個最大的λ3，則δ3=min{δ，λ3}=min{1，3}=1，此時分流量的調整幅度已經為δ=0，則δ1=0．即增流鏈的總流量及分流量的調整量為5(0，4，1)．流量分配結果如圖3所示．

第3步 針對圖3繼續(xù)尋找關于運送費用最低的增流鏈，余下過程省略，最終的最小費用最大流分配結果如圖4所示.

針對圖4，仍能尋找到增流鏈x2→v1→v3→y1，但由于y1所需要的第I、II品種已經全部得到滿足，不需要對流量進行增加，并且從源x1、x2出發(fā)的邊中，只有邊(x1，y1)為不飽和邊，但匯y1需要的第I、II品種已經得到全部滿足，不需要對流量進行增加，因此此時為最小費用流．由圖4可以知道，該引例中各個品種的具體運送方案，把該引例的總體方案以及各個品種的具體方案匯總，發(fā)送和接收的總量均為42，則3個品種的費用WⅠ、WⅡ、WⅢ分別為299、189、365，總費用W=WⅠ+WⅡ+WⅢ=853．

圖3 流量調整后的狀態(tài)圖

圖4 多品種流的最小費用最大流量終分布狀態(tài)圖

4 結論

1)在連續(xù)最短路算法和Ford-Fulkerson算法基礎上，通過構建復合指標，建立了運送費用無差異的多品種流最小費用流分配方法，另外，通過設計復合參數，也標定了多品種流的流量分配狀態(tài).

2)構造的基于復合參數和復合指標的多品種流最小費用流算法，避免了傳統(tǒng)算法需要改變網絡圖結構的不足，在算法實現上也體現了便利.在交通運輸領域，存在運送費無差異的多品種流分配問題，但針對此類問題的研究文獻還不多見，該算法也為解決交通網絡的一系列相關實際問題提供了應用基礎.

3)在實際應用中，多品種流大部分會存在費用上的差異，相對的算法設計難度較大，在此研究的基礎上，后期需要研究運送費用有差異的多品種流交通網絡最小費用流分配問題.

［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］謝政，湯澤瀅.帶模糊約束的最小費用流問題［J］.模糊系統(tǒng)與數學，1999，13(2):90-941.

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

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

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

［9］ORLIN J B.Network optimization［EB/OL］.［2010-05-08］.http://www.core.org.cn/OcwWeb/index.htm.

［10］CHABINI I，ODONI A R.Transportation flow system［EB/OL］.［2012-03-16］.http://www.core.org.cn/OcwWeb/index.htm.

［11］SHEPHERD B，ZHANG L.A cycle augmentation algorithm for minimum cost multicommodity flows on a ring ［J］. Global Tele communications Conference，1999，2:1535-1543.

［12］RETVARI G，BIRO J J，CINKLER T.A novel lagrangian-relaxation to the minimum cost multicommodity flow problem and its application to OSPF traffic engineering ［J］. Computers and Communications，2004，2:957-962.

［13］寇瑋華，崔皓瑩.有運送路徑限制的多品種流交通網絡最小費用流算法研究［J］.蘭州理工大學學報，2013，32(6):1-7.