網(wǎng)絡(luò)流理論在地震救災(zāi)物資運(yùn)輸模型中的應(yīng)用

邱 攀， 胡圣能 （華北水利水電學(xué)院，河南 鄭州 450011）

地震是對(duì)人類生存安全危害最大的自然災(zāi)害之一。2007年全世界有災(zāi)情的地震共計(jì)13次，經(jīng)濟(jì)損失總數(shù)達(dá)200億美元。2008年中國(guó)汶川8.0級(jí)大地震是新中國(guó)成立以來(lái)破壞性最強(qiáng)、涉及范圍最廣、救災(zāi)難度最大的一次地震，重災(zāi)區(qū)面積達(dá)10萬(wàn)平方公里；地震直接經(jīng)濟(jì)損失超過(guò)1萬(wàn)億元人民幣。地震的一大特點(diǎn)就是突發(fā)性強(qiáng)，以目前的預(yù)報(bào)水平，還不能準(zhǔn)確地知道在什么時(shí)候、什么地方、發(fā)生多大地震，這就要求必須提高地震應(yīng)急反應(yīng)能力。

所謂應(yīng)急物流，就是指以提供突發(fā)性自然災(zāi)害、突發(fā)性公共衛(wèi)生事件等突發(fā)性事件所需應(yīng)急物資為目的，以追求時(shí)間效益最大化和災(zāi)害損失最小化為目標(biāo)的特種物流活動(dòng)[1]。我國(guó)是世界上地震活動(dòng)最強(qiáng)烈和地震災(zāi)害最嚴(yán)重的國(guó)家之一，歷次地震災(zāi)害都造成了建筑損毀、人員死傷、交通中斷等巨大損失。在災(zāi)害發(fā)生時(shí)，盡管各級(jí)政府均積極成立救災(zāi)指揮中心以及救災(zāi)專門(mén)小組，但面對(duì)復(fù)雜的道路交通情況和各地救災(zāi)物資需求量的不同，如果不統(tǒng)籌安排會(huì)造成運(yùn)輸費(fèi)用增加，局部救災(zāi)物資短缺或過(guò)剩，會(huì)影響搶救生命財(cái)產(chǎn)的進(jìn)度和社會(huì)穩(wěn)定。這就給決策者提出一個(gè)問(wèn)題：怎樣在滿足各受災(zāi)地區(qū)物資最小需求的前提下，以最低的運(yùn)輸費(fèi)用將盡可能多的救災(zāi)物資運(yùn)送到各災(zāi)區(qū)。本文在對(duì)最小費(fèi)用最大流理論研究的基礎(chǔ)上，建立地震救災(zāi)物資運(yùn)輸數(shù)學(xué)模型，得出在滿足各災(zāi)區(qū)救災(zāi)物資最小需求的前提下，以最低的運(yùn)輸費(fèi)用將救災(zāi)物資運(yùn)送到各災(zāi)區(qū)的運(yùn)輸方案。

1 最小費(fèi)用最大流理論[2－4]

定義1整個(gè)應(yīng)急物流網(wǎng)絡(luò)可以分解為若干條自起點(diǎn)vs到終點(diǎn)vt的鏈，每條鏈由若干個(gè)弧組成，若鏈上弧的方向與鏈的方向相同 （起點(diǎn)到終點(diǎn)），則稱這個(gè)弧為鏈的正向弧，記為u+；否則稱為逆向弧，記為u－。

定義2一個(gè)可行流，u是從起點(diǎn)vs到終點(diǎn)vt的一條鏈，若u滿足下列條件，則稱之為一條增廣鏈。

（1） 在弧 （ vi, vj）∈u+上，0≤qi,j＜ci,j， 即u+中每一條弧是非飽和弧； （2） 在弧 （vi, vj）∈u－上，即 u－中每一條弧是非飽和弧。

