寇瑋華，崔皓瑩

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

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

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

1 運送費用無差異的多品種流交通網(wǎng)絡(luò)分析

1.1 運送費用無差異的多品種流的交通網(wǎng)絡(luò)引例

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

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

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

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

1.2 運送費用無差異的多品種流交通網(wǎng)絡(luò)問題分析

先給定單一品種流的交通網(wǎng)絡(luò)G=(V，E，C，F(xiàn)，W，X，Y)，其中頂點集合 V=(v1，v2，…，vn)，邊E=(e1，e2，…，em)．對集合V取定兩個非空子集X和Y，X為只發(fā)出流量的頂點集合，Y為只接收流量的頂點集合，且X∩Y=?，把X中的頂點x稱為網(wǎng)絡(luò)G的源，Y中的頂點y稱為網(wǎng)絡(luò)G的匯．針對邊(vi，vj)賦予 3 個非負的整數(shù)參數(shù)cij、fij、wij，分別為容量、流量、費用．設(shè)頂點vi?X、Y，即vi為轉(zhuǎn)運點，用f+(vi)表示頂點vi發(fā)出的流量之和，f-(vi)表示頂點vi接收的流量之和．設(shè)分配目標流的流值為A，fA為流值為A的網(wǎng)絡(luò)流，即Valf=A．

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

設(shè)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)也要遵從容量約束條件，即所有品種的流量之和要小于該邊的容量，則有所有轉(zhuǎn)運頂點vi也都要遵從流量守恒條件，而這里所謂的流量守恒是，既要保證所有品種的流量總和守恒，也要保證每一個單一品種的分量之和守恒，則有

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

2 運送費用無差異的多品種流交通網(wǎng)絡(luò)最小費用流算法設(shè)計

單一品種流最小費用流Ford-Fulkerson算法，是通過構(gòu)造增流網(wǎng)絡(luò)，在增流網(wǎng)絡(luò)中尋找關(guān)于費用代數(shù)和最低的路徑，再針對此路徑所對應(yīng)原網(wǎng)絡(luò)中的增流鏈進行流量調(diào)整.

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

2.1 算法思想

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

2.1.1 復(fù)合參數(shù)及復(fù)合指標的設(shè)定

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

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

2.1.2 復(fù)合指標中相關(guān)指標的計算規(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的調(diào)整量λ;基于前面的容量約束條件，給出了當前鏈路中針對第r個品種分流量fijr的最大可能調(diào)整量λr．

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

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

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

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

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

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

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

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

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

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

2.2 算法步驟

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

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

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

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

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

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

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

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

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

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

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

第11步 轉(zhuǎn)到第3步，反復(fù)進行，直到找不到關(guān)于運送費用最低的增流鏈為止.

3 示例求解

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

第1步 設(shè)集合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均賦予復(fù)合指標(0，0，+)|［+∞(+∞，+∞，+∞)］;對其余各個頂點均可以賦予復(fù)合指標(+∞，0，+)|［+∞(+∞，+∞，+∞)］．圖2為求解時流量調(diào)整以后某一過程的狀態(tài)圖．

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

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

表1 復(fù)合指標結(jié)果

針對表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ù)求復(fù)合指標，頂點v1與頂點v2、v3、y1、y2有直接連線，只需計算這4個頂點的復(fù)合指標即可，其余頂點復(fù)合參數(shù)保持不變，詳細計算過程如下:1)(v1，v2)為后向邊，同時f12=3＞0，此邊可以成為增流鏈中的邊，則l(v2)=min{l(v2)，l(v1)-W12}=min{+∞，10}=10，l(v2)值來自第2項，總流量的調(diào)整量λ=min{λ，f12}=min{9，3}=3，v2∈V，各個品種的最大調(diào)整量分別為λ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項，總流量的調(diào)整量 λ=min{λ，c13-f13}=min{9，6-2}=4，此時v3∈V，各個品種的最大調(diào)整量分別為λ1=λ2=λ3=4．3)(v1，y1)為前向邊，此時f11=8=c11=8，此時總流量不能增加，即邊不可以成為增流鏈中的邊，那么最短路也就不能經(jīng)過該邊，此時頂點y1的復(fù)合指標保持不變．4)(v1，y2)為前向邊，同時f12=0＜c12=5，此邊可以成為增流鏈中的邊，則l(y2)=min{l(y2)，l(v1)+W12}=min{+∞，28}=28，l(y2)值來自第2項，總流量的調(diào)整量λ=min{λ，c12-f12}=min{9，5-0}=5．匯y2不需要第I品種，則第I品種的最大可能調(diào)整量λ1=0;針對第II品種有λ2=min{λ，t22-f-(y22)}=min{5，4-0}=4;對第Ⅲ品種有λ3=min{λ，t23-f-(y23)}=min{5，9-6}=3．修改后的復(fù)合指標如表2所示．

