寇瑋華，崔皓瑩

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

最小費用流問題是網(wǎng)絡(luò)與流的核心問題之一，基本算法是Ford-Fulkerson算法，還有網(wǎng)絡(luò)單純形算 法 （Graph Simplex Algorithm）、松 弛 算 法（Relaxation Algorithm）、消圈算法（cycle-canceling algorithm）、瑕疵算法（Out-Of-Kilter Algorithm）等等［1－8］，這些算法都只能解決單一品種流的最小費用流分配，而且每個單一品種流在每一個階段即在每個邊上的費用代價是相同的.在實際交通網(wǎng)絡(luò)應(yīng)用中，普遍出現(xiàn)了多品種流問題，所以有了流變換、流分解、組合應(yīng)用、多品種流及預(yù)流推進(jìn)等新的理論和方法［9－10］，但這些算法都沒有徹底解決多品種流的最小費用流分配問題，尤其是針對不同品種流在同一個階段的運費有差異的問題還沒有很好地解決.

針對交通運輸領(lǐng)域出現(xiàn)的運費有差異的多品種流交通網(wǎng)絡(luò)有必要做深入研究.本文首先對運費有差異的多品種流交通網(wǎng)絡(luò)相關(guān)問題進(jìn)行分析，再基于連續(xù)最短路算法（Successive Shortest Path Algorithm）和Ford-Fulkerson算法的思路構(gòu)造費用有差異的多品種流交通網(wǎng)絡(luò)的最小費用流算法.

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

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

為了了解運費有差異的多品種流交通網(wǎng)絡(luò)最小費用流問題，先給出運費有差異的多品種流交通網(wǎng)絡(luò)的一個簡單引例.

有一交通網(wǎng)絡(luò)如圖1所示，x1，x2為發(fā)送地，v1，v2，v3為中轉(zhuǎn)地，y1，y2，y3為接收地，圖中的邊分別給出了運送能力和運送量，即邊的容量、流量（零流）.其中x1有產(chǎn)品Ⅰ，Ⅱ，數(shù)量分別為18t和8t；x2有產(chǎn)品Ⅱ，Ⅲ，數(shù)量分別為6t和19t.y1需要產(chǎn)品Ⅰ，Ⅱ，需求量分別為6t和7t；y2需要產(chǎn)品Ⅱ，Ⅲ，需求量分別為4t和9t；y3需要產(chǎn)品Ⅰ，Ⅲ，需求量分別為8t和13t.另外，每種品種在每條邊上的運費如表1所示，其中運費按照品種序號排序，即為（wⅠ，wⅡ，wⅢ），如果與某品種無關(guān)，運費設(shè)為＋∞.現(xiàn)在需要設(shè)計的方案是，在滿足總運費最少的前提下將盡可能多的產(chǎn)品運送到需求地.

圖1 多品種流交通網(wǎng)絡(luò)Fig.1 Multi-commodity flow traffic network

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

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

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

表1 不同品種流的運費Tab.1 The conveyance cost of different commodity flows

以上描述是針對單一品種流的，而且每一種品種在每一個階段即在每個邊上的費用是相同的.在實際的交通網(wǎng)絡(luò)中，多品種流現(xiàn)象普遍存在，而且在同一個階段的不同品種流運費可能不盡相同.下面對運費有差異的多品種流交通網(wǎng)絡(luò)特點進(jìn)行分析.

基于以上分析，運費有差異的多品種流交通網(wǎng)絡(luò)最小費用流線性規(guī)劃模型如模型（1）所示.

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

運費無差異的單一品種流最小費用流Ford-Fulkerson算法是先構(gòu)造增流網(wǎng)絡(luò)，在增流網(wǎng)絡(luò)中尋找關(guān)于費用代數(shù)和最小的路徑，再針對此路徑所對應(yīng)原網(wǎng)絡(luò)中的增流鏈進(jìn)行流量調(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ù)合指標(biāo)，從而建立運費有差異的多品種流交通網(wǎng)絡(luò)最小費用流算法.

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

