寇瑋華，崔皓瑩

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

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

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

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

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

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

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

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

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

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

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

表1 不同品種流的運(yùn)費(fèi)Tab.1 The conveyance cost of different commodity flows

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

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

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

運(yùn)費(fèi)無(wú)差異的單一品種流最小費(fèi)用流Ford-Fulkerson算法是先構(gòu)造增流網(wǎng)絡(luò)，在增流網(wǎng)絡(luò)中尋找關(guān)于費(fèi)用代數(shù)和最小的路徑，再針對(duì)此路徑所對(duì)應(yīng)原網(wǎng)絡(luò)中的增流鏈進(jìn)行流量調(diào)整.針對(duì)運(yùn)費(fèi)有差異的多品種流交通網(wǎng)絡(luò)，如果再構(gòu)造增流網(wǎng)絡(luò)勢(shì)必會(huì)造成增流網(wǎng)絡(luò)結(jié)構(gòu)龐大而且復(fù)雜，同時(shí)計(jì)算過(guò)程更為繁瑣，所以直接利用Ford-Fulkerson算法可行但不是優(yōu)化的方法.

2.1 算法思想

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

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

（2）復(fù)合指標(biāo).連續(xù)最短路算法中，頂點(diǎn)vj的指標(biāo)為（l（vj），vi），其中l(wèi)（vj）表示從起點(diǎn)經(jīng)頂點(diǎn)vi到頂點(diǎn)vj關(guān)于費(fèi)用的最短路長(zhǎng)度，vi表示vj前一個(gè)頂點(diǎn).Ford-Fulkerson算法針對(duì)流量調(diào)整，設(shè)定u表示被標(biāo)識(shí)點(diǎn)vj前一個(gè)頂點(diǎn)；D表示邊的方向，通過(guò)“＋”或“－”來(lái)標(biāo)識(shí)是前向邊還是后向邊；δ表示流量的調(diào)整量，構(gòu)建頂點(diǎn)vj的指標(biāo) （u，D，δ）.針對(duì)多品種流交通網(wǎng)絡(luò)，既要考慮最短路指標(biāo)和流量調(diào)整指標(biāo)，也要考慮多品種及運(yùn)費(fèi)有差異的問(wèn)題，所以構(gòu)建復(fù)合指標(biāo)［…，（l（r）（vj），vi，D，δr），…］｜（m，δ），其中l(wèi)（r）（vj）表示第r個(gè)品種從起點(diǎn)經(jīng)過(guò)前一個(gè)頂點(diǎn)vi到頂點(diǎn)vj關(guān)于運(yùn)費(fèi)最低的最短路長(zhǎng)度；vi表示頂點(diǎn)vj的前一個(gè)頂點(diǎn)；“邊的方向”表明邊（vi，vj）是前向邊還是后向邊，即（vi，vj）的流量是增加還是減少；δr表示關(guān)于第r個(gè)品種最短路所對(duì)應(yīng)的第r個(gè)品種的流量調(diào)整量；m表示在所有品種的最短路徑中路徑長(zhǎng)度 最 小 所 對(duì) 應(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)能找出費(fèi)用最低的最短路，并可以確定出其對(duì)應(yīng)的品種，再判斷此最短路是否為增流鏈，如果是增流鏈，就對(duì)相應(yīng)的品種進(jìn)行流量調(diào)整，即通過(guò)修改復(fù)合參數(shù)值來(lái)分配流量，這樣就可以避免先指定某一品種進(jìn)行最小費(fèi)用流分配的錯(cuò)誤.以上思路是二次求解法，即先尋找關(guān)于費(fèi)用最低的最短路，再判斷此最短路是否為增流鏈.但本文算法的核心思路是，隨著所求最短路的延伸，同時(shí)消除非增流邊，這樣既杜絕了二次求解問(wèn)題，也避免了全枚舉的問(wèn)題.

2.2 算法步驟

