基于最小費(fèi)用流的應(yīng)急物資運(yùn)輸問(wèn)題研究

李廣興 何 珊

(華北電力大學(xué)，北京 102206)

1 引言

應(yīng)急物資就是預(yù)防、應(yīng)對(duì)災(zāi)害過(guò)程中為保證各個(gè)環(huán)節(jié)的順利進(jìn)行而儲(chǔ)存應(yīng)急資源。應(yīng)對(duì)災(zāi)害需要有充足的應(yīng)急物資，并能夠在最短的時(shí)間內(nèi)將物資運(yùn)輸?shù)綖?zāi)害發(fā)生地，以最大程度減少人民生命財(cái)產(chǎn)損失。如何制定調(diào)運(yùn)方案，將物資運(yùn)往指定地點(diǎn)，而且實(shí)現(xiàn)運(yùn)輸成本的最小化和運(yùn)輸時(shí)間的最短，即為運(yùn)輸問(wèn)題。與一般線性規(guī)劃問(wèn)題不同，它的約束方程組的系數(shù)矩陣具有特殊的結(jié)構(gòu)，這就需要采用不同的甚至更為簡(jiǎn)便的求解方法來(lái)解決這種在實(shí)際工作中經(jīng)常遇到的問(wèn)題。

1.1 應(yīng)急物資運(yùn)輸問(wèn)題

從應(yīng)急救援角度來(lái)看早在1984年Kembell Cook對(duì)索馬里旱災(zāi)的救援行動(dòng)就考慮了應(yīng)急物流的問(wèn)題。隨后，研究學(xué)者對(duì)應(yīng)急物流問(wèn)題提出了不同的線性規(guī)劃模型來(lái)研究這一問(wèn)題，Knott Rathi等人將大規(guī)模應(yīng)急物流描述為具有時(shí)間窗限制的多物品、多模式網(wǎng)絡(luò)流問(wèn)題，并給出了求解方法。Haghani和Oh把大規(guī)模災(zāi)害的救援物資運(yùn)輸問(wèn)題作為多物資多模式網(wǎng)絡(luò)流模型推導(dǎo)出單目標(biāo)函數(shù)，它以時(shí)空網(wǎng)絡(luò)概念為基礎(chǔ)，在模型中時(shí)變的物資需求和運(yùn)輸網(wǎng)絡(luò)中的載運(yùn)工具的位移由路徑、運(yùn)輸、供需執(zhí)行三種類型連接起來(lái)，簡(jiǎn)化了多物資多模式多需求導(dǎo)致的復(fù)雜網(wǎng)絡(luò)流問(wèn)題。應(yīng)急物流活動(dòng)中，物資配送的關(guān)鍵是出救點(diǎn)到需求點(diǎn)之間的物流網(wǎng)絡(luò)中選擇最優(yōu)路徑，從而使應(yīng)急物流活動(dòng)的耗時(shí)最短，成本最低?！皯?yīng)急物流”這一概念是由歐忠文在國(guó)內(nèi)首先提出的，他給出了應(yīng)急物流的定義，即“以提供突發(fā)性自然災(zāi)害、突發(fā)性公共衛(wèi)生事件等突發(fā)性事件所需應(yīng)急物資為目的，以追求時(shí)間效益最大化和災(zāi)害損失最小化為目標(biāo)的特種物流活動(dòng)”。孟參探討了應(yīng)急物資的庫(kù)存控制及運(yùn)輸配送。謝征等人提出求解各種最小費(fèi)用流問(wèn)題的算法。如果最小費(fèi)用流問(wèn)題中給定的流值為最大流，則為最小費(fèi)用最大流問(wèn)題?？墁|華、董雪、呂林劍等人利用最小費(fèi)用流算法，解決了交通運(yùn)輸網(wǎng)絡(luò)中兩個(gè)結(jié)點(diǎn)之間有流量約束的最小費(fèi)用最大流分配問(wèn)題。