（2）復(fù)合指標(biāo).連續(xù)最短路算法中，頂點vj的指標(biāo)為（l（vj），vi），其中l(wèi)（vj）表示從起點經(jīng)頂點vi到頂點vj關(guān)于費用的最短路長度，vi表示vj前一個頂點.Ford-Fulkerson算法針對流量調(diào)整，設(shè)定u表示被標(biāo)識點vj前一個頂點；D表示邊的方向，通過“＋”或“－”來標(biāo)識是前向邊還是后向邊；δ表示流量的調(diào)整量，構(gòu)建頂點vj的指標(biāo) （u，D，δ）.針對多品種流交通網(wǎng)絡(luò)，既要考慮最短路指標(biāo)和流量調(diào)整指標(biāo)，也要考慮多品種及運費有差異的問題，所以構(gòu)建復(fù)合指標(biāo)［…，（l（r）（vj），vi，D，δr），…］｜（m，δ），其中l(wèi)（r）（vj）表示第r個品種從起點經(jīng)過前一個頂點vi到頂點vj關(guān)于運費最低的最短路長度；vi表示頂點vj的前一個頂點；“邊的方向”表明邊（vi，vj）是前向邊還是后向邊，即（vi，vj）的流量是增加還是減少；δr表示關(guān)于第r個品種最短路所對應(yīng)的第r個品種的流量調(diào)整量；m表示在所有品種的最短路徑中路徑長度 最 小 所 對 應(yīng) 的 品 種，即 有l(wèi)（m）（vj）＝min｛（l（1）（vj），…，l（r）（vj）…，l（q）（vj）｝；δ表示第m品種的流量調(diào)整量，即有δ＝δm.

（3）算法思路.利用給出的復(fù)合參數(shù)和復(fù)合指標(biāo)能找出費用最低的最短路，并可以確定出其對應(yīng)的品種，再判斷此最短路是否為增流鏈，如果是增流鏈，就對相應(yīng)的品種進(jìn)行流量調(diào)整，即通過修改復(fù)合參數(shù)值來分配流量，這樣就可以避免先指定某一品種進(jìn)行最小費用流分配的錯誤.以上思路是二次求解法，即先尋找關(guān)于費用最低的最短路，再判斷此最短路是否為增流鏈.但本文算法的核心思路是，隨著所求最短路的延伸，同時消除非增流邊，這樣既杜絕了二次求解問題，也避免了全枚舉的問題.

2.2 算法步驟

步驟1：設(shè)源X＝｛x1，…，xi，…，xn｝，轉(zhuǎn)運點V＝｛v1，…，vi，…，vn｝，匯yi＝｛y1，…，yi，…，yn｝.設(shè)源xi具有第r品種的數(shù)量為s（r），i，匯yi需要第r品種的數(shù)量為t（r），i.設(shè)δr＝＋∞.被標(biāo)識的頂點寫入集合S中，初始時S＝?，設(shè)頂點集合T＝｛x1，…，xi，…，xn，v1，…，vi，…，vn，y1，…，yi，…，yn｝.

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

步驟3：設(shè)l（r）（xi）＝0，對起點xi賦予復(fù)合指標(biāo)，即［（0，0，＋，＋∞），…，（0，0，＋，＋∞），…，（0，0，＋，＋ ∞）］｜（0，＋ ∞）；設(shè) 其余頂點l（r）（vi）＝＋∞，l（r）（yi）＝＋∞，則其余頂點均可以賦予復(fù)合指標(biāo)，即［（＋∞，0，＋，＋∞），…，（＋∞，0，＋，＋∞），…，（＋∞，0，＋，＋∞）］｜（0，＋∞）.

步驟4：選擇起點xi檢查，將起點xi復(fù)合指標(biāo)標(biāo)上＊，表示頂點vi已被檢查.同時設(shè)集合S＝｛xi｝，xi?T.

