運(yùn)費(fèi)無(wú)差異的多品種流交通網(wǎng)絡(luò)最小費(fèi)用算法

寇瑋華，崔皓瑩

(西南交通大學(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-ofkilter algorithm)等等［1-8］，這些算法都可以解決單一品種流的最小費(fèi)用流分配問(wèn)題.在實(shí)際的交通網(wǎng)絡(luò)應(yīng)用中，普遍出現(xiàn)了多品種流問(wèn)題，所以有了流變換、流分解、組合應(yīng)用、多品種流及預(yù)流推進(jìn)等新的理論和方法［9-13］，但這些算法都沒(méi)有徹底解決多品種流的最小費(fèi)用流分配問(wèn)題.針對(duì)交通運(yùn)輸領(lǐng)域出現(xiàn)的多品種流交通網(wǎng)絡(luò)，有必要對(duì)其最小費(fèi)用流分配問(wèn)題作進(jìn)一步研究，并在其他算法的基礎(chǔ)上，構(gòu)造可行的最小費(fèi)用流分配算法.

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

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

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

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

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

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

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

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

先給定單一品種流的交通網(wǎng)絡(luò)G=(V，E，C，F(xiàn)，W，X，Y)，其中頂點(diǎn)集合 V=(v1，v2，…，vn)，邊E=(e1，e2，…，em)．對(duì)集合V取定兩個(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、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=A．

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

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

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

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

單一品種流最小費(fèi)用流Ford-Fulkerson算法，是通過(guò)構(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ú)差異的多品種流交通網(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ú)差異的多品種流交通網(wǎng)絡(luò)最小費(fèi)用流算法.

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

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

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

2.1.2 復(fù)合指標(biāo)中相關(guān)指標(biāo)的計(jì)算規(guī)則

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

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

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

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

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

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

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

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

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

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

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

基于Ford-Fulkerson算法，將關(guān)于運(yùn)送費(fèi)用最低的增流鏈的流量進(jì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ù)合指標(biāo)以及相應(yīng)的規(guī)則，本文算法的思路是，隨著所求最短路的延伸，同時(shí)消除非增流邊，這樣既杜絕了二次求解問(wèn)題，也避免了全枚舉的問(wèn)題，算法步驟如下.第1～3步為初始化過(guò)程，第4～8步為尋找費(fèi)用最低的增流鏈過(guò)程，第9～11步為流量調(diào)整過(guò)程.

第1 步 設(shè)源 X={x1，…，xi，…，xn}，轉(zhuǎn)運(yùn)點(diǎ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步 對(duì)運(yùn)送費(fèi)用無(wú)差異的多品種流交通網(wǎng)絡(luò)，在零流(平凡流)基礎(chǔ)上，利用給出的容量、費(fèi)用，把邊的屬性設(shè)為復(fù)合參數(shù)形式，即［cij，fij(fij1，…，fijr，…，fijq)，wij］， 此 時(shí) 初 始 的 流 量fij(fij1，…，fijr，…，fijq)均為 0(0，…，0，…，0)，即有Valf=0．

第3步 設(shè)l(xi)=0，對(duì)起點(diǎn)xi賦予復(fù)合指標(biāo)(0，0，+)|［+∞(+∞，…，+∞…，+∞)］;設(shè)其余頂點(diǎn)的l(vi)=+∞、l(yi)=+∞，那么其余頂點(diǎn)均可以賦予復(fù)合指標(biāo)(+∞，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)中的各個(gè)指標(biāo)計(jì)算如下:按照規(guī)則1可知l(vj)=min{l(vj)，l(xi)+Wij}，如果l(vj)值來(lái)自第1項(xiàng)l(vj)，頂點(diǎn)vj的復(fù)合指標(biāo)保持不變．如果l(vj)值來(lái)自第2項(xiàng)l(xi)+Wij，總流量調(diào)整量λ=min{λ，cij-fij，A-Valf}．當(dāng)vj∈V時(shí)，所有品種的最大可能調(diào)整量λr=λ．當(dāng)vj∈Y時(shí)，若-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)}．此時(shí)需要將頂點(diǎn)vj復(fù)合指標(biāo)修改為(l(vj)，xi，邊的方向)|［λ(λ1，…，λr…，λp)］．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ì)算如下:按照規(guī)則2可知l(vj)=min{l(vj)，l(xi)-Wij}，如果l(vj)值來(lái)自第1項(xiàng)l(vj)，頂點(diǎn)vj復(fù)合指標(biāo)保持不變．如果l(vj)值來(lái)自第2項(xiàng)l(xi)-Wij，總流量的調(diào)整量 λ=min{λ，fij，A-Valf}．當(dāng)vj∈ V 時(shí)，所有品種的最大可能調(diào)整量λr=min{λ，fijr}．當(dāng)vj∈Y時(shí)，若-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)}．此時(shí)需要將頂點(diǎn)vj復(fù)合指標(biāo)修改為(l(vj)，xi，邊的方向)|［λ(λ1，…，λr…，λp)］．