表2 復(fù)合指標結(jié)果

針對表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ù)求復(fù)合指標，頂點v2與頂點v3、y3有直接連線．但由于在前向邊(v2，v3)上，f23=8=c23=8，此時流量不能增加，即邊(v2，v3)不能成為增流鏈中的邊，那么最短路也就不能經(jīng)過該邊，此時頂點v3的復(fù)合指標保持不變;同理，在前向邊(v2，y3)上由于f23=5=c23=5，流量不能增加，此時頂點y3的復(fù)合指標保持不變．此種情況說明，無法通過頂點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ù)求復(fù)合指標，頂點v3與頂點y1、y2、y3有直接連線，只需要計算這3個頂點的復(fù)合指標即可，其余頂點復(fù)合參數(shù)保持不變，詳細計算過程如下:1)(v3，y1)為前向邊，此時f31=0＜c31=4，此邊可以成為增流鏈中的邊，則l(y1)=min{l(y1)，l(v3)+W31}=min{23，26}=23，l(y1)值來自第1項，頂點y1的復(fù)合指標保持不變．2)(v3，y2)為前向邊，此時f32=c32=6，此時流量不能增加，即邊(v3，y2)不能成為增流鏈中的邊，那么最短路也就不能經(jīng)過該邊，頂點y2的復(fù)合指標保持不變．3)(v3，y3)為前向邊，此時f33=4＜c33=6，此邊可以成為增流鏈中的邊．則l(y3)=min{l(y3)，l(v3)+W33}=min{+∞，30}=30，l(y3)值來自第2項，總流量的調(diào)整量λ=min{λ，c33-f33}=min{4，6-4}=2，此時針對第I品種有=8-(5+2)=1，則第I品種的最大可能調(diào)整量 λ1=minf-(y31)}=min{2，1}=1;針對第Ⅱ品種有-f-(y32)=0，則第Ⅱ品種的最大可能調(diào)整量λ2=0;針對第Ⅲ品種有=13-(0+2+7)=4，則第Ⅲ品種的最大可能調(diào)整量λ3=min{λ，t33-f-(y33)}=min{2，4}=2．修改后的復(fù)合指標如表3所示．

表3 復(fù)合指標結(jié)果

針對表3取l(vj)*=min{l(vj);vj?S}=min{23，28，30}=23=l(y1)*．由此可知關(guān)于費用的最短路的增流鏈應(yīng)為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，說明已經(jīng)找到關(guān)于運送費用最低的增流鏈．

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

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

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

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

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

4 結(jié)論

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

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

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

［1］寇瑋華.運籌學(xué)［M］.成都:西南交通大學(xué)出版社，2013.

［2］甘愛英.運籌學(xué)［M］.北京:清華大學(xué)出版社，2002.

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

［4］寇瑋華，董雪，呂林劍.交通運輸網(wǎng)絡(luò)中兩個結(jié)點間有流量約束的最小費用最大流算法［J］.蘭州交通大學(xué)學(xué)報，2009，28(6):104-109.

［5］謝政，湯澤瀅.帶模糊約束的最小費用流問題［J］.模糊系統(tǒng)與數(shù)學(xué)，1999，13(2):90-941.

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

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

［8］任剛，王煒.可直接計算轉(zhuǎn)向流量的改進型Dial交通分配算法［J］.中國公路學(xué)報，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］寇瑋華，崔皓瑩.有運送路徑限制的多品種流交通網(wǎng)絡(luò)最小費用流算法研究［J］.蘭州理工大學(xué)學(xué)報，2013，32(6):1-7.