步驟5：若xi與其他頂點沒有直接連線，其他頂點的復(fù)合指標(biāo)保持不變；若有直接連線，則計算其他頂點的復(fù)合指標(biāo)值，計算方法如下.

（1）（xi，vj）為前向邊.①若fij＝cij，此時流量不能增加，邊（xi，vj）不能成為增流鏈的邊，那么最短路不能經(jīng)過該邊，此時頂點vj復(fù)合指標(biāo)不變.②若fij＜cij，此時流量可以增加，邊（xi，vj）可以成為增流鏈的邊，最短路就可以經(jīng)過該邊.復(fù)合指標(biāo)的各指標(biāo)計算如下.設(shè)l（r）（vj）＝min｛l（r）（vj），l（r）（xi）＋Wijr｝，若l（r）（vj）值來自第1項l（r）（vj），那么頂點vj復(fù)合指標(biāo)第1復(fù)合項關(guān)于第r品種的子指標(biāo)組保持不變；若l（r）（vj）值來自第2 項l（r）（xi）＋Wijr，當(dāng)vj∈V時，δr＝min｛cij－fij，s（r），i－f＋（xir），δr｝；當(dāng)vj∈Y時，若s（r），i－f＋（xir）＝0或t（r），j－f－（yjr）＝0，頂點vj復(fù)合指標(biāo)中第1復(fù)合項關(guān)于第r品種的子指標(biāo) 組 保 持 不 變，否 則δr＝min｛cij－fij，s（r），if＋（xir），t（r），j－f－（yjr），δr｝，此時將頂點vj復(fù)合指標(biāo)中第1復(fù)合項關(guān)于第r品種的子指標(biāo)組修改為（l（r）（vj），xi，＋，δr）.設(shè) 第m個 品 種 的l（m）（vj）＝min｛（l（1）（vj），…，l（r）（vj）…，l（q）（vj）｝，令δ＝ ｛δm，A－Valf｝，將頂點vj復(fù)合指標(biāo)中的第2復(fù)合項修改為（m，δ）.

（2）（xi，vj）為后向邊.①若fij＝0，此時流量不能減少，邊（xi，vj）不能成為增流鏈的邊，那么最短路不能經(jīng)過該邊，此時頂點vj復(fù)合指標(biāo)保持不變.②若fij＞0，此時流量可以減少，邊（xi，vj）可以成為增流鏈的邊，最短路就可以經(jīng)過該邊.復(fù)合指標(biāo)的各個指標(biāo)計算如下.設(shè)l（r）（vj）＝min｛l（r）（vj），l（r）（xi）－Wijr｝，如果l（r）（vj）值來自第1項l（r）（vj），那么頂點vj復(fù)合指標(biāo)中第1復(fù)合項關(guān)于第r品種的子指標(biāo)組保持不變；如果l（r）（vj）值來自第 2 項l（r）（xi）－Wijr，當(dāng)vj∈V時，δr＝min｛fij，fijr，s（r），i－f＋（xir），δr｝；當(dāng)vj∈Y時，若s（r），i－f＋（xir）＝0 或t（r），jf－（yjr）＝0，頂點vj復(fù)合指標(biāo)中第1復(fù)合項關(guān)于第r品種的子指標(biāo)組保持不變，否則δr＝min｛fij，fijr，s（r），i－f＋（xir），t（r），j－f－（yjr），δr｝，此 時 將 頂點vj復(fù)合指標(biāo)中第1復(fù)合項關(guān)于第r品種的子指標(biāo)組修改 為 （l（r）（vj），xi，－，δr）.設(shè) 第m個 品 種 的l（m）（vj）＝min｛（l（1）（vj），…，l（r）（vj）…，l（q）（vj）｝，令δ＝｛δm，A－Valf｝，將頂點vj復(fù)合指標(biāo)中的第2復(fù)合項修改為（m，δ）.