1.2 最小費(fèi)用流的引入

一般情況下，運(yùn)輸問(wèn)題可利用以下幾種方法解決：表上作業(yè)法、最短線路法和智能搜索算法等。這些研究方法，都能解決運(yùn)輸網(wǎng)絡(luò)的設(shè)計(jì)問(wèn)題，但也都各有優(yōu)缺點(diǎn)。本文試圖利用網(wǎng)絡(luò)流中的最小費(fèi)用流問(wèn)題的方法，來(lái)解決應(yīng)急物資網(wǎng)絡(luò)運(yùn)輸?shù)膯?wèn)題。

(1)表上作業(yè)法。當(dāng)已知某些物資從出發(fā)地運(yùn)往不同目的地單位物資的運(yùn)輸費(fèi)用時(shí)，常采用表上作業(yè)法，求出使運(yùn)輸費(fèi)用最省、時(shí)間最短的物資合理調(diào)配方案。

然而有時(shí)會(huì)出現(xiàn)迭代次數(shù)較多，工作量繁瑣的情況。

(2)最短路線法。當(dāng)已知某物資從出發(fā)地運(yùn)往目的地，可有多條運(yùn)輸路線供選擇，這時(shí)，可構(gòu)造費(fèi)用網(wǎng)絡(luò)圖，用求最短路線的方法，選擇最優(yōu)的運(yùn)輸方案，使運(yùn)輸時(shí)間最短、費(fèi)用最省。對(duì)于這類運(yùn)輸問(wèn)題，只需畫出各種運(yùn)輸路線的線路圖及圖上每一條邊(或弧)上的距離或費(fèi)用(也可以用鄰接矩陣表示)，然后用狄克斯特拉的標(biāo)號(hào)法或鄰接矩陣法求最優(yōu)運(yùn)輸路線。

基于此，本文在應(yīng)急物資運(yùn)輸網(wǎng)絡(luò)問(wèn)題中試圖尋找一種更加簡(jiǎn)便有效的方法來(lái)進(jìn)行求解，因此引入了最小費(fèi)用流的方法。眾所周知，在一個(gè)網(wǎng)絡(luò)中每段路徑都有“容量”和“費(fèi)用”兩個(gè)限制的條件下，此類問(wèn)題的研究試圖尋找出：流量從A到B(A指出救點(diǎn)，B指需求點(diǎn)，出救點(diǎn)可以是多個(gè)地點(diǎn))，如何選擇路徑、分配經(jīng)過(guò)路徑的流量，可以在流量一定的前提下，達(dá)到所用的費(fèi)用最小的要求。如n輛卡車要運(yùn)送物品，從A地到B地。由于每條路段都有不同的路費(fèi)要繳納，每條路能容納的車的數(shù)量有限制，最小費(fèi)用流問(wèn)題指如何分配卡車的出發(fā)路徑可以達(dá)到費(fèi)用最低，物品又能全部送到。

因此，本文基于最小費(fèi)用流的方法，設(shè)計(jì)使用與供應(yīng)鏈網(wǎng)絡(luò)運(yùn)輸問(wèn)題的最小費(fèi)用流算法，用以處理供應(yīng)急物資運(yùn)輸網(wǎng)絡(luò)模型，并利用具體例子來(lái)驗(yàn)證該算法的有效性。

2 應(yīng)急網(wǎng)絡(luò)運(yùn)輸問(wèn)題描述

應(yīng)急運(yùn)輸網(wǎng)絡(luò)一般有三級(jí)組成，即出救點(diǎn)、中轉(zhuǎn)中心和需求點(diǎn)。因此，中轉(zhuǎn)中心選址問(wèn)題可描述為對(duì)于i個(gè)出救點(diǎn)經(jīng)過(guò)j個(gè)的中轉(zhuǎn)中心，為k個(gè)需求點(diǎn)配送物品，使得在所選路線及路線的流量在滿足配送需求的前提下，使得總費(fèi)用最低，其運(yùn)輸網(wǎng)絡(luò)結(jié)構(gòu)如圖1所示。

