自然災(zāi)害下的緊急物流計(jì)劃

1、自然災(zāi)害下的緊急物流計(jì)劃Contents1.介紹 2. 數(shù)學(xué)模型提出3. 實(shí)例檢驗(yàn)4. 總結(jié)AuthorsLINET ZDAMAR Nanyang Technological University, School of Mechanical and Production EngineeringEDIZ EKINCI Captain, Turkish Armed Forces, TurkeyBESTE KKYAZICI Yeditepe University, Department of Systems Engineering, TurkeyBackground introduction 199

2、9年土耳其的兩次地震年土耳其的兩次地震 自然災(zāi)害物流決策支持系統(tǒng)自然災(zāi)害物流決策支持系統(tǒng) 物資運(yùn)輸計(jì)劃與交通工具時(shí)間表物資運(yùn)輸計(jì)劃與交通工具時(shí)間表 整數(shù)多階段多物資網(wǎng)絡(luò)流整數(shù)多階段多物資網(wǎng)絡(luò)流 在大規(guī)模自然災(zāi)害下（拉格朗日松弛法）在大規(guī)模自然災(zāi)害下（拉格朗日松弛法）Research problem1.在緊急物流中，供給在當(dāng)前時(shí)期和將來指定的時(shí)期在緊急物流中，供給在當(dāng)前時(shí)期和將來指定的時(shí)期里是有限的，需求在當(dāng)前時(shí)期是已知的在將來的時(shí)里是有限的，需求在當(dāng)前時(shí)期是已知的在將來的時(shí)期里可以預(yù)測(cè)期里可以預(yù)測(cè)2.收到物資的節(jié)點(diǎn)可以被看作一個(gè)形式上的倉(cāng)庫收到物資的節(jié)點(diǎn)可以被看作一個(gè)形式上的倉(cāng)庫3.運(yùn)輸工具停

3、在節(jié)點(diǎn)處等待物流協(xié)調(diào)中心的下一個(gè)命令運(yùn)輸工具停在節(jié)點(diǎn)處等待物流協(xié)調(diào)中心的下一個(gè)命令4.文獻(xiàn)綜述文獻(xiàn)綜述(VRP)contribution 整合了多物資網(wǎng)絡(luò)流問題與運(yùn)輸路線問題整合了多物資網(wǎng)絡(luò)流問題與運(yùn)輸路線問題 模型分解成兩個(gè)多物資網(wǎng)絡(luò)流問題模型分解成兩個(gè)多物資網(wǎng)絡(luò)流問題 子模型運(yùn)用拉格朗日松弛法子模型運(yùn)用拉格朗日松弛法 算法經(jīng)過小事件測(cè)試和實(shí)際規(guī)模地震的檢驗(yàn)算法經(jīng)過小事件測(cè)試和實(shí)際規(guī)模地震的檢驗(yàn)數(shù)學(xué)模型數(shù)學(xué)模型運(yùn)輸方式（運(yùn)輸方式（transportation mode）需要注意：）需要注意：一對(duì)節(jié)點(diǎn)之間可能不止一條連線一對(duì)節(jié)點(diǎn)之間可能不止一條連線(弧弧),每條連線代表一種運(yùn)輸方式每條連線代表

4、一種運(yùn)輸方式.運(yùn)輸時(shí)間取決于運(yùn)輸方式運(yùn)輸時(shí)間取決于運(yùn)輸方式.1. 不失一般性不失一般性,忽略運(yùn)輸方式之間的轉(zhuǎn)換時(shí)間忽略運(yùn)輸方式之間的轉(zhuǎn)換時(shí)間.如將火車的貨物卸如將火車的貨物卸下下,分裝到貨車上分裝到貨車上,即從鐵路運(yùn)輸轉(zhuǎn)換到地面運(yùn)輸即從鐵路運(yùn)輸轉(zhuǎn)換到地面運(yùn)輸.(ground transportation) 集合集合T : length of the planning horizon,(計(jì)劃期長(zhǎng)度計(jì)劃期長(zhǎng)度) C : set of all nodes,(結(jié)點(diǎn)集結(jié)點(diǎn)集)M: set of transportation modes, (運(yùn)輸方式集運(yùn)輸方式集)CD: set of demand nod

5、es including transshipment nodes, (需求結(jié)點(diǎn)集需求結(jié)點(diǎn)集) CS: set of supply nodes, (供給結(jié)點(diǎn)集供給結(jié)點(diǎn)集) do: dummy node defined for expressing the availability of vehicles, (虛結(jié)點(diǎn)虛結(jié)點(diǎn)) RO: set of nodes excluding dummy node; RO = Cdo,(虛結(jié)點(diǎn)的補(bǔ)集虛結(jié)點(diǎn)的補(bǔ)集) A: set of commodities, (商品集商品集)Vm: set of vehicle types defined for each tr