步 驟 6：針 對 頂 點vj，計 算l（m）（vj）＊＝min｛l（m）（vj）；其中j＝1，2，…，n；vj?S｝.將頂點vj復(fù)合指標(biāo)標(biāo)上＊，表示頂點vj已被檢查，設(shè)集合S＝｛xi，…，vj｝，vj?T.當(dāng)vj∈Y時，轉(zhuǎn)步驟9.

步驟7：從頂點vj出發(fā)，求其他頂點vk的復(fù)合指標(biāo).若頂點vj與頂點vk沒有直接連線，頂點vk的復(fù)合指標(biāo)保持不變；若有直接連線，則計算頂點vk的復(fù)合指標(biāo)值，計算方法如下.

（1）（vj，vk）為前向邊.①若fjk＝cjk，此時流量不能增加，邊（vj，vk）不能成為增流鏈的邊，那么最短路不能經(jīng)過該邊，此時頂點vk復(fù)合指標(biāo)保持不變.②若fjk＜cjk，此時流量可以增加，邊（vj，vk）可以成為增流鏈的邊，最短路就可以經(jīng)過該邊.復(fù)合指標(biāo)的各個 指 標(biāo) 計 算 如 下.設(shè)l（r）（vk）＝min｛l（r）（vk），l（r）（vj）＋Wjkr｝，若l（r）（vk）值來自第1項l（r）（vk），那么頂點vk復(fù)合指標(biāo)中第1復(fù)合項關(guān)于第r品種的子指標(biāo)組保持不變；若l（r）（vk）值來自第2項l（r）（vj）＋Wjkr，當(dāng)vk∈V時，δr＝min｛cjk－fjk，δr｝；當(dāng)vj∈Y時，若t（r），j－f－（yjr）＝0，頂點vj復(fù)合指標(biāo)中第1復(fù)合項關(guān)于第r品種的子指標(biāo)組保持不變，否則δr＝min｛cij－fij，t（r），j－f－（yjr），δr｝，此時將頂點vj復(fù)合指標(biāo)中第1復(fù)合項關(guān)于第r品種的子指標(biāo)組修改為（l（r）（vk），vj，＋，δr）.設(shè)第m個品種的l（m）（vk）＝min｛（l（1）（vk），…，l（r）（vk）…，l（q）（vk）｝，令δ＝｛δm，A－Valf｝，將頂點vj復(fù)合指標(biāo)第2復(fù)合項修改為（m，δ）.

（2）（vj，vk）為后向邊.①若fjk＝0，此時流量不能減少，邊（vj，vk）不能成為增流鏈中的邊，那么最短路不能經(jīng)過該邊，此時頂點vk復(fù)合指標(biāo)保持不變.②若fjk＞0，此時流量可以減少，邊（vj，vk）可以成為增流鏈的邊，最短路就可以經(jīng)過該邊.復(fù)合指標(biāo)的各個指 標(biāo) 計 算 如 下.設(shè)l（r）（vk）＝ min｛l（r）（vk），l（r）（vj）－Wijr｝，若l（r）（vk）值來自第1項l（r）（vk），那么頂點vk復(fù)合指標(biāo)中第1復(fù)合項關(guān)于第r品種的子指標(biāo)組保持不變；若l（r）（vk）值來自第2項l（r）（vj）－Wjkr，當(dāng)vk∈V時，δr＝min｛fjk，fjkr，δr｝；當(dāng)vk∈Y時，若t（r），j－f－（yjr）＝0，頂點vj復(fù)合指標(biāo)中第1復(fù)合項關(guān)于第r品種的子指標(biāo)組保持不變，否則δr＝min｛fjk，fjkr，t（r），j－f－（yjr），δr｝，此時將頂點vk復(fù)合指標(biāo)中第1復(fù)合項關(guān)于第r品種的子指標(biāo)組修改為 （l（r）（vk），vj，－，δr）.設(shè) 有 第m個 品 種 的l（m）（vk）＝min｛（l（1）（vk），…，l（r）（vk）…，l（q）（vk）｝，令δ＝｛δm，A－Valf｝，將頂點vj復(fù)合指標(biāo)第2復(fù)合項修改為（m，δ）.

