應(yīng)急物資運(yùn)輸問題研究綜述

應(yīng)急物資運(yùn)輸問題研究綜述

一、應(yīng)急物流與商業(yè)物資運(yùn)輸?shù)膮^(qū)別近年來，自然災(zāi)害、各種事故和公共安全災(zāi)害的發(fā)生頻率和規(guī)模都明顯超過了正常情況。九八洪水、SARS危機(jī)等都對我國社會整體生產(chǎn)生活程序造成了巨大沖擊。隨著我國經(jīng)濟(jì)的快速發(fā)展與政府行政體制改革的深化,政府部門逐漸認(rèn)識到在經(jīng)濟(jì)建立中,加強(qiáng)自身對大規(guī)模自然災(zāi)害與公共事件的管理,建立有效地應(yīng)急反應(yīng)機(jī)制的重要性。正在積極采取有效措施建立各級部門的應(yīng)急反應(yīng)機(jī)制,以快速、高效地化解各種危機(jī),減少災(zāi)害損失,最大限度地保障人民生命財(cái)產(chǎn)安全。這就迫使我們加強(qiáng)對自然災(zāi)害與突發(fā)公共事件應(yīng)急管理地研究,提高對這些事件的應(yīng)對能力。如何利用先進(jìn)的技術(shù)手段,增強(qiáng)政府與社會有關(guān)團(tuán)體、組織應(yīng)對自然災(zāi)害與突發(fā)公共事件的應(yīng)急反應(yīng)能力是我們社會所面臨的一個重要課題。應(yīng)急物流(emergencyLogistic)這個概念是在文獻(xiàn)中提出,它指以提供突發(fā)性自然災(zāi)害、公共衛(wèi)生事件等突發(fā)性事件所需應(yīng)急物資為目的,以追求時間效益最大化和災(zāi)害損失最小化為目標(biāo)的特種物流活動。應(yīng)急物流與普通物流一樣,由流體、載體、流向、流量、流程、流速等要素構(gòu)成,具有空間效用、時間效用和形質(zhì)效用。普通商業(yè)物流既強(qiáng)調(diào)物流的效率,又強(qiáng)調(diào)物流的效益,而應(yīng)急物流在許多情況下是通過物流效率的實(shí)現(xiàn)來完成其物流效益的實(shí)現(xiàn)。它的主要研究內(nèi)容包括,應(yīng)急物資運(yùn)輸與配送、應(yīng)急物資的儲備、應(yīng)急物流中心的構(gòu)建、應(yīng)急物資的籌措與采購、應(yīng)急物流的快速保障技術(shù)平臺的構(gòu)建等等。由此可以得出它與商業(yè)物資運(yùn)輸?shù)牟顒e主要有以下幾點(diǎn):1.應(yīng)急救援物資運(yùn)輸具有弱經(jīng)濟(jì)性,平時物資運(yùn)輸?shù)慕?jīng)濟(jì)效益原則將不再作為運(yùn)輸活動的中心目標(biāo)加以考慮,它的目標(biāo)是在盡快將救援物資運(yùn)輸?shù)侥康牡氐那疤嵯聦?shí)現(xiàn)運(yùn)輸成本最小化,屬于同時追求貨物運(yùn)輸時間最小化與成本最小化的多目標(biāo)規(guī)劃問題。而商業(yè)物資運(yùn)輸與配送問題的目標(biāo)一般是運(yùn)輸成本最小化或滿足貨物配送時間約束下的運(yùn)輸成本最小化問題。2.由于自然災(zāi)害與公共突發(fā)事件的突發(fā)性與規(guī)模、種類的不確定。救援物資種類較多,如食物、水、帳篷、衣物、藥品、救援設(shè)備,每種物資的供應(yīng)點(diǎn)與需求點(diǎn)可能都不一致。而且物資的需求量、供應(yīng)量可能會隨著時間而變化的。同時可供使用的運(yùn)輸車輛數(shù)、地點(diǎn),物資的供應(yīng)點(diǎn)會隨著事件的發(fā)展而變化。而商業(yè)物流中對于運(yùn)輸商品種類、供應(yīng)點(diǎn)等參數(shù)在計(jì)劃期內(nèi)基本是確定的,可用運(yùn)輸車輛數(shù)與地點(diǎn)也不會隨時間而變化。3.救援物資運(yùn)輸行動是由政府組織的非常規(guī)性活動,貨物配送中需要的車輛,一般是由政府按照應(yīng)急預(yù)案臨時征用社會團(tuán)體或個人的,它可以出現(xiàn)在網(wǎng)絡(luò)中的任何一點(diǎn)。在運(yùn)輸過程中車輛完成運(yùn)輸任務(wù)后也無需返回出發(fā)點(diǎn),所以需要同時研究貨物流及配套車輛流問題。而商業(yè)車輛調(diào)度問題具有固定的車場、物資供應(yīng)點(diǎn),運(yùn)輸車輛完成任務(wù)后需要返回車場。一般通過車輛的運(yùn)輸路線就可以確定物資流向。4.應(yīng)急救援物資運(yùn)輸需要使用公路、鐵路、航空等多種運(yùn)輸方式,而且經(jīng)常會在不同的運(yùn)輸方式中進(jìn)行轉(zhuǎn)換,因?yàn)樵诘卣?、洪水等自然?zāi)害發(fā)生時,通往災(zāi)害發(fā)生地的道路都給毀壞了,這時只有通過航空運(yùn)輸?shù)姆绞讲拍軐⒕仍镔Y運(yùn)送到災(zāi)害發(fā)生地。根據(jù)以上不同特點(diǎn),我們可以總結(jié)應(yīng)急救援物資運(yùn)輸與配送問題約束條件是運(yùn)輸多種物資,每有物資都可能有多個供應(yīng)點(diǎn)與需求點(diǎn),物資的供應(yīng)量、需求量、供需地點(diǎn)會隨時間變化;物資運(yùn)輸需要使用多種運(yùn)輸方式并可以在運(yùn)輸途中進(jìn)行運(yùn)輸方式的轉(zhuǎn)換,在計(jì)劃期內(nèi)可用車輛數(shù)量可變,車輛沒有固定的出發(fā)點(diǎn),在運(yùn)輸任務(wù)完成以后也無需返回出發(fā)點(diǎn),運(yùn)輸工具變量是整形變量;在這些條件的約束下問題的目標(biāo)是追求運(yùn)輸時間最短與運(yùn)輸成本最小。因此應(yīng)急物資運(yùn)輸問題是一個復(fù)雜的集成了多貨物多起止點(diǎn)網(wǎng)絡(luò)流問題與多運(yùn)輸方式滿載車輛無固定起止點(diǎn)運(yùn)輸工具調(diào)度問題的多目標(biāo)規(guī)劃。二、當(dāng)前和文獻(xiàn)中的研究(一)重大突發(fā)事件及其應(yīng)急救援的文獻(xiàn)分析由于存在多目標(biāo)、多運(yùn)輸方式、多種類貨物等約束條件,使得應(yīng)急救援物資運(yùn)輸問題的建構(gòu)與解決非常復(fù)雜,目前討論此問題的文獻(xiàn)較少,不能與其重要性及目前應(yīng)用需要相適應(yīng)。而且多數(shù)文獻(xiàn)是從商業(yè)物資運(yùn)輸問題的框架著手研究,沒有考慮到突發(fā)性事件這個特定場景所產(chǎn)生一些特殊要求。比如大多數(shù)文獻(xiàn)建立模型都是以成本最小化作為目標(biāo)函數(shù)。而救援物資運(yùn)輸?shù)哪繕?biāo)降低運(yùn)輸時間與減少運(yùn)輸成本相結(jié)合。以下按照目標(biāo)函數(shù)的不同,將相關(guān)文獻(xiàn)分為成本最小化與運(yùn)輸貨物延遲最小化兩類:1.混合系統(tǒng)規(guī)劃方法Barbarosoglu提出了一個兩階段多運(yùn)輸方式、多種類貨物網(wǎng)絡(luò)流模型,模擬救援物資的運(yùn)輸計(jì)劃。通過提前確定發(fā)生地震范圍與震級的概率,解決在第一輪救援行動中,沒有得到災(zāi)情詳細(xì)數(shù)據(jù)的情況下,物資供應(yīng)與需求不平衡的問題。在該文中主要采用隨機(jī)線性規(guī)劃來建立系統(tǒng)模型,沒有考慮用來完成運(yùn)輸任務(wù)的車輛調(diào)度問題,所以模擬多運(yùn)輸方式不完整。Wael在他的博士論文中提出災(zāi)害發(fā)生時運(yùn)輸問題屬于CTDAP(Thecombinedtripdistributionandassignmentproblem)。提出使用混合整數(shù)規(guī)劃的方法建立應(yīng)急物資模型計(jì)算較為復(fù)雜,并且花費(fèi)時間較長,不適合于突發(fā)事件應(yīng)急管理場景的需要,并認(rèn)為主要原因是使用混合整數(shù)規(guī)劃的方法建立模型增加了問題的復(fù)雜性,作者在文章中提出了一種新的使用CellularAutomata技術(shù)建立混合路線分布與指派問題數(shù)學(xué)模型的方法,并在實(shí)例中使用精確算法與CA模型算法進(jìn)行比較,證明了CA方法求解速度快、靈活的優(yōu)點(diǎn),但是在該文獻(xiàn)中并沒有考慮運(yùn)輸方式、可用交通工具地點(diǎn)、數(shù)量等應(yīng)急場景中經(jīng)常出現(xiàn)的一些決策變量。Rathi研究了在緊急狀態(tài)下物資供應(yīng)問題的線性規(guī)劃模型,在該模型中源點(diǎn)與目的點(diǎn)之間的路線以及在每條路線上貨物運(yùn)輸量都是預(yù)先定義好的,解決的是每條線路上分配的最優(yōu)運(yùn)輸車輛的數(shù)量,解出的最優(yōu)車輛數(shù)不是整數(shù)時,則將車輛數(shù)都增加至大于這個實(shí)數(shù)的最小整數(shù)。因?yàn)樵趩栴}中沒有限制車輛的數(shù)量,這與應(yīng)急物流的場景是不相符的,這個問題實(shí)際演化成商業(yè)物流中多車場情況下集貨與送貨一體化的車輛調(diào)度問題。Eqi將應(yīng)急物流中的貨物運(yùn)輸考慮成一個混合運(yùn)輸與車輛調(diào)度問題,在該文所描述的問題中運(yùn)輸問題解決的是從給定數(shù)量的供應(yīng)點(diǎn)中計(jì)算出可以滿足需要的最優(yōu)路線數(shù)。另一方面,車輛調(diào)度問題計(jì)算的是在這些路線上分配卡車的數(shù)量,這個問題也忽略了應(yīng)急物流最終目標(biāo)是加快貨物運(yùn)輸速度,減少達(dá)到目的地的延遲,而不是解決車輛的分配問題。2.應(yīng)急管理目標(biāo)函數(shù)Linet描述了應(yīng)急救援物資運(yùn)輸?shù)南拗茥l件:包括供應(yīng)物資有限,使用運(yùn)輸方式與工具種類較多,車輛數(shù)、物資供應(yīng)量、車場等各種問題參數(shù)都是隨時變化的等等。提出應(yīng)急物資運(yùn)輸目標(biāo)函數(shù)是盡量減少貨物運(yùn)輸延遲,車輛完成運(yùn)輸任務(wù)后不需要回到出發(fā)車場等,同時根據(jù)以上條件設(shè)計(jì)了宏觀應(yīng)急物資運(yùn)輸計(jì)劃模型,這個模型主要解決的是隨時間變化的動態(tài)貨物運(yùn)輸問題。完全沒有考慮運(yùn)輸成本的最小化問題。同時目標(biāo)函數(shù)是最小化各周期內(nèi)未滿足貨物量的總和,這實(shí)際上給量大的物資賦予較高的運(yùn)輸優(yōu)先權(quán),從而使一些重要比重小的物資如藥品最后運(yùn)輸,對應(yīng)急物流實(shí)踐的指導(dǎo)作用有限。宋明安在應(yīng)急救援物資輸配送系統(tǒng)模式構(gòu)建的論文中,將救災(zāi)物資配送分為前端物資指派與后端的物資配送兩部分。其中第一部分是以最小化運(yùn)輸時間的目標(biāo)下,探討了救援物資的運(yùn)輸問題,整個系統(tǒng)通過模糊集分類法解決救災(zāi)初期救援物資供需失衡的問題,以最大限度減少物資的浪費(fèi)與閑置。中國科學(xué)院計(jì)雷教授提出應(yīng)急管理中的救援物資運(yùn)輸問題是多目標(biāo)組合優(yōu)化問題,其中主要目標(biāo)是如何盡快的把物資運(yùn)輸運(yùn)送到指定的災(zāi)害發(fā)生地區(qū),目標(biāo)函數(shù)不僅僅是成本最小化,更重要的是運(yùn)送時間最小化,屬于多目標(biāo)優(yōu)化的運(yùn)輸問題。所以該文獻(xiàn)提出使用多目標(biāo)規(guī)劃來描述應(yīng)急物資運(yùn)輸?shù)哪Ｐ筒⑶蠼狻５窃撐墨I(xiàn)并沒有涉及到運(yùn)輸模型的建立與實(shí)現(xiàn)。同時可以看出應(yīng)急物資運(yùn)輸問題研究的是如何盡快運(yùn)用各種運(yùn)輸工具把特定數(shù)量與種類的救援物資從倉庫或中轉(zhuǎn)站運(yùn)送到指定的災(zāi)害或事件發(fā)生地的問題,它與普通的商業(yè)背景下調(diào)度車輛運(yùn)輸配送貨物的車輛路線問題(vehicleroutingproblem,簡記VRP)或VSP非常相似,因此可以借鑒VRP問題的分析思路、方法、以及解題算法來研究應(yīng)急物流中救援物資運(yùn)輸配送問題。(二)顧客配送方法VSP(或稱為VRP)一直是網(wǎng)絡(luò)優(yōu)化問題中最基本的問題之一,由于其應(yīng)用的廣泛性和經(jīng)濟(jì)上的重大價(jià)值,一直受到國內(nèi)外學(xué)者的廣泛關(guān)注。在中進(jìn)行了詳盡的闡述。其研究領(lǐng)域跨越了運(yùn)籌學(xué)、應(yīng)用數(shù)學(xué)、組合數(shù)學(xué)、圖論、計(jì)算機(jī)應(yīng)用等學(xué)科,該問題的一般定義為:設(shè)有一個場站(depot),共有M輛貨車,車輛容量為Q,有N位顧客(customer),每位顧客有其需求量D。車輛從場站出發(fā)對客戶進(jìn)行配送服務(wù)最后返回場站,要求所有顧客都被配送,每位顧客一次配送完成,且不能違反車輛容量的限制,目的是所有車輛路線的總距離最小或費(fèi)用最少。下VSP問題按照不同應(yīng)用場景形成多種不同的VSP問題分類方法,按文獻(xiàn)可以分為:按照任務(wù)特征劃分為純裝問題和裝卸混合問題;按任務(wù)性質(zhì)分為對弧服務(wù)問題、對點(diǎn)服務(wù)問題和混合服務(wù)問題;按車輛載貨情況劃分為滿載問題和非滿載問題;按車場數(shù)目分為單車場問題和多車場問題等。目前對車輛調(diào)度問題研究較多的變形問題主要有時窗限制車輛路線問題(vehicleroutingproblemswithtimewindows,VRPTW)、多車種車輛路線問題(fleetsizeandmixvehicleroutingproblems,FSVRP)、考慮收集的車輛路線問題(vehicleroutingproblemswithbackhauls,VRPB)、隨機(jī)需求車輛路線問題(vehicleroutingproblemwithstochasticdemand,VRPSD)等。在這其中FSVRP、VRPSD、VRPB等問題都函蓋了應(yīng)急物資運(yùn)輸問題的某些特點(diǎn),比如VRPSD問題描述了應(yīng)急物資運(yùn)輸中經(jīng)常出現(xiàn)的物資的需求量、供應(yīng)量可能會隨機(jī)變化的特點(diǎn)?？梢越梃bFSVRP的解決方法解決應(yīng)急物資運(yùn)輸中多車型、多運(yùn)輸方式的問題。多車場VRP問題的解決方案對解決應(yīng)急物資運(yùn)輸多車輛分派也具有指導(dǎo)意義。三、局部搜索優(yōu)化算法由于應(yīng)急物資運(yùn)輸問題非常類似于VRP問題,它與VRP問題一樣基本上是NPhard問題,難以用精確算法求解。啟發(fā)式算法是求解車輛運(yùn)輸問題的主要方法,多年來許多學(xué)者對車輛運(yùn)輸問題進(jìn)行了研究,提出了各種各樣的解決方法。為解決復(fù)雜混合優(yōu)化問題而出現(xiàn)的亞啟發(fā)式算法是近二十年中運(yùn)籌學(xué)領(lǐng)域最引人矚目的成果之一,它也是解決VRP問題最具有成效的算法。亞啟發(fā)式算法包括表搜索算法(tabusearch)、模擬退火算法(stimulatedannealing)、遺傳算法(geneticalgorithm)和神經(jīng)網(wǎng)絡(luò)算法(neutralnetworks)方法等。表搜索法是一種廣義的局部搜索算法,在每一步搜索中,都要求找到在當(dāng)前解的局部鄰域,將局部領(lǐng)域里面的最優(yōu)解選作新的當(dāng)前解,盡管在領(lǐng)域里面的最優(yōu)解可能不如當(dāng)前解,但是TS算法還是繼續(xù)將領(lǐng)域中的最優(yōu)解作為當(dāng)前解繼續(xù)搜索,而不像其他局部搜索算法一樣中止搜索。設(shè)計(jì)一個Tabu表,所有局部最優(yōu)解都被存放在一個Tabu表中,避免搜索過程中的循環(huán)。模擬退火算法源自固體退火原理,在其中將內(nèi)能E模擬為目標(biāo)函數(shù)值f,溫度T演化成控制參數(shù)t,即得到解組合優(yōu)化問題的模擬退火算法:由初始解i和控制參數(shù)初值t開始,對當(dāng)前解迭代進(jìn)行產(chǎn)生新解的同時計(jì)算目標(biāo)函數(shù)差;接受或舍棄解,并逐步衰減t值,算法終止時的當(dāng)前解即為所得近似最優(yōu)解。遺傳算法是一種通過模擬自然選擇進(jìn)化過程解決最優(yōu)化問題的計(jì)算模型。首先對可行域中的解進(jìn)行編碼,計(jì)算每個解的目標(biāo)函數(shù)值,也就是編碼的適應(yīng)度。利用選擇機(jī)制從編碼組中隨機(jī)挑選編碼作為繁殖過程前的編碼樣本。并通過交叉和變異兩種算子對挑選后的樣本進(jìn)行交換。模擬生物的繁殖過程。迭代進(jìn)行選擇和繁殖過程,直到結(jié)束條件得到滿足為止以得到最優(yōu)化解。TS算法在求解VSP中已取得較好的效果,但是這個方法過于復(fù)雜,所得到的解最接近最優(yōu)解,但其運(yùn)算量較大,涉及復(fù)雜的領(lǐng)域轉(zhuǎn)換和求解策略,運(yùn)算時間也最長,是GA算法的2~3倍,SA算法的近20倍,在實(shí)際中不易實(shí)現(xiàn)。SA算法具有收斂速度快,全局搜索的特點(diǎn),能提供一定程度上的優(yōu)化方案,在求解較小規(guī)模問題上具有較好效果。遺傳算法能較好的逼近最優(yōu)解,同時使運(yùn)算時間大大縮短,所以GA算法能兼顧運(yùn)算時間和效率兩方面,是具有較好的發(fā)展前途的方法。四、建立完善的應(yīng)急救援物資運(yùn)輸評價(jià)體系從以上分析可以看出,目前在應(yīng)急物資運(yùn)輸問題方面研究還非常不足,從問題模型的建立到算法的設(shè)計(jì)與求解,都未能滿足在大規(guī)模災(zāi)害與公共突發(fā)事件發(fā)生的情況下應(yīng)急救援物資運(yùn)輸與配送實(shí)踐的需要,應(yīng)急物資運(yùn)輸問題研究的方向主要集中在以下幾點(diǎn):1.建立適合災(zāi)害發(fā)生場景需要的應(yīng)急物資運(yùn)輸問題評價(jià)體系。在大規(guī)模自然災(zāi)害或突發(fā)性公共事件發(fā)生的情況下,救援物資運(yùn)輸問題的主要目標(biāo)是盡快將物資運(yùn)輸?shù)侥康牡?配送至受影響的當(dāng)?shù)厝罕娛种?在此前提下才能追求運(yùn)輸成本最小化,而目前多數(shù)應(yīng)急物資運(yùn)輸問題的目標(biāo)函數(shù)是借鑒商業(yè)物資運(yùn)輸?shù)脑u價(jià)體系,以最小化運(yùn)輸成本為