6、ansportation mode m, (運(yùn)輸方式運(yùn)輸方式m的車型集的車型集) topm: time required to traverse arc (o, p) in transportation mode m; topm is zero for non-existent links,(o p的往返時(shí)間的往返時(shí)間) daot : amount of commodity of type a demanded or supplied at node o at time t ,positive for supply and negative for demand,(t時(shí)段時(shí)段 o結(jié)點(diǎn)結(jié)點(diǎn)a商品

7、的需求商品的需求量量(-)或供給量或供給量(+) avovmt : number of vehicles of type v transportation mode m at node o added to thefleet at time t ,( t時(shí)段時(shí)段o點(diǎn)點(diǎn)m運(yùn)輸方式的運(yùn)輸方式的v型型加入到車隊(duì)的數(shù)量型型加入到車隊(duì)的數(shù)量)wa: unit weight of commodity a,(單位單位 a商品的數(shù)量商品的數(shù)量)capvm: load capacity of vehicle type v transportation mode m,（m運(yùn)輸方式的運(yùn)輸方式的v型車的載重）型車的載

8、重）K: a big number.（一個(gè)大數(shù)）（一個(gè)大數(shù)） 參數(shù)參數(shù)決策變量決策變量 Zaopmt : amount of commodity type a traversing arc (o, p) at time t using transportationmode m,（t時(shí)段以時(shí)段以m方式從方式從o運(yùn)送到運(yùn)送到p的商品的商品a的數(shù)量）的數(shù)量）devaot : amount of unsatisfied demand of commodity type a at node o at time t ,（t時(shí)段結(jié)點(diǎn)時(shí)段結(jié)點(diǎn)o未滿足的商品未滿足的商品a 的需求量）的需求量）Yopvmt :

9、integer number of vehicles of type v transportation mode m traversing thearc (o, p) at time t ,（t時(shí)段往返于時(shí)段往返于o-p之間的之間的m運(yùn)輸方式運(yùn)輸方式v型車的數(shù)量）型車的數(shù)量）surovmt : number of vehicles of type v transportation mode m that wait at node o attime t .（t時(shí)段在時(shí)段在o點(diǎn)等待的點(diǎn)等待的m運(yùn)輸方式運(yùn)輸方式v型車的數(shù)量）型車的數(shù)量） 模型模型 模型的第一部分（約束，）是一個(gè)線性多商品網(wǎng)絡(luò)流問題。

10、模型的第一部分（約束，）是一個(gè)線性多商品網(wǎng)絡(luò)流問題。 第二部分（約束，第二部分（約束，5 5，6 6，）是一個(gè)整數(shù)多商品網(wǎng)絡(luò)流問，）是一個(gè)整數(shù)多商品網(wǎng)絡(luò)流問題但約束右邊也含有變量，所以比一般的整數(shù)多商品網(wǎng)絡(luò)流題但約束右邊也含有變量，所以比一般的整數(shù)多商品網(wǎng)絡(luò)流問題復(fù)雜。問題復(fù)雜。 第一部分的商品流驅(qū)動(dòng)著第二部分的車輛流。第一部分的商品流驅(qū)動(dòng)著第二部分的車輛流。 模型解釋重新作計(jì)劃重新作計(jì)劃 （迭代運(yùn)算時(shí)賦值問題）（迭代運(yùn)算時(shí)賦值問題）實(shí)例分析實(shí)例分析網(wǎng)絡(luò)流：網(wǎng)絡(luò)流：車輛流：車輛流：n公路運(yùn)輸n鐵路運(yùn)輸n海上運(yùn)輸n空中運(yùn)輸物資流物資流n醫(yī)療用品n食品注意：為了簡(jiǎn)單直觀，并注意：為了簡(jiǎn)單直觀，并沒

11、有在模型中標(biāo)注虛擬節(jié)沒有在模型中標(biāo)注虛擬節(jié)1. 點(diǎn)。點(diǎn)。模型狀態(tài)描述模型狀態(tài)描述局部最優(yōu)解局部最優(yōu)解模型模型P解決方法解決方法t時(shí)段弧opm運(yùn)載能力不能滿足需求的數(shù)量 t時(shí)段弧opm運(yùn)載能力超過需求的數(shù)量 t時(shí)段弧opm不能滿足運(yùn)輸?shù)倪\(yùn)載能力的數(shù)量 算法思想算法思想第一部分的商品流驅(qū)動(dòng)著第二部分的車輛流，首先計(jì)算第一部分的商品流驅(qū)動(dòng)著第二部分的車輛流，首先計(jì)算p1,根據(jù)有根據(jù)有p1計(jì)算的最優(yōu)商品流，來計(jì)算每條弧上對(duì)車輛運(yùn)載能力的需計(jì)算的最優(yōu)商品流，來計(jì)算每條弧上對(duì)車輛運(yùn)載能力的需求求 然后計(jì)算然后計(jì)算p2，使，使p2的目標(biāo)達(dá)到最小化，這時(shí)會(huì)得到最優(yōu)的車的目標(biāo)達(dá)到最小化，這時(shí)會(huì)得到最優(yōu)的車輛流，