步 驟 8：針 對 頂 點vk，計 算l（m）（vk）＊＝min｛l（m）（vk），其中j＝1，2，…，n；vk?S｝.將頂點vk復(fù)合指標(biāo)標(biāo)上＊，表示頂點vk已被檢查，設(shè)集合S＝｛xi，…，vk｝，vk?T.當(dāng)vk∈Y時，轉(zhuǎn)步驟9.

步驟9：當(dāng)yi?S時，說明已經(jīng)找到了品種m的關(guān)于運費最短的增流鏈.自匯yi逆向追蹤，沿著每個頂點復(fù)合指標(biāo)中第1復(fù)合項第m個子指標(biāo)組的vi即可得出關(guān)于品種m的最短路，路長為l（m）（yi），流量調(diào)整量為δ.將最短路中前向邊（vi，vj）的復(fù)合參數(shù)修改為［cij，fij＋δ（fij1，…，fijm＋δ，…，fijq）］；將最短路中后向邊（vi，vj）的復(fù)合參數(shù)修改為［cij，fijδ（fij1，…，fijm－δ，…，fijq）］.

步驟10：轉(zhuǎn)到步驟3，反復(fù)進(jìn)行，直到找不到關(guān)于運費最低的增流鏈為止.

其中步驟1～3為初始化過程，步驟4～8為尋找費用最低增流鏈的過程，步驟9～10為流量調(diào)整過程.此算法是基于構(gòu)建的復(fù)合參數(shù)和復(fù)合指標(biāo)在Ford-Fulkerson算法基礎(chǔ)上對運費有差異的多品種流交通網(wǎng)絡(luò)進(jìn)行了最小費用流分配.

3 示例求解

最小費用最大流是最小費用流的一種情況，即最小費用最大流的目標(biāo)流是最大流的流值，此時只需將本文算法中第m品種的流量調(diào)整量δ＝｛δm，A－Valf｝的A－Valf去掉即可.利用前面的引例進(jìn)行多品種流的最小費用最大流分配以更清晰地說明本文算法.由于圖顯示的局限，在圖中不標(biāo)出費用（wij1，…，wijr，…，wijq），也不對頂點進(jìn)行復(fù)合指標(biāo)的標(biāo)號；另外因篇幅限制，將相應(yīng)的計算過程省略.

步驟1：設(shè)集合S＝?，集合T＝｛x1，x2，v1，v2，v3，y1，y2，y3｝.此時初始的流量fij（fij1，…，fijr，…，fijq）均為0（0，…，0，…，0）.此問題涉及品種Ⅰ，Ⅱ，Ⅲ，用1，2，3序號來標(biāo)識.對起點xi均賦予復(fù)合指標(biāo)［（0，0，＋，＋ ∞），（0，0，＋，＋ ∞），（0，0，＋，＋∞）］｜（0，＋∞）；對其余各個頂點均賦予復(fù)合指標(biāo)［（＋∞，0，＋，＋∞），（＋∞，0，＋，＋∞），（＋∞，0，＋，＋∞）］｜（0，＋∞）.圖2為求解過程中流量調(diào)整以后的一種狀態(tài).

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

圖2 某一過程流量調(diào)整后的狀態(tài)Fig.2 The state after a flow adjustment

表2 復(fù)合指標(biāo)結(jié)果1Tab.2 Result 1of composite indicators

針對表2取l（m）（vj）＊＝min｛l（m）（vj）；vj?S｝＝min｛9，4，23｝＝4＝l（2）（v2）＊，將表2中頂點v2的指標(biāo)標(biāo)記＊，此時S＝｛x1，x2，v2｝，集合T＝｛v1，v3，y1，y2，y3｝.從頂點v2出發(fā)，繼續(xù)求復(fù)合指標(biāo)，頂點v2與頂點v1，v3，y3有直接連線，只需計算這3個頂點的復(fù)合指標(biāo)即可，其余頂點復(fù)合參數(shù)保持不變，詳細(xì)計算過程如下.