第6步 針對(duì)頂點(diǎn)vj，計(jì)算l(vj)*=min{l(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 步，否則轉(zhuǎn)第7步．

第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ì)算如下:按照規(guī)則1可知l(vk)=min{l(vk)，l(vj)+Wjk}，如果l(vk)值來(lái)自第1項(xiàng)l(vk)，頂點(diǎn)vk的復(fù)合指標(biāo)保持不變．如果l(vk)值來(lái)自第2項(xiàng)l(vj)+Wjk，總流量的調(diào)整量λ=min{λ，cjk-fjk，A-Valf}．當(dāng)vk∈ V 時(shí)，所有品種的最大可能調(diào)整量λr=λ．當(dāng)vk∈Y時(shí)，若-f-(yjk)=0，則k品種的最大可能調(diào)整量λk=0，其余品種的最大可能調(diào)整量-f-(yjk)};否則，所有品種的最大可能調(diào)整量λr=min{λ，tjk-f-(yjk)}．此時(shí)需要將頂點(diǎn)vk復(fù)合指標(biāo)修改為(l(vk)，vj，邊的方向)|［λ(λ1，…，λr，…，λp)］．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ì)算如下:按照規(guī)則2可知l(vk)=min{l(vk)，l(vj)-Wjk}，如果l(vk)值來(lái)自第1項(xiàng)l(vk)，頂點(diǎn)vk復(fù)合指標(biāo)保持不變．如果l(vk)值來(lái)自第2項(xiàng)l(vj)-Wjk，總流量的調(diào)整量 λ=min{λ，fjk，AValf}．當(dāng)vk∈V時(shí)，所有品種的最大可能調(diào)整量λr=min{λ，fjkr}．當(dāng)vk∈Y時(shí)，若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)}．此時(shí)需要將頂點(diǎn)vk復(fù)合指標(biāo)修改為(l(vk)，vj，邊的方向)|［λ(λ1，…，λr…，λp)］．