12、但這時(shí)車輛流不能滿足商品流對(duì)運(yùn)載能力的需求在這輛流，但這時(shí)車輛流不能滿足商品流對(duì)運(yùn)載能力的需求在這種情況下，種情況下，p2得到正的目標(biāo)函數(shù)值接下來把最優(yōu)車輛流反得到正的目標(biāo)函數(shù)值接下來把最優(yōu)車輛流反饋到饋到p1中，作為商品流能獲得的運(yùn)載能力的上限然后計(jì)算中，作為商品流能獲得的運(yùn)載能力的上限然后計(jì)算p1，進(jìn)行第二次迭代進(jìn)行第二次迭代就這樣，就這樣，p1和和p2 交替求解，彼此交換參數(shù)，直至達(dá)到一定的交替求解，彼此交換參數(shù)，直至達(dá)到一定的迭代次數(shù)，當(dāng)?shù)螖?shù)，當(dāng)p2的目標(biāo)函數(shù)值為，拉格朗日松弛法收斂于一的目標(biāo)函數(shù)值為，拉格朗日松弛法收斂于一點(diǎn)，這意味著得到了可行解最終點(diǎn)，這意味著得到了可行解最終p

13、1目標(biāo)函數(shù)值是原模型目標(biāo)函目標(biāo)函數(shù)值是原模型目標(biāo)函數(shù)值的一個(gè)上限（數(shù)值的一個(gè)上限（B） 算法步驟算法步驟子模型的分析子模型的分析模型模型P1變化的多物資最小成本流問題變化的多物資最小成本流問題算法算法n改進(jìn)的最短路徑法 （Orlin 1993）nDecomposition based approaches and column generation technique （Aewrbuch and Leighton; Jones et al.;Frangioni）模型模型P2整數(shù)型多物資網(wǎng)絡(luò)流問題整數(shù)型多物資網(wǎng)絡(luò)流問題算法算法n啟發(fā)式算法 （Barnhart&Sheffi;1993 Ag

14、garwal et al.1995)n窮舉法 （Barnhart et al.1996)n割平面法 （Brunetta et al. 1995)注意：在解決大型網(wǎng)絡(luò)問題時(shí)，算法的高效率是非常重要的。注意：在解決大型網(wǎng)絡(luò)問題時(shí)，算法的高效率是非常重要的。在一些假設(shè)條件進(jìn)行測(cè)試在一些假設(shè)條件進(jìn)行測(cè)試需求/供應(yīng)/運(yùn)輸?shù)墓?jié)點(diǎn)數(shù)在6-9之間1物品的數(shù)量和交通工具的類型都是受限制的2每個(gè)點(diǎn)上需求/供應(yīng)的量在0,100間平均分布3在網(wǎng)絡(luò)拓?fù)渲?，需?供應(yīng)的分布是任意的45假設(shè)條件假設(shè)條件從上面的表格，可以看出以下幾點(diǎn)結(jié)論：從上面的表格，可以看出以下幾點(diǎn)結(jié)論：在所有問題中，枚舉法需要的迭代次數(shù)非常多 除了12

15、號(hào)和16號(hào)問題上，偏差稍大一些，總體平均而言， AlgLR與最優(yōu)解決方案相比，它的偏差平均1.96%。 。當(dāng)計(jì)劃系統(tǒng)需要經(jīng)常更改或要提供一個(gè)快速答案時(shí)，應(yīng)用枚舉法就相當(dāng)困難（如表中的問題17和18）運(yùn)輸能力緊缺使得算法偏差偏大拓?fù)浣Y(jié)構(gòu)的復(fù)雜程度也影響算法的偏差地震區(qū)域及死傷人數(shù)物品種類/需求/供應(yīng)交通工具的類型和負(fù)載能力模型在現(xiàn)實(shí)緊急情況下的應(yīng)用：模型在現(xiàn)實(shí)緊急情況下的應(yīng)用：1999年發(fā)生在土耳其的一次地震年發(fā)生在土耳其的一次地震震區(qū)死傷人數(shù)震區(qū)死傷人數(shù)物品種類物品種類/需求需求/供應(yīng)供應(yīng)交通工具的類型和負(fù)載能力交通工具的類型和負(fù)載能力拓?fù)浣Y(jié)構(gòu)拓?fù)浣Y(jié)構(gòu)1234567891011進(jìn)取啟發(fā)式算法進(jìn)取啟發(fā)式算法原理：與原理：與Orlin (1993)提出的修改后的最短路徑算法相同提出的修改后的最短路徑算法相同 建立于一些假設(shè)條件（其中包括運(yùn)輸能力充足）建立于一些假設(shè)條件（其中包括運(yùn)輸能力充足）綜合比較綜合