（1）（v2，v1）為前向邊，此時f21＝0＜c21＝4，此邊可以成為增流鏈中的邊.①針對第I品種有l(wèi)（1）（v1）＝min｛l（1）（v1），l（1）（v2）＋W211｝＝min｛＋∞，＋∞＋8｝＝＋∞，l（1）（v1）值來自第1項，頂點v1復(fù)合指標(biāo)中關(guān)于第Ⅰ品種的子指標(biāo)組保持不變.②針對第Ⅱ品種有l(wèi)（2）（v1）＝min｛l（2）（v1），l（2）（v2）＋W212｝＝min｛＋∞，4＋7｝＝11，l（2）（v1）值來自第2項，關(guān)于第Ⅱ品種的流量調(diào)整量δ2＝min｛c21－f21，δ2｝＝min｛4－0，＋∞｝＝4，此時將頂點v1復(fù)合指標(biāo)中關(guān)于第Ⅱ品種的子指標(biāo)組修改為（11，v2，＋，4）.③ 針 對 第 Ⅲ 品 種 有l(wèi)（3）（v1）＝ min｛l（3）（v1），l（3）（v2）＋W213｝＝min｛9，8＋7｝＝9，l（3）（v1）值來自第1項，頂點v1復(fù)合指標(biāo)中關(guān)于第Ⅲ品種的子指標(biāo)組保持不變.

（2）（v2，v3）為前向邊，同時f23＝c23＝8，說明流量不能增加，即邊（v2，v3）不能成為增流鏈中的邊，那么最短路也就不能經(jīng)過該邊，此時頂點v3的復(fù)合指標(biāo)保持不變.

（3）（v2，y3）為前向邊，同時f23＝c23＝5，說明流量不能增加，即邊（v2，y3）不能成為增流鏈中的邊，那么最短路也就不能經(jīng)過該邊，此時頂點y3的復(fù)合指標(biāo)保持不變.

修改后的復(fù)合指標(biāo)如表3所示.

表3 復(fù)合指標(biāo)結(jié)果2Tab.3 Result 2of composite indicators

針對表3取l（m）（vj）＊＝min｛l（m）（vj）；vj?S｝＝min｛9，23｝＝9＝l（3）（v1）＊，將表3中頂點v1指標(biāo)標(biāo)記＊.此時S＝｛x1，x2，v2，v1｝，集合T＝｛v3，y1，y2，y3｝.從頂點v1出發(fā)求復(fù)合指標(biāo)，頂點v1與頂點v3，y1，y2有直接連線，只計算這3個頂點復(fù)合指標(biāo)即可，其余頂點復(fù)合參數(shù)保持不變，計算過程省略.復(fù)合指標(biāo)如表4所示.

表4 復(fù)合指標(biāo)結(jié)果3Tab.4 Result 3of composite indicators

針對表4取l（m）（vj）＊＝min｛l（m）（vj）；vj?S｝＝min｛16，23｝＝16＝l（2），v3）＊，將表4中頂點v3的指標(biāo)標(biāo)記＊，此時S＝｛x1，x2，v2，v1，v3｝，集合T＝｛y1，y2，y3｝.從頂點v3出發(fā)，繼續(xù)求復(fù)合指標(biāo)，頂點v3與頂點y1，y2，y3有直接連線，只需要計算這3個頂點的復(fù)合指標(biāo)即可，其余頂點復(fù)合參數(shù)保持不變，詳細(xì)計算過程如下：

