李廣興 何 珊

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

1 引言

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

1.1 應(yīng)急物資運輸問題

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

1.2 最小費用流的引入

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

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

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

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

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

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

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

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

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

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

為了方便說明問題并且提高本文算法的通用性，對運輸問題進行如下假設(shè)：

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

(2)各個需求點的需求量已知或可預測；

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

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

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

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

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

i表示出救點，I為出救點的集合，則i∈I。

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

k表示需求點，K為需求點的集合，則k∈K。

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

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

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

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

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

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

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

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

pj表示中轉(zhuǎn)中心j的庫存費用。

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

Dk為第k個需求點的需求總量(單位：t)。

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

3 算法設(shè)計

運輸問題的目的是要求一個目標函數(shù)F，使得總費用W(F)達到最小，本文算法的模型如下：

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

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

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

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

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

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

(1)

(2)

(3)

(4)

cjk≥Qjk

(5)

cij≥Qij

(6)

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

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

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

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

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

(5)將當前流保存為最小費用流，輸出。

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

圖2 算法流程圖

4 算例分析

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

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

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

圖4 初始可行流圖

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

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

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

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

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

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

5 結(jié)論

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

[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] 歐忠文，王會云，姜大立等.應(yīng)急物流[J].重慶大學學報，2004，27(3)：164-166.

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

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

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