陳志新,陳方玉,盧成林,劉 鑫
(北京物資學(xué)院 物流學(xué)院,北京 101149)
應(yīng)急物流路徑選擇模型研究
陳志新,陳方玉,盧成林,劉鑫
(北京物資學(xué)院物流學(xué)院,北京101149)
結(jié)合自然災(zāi)害的特點(diǎn),建立了一個(gè)二層級(jí)的多目標(biāo)應(yīng)急物流路徑選擇模型,模型中的目標(biāo)包括:時(shí)效性、安全性及經(jīng)濟(jì)性,并且根據(jù)自然災(zāi)害對(duì)于時(shí)間的要求,加了硬時(shí)間窗的約束。時(shí)效性和安全性的考慮使得模型的建立更加符合實(shí)際。用遺傳算法求解本模型,算例驗(yàn)證了模型的有效性和可行性。
突發(fā)性自然災(zāi)害;應(yīng)急物流;車輛路徑;遺傳算法
自然災(zāi)害給應(yīng)急管理提出了很高的要求,如何將應(yīng)急保障物資以最快的方式送達(dá)受災(zāi)地點(diǎn),是災(zāi)害應(yīng)急管理需要考慮的重要問(wèn)題。確保救援物資順利運(yùn)輸?shù)年P(guān)鍵是車輛如何調(diào)度,然而運(yùn)輸車輛調(diào)度的核心是如何選擇合理的運(yùn)輸路徑。劉長(zhǎng)石、寇綱(2014)以地震災(zāi)害為研究背景,提出在災(zāi)后時(shí)間、空間和資源都有限的情況下如何將物資以最快最有效的方式運(yùn)送到受災(zāi)地點(diǎn)是一個(gè)值得考慮的問(wèn)題,提出路徑的選擇是一個(gè)重要的研究?jī)?nèi)容[1]。
近些年來(lái),隨著物流產(chǎn)業(yè)的逐步發(fā)展,對(duì)于車輛路徑選擇問(wèn)題研究也越來(lái)越多。Jabali O等人(2015)研究了帶硬時(shí)間窗的物流路徑選擇問(wèn)題并給出在時(shí)間約束下怎樣使得時(shí)間最短成本最低[2]。王榮、檀小璐(2014)針對(duì)于物流配送領(lǐng)域的車輛路徑選擇問(wèn)題,以成本最小化為目標(biāo),基于對(duì)實(shí)際道路的考察,建立模型并用遺傳算法進(jìn)行求解[3]。
應(yīng)急物流區(qū)別于一般物流的一個(gè)顯著特征就是時(shí)間的緊迫性、信息的不確定性和發(fā)展變化性,對(duì)此國(guó)內(nèi)外學(xué)者也做了很多的研究。Qin Xu、Zhujun Ma等人(2012)基于地震災(zāi)害的發(fā)生為研究背景,考慮到災(zāi)害發(fā)生之后時(shí)間和資源的有限性,將死亡人數(shù)最小作為該問(wèn)題的目標(biāo),建立了車輛的最優(yōu)路線的選擇模型[4]。Gu H(2014)考慮到突發(fā)事件發(fā)生之后對(duì)于應(yīng)急時(shí)間的要求,在災(zāi)害發(fā)生之后車輛、物資都有限的情況下,建立了以時(shí)間最小化為目標(biāo)的運(yùn)輸路徑選擇模型,并且利用免疫算法來(lái)對(duì)模型進(jìn)行求解[5]。高鴻鶴、唐辰(2014)面對(duì)近年來(lái)地震災(zāi)害的頻繁發(fā)生,基于救援的緊迫性,建立了以配送時(shí)間最短為目標(biāo)的路徑選擇模型,并用Lingo編程軟件對(duì)模型進(jìn)行求解,給出了具體的案例分析[6]。成桂玲(2014)運(yùn)用層次分析法分析了影響路徑選擇的因素,在以服務(wù)、時(shí)間和成本為二級(jí)指標(biāo)的前提下建立三級(jí)指標(biāo),并最終算出各二級(jí)指標(biāo)的權(quán)重[7]。
現(xiàn)有文獻(xiàn)以多出救點(diǎn)、多受災(zāi)點(diǎn)、交通限制、時(shí)間最短、多種物資等為立足點(diǎn),鮮見(jiàn)考慮安全性。研究救助中心對(duì)受災(zāi)點(diǎn)的物資運(yùn)輸,屬于一層級(jí)的道路運(yùn)輸問(wèn)題,對(duì)于二層級(jí)的路徑選擇很少研究。本文建立了一個(gè)考慮安全性的二層級(jí)的多目標(biāo)應(yīng)急物流路徑選擇模型,給自然災(zāi)害應(yīng)急物流路徑選擇提供一定的借鑒和參考。
2.1問(wèn)題描述
在此設(shè)應(yīng)急配送中心、救助中心和受災(zāi)點(diǎn)之間的二層級(jí)配送路徑選擇的模型如圖1所示。
圖1 二層級(jí)應(yīng)急運(yùn)輸路徑示意圖
當(dāng)自然災(zāi)害發(fā)生以后,應(yīng)急配送中心需要根據(jù)受災(zāi)嚴(yán)重程度和影響范圍以及各受災(zāi)點(diǎn)的實(shí)際需求情況,向n個(gè)不同的受災(zāi)點(diǎn)緊急運(yùn)送應(yīng)急物資,應(yīng)急配送中心與受災(zāi)點(diǎn)之間有救助中心,已知的是救助中心的位置及成本情況,需要結(jié)合救助中心選取及運(yùn)輸路徑安排進(jìn)行優(yōu)化,達(dá)到在滿足應(yīng)急需求的同時(shí)使運(yùn)送時(shí)間短、安全性高并且成本低。
2.2模型的目標(biāo)分析和假設(shè)
突發(fā)性自然災(zāi)害發(fā)生后,綜合考慮多方面的因素,尋找一條最有效的配送路徑,具體分析如下:(1)總用時(shí)最小;(2)安全性高;(3)成本低。
本文研究二層級(jí)的應(yīng)急路徑選擇問(wèn)題,對(duì)模型的構(gòu)建提出假設(shè)條件如下:
(1)不考慮貨物混裝的情況,本文假定運(yùn)送的是應(yīng)急生命救助物資,而且不作具體分類;
(2)假定所有的車規(guī)格型號(hào)完全一樣;
(3)只考慮車輛載重的限定,忽略車容量的限定;也即假定車輛一定能夠容納它所要配送的受災(zāi)點(diǎn)的物資;
(4)假定應(yīng)急物資的儲(chǔ)備量能夠滿足所有受災(zāi)點(diǎn)的需求;
(5)假設(shè)應(yīng)急配送中心、救助中心的容量和地理位置都已知,建設(shè)中心的相關(guān)費(fèi)用也已知,并且每個(gè)受災(zāi)點(diǎn)的需求量和地理位置也已知;
(6)忽略所有裝卸時(shí)間及費(fèi)用;
(7)忽略車輛經(jīng)過(guò)節(jié)點(diǎn)的停留時(shí)間。
2.3模型參數(shù)及決策變量
(1)集合。L-應(yīng)急配送中心L={P|P=1};G-救助中心G={r|r=1,2,…,r};H-一系列需要緊急物資的受災(zāi)點(diǎn)H={i|i=1,2,…,n};S-所有救助中心和受災(zāi)點(diǎn)總和S=G∪H;V-第k輛到受災(zāi)點(diǎn)的運(yùn)輸車輛所在的路線V={k|k= 1,2,…,k}。
(2)參數(shù)。Cij為受災(zāi)點(diǎn)與受災(zāi)點(diǎn)之間運(yùn)輸車輛的平均單位距離運(yùn)輸成本,相對(duì)偏?。籆ir為受災(zāi)點(diǎn)與救助中心之間運(yùn)輸車輛的平均單位距離運(yùn)輸成本,相對(duì)偏??;Cpr為從應(yīng)急配送中心到救助中心的平均單位距離運(yùn)輸成本,相對(duì)偏大;Ck為車輛k的固定成本;Fr為建設(shè)救助中心的固定成本;qi為每個(gè)受災(zāi)點(diǎn)所需救災(zāi)物資的需求量;Qk為運(yùn)輸車輛k的容量;Qr為救助中心r的容量;dij、dir、dpr分別為受災(zāi)點(diǎn)與受災(zāi)點(diǎn)、受災(zāi)點(diǎn)與救助中心及應(yīng)急配送中心與救助中心之間的距離;Vij、Vir、Vpr分別代表受災(zāi)點(diǎn)與受災(zāi)點(diǎn)之間、受災(zāi)點(diǎn)與救助中心及應(yīng)急配送中心和救助中心之間的運(yùn)輸速度;Xrjk和Xrmk分別表示第k輛車從救助中心r向受災(zāi)地j和受災(zāi)地m運(yùn)送緊急物資;LTj為受災(zāi)地j所要求的硬時(shí)間窗的最晚到達(dá)時(shí)間,超出這個(gè)時(shí)間范圍運(yùn)輸無(wú)效;tj為車輛到達(dá)受災(zāi)點(diǎn)j的時(shí)間。
(3)決策變量
2.4模型構(gòu)建
分別以時(shí)間要素、安全要素、成本要素建立各個(gè)模型,經(jīng)過(guò)目標(biāo)函數(shù)的建立、目標(biāo)效用函數(shù)的轉(zhuǎn)換以及標(biāo)準(zhǔn)0-1變換,最終可以將以上多目標(biāo)函數(shù)轉(zhuǎn)化為單目標(biāo)函數(shù),如下:
約束條件:
式(1)為本文所建立的效用值最大函數(shù),即目標(biāo)函數(shù);約束條件(2)是對(duì)到達(dá)時(shí)間的限制,不能晚于本文所規(guī)定的最晚時(shí)間;約束條件(3)是為了保證每一個(gè)受災(zāi)點(diǎn)有且僅有一輛車為其提供緊急物資的配送;約束條件(4)為車載量約束,保證路線上行駛的車輛不會(huì)超載;約束條件(5)為一系列路線連續(xù)約束,指運(yùn)至某一受災(zāi)點(diǎn)的應(yīng)急物資由同輛車運(yùn)出;約束條件(6)保證在任意兩個(gè)救助中心之間無(wú)其他連接方式;約束條件(7)為救助中心的容量約束,救助中心的容量能夠滿足它要配送的一系列受災(zāi)點(diǎn)的需求;約束條件(8)保證每個(gè)車輛的路線最多從一個(gè)救助中心駛出;約束條件(9)、(10)保證三個(gè)目標(biāo)的權(quán)重和為1。約束條件(11)、(12)、(13)、(14)、(15)為整數(shù)約束。
3.1數(shù)據(jù)分析
為了測(cè)試論文提出的模型及其求解算法的可行性和實(shí)用性,本文選用算例驗(yàn)證。算例將包含1個(gè)應(yīng)急配送中心和2個(gè)救助中心及30個(gè)自然災(zāi)害受災(zāi)點(diǎn)。本文選取Solomon提出的Rc型題庫(kù)中的Rc208為基礎(chǔ),補(bǔ)充部分?jǐn)?shù)據(jù),產(chǎn)生測(cè)試用的算例。具體見(jiàn)表1、表2。
表1 應(yīng)急配送中心和救助中心信息表
其他數(shù)據(jù):車輛的容量限制:Q=100;
硬時(shí)間窗系數(shù):ω1=0.5,ω2=0.3,ω3=0.2;
假設(shè)vij=15,vir=20,vpr=25,并且在各區(qū)間上勻速行駛;假設(shè)一級(jí)運(yùn)輸單位距離成本為1,二級(jí)運(yùn)輸單位距離成本為0.8,受災(zāi)點(diǎn)與救助中心之間運(yùn)輸單位距離成本為0.8。
安全性系數(shù)pij、pip、ppr的數(shù)據(jù)根據(jù)實(shí)際情況設(shè)定;交叉概率:0.7;變異概率:0.05;兩個(gè)救助中心節(jié)點(diǎn)的單位固定成本:48,42。
3.2結(jié)果分析
用matlab編程,借助Sheffield(謝菲爾德)大學(xué)推出的遺傳算法工具箱進(jìn)行模型求解,得到的結(jié)果如下:
圖2表示的是所設(shè)自然災(zāi)害配送中心及各受災(zāi)點(diǎn)坐標(biāo)的地理分布圖。圖3是經(jīng)過(guò)matlab程序運(yùn)行之后產(chǎn)生的有臨時(shí)救助中心時(shí)的運(yùn)輸路線圖;圖4是經(jīng)過(guò)matlab程序運(yùn)行之后產(chǎn)生的不設(shè)臨時(shí)救助中心時(shí)的運(yùn)輸路線圖。
表2 各受災(zāi)點(diǎn)信息表
圖2 配送中心、受災(zāi)點(diǎn)分布圖
從圖2中可以看出,本文所設(shè)位置坐標(biāo)的合理性,因?yàn)楫?dāng)自然災(zāi)害發(fā)生的時(shí)候,受災(zāi)范圍比較集中,并且總的應(yīng)急配送中心往往設(shè)立在城市邊緣,因此離受災(zāi)點(diǎn)比較遠(yuǎn)。并且圖中坐標(biāo)位置(15.47,93.44)以及(22,89.55)為本文所設(shè)臨時(shí)中間節(jié)點(diǎn),通過(guò)地理分布圖,可以看出設(shè)立臨時(shí)中間節(jié)點(diǎn)的合理性。
圖3是運(yùn)用所構(gòu)建的遺傳算法求解過(guò)程而得出的當(dāng)有臨時(shí)救助中心時(shí)的緊急物資運(yùn)輸車輛路徑圖,并且根據(jù)運(yùn)行出的結(jié)果可以知道優(yōu)化后的設(shè)臨時(shí)分配送中心的救災(zāi)路線圖的總距離為84.122 6。
圖3 救助中心選擇路徑安排結(jié)果
圖4是運(yùn)用所構(gòu)建的遺傳算法求解過(guò)程而得來(lái)的當(dāng)沒(méi)有臨時(shí)救助中心時(shí)的緊急物資運(yùn)輸車輛路徑圖,并且根據(jù)運(yùn)行出的結(jié)果可以知道優(yōu)化后的不設(shè)臨時(shí)分配送中心的救災(zāi)路線圖的總距離為113.678。
圖4 不設(shè)救助中心時(shí)的路線配送圖
通過(guò)上述兩個(gè)結(jié)果比較,加入中間節(jié)點(diǎn)之后,不僅使配送路線得到優(yōu)化,并且使總的運(yùn)輸距離縮短,證明了模型的有效性,并且驗(yàn)證了之前的理論觀點(diǎn),當(dāng)自然災(zāi)害發(fā)生的時(shí)候,由于受災(zāi)范圍比較廣并且較集中,通過(guò)設(shè)立中間節(jié)點(diǎn)也即救助中心可以使得緊急運(yùn)輸發(fā)揮運(yùn)輸?shù)囊?guī)模效應(yīng),不僅能夠降低成本,縮短運(yùn)輸距離,還可以提高緊急救援的效率。
現(xiàn)有文獻(xiàn)關(guān)于一般商業(yè)性物流的路徑選擇和應(yīng)急性物流路徑選擇多以時(shí)間和成本作為目標(biāo),而對(duì)于安全性這一特殊屬性很少有研究。針對(duì)上述問(wèn)題,本文建立了一個(gè)以時(shí)效性、安全性及經(jīng)濟(jì)性為目標(biāo)的多目標(biāo)二層級(jí)應(yīng)急物流路徑選擇模型,并增加了硬時(shí)間窗的約束。通過(guò)算例對(duì)本文模型結(jié)合遺傳算法進(jìn)行了有效性和可行性驗(yàn)證。
[1]劉長(zhǎng)石,寇綱.震后應(yīng)急物流系統(tǒng)中的模糊定位—路徑問(wèn)題研究[A].中國(guó)系統(tǒng)工程學(xué)會(huì).中國(guó)系統(tǒng)工程學(xué)會(huì)第十八屆學(xué)術(shù)年會(huì)論文集—A11系統(tǒng)工程方法在公共衛(wèi)生、突發(fā)事件應(yīng)急管理方面的研究[C].2014.
[2]Jabali O,Leus R,Woensel T,Kok T.Self-imposed time windows in vehicle routing problems[J].OrSpectrum,2010,37(2)∶331-352.
[3]王榮,檀小璐.基于遺傳算法的運(yùn)輸路徑選擇問(wèn)題[J].無(wú)線互聯(lián)科技,2014,(6)∶205-206.
[4]Jinhui Dai.EarthquakeDisaster EmergencyLogisticsof Transport Route Optimization Research[J].International Conference on Logistics,Engineering,Management and Computer Science,LEMCS 2014∶114.
[5]Gu H.Applications in Emergency Logistics Vehicle Scheduling based on Immune Algorithm[J].Logistics Technology,2003,(11)∶24-27.
[6]高鴻鶴,唐辰.基于配送時(shí)間最短的應(yīng)急物流路徑規(guī)劃[J].物流工程與管理,2014,(2)∶75-78.
[7]成桂玲.層次分析法在應(yīng)急物流車輛配送路徑選擇上的應(yīng)用[J].電子世界,2014,(2)∶164.
Study on Emergency Logistics Route Selection Model
Chen Zhixin,Chen Fangyu,Lu Chenglin,Liu Xin
(School of Logistics, Beijing Wuzi University, Beijing 101149, China)
In this paper, in view of the characteristics of natural disasters, we built a two-echelon multi-objective emergency logisticsroute selection model whose constraints included timeliness, safety and economy, and then according to the temporal requirement of thenatural disasters, included in a hard time window constraint. The consideration of the timeliness and safety increased the relevancy of themodel established. At the end, we used the genetic algorithm to solve the model which proved the validity and feasibility of the model.
outbreak natural disaster; emergency logistics; vehicle route; genetic algorithm
F252;F224
A
1005-152X(2016)03-0123-04
10.3969/j.issn.1005-152X.2016.03.026
2016-02-18
2012年度北京市委組織部?jī)?yōu)秀人才培養(yǎng)資助個(gè)人項(xiàng)目D類(2012D005009000002);北京物資學(xué)院青年基金項(xiàng)目(2012XJQN014);北京市物流系統(tǒng)與技術(shù)重點(diǎn)實(shí)驗(yàn)室資助
陳志新(1973-),男,工學(xué)博士,副教授。