（1）（v3，y1）為前向邊，此時f31＝2＜c31＝4，此邊可以成為增流鏈中的邊.①針對第I品種有l(wèi)（1）（y1）＝min｛l（1）（y1），l（1）（v3）＋W311｝＝min｛23，＋∞＋6｝＝23，l（1）（y1）值來自第1項，頂點y1復(fù)合指標(biāo)中關(guān)于第Ⅰ品種的子指標(biāo)組保持不變.②針對第Ⅱ品種，有t（r），j－f－（yjr）＝y(tǒng)1（2）－f－（y12）＝7－（5＋2）＝0，此時頂點y1不再需要接收第Ⅱ品種，頂點y1復(fù)合指標(biāo)中關(guān)于第Ⅱ品種的子指標(biāo)組保持不變.③頂點y1本身不需要接收第Ⅲ品種，那么頂點y1復(fù)合指標(biāo)中關(guān)于第Ⅲ品種的子指標(biāo)組保持不變.

（2）（v3，y2）為前向邊，此時f32＝c32＝6，此時流量不能增加，即邊（v3，y2）不能成為增流鏈中的邊，那么最短路也就不能經(jīng)過該邊，此時頂點y2的復(fù)合指標(biāo)保持不變.

（3）（v3，y3）為前向邊，此時f33＝1＜c33＝6，此邊可以成為增流鏈中的邊.①針對第Ⅰ品種有l(wèi)（1）（y3）＝min｛l（1）（y3），l（1）（v3）＋W331｝＝min｛＋∞，＋∞＋5｝＝＋∞，l（1）（y3）值來自第1項，頂點y3復(fù)合指標(biāo)中關(guān)于第Ⅰ品種的子指標(biāo)組保持不變.②頂點y3本身不需要接收第Ⅱ品種，那么頂點y3復(fù)合指標(biāo)中關(guān)于第Ⅱ品種的子指標(biāo)組保持不變.③針對第Ⅲ 品 種 有l(wèi)（3）（y3）＝min｛l（3）（y3），l（3）（v3）＋W333｝＝min｛＋∞，17＋6｝＝23，l（3）（y3）值來自第2項，又有t（r），j－f－（yjr）＝y(tǒng)（3），3－f－（y33）＝13－（7＋1）＝5，那么關(guān)于第Ⅲ品種的流量調(diào)整量δ3＝min｛c33－f33，y（3），3－f－（y33），δ3｝＝min｛6－1，5，2｝＝2.此時將頂點y3復(fù)合指標(biāo)中關(guān)于第Ⅲ品種的子指標(biāo)組修改為（23，v3，＋，2）.

修改后的復(fù)合指標(biāo)如表5所示.

表5 復(fù)合指標(biāo)結(jié)果4Tab.5 The results of composite indicators

針對表5取l（m）（vj）＊＝min｛l（m）（vj）；vj?S｝＝min｛23，23｝＝23＝l（1）（y1）＊＝l（3）（y3）＊.將表5中頂點y1，y3的指標(biāo)標(biāo)記＊，此時S＝｛x1，x2，v1，v2，v3，y1，y3｝，集合T＝｛y2｝.出現(xiàn)y1?S，y3?S情況，說明已經(jīng)找到關(guān)于品種Ⅰ和品種Ⅲ的運費最低的2條增流鏈.

自匯y1沿著每個頂點復(fù)合指標(biāo)中第1復(fù)合項的第1個子指標(biāo)組逆向追蹤，可得出關(guān)于品種Ⅰ的最短路為x1→y1，路長為23，流量調(diào)整量為3.

自匯y3沿著每個頂點復(fù)合指標(biāo)的第1復(fù)合項中第3個子指標(biāo)組逆向追蹤，可得出關(guān)于品種Ⅲ最短路為x2→v1→v3→y3，路長為23，流量調(diào)整量為2.

最終流量分配結(jié)果如圖3所示.

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

圖3 圖2流量調(diào)整后的狀態(tài)Fig.3 The state after flow adjustment in Fig.2