圖1 運(yùn)輸問(wèn)題網(wǎng)絡(luò)結(jié)構(gòu)

在應(yīng)急網(wǎng)絡(luò)運(yùn)輸問(wèn)題中，出救點(diǎn)的個(gè)數(shù)和需求點(diǎn)的數(shù)量和位置以及需求量是固定的，物流中轉(zhuǎn)中心的地點(diǎn)也是固定的但流經(jīng)各中轉(zhuǎn)中心的流量不定，因此，該運(yùn)輸問(wèn)題的目標(biāo)是在需求節(jié)點(diǎn)需求量得到滿足的前提下使得總費(fèi)用最小。

為了方便說(shuō)明問(wèn)題并且提高本文算法的通用性，對(duì)運(yùn)輸問(wèn)題進(jìn)行如下假設(shè)：

(1)從出救點(diǎn)到中轉(zhuǎn)中心、從中轉(zhuǎn)中心到需求點(diǎn)之間的運(yùn)輸距離是已知的；

(2)各個(gè)需求點(diǎn)的需求量已知或可預(yù)測(cè)；

(3)物流經(jīng)過(guò)中轉(zhuǎn)節(jié)點(diǎn)的相關(guān)成本已知；

(4)只考慮一種物資的運(yùn)輸，運(yùn)輸費(fèi)用只和運(yùn)輸量和距離有關(guān)且已知；

(5)一個(gè)中轉(zhuǎn)中心可由多個(gè)出救點(diǎn)配送物資，一個(gè)需求點(diǎn)的需求也可由多個(gè)中轉(zhuǎn)中心提供。

(6)各線路的容量已知。

基于上述的假設(shè)條件，接下來(lái)進(jìn)行模型涉及的參數(shù)和變量進(jìn)行定義：

i表示出救點(diǎn)，I為出救點(diǎn)的集合，則i∈I。

j表示中轉(zhuǎn)中心，J為中轉(zhuǎn)中心的集合，則j∈J。

k表示需求點(diǎn)，K為需求點(diǎn)的集合，則k∈K。

dij表示從出救點(diǎn)i向中轉(zhuǎn)中心j的運(yùn)輸距離(單位：km)。

djk表示從中轉(zhuǎn)中心j向需求點(diǎn)k的運(yùn)輸距離(單位：km)。

Qij表示從出救點(diǎn)i向中轉(zhuǎn)中心j的實(shí)際運(yùn)輸量(單位：t)。

Qjk表示從中轉(zhuǎn)中心j向需求點(diǎn)k的實(shí)際運(yùn)輸量(單位：t)。

cij表示從出救點(diǎn)i向中轉(zhuǎn)中心j的最大運(yùn)輸量(單位：t)。

cjk表示從中轉(zhuǎn)中心j向需求點(diǎn)k的最大運(yùn)輸量(單位：t)

Pij表示從出救點(diǎn)i向中轉(zhuǎn)中心j的單位運(yùn)輸費(fèi)率(單位：Yuan/(t·km))。

Pjk表示從中轉(zhuǎn)中心j向需求點(diǎn)k的單位運(yùn)輸費(fèi)率(單位：Yuan/(t·km))。

pj表示中轉(zhuǎn)中心j的庫(kù)存費(fèi)用。

Mj為第j個(gè)中轉(zhuǎn)中心的最大容量(單位：t)。

Dk為第k個(gè)需求點(diǎn)的需求總量(單位：t)。

Ai為出救點(diǎn)i的供應(yīng)能力(單位：t)。

3 算法設(shè)計(jì)

運(yùn)輸問(wèn)題的目的是要求一個(gè)目標(biāo)函數(shù)F，使得總費(fèi)用W(F)達(dá)到最小，本文算法的模型如下：