步驟1：設(shè)源X＝｛x1，…，xi，…，xn｝，轉(zhuǎn)運(yùn)點(diǎ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)識(shí)的頂點(diǎn)寫(xiě)入集合S中，初始時(shí)S＝?，設(shè)頂點(diǎn)集合T＝｛x1，…，xi，…，xn，v1，…，vi，…，vn，y1，…，yi，…，yn｝.

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

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

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

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

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

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

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

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

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

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

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

步驟9：當(dāng)yi?S時(shí)，說(shuō)明已經(jīng)找到了品種m的關(guān)于運(yùn)費(fèi)最短的增流鏈.自匯yi逆向追蹤，沿著每個(gè)頂點(diǎn)復(fù)合指標(biāo)中第1復(fù)合項(xiàng)第m個(gè)子指標(biāo)組的vi即可得出關(guān)于品種m的最短路，路長(zhǎng)為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)于運(yùn)費(fèi)最低的增流鏈為止.

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

3 示例求解

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

（3）（v3，y3）為前向邊，此時(shí)f33＝1＜c33＝6，此邊可以成為增流鏈中的邊.①針對(duì)第Ⅰ品種有l(wèi)（1）（y3）＝min｛l（1）（y3），l（1）（v3）＋W331｝＝min｛＋∞，＋∞＋5｝＝＋∞，l（1）（y3）值來(lái)自第1項(xiàng)，頂點(diǎn)y3復(fù)合指標(biāo)中關(guān)于第Ⅰ品種的子指標(biāo)組保持不變.②頂點(diǎn)y3本身不需要接收第Ⅱ品種，那么頂點(diǎn)y3復(fù)合指標(biāo)中關(guān)于第Ⅱ品種的子指標(biāo)組保持不變.③針對(duì)第Ⅲ 品 種 有l(wèi)（3）（y3）＝min｛l（3）（y3），l（3）（v3）＋W333｝＝min｛＋∞，17＋6｝＝23，l（3）（y3）值來(lái)自第2項(xiàng)，又有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.此時(shí)將頂點(diǎn)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

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

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

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

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

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

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

針對(duì)圖4，從源x1，x2出發(fā)的邊中只有邊（x1，y1）為不飽和邊，但匯y1需要的Ⅰ，Ⅱ品種已經(jīng)得到全部滿足，所以沒(méi)有辦法再找到增流鏈.由圖4可以知道該引例中各個(gè)品種的具體運(yùn)送方案，把該引例的總體方案、各個(gè)品種的具體方案列于表6，發(fā)送和接收的總量都為42，則3個(gè)品種的費(fèi)用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.總費(fèi)用W＝WⅠ＋WⅡ＋WⅢ＝216＋157＋336＝709.

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

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

4 結(jié)語(yǔ)

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

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

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

［2］ 寇瑋華，崔皓瑩.有運(yùn)送路徑限制的多品種流交通網(wǎng)絡(luò)最小費(fèi)用流算法研究［J］.蘭州交通大學(xué)學(xué)報(bào)，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ò)流量增長(zhǎng)態(tài)勢(shì)的擴(kuò)能優(yōu)化研究［J］.交通運(yùn)輸工程與信息學(xué)報(bào)，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］ 寇瑋華，董雪，呂林劍.交通運(yùn)輸網(wǎng)絡(luò)中兩個(gè)結(jié)點(diǎn)間有流量約束的最小費(fèi)用最大流算法［J］.蘭州交通大學(xué)學(xué)報(bào)，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交通量分配模型和選擇率問(wèn)題的研究［J］.交通運(yùn)輸系統(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］ 陳光亞.帶有向量值費(fèi)用函數(shù)的交通網(wǎng)絡(luò)平衡問(wèn)題——模型與分析［J］.交通運(yùn)輸系統(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］ 任剛，王煒.可直接計(jì)算轉(zhuǎn)向流量的改進(jìn)型Dial交通分配算法［J］.中國(guó)公路學(xué)報(bào)，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.