針對圖4，從源x1，x2出發(fā)的邊中只有邊（x1，y1）為不飽和邊，但匯y1需要的Ⅰ，Ⅱ品種已經(jīng)得到全部滿足，所以沒有辦法再找到增流鏈.由圖4可以知道該引例中各個品種的具體運送方案，把該引例的總體方案、各個品種的具體方案列于表6，發(fā)送和接收的總量都為42，則3個品種的費用WⅠ，WⅡ，WⅢ分別為：WⅠ＝23×3＋3×3＋6×7＋9×3＋4×2＋8×2＋7×5＋5×2＝216，WⅡ＝8×4＋4×1＋6×6＋8×5＋6×4＋5×1＋8×1＋4×2＝157，WⅢ＝9×3＋8×8＋16×7＋5×1＋8×3＋8×1＋6×7＋5×6＋6×4＝336.總費用W＝WⅠ＋WⅡ＋WⅢ＝216＋157＋336＝709.

圖4 多品種流的最小費用最大流最終分布狀態(tài)Fig.4 Minimum cost of the maximum flow distribution of multi-commodity flow

表6 最小費用最大流具體分配方案Tab.6 Specific allocation scheme for the minimum cost of the maximum flow

4 結(jié)語

在連續(xù)最短路算法和Ford-Fulkerson算法基礎(chǔ)上，通過構(gòu)建復(fù)合指標(biāo)建立了運費有差異的多品種流最小費用流分配方法，另外，通過設(shè)計的復(fù)合參數(shù)也標(biāo)定了多品種流的流量分配狀態(tài).本文構(gòu)造的基于復(fù)合參數(shù)和復(fù)合指標(biāo)的多品種流最小費用流算法避免了傳統(tǒng)算法需要改變網(wǎng)絡(luò)圖結(jié)構(gòu)的不足，在算法實現(xiàn)上也體現(xiàn)了便利.在交通運輸領(lǐng)域，運費有差異的多品種流分配問題普遍存在，但針對此類問題的研究文獻(xiàn)很少，本文算法也為解決交通網(wǎng)絡(luò)的一系列相關(guān)實際問題提供了參考.

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

KOU Weihua.Operational research［M］.Chengdu：Southwest Jiaotong University Press，2013.

［2］ 寇瑋華，崔皓瑩.有運送路徑限制的多品種流交通網(wǎng)絡(luò)最小費用流算法研究［J］.蘭州交通大學(xué)學(xué)報，2013，32（6）：1.

KOU Weihua，CUI Haoying.An algorithm for the minimum cost flow which has limited transmission-path in multi-species flow traffic network ［J］. Journal of Transportation Engineering and Information，2013，32（6）：1.

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

KOU Weihua，CUI Haoying.Optimizing study on enlarging the capacity of traffic network to meet the need of the increscent flow［J］.Journal of Transportation Engineering and Information，2012，10（4）：19.

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

KOU Weihua，DONG Xue，LüLinjian.An algorithm for the minimum cost max-flow which has limited flow between two notes in the traffic and transportation network［J］.Journal of Lanzhou Jiaotong University，2009，28（6）：104.

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

CHENG Lin，WANG Wei.On dial assignment and choice probabilities［J］.Journal of Transportation Systems Engineering and Information Technology，2002，2（3）：29.

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

CHEN Guangya.Equilibrium problems of traffic networks with vector cost functions：model and analysis［J］.Journal of Transportation Systems Engineering and Information Technology，2006，6（5）：56.

［7］ 任剛，王煒.可直接計算轉(zhuǎn)向流量的改進(jìn)型Dial交通分配算法［J］.中國公路學(xué)報，2005，18（4）：83.

REN Gang，WANG Wei.Improved Dial’s traffic assignment algorithm for directly computation on turning flows［J］.China Journal of Highway and Transport，2005，18（4）：83.

［8］ Orlin B J.Network optimization［EB／OL］.［2013-04-01］.http：／／www.core.org.cn／OcwWeb／index.htm.

［9］ Chabini I，Odoni R A.Transportation flow system.MIT open courseware［EB／OL］.［2013-04-20］.http：／／www.core.org.cn／OcwWeb／index.htm.

［10］ Shepherd B，Zhang L.A cycle augmentation algorithm for minimum cost multicommodity flows on a ring［C］／／Global Telecommunications Conference. Rio de Janeiro：IEEE Commumcations Society，1999：1535-1543.