約束條件(1)為救援物資供應(yīng)能力限制；

約束條件(2)是中轉(zhuǎn)中心的物資進(jìn)出量平衡約束，即運(yùn)往中轉(zhuǎn)中心j的物資總量，等于從中轉(zhuǎn)中心j運(yùn)出的物資總量。

約束條件(3)為中轉(zhuǎn)中心的容量限制，即從出救點(diǎn)運(yùn)往中轉(zhuǎn)中心j的運(yùn)輸總量必須小于中轉(zhuǎn)中心j的最大容量。

約束條件(4)為滿足需求約束，即從所有選中的中轉(zhuǎn)中心向需求點(diǎn)k的運(yùn)輸總量必須滿足需求點(diǎn)k的需求。

約束條件(5)和(6)為各線路的容量限制。

另外，本模型涉及的所有參量均為非負(fù)參量。

(1)

(2)

(3)

(4)

cjk≥Qjk

(5)

cij≥Qij

(6)

利用最小費(fèi)用流算法處理該模型，在算法求解過(guò)程中，保持總流量保持不變(即出救節(jié)點(diǎn)發(fā)出的物流不變)，并逐步向最優(yōu)性條件過(guò)渡，直到滿足最優(yōu)性條件，算法步驟如下：

(1)初始化，根據(jù)實(shí)際情況構(gòu)建運(yùn)輸網(wǎng)絡(luò)圖(將各中轉(zhuǎn)節(jié)點(diǎn)當(dāng)成一條有容量限制的弧)，并確定各供應(yīng)節(jié)點(diǎn)的產(chǎn)量，各中轉(zhuǎn)中心的容量及各需求節(jié)點(diǎn)的需求量，并確定各路線的距離及單位運(yùn)費(fèi)率；

(2)在初始網(wǎng)絡(luò)中，找到一條滿足條件的可行流；

(3)若在網(wǎng)絡(luò)中存在可調(diào)整的負(fù)代價(jià)圈，則轉(zhuǎn)入(4)，若不存在則轉(zhuǎn)入(5)；

(4)增量構(gòu)造新流(保持總流量不變)，轉(zhuǎn)至(3)；

(5)將當(dāng)前流保存為最小費(fèi)用流，輸出。

為使得算法更為迅捷，在第(4)步構(gòu)造新流過(guò)程中，取增量θ=min{容量-正向弧流量；逆向弧流量}。

圖2 算法流程圖

4 算例分析

圖3為一個(gè)簡(jiǎn)易的公路網(wǎng)絡(luò)，為簡(jiǎn)便起見(jiàn)，下例只有一個(gè)出救節(jié)點(diǎn)S和一個(gè)需求節(jié)點(diǎn)T，并有兩個(gè)中轉(zhuǎn)節(jié)點(diǎn)(中轉(zhuǎn)點(diǎn)1和中轉(zhuǎn)點(diǎn)2，且1可以向2輸送物資)，且將各路線的距離轉(zhuǎn)化為單位物流費(fèi)用表示。每條弧上的數(shù)據(jù)從左至右分別為單位物流費(fèi)用、當(dāng)前流量、容量。出救節(jié)點(diǎn)需要將8噸的物資經(jīng)過(guò)兩個(gè)中轉(zhuǎn)節(jié)點(diǎn)送到需求節(jié)點(diǎn)。

圖3 公路網(wǎng)路線圖

構(gòu)建應(yīng)急物資運(yùn)輸網(wǎng)絡(luò)時(shí)將中轉(zhuǎn)節(jié)點(diǎn)當(dāng)成一條有流量限制的弧，該弧費(fèi)用為該中轉(zhuǎn)節(jié)點(diǎn)的庫(kù)存費(fèi)用，給各節(jié)點(diǎn)編號(hào)，并給出一個(gè)初始可行流：

圖4 初始可行流圖