1.1 最小費(fèi)用最大流問(wèn)題的描述。 在網(wǎng)絡(luò)D=（V,A,C ）中， 對(duì)應(yīng)每一條弧 （vi, vj）∈A， 除了已給弧 （vi,vj）的容量ci,j（ci,j＞0 ）外， 還給了一個(gè)單位流量通過(guò)弧 （vi,vj）的費(fèi)用fi,j（fi,j＞0D的一條可行流，則其總費(fèi)用為則求使最小且流量大的問(wèn)題稱為最小費(fèi)用最大流問(wèn)題。

1.2 最小費(fèi)用最大流理論的算法思想。若q是流量為v（q ）的可行流中費(fèi)用最小者，而u是關(guān)于q的所有增廣鏈中費(fèi)用最小的增廣鏈，那么沿著u以ε去調(diào)整q，得到的可行流q'就是流量為v（ q'）（v（ q'）=v（q）+ε ）的所有可行流中的最小費(fèi)用流。這樣，當(dāng)q'為最大流時(shí)，它也就是我們所要求的最小費(fèi)用最大流了。根據(jù)這個(gè)結(jié)論，如果已知q是流值為v（q ）的最小費(fèi)用流，則關(guān)鍵是要求出關(guān)于q的最小費(fèi)用的增廣鏈。為此，需要在原網(wǎng)絡(luò)D的基礎(chǔ)上構(gòu)造一個(gè)新的賦權(quán)有向圖h（q ），使其頂點(diǎn)與D的頂點(diǎn)相同， 且將D中每條弧 （vi, vj）均變成兩個(gè)方向相反的弧 （vi, vj）和（vj, vi）。 新圖h（q ）中各弧的權(quán)值與q中弧的權(quán)值有密切關(guān)系，圖h（q ）中各弧的權(quán)值定義為：

由增廣鏈費(fèi)用的概念及圖h（q ）中權(quán)的定義可知，在網(wǎng)絡(luò)D中尋求關(guān)于可行最小費(fèi)用增廣鏈，等價(jià)于在圖h（q）中尋求從源點(diǎn)到匯點(diǎn)的最短路。

2 數(shù)學(xué)模型

2.1 救災(zāi)物資模型建立。地震救災(zāi)物資運(yùn)輸要求在滿足各災(zāi)區(qū)救災(zāi)物資需求的前提下，以最低的運(yùn)輸費(fèi)用將盡可能多的救災(zāi)物資從各救災(zāi)物資收集點(diǎn)運(yùn)送到各災(zāi)區(qū)，這要求考慮3個(gè)問(wèn)題： （1）滿足各災(zāi)區(qū)的最低物資需求； （2）在滿足最低物資需求的前提下，將盡可能多的物資從各救災(zāi)物資收集點(diǎn)運(yùn)送到災(zāi)區(qū)； （3）總運(yùn)輸費(fèi)用最小。為了更好地處理這3個(gè)問(wèn)題，我們定義兩個(gè)常量fij和qij。fij為運(yùn)送單位救災(zāi)物資從第i救災(zāi)物資收集點(diǎn)到第j災(zāi)區(qū)所需費(fèi)用，qij為從第i救災(zāi)物資收集點(diǎn)到第j災(zāi)區(qū)運(yùn)送救災(zāi)物資的數(shù)量。這樣以總運(yùn)輸費(fèi)用最小和救災(zāi)物資運(yùn)輸量最大為目標(biāo)函數(shù)，以各救災(zāi)物資收集點(diǎn)的物資儲(chǔ)備量、道路運(yùn)輸能力、各災(zāi)區(qū)所需要的最小物資量為約束條件構(gòu)造模型如下：

式中pi為第i個(gè)倉(cāng)庫(kù)的物資儲(chǔ)備數(shù)量，wi為第j個(gè)災(zāi)區(qū)至少所需要的物資數(shù)量，cij為從第i個(gè)倉(cāng)庫(kù)到第j個(gè)災(zāi)區(qū)道路運(yùn)輸能力，s表示起點(diǎn)，t表示終點(diǎn)。第1個(gè)約束條件表示各節(jié)點(diǎn)救災(zāi)物資流量守恒；第2個(gè)約束條件表示從第i個(gè)倉(cāng)庫(kù)到第j個(gè)災(zāi)區(qū)救災(zāi)物資運(yùn)輸量必須在運(yùn)輸能力范圍內(nèi)。第3個(gè)約束條件表示從第i個(gè)倉(cāng)庫(kù)運(yùn)走的所有物資數(shù)量必須小于第i個(gè)倉(cāng)庫(kù)的物資儲(chǔ)備量；第4個(gè)約束條件表示運(yùn)送到第j個(gè)災(zāi)區(qū)的所有物資數(shù)量必須不小于第j個(gè)災(zāi)區(qū)最少需求量。