第8步 針對(duì)頂點(diǎn)vk，計(jì)算l(vk)*=min{l(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í)，自匯yi逆向追蹤，沿著每個(gè)頂點(diǎn)復(fù)合指標(biāo)中第1個(gè)子指標(biāo)組的vi即可得出運(yùn)送費(fèi)用最低的增流鏈，路長(zhǎng)為l(yi)，總流量的調(diào)整量δ=λ．再按照規(guī)則3、4，即可確定出增流鏈中每個(gè)品種的分流量的調(diào)整量δr．

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

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

3 示例求解

為了說(shuō)明本文算法，下面對(duì)引例進(jìn)行最小費(fèi)用最大流分配，最小費(fèi)用最大流的目標(biāo)流是最大流，此時(shí)將算法中總流量調(diào)整量λ公式中的AValf去掉即可.由于圖顯示空間的局限，不對(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，fij2，fij3)均為 0(0，0，0)．此問(wèn)題涉及 I、II、III 3 個(gè)品種，這里用1、2、3序號(hào)來(lái)標(biāo)識(shí)．對(duì)起點(diǎn)xi均賦予復(fù)合指標(biāo)(0，0，+)|［+∞(+∞，+∞，+∞)］;對(duì)其余各個(gè)頂點(diǎn)均可以賦予復(fù)合指標(biāo)(+∞，0，+)|［+∞(+∞，+∞，+∞)］．圖2為求解時(shí)流量調(diào)整以后某一過(guò)程的狀態(tài)圖．

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

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

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

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

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

針對(duì)表2取l(vj)*=min{l(vj);vj?S}=min{10，23，23，28}=10=l(v2)* ，將表 2 中頂點(diǎn)v2的指標(biāo)標(biāo)記 *．此時(shí) S={x1，x2，v1，v2}，集合 T={v3，y1，y2，y3}．從頂點(diǎn)v2出發(fā)，繼續(xù)求復(fù)合指標(biāo)，頂點(diǎn)v2與頂點(diǎn)v3、y3有直接連線．但由于在前向邊(v2，v3)上，f23=8=c23=8，此時(shí)流量不能增加，即邊(v2，v3)不能成為增流鏈中的邊，那么最短路也就不能經(jīng)過(guò)該邊，此時(shí)頂點(diǎn)v3的復(fù)合指標(biāo)保持不變;同理，在前向邊(v2，y3)上由于f23=5=c23=5，流量不能增加，此時(shí)頂點(diǎn)y3的復(fù)合指標(biāo)保持不變．此種情況說(shuō)明，無(wú)法通過(guò)頂點(diǎn)v2找到一條到達(dá)匯的增流鏈，此時(shí)需要返回到前一個(gè)頂點(diǎn)v1，通過(guò)與頂點(diǎn)v1有直接連線的其他頂點(diǎn)來(lái)尋找最短路．針對(duì)表2取l(vj)*=min{l(vj);vj? S}=min{23，23，28}=23=l(y1)=l(v3)*，這里選擇頂點(diǎn)v3作為標(biāo)記點(diǎn)，即將表2中頂點(diǎn)v3的指標(biāo)標(biāo)記 *．此時(shí) S={x1，x2，v1，v2，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=0＜c31=4，此邊可以成為增流鏈中的邊，則l(y1)=min{l(y1)，l(v3)+W31}=min{23，26}=23，l(y1)值來(lái)自第1項(xiàng)，頂點(diǎn)y1的復(fù)合指標(biāo)保持不變．2)(v3，y2)為前向邊，此時(shí)f32=c32=6，此時(shí)流量不能增加，即邊(v3，y2)不能成為增流鏈中的邊，那么最短路也就不能經(jīng)過(guò)該邊，頂點(diǎn)y2的復(fù)合指標(biāo)保持不變．3)(v3，y3)為前向邊，此時(shí)f33=4＜c33=6，此邊可以成為增流鏈中的邊．則l(y3)=min{l(y3)，l(v3)+W33}=min{+∞，30}=30，l(y3)值來(lái)自第2項(xiàng)，總流量的調(diào)整量λ=min{λ，c33-f33}=min{4，6-4}=2，此時(shí)針對(duì)第I品種有=8-(5+2)=1，則第I品種的最大可能調(diào)整量 λ1=minf-(y31)}=min{2，1}=1;針對(duì)第Ⅱ品種有-f-(y32)=0，則第Ⅱ品種的最大可能調(diào)整量λ2=0;針對(duì)第Ⅲ品種有=13-(0+2+7)=4，則第Ⅲ品種的最大可能調(diào)整量λ3=min{λ，t33-f-(y33)}=min{2，4}=2．修改后的復(fù)合指標(biāo)如表3所示．

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

針對(duì)表3取l(vj)*=min{l(vj);vj?S}=min{23，28，30}=23=l(y1)*．由此可知關(guān)于費(fèi)用的最短路的增流鏈應(yīng)為x1→y1，但由于匯y1需要的第I、II品種已全部滿足，其流量無(wú)法增加，此時(shí)需要選擇包含匯的次最短路．針對(duì)表3取l(vj)*=min{l(vj);vj?S}=min{28，30}=28=l(y2)*．將表3中頂點(diǎn)y2的指標(biāo)標(biāo)記*，此時(shí)S={x1，x2，v1，v2，v3，y2}，集合T={y1，y3}．因?yàn)閥2?S，說(shuō)明已經(jīng)找到關(guān)于運(yùn)送費(fèi)用最低的增流鏈．

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

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

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

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

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

4 結(jié)論

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

2)構(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ú)差異的多品種流分配問(wèn)題，但針對(duì)此類(lèi)問(wèn)題的研究文獻(xiàn)還不多見(jiàn)，該算法也為解決交通網(wǎng)絡(luò)的一系列相關(guān)實(shí)際問(wèn)題提供了應(yīng)用基礎(chǔ).

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

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

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

［3］寇瑋華，崔皓瑩.滿足交通網(wǎng)絡(luò)流量增長(zhǎng)態(tài)勢(shì)的擴(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］謝政，湯澤瀅.帶模糊約束的最小費(fèi)用流問(wèn)題［J］.模糊系統(tǒng)與數(shù)學(xué)，1999，13(2):90-941.

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

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

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