該初始可行流的運(yùn)輸總費(fèi)用W(F)=20+9+4+3+5+18+15=74，尋找到的第一個(gè)可調(diào)整負(fù)代價(jià)圈是圈①④②，對(duì)該圈增加一個(gè)增量θ=2，得到新流如圖5。

圖5 第一次調(diào)整結(jié)果圖

該調(diào)整后的圖的運(yùn)輸總費(fèi)用W(F)=12+15+3+5+18+15=68，尋找到的第二個(gè)可調(diào)整負(fù)代價(jià)圈是圈③⑤⑥，對(duì)該圈增加一個(gè)增增量θ=2，得到新流如圖6。

圖6 第二次調(diào)整結(jié)果圖

該調(diào)整后的圖的運(yùn)輸總費(fèi)用W(F)=12+15+3+5+4+21+6=66，此時(shí)圖中不存在可調(diào)整的負(fù)代價(jià)圈，調(diào)整結(jié)束，得到最小費(fèi)用流。相比與初始可行流，

費(fèi)用由74減少到了68，調(diào)整結(jié)果較好。

5 結(jié)論

應(yīng)急物資運(yùn)輸問(wèn)題的核心是運(yùn)輸成本最小化，即尋找最佳的運(yùn)輸方案使得總費(fèi)用最低，不同的線路流量設(shè)計(jì)將導(dǎo)致不同的費(fèi)用，這個(gè)過(guò)程可以抽象為一個(gè)有流量限制的最小費(fèi)用流問(wèn)題。本文首先將應(yīng)急物資運(yùn)輸網(wǎng)絡(luò)問(wèn)題模型化，使其成為一個(gè)總量一定的最小費(fèi)用流問(wèn)題；其次，對(duì)已有的最小費(fèi)用流算法進(jìn)行相應(yīng)調(diào)整，使其適用于應(yīng)急物資運(yùn)輸網(wǎng)絡(luò)問(wèn)題；最后，利用具體算例，進(jìn)行實(shí)例分析。利用最小費(fèi)用流算法解決應(yīng)急物資運(yùn)輸網(wǎng)絡(luò)問(wèn)題，能夠減少運(yùn)輸成本，提高社會(huì)效益。本文考慮的情況較為簡(jiǎn)單，后繼研究可以對(duì)應(yīng)急物資運(yùn)輸網(wǎng)絡(luò)問(wèn)題的各項(xiàng)費(fèi)用進(jìn)行更精細(xì)的劃分，使得算法更符合實(shí)際情況。

[1] KemballCook，Stephenson R.LessoninlogisticsfromSomalia[J].Disaster，1984，(8)：57-66.

[2] RathiA.K.，ChurchR.L.，SolankiR.S..Allocating resources to support a multicommodity flow With time windows[J].Logisties and Trans Portation Review，1992，28(2)：167-188.

[3] HaghaniA.，OhS.-C.Formulation and solution of a multicommodity，multimodal network Flow model for disaster relief operations[J].Transportation Research Part A，1996，30(3)：231-250.

[4] 歐忠文，王會(huì)云，姜大立等.應(yīng)急物流[J].重慶大學(xué)學(xué)報(bào)，2004，27(3)：164-166.

[5] 孟參等.應(yīng)急物流系統(tǒng)運(yùn)作流程分析及其管理[J].物流技術(shù)，2006，(9)：15-17.

[6] 謝政，湯澤瀅.帶模糊約束的最小費(fèi)用流問(wèn)題[J].模糊系統(tǒng)與數(shù)學(xué)，1999，13(2)：940-941.

[7] 寇瑋華，董雪，呂林劍.交通運(yùn)輸網(wǎng)絡(luò)中兩個(gè)結(jié)點(diǎn)間有流量約束的最小費(fèi)用最大流算法[J].蘭州交通大學(xué)學(xué)報(bào)，2009，28(6)：104-109.