2.2 模型求解。最小費(fèi)用最大流理論的求解過(guò)程是對(duì)單一源點(diǎn)到單一匯點(diǎn)進(jìn)行的，當(dāng)救災(zāi)物資運(yùn)輸問(wèn)題涉及到多個(gè)儲(chǔ)存物資的倉(cāng)庫(kù) （源點(diǎn)）和多個(gè)需求物資的倉(cāng)庫(kù) （匯點(diǎn)）時(shí)就需要引進(jìn)s點(diǎn)作為單源，引進(jìn)t點(diǎn)作為單匯。

定義1規(guī)定從s點(diǎn)到第i個(gè)倉(cāng)庫(kù)的道路運(yùn)輸能力為i個(gè)倉(cāng)庫(kù)的物資儲(chǔ)備量，從s點(diǎn)運(yùn)送到第i個(gè)倉(cāng)庫(kù)的單位物資運(yùn)輸費(fèi)用為0；

定義2規(guī)定從第j個(gè)災(zāi)區(qū)到t點(diǎn)的道路運(yùn)輸能力為+∞，從第j個(gè)災(zāi)區(qū)運(yùn)送到t點(diǎn)的單位物資運(yùn)輸費(fèi)用為0。

這樣一來(lái)，運(yùn)輸?shù)目傎M(fèi)用不會(huì)變，也可以應(yīng)用最小費(fèi)用最大流算法對(duì)模型進(jìn)行求解。求解步驟如下:（1）確定初始可行流它是運(yùn)輸量為0的最小費(fèi)用流； （2）經(jīng)k次調(diào)整得到的最小費(fèi)用流，構(gòu)造賦權(quán)有向圖（3） 在賦權(quán)有向圖尋求從源點(diǎn)vs到匯點(diǎn)vt的最小費(fèi)用路 （調(diào)用Dijkstra算法），若不存在最小費(fèi)用路，是最小費(fèi)用最大運(yùn)量流，計(jì)算終止；若存在最小費(fèi)用路，則此最小費(fèi)用路即為原網(wǎng)絡(luò)D中相應(yīng)的增廣鏈u，轉(zhuǎn)入下一步； （4）在增廣鏈μ上行調(diào)整，調(diào)整量為：（5）得到新的可行流使流值增大，令k=k+1，返回到第 （2）步驟。

3 結(jié)束語(yǔ)

利用最小費(fèi)用最大流理論時(shí)應(yīng)注意流的可行性和經(jīng)濟(jì)性。實(shí)際網(wǎng)絡(luò)中的流必須是可行流，其流量不可以超過(guò)最大流量，費(fèi)用不會(huì)低于最小費(fèi)用時(shí)的費(fèi)用。最小費(fèi)用最大流理論可以求解出任意的對(duì)應(yīng)于某個(gè)最低運(yùn)輸量的運(yùn)輸方案，即只要給定災(zāi)區(qū)的最低需求量，就可以根據(jù)最小費(fèi)用最大流理論求解出在這個(gè)最低運(yùn)輸量限制下的運(yùn)輸方案，實(shí)際中可以根據(jù)災(zāi)情的變化，隨時(shí)根據(jù)災(zāi)區(qū)的實(shí)際需求量，改變運(yùn)輸方案。

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

[2] 李德，錢頌迪.運(yùn)籌學(xué)[M].北京：清華大學(xué)出版社，1982.

[3] 劉家壯，徐源.網(wǎng)絡(luò)最大化[M].北京：高等教育出版社，1991.

[4] 郭耀煌,等.運(yùn)籌學(xué)原理與方法[M].成都：西南交通大學(xué)出版社，2000.