應急物資運輸問題研究綜述

應急物資運輸問題研究綜述

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