多車批量配送的應急物流模型

基于sdrsp的應急物流管理據(jù)統(tǒng)計，世界上突發(fā)事件（自然災害、感染疾病、流血沖突等）的頻率和烈度逐年增加。應急物流研究在突發(fā)事件下如何將救援物資及時、可靠、高效地送達各災點,直接影響到人員傷亡和財產(chǎn)損失,意義重大。應急物流一般抽象為車輛路徑規(guī)劃問題(VehicleRoutingProblem,VRP),具有強時效性、弱經(jīng)濟性等特點。采用VRP經(jīng)典框架,但以最終(或平均)送達時間最小化為目標。為提高運輸車輛的靈活性和使用率,建立多車場VRP模型,進一步提出多周期的分層VRP方案。突發(fā)事件背景下,一方面,災點的物資需求量往往超過單車單次供應量,故只能由多車多批次予以滿足。另一方面,分批配送可保證各災點都能獲得及時救援,又避免了過量物資同時送達造成的囤積乃至混亂?？紤]到分批配送的車輛路徑問題(SplitDeliveryVehicleRoutingProblem,SDVRP)將各顧客點(即本文中的災點)的總需求進行拆分,允許其被多車多次服務,可以節(jié)約運輸車輛或配送路徑,因此適用于道路受損、車輛有限的應急物流。VRP是一種典型的非線性規(guī)劃(NP)難題,精確求解代價過大,實踐中往往采用亞啟發(fā)式算法,如禁忌搜索(tabusearch,TS)、遺傳算法(GA)、蟻群算法(ACO)等,近年來SDVRP的研究也取得重大進展,但用于應急物流還鮮有報道。為此本文建立應急物流的SDVRP模型,分別設計適用于該模型的GA、ACO以及ACO-GA混合算法,并通過數(shù)值算例仿真說明混合算法的優(yōu)勢。1批發(fā)供應車輛路徑的建模1.1救援物資狀態(tài)假設突發(fā)事件(如大規(guī)模自然災害)在某地區(qū)造成A個災點。該地區(qū)有且僅有一個車場。V臺車輛由車場出發(fā),依次對若干災點配送救援物資,最后空載返回車場,可能形成R條(閉合)路徑。為簡化分析,做如下假設(1)救援物資為統(tǒng)一包裝(重量、體積)的單元(包括藥品、飲用水、食物等)。(2)運輸車輛運載容量相同,行駛速度一致(3)各災點與車場均有道路連通,車輛無需原路返回(4)各災點各周期的需求已知或可準確估計,且在該規(guī)劃周期內(nèi)保持不變。(5)車場庫存可滿足所有災點的需求總量,故只需關注如何將足量物資送達。(6)各災點物資需求量較大,單車單次配送無法滿足,必須由多車分批配送。(7)車輛從車場出發(fā),前往通行距離(由道路長度及損毀程度共同決定)最遠的災點,也可當日返回。(8)救援行動將在T個周期內(nèi)終止,在災后T個周期之外送達的物資無效。(9)模型中所有變量均為整數(shù),屬于整數(shù)規(guī)劃問題。1.2周期t的需求t:周期集中的編號結(jié)合救災72小時黃金時間的一般原則,設T(28)3,即盡量將救援物資在3天內(nèi)送達災點。qarv(t,t):為滿足災點a在周期t的需求,車輛v經(jīng)由路徑r在周期t送達的物資量,顯然為如期配送,為無效配送tr:車輛在路徑r上的行駛時間tr是路徑里程、行車速度和災害破壞狀況的函數(shù),路徑越長、車速越低、損毀越嚴重,tr越大;反之則tr越小。路徑?jīng)Q策函數(shù),若車輛v在周期t經(jīng)過路徑r,Q:單車的額定容量H:車輛在每個周期內(nèi)的工作時間表示救援行動終止時,災點a獲得的救災物資總量與其需求總量之比值。sa越大,需求滿足得越充分,則該災點的滿意度越高。1.3救援+分區(qū)z1為受災地區(qū)所有災點總需求與總配送的差值,最小化(3)式要求盡量滿足災區(qū)的物資需求。z2為所有車輛在救援路網(wǎng)中的總耗時,最小化(4)式反映了救援的及時性要求。z3為任意兩災點i,j的滿意度差異的最大值,最小化(5)式力求均衡各災點的供需比,反映了救援的公平性原則。1.4需求總量不得超過已達需求總量單車單次需給至少一個災點配送救援物資單車單次配送物資量不得超過其額定容量各災點獲得物資總量不應超過其需求總量結(jié)合式(2),有災害損毀交通設施,限制了運輸車輛的運行時段。即車輛在一個周期內(nèi)的總行駛時間存在上限1.5確定目標函數(shù)應急物流配送模型兼顧效用、時間、均衡三方面的要求,屬于多目標優(yōu)化問題。各目標相互獨立,且有矛盾關系(例如保證物資供應,就需用較多車輛經(jīng)由較多路徑;而縮減路徑則往往導致各災點物資配送不均),因此必須做折中考慮。本文采用加權求和法,應用層次分析法(AHP)確定各目標權值。根據(jù)專家經(jīng)驗,結(jié)合災情實際,得出各目標重要性的相對關系,即重要度比較矩陣故權值向量為經(jīng)實際計算發(fā)現(xiàn),各函數(shù)的取值區(qū)間大致為z1:60~100,z2:0~24,z3:0~5。故對z1和z2取對數(shù),z3不做變換,依(11)式,得到單一目標函數(shù)2遺傳計算方法的改進2.1車場的編碼染色體編碼是遺傳算法的關鍵和難點。結(jié)合本文模型的具體特點,將需求量為d的災點視為需求量為1的d個同名災點,規(guī)定:(a)一條染色體表示一個周期的配送方案,由相互獨立的段基因組成;(b)每段基因表示一輛車的配送路徑,由Q位組成(c)每位表示一份物資,該位上的數(shù)字即為物資送達的災點編號;由于車輛不一定滿載出發(fā),故基因上可能出現(xiàn)的空位用0補齊?？紤]SDVRP,車場記為D,6個災點記為1~6,總需求量單車額定容量Q=5,故需3條配送路徑,為便于后續(xù)遺傳操作,編碼時將車場省去。編碼后的染色體分為3段,每段5位顯然三條路徑整體互換不影響目標函數(shù)值,性能優(yōu)化主要通過兩種方式實現(xiàn):(1)不同路徑之間,基因段的交換(2)同一路徑內(nèi)部,基因位的重新排序2.2災點i用量累積概率由于本文模型為分階段規(guī)劃問題,而各災區(qū)在各周期的需求量動態(tài)變化,因此必須將災區(qū)的需求信息編入種群。設周期t時,各災點需求集為Dmd={d1,…,dA},uf072i為災點i需求量的累積概率。借鑒賭盤輪轉(zhuǎn)思想,算法偽代碼如下Step.1設置ρi=0,Dmd為初始值Step.2計算Step.3生成一個之間的隨機數(shù),若落在(ρi,ρi+1],則將災點i寫入當前位Step.4更新DmdStep.5若單條染色體還有剩余的位,回到Step.2;否則,轉(zhuǎn)Step.6Step.6若種群數(shù)未到達n,回到Step.1;否則,初始種群Pop生成完畢周期t規(guī)劃結(jié)束時,將各災點未被滿足的需求量與周期t(10)1產(chǎn)生的新需求相累加,進入下一周期的規(guī)劃。2.3遺傳實踐與創(chuàng)新2.3.1父代種群和子代種群同樣采用賭盤輪轉(zhuǎn)法對種群進行選擇操作,保證父代的優(yōu)質(zhì)個體以較大概率被選中。種群的適應度集為其中fi為染色體i適應度,與目標函數(shù)反相關,ρi為fi的累積概率,記父代種群為Pop,子代種群為PopNext。算法偽代碼如下Step.1設置ρi=0,計算fiStep.3生成之間的隨機數(shù),若落在(ρi,ρi+1],則選擇染色體i,編入PopNextStep.4若已達到子代種群數(shù)n,轉(zhuǎn)Step.5;否則,回到Step.3,選擇另一條染色體Step.5選擇結(jié)束,PopNext={Pop,PopNext}為了保證解的多樣性,將種群父代也編入子代進行交叉變異操作,因此選擇后生成的子代種群為PopNext={Pop,PopNext}。2.3.2chromissschromi的交叉操作采用部分交叉法,使種群在當前解附近尋找更優(yōu)解。設交叉概率為CP,算法偽代碼如下。Step.1從種群PopNext中隨機選擇兩條染色體1Chromi,Chromi(10)Step.2生成之間隨機數(shù)rand,若進行交叉操作Step.3隨機生成兩個交叉位x,y,將Chromi,Chromi+1內(nèi)x,y之間的基因位交換,得到新的染色體Step.4若回到Step.1;否則,轉(zhuǎn)Step.5Step.5交叉操作結(jié)束,用更新PopNext隨機得x=4,y=8,交叉后得到的分別為2.3.3變異矩陣采用多點變異,設變異概率為PM,算法偽代碼如下2.3.4同一路徑內(nèi)同一災點,重復基因型經(jīng)交叉、變異得到的染色體,很可能出現(xiàn)同一路徑內(nèi)同一災點被分割的情況,這顯然不符合救災實際,必須避免,為此調(diào)整基因位序,將同一路徑內(nèi)的同名災點放在一起。例如:變異操作后的為調(diào)整后,得到合理的染色體對PopNext中的所有染色體均作上述處理。2.4路徑行駛時間遺傳操作完成后,必須應用單周期的工作時間約束驗證解的可行性,檢驗其是否服從(9)式約束。算法偽代碼如下Step.1對染色體Chromi,從第一位開始,每Q位構成一條完整路徑Step.2累計上述每條路徑的行駛時間,如果均小于H,則轉(zhuǎn)Step.3;否則,轉(zhuǎn)Step.4Step.3Chromi可行,保留,轉(zhuǎn)Step.5Step.4Chromi不可行,淘汰,轉(zhuǎn)Step.5Step.5驗證下一條染色體Chromi+1,直至生成規(guī)定數(shù)量的可行種群,作為下一輪遺傳操作的父代種群Pop3螞蟻-遺傳混合算法的設計3.1災點隨機配送規(guī)劃上述遺傳操作基于隨機生成的初始種群,大量計算時間消耗于淘汰初始種群中可行卻明顯劣質(zhì)的個體,收斂時間長,尋優(yōu)效率低。為此考慮利用ACO的正反饋機制,通過較少次數(shù)迭代,對問題的解空間做一粗略搜索,提高初始種群質(zhì)量;再應用GA進一步優(yōu)化。基本流程如圖1所示。采用蟻群算法依次完成以下步驟第一,規(guī)劃出遍歷路徑第二,根據(jù)各災點的實時需求生成一個配送額第三,根據(jù)車輛載荷約束,插入車場,完成規(guī)劃。設Tabu(k)為螞蟻k的禁忌表,算法偽代碼如下Step.1螞蟻k隨機處于災點i,其禁忌表Tabu(k)={i}Step.3由轉(zhuǎn)移概率的最大值,確定下一步的災點并更新禁忌表Step.4根據(jù)災點j的實時需求,生成一個配送量Step.5若已遍歷所有災點,轉(zhuǎn)Step.6;否則回到Step.2Step.6Tabu(k)為螞蟻k的旅行路徑Step.7根據(jù)式(3)~(5)評價Tabu(k),結(jié)束由于災區(qū)的物資需求量一般大于車輛額定載荷,所以若根據(jù)災區(qū)需求隨機生成配送量,可能出現(xiàn)單次配送過多,當前周期負荷過重的情形,導致物資配送的周期不均衡性。因此,需要對配送量設置閾值,本文取車輛載重的60%。3.2基于信息素與啟發(fā)因子的路徑選擇算法由于式(5)引入了滿意度指標以保證救援物資的公平發(fā)放,因此要求螞蟻在每一步選擇下個災點時,不僅應關注路徑信息素與兩點間距,同時還需考慮待選災點的需求量,故上述算法Step.3中的轉(zhuǎn)移概率為其中和η分別為信息素與啟發(fā)因子,為災點j在周期t的需求量函數(shù)。將蟻群若干次迭代后尋得的路徑按照2.1的編碼規(guī)則映射為染色體,即獲得較為優(yōu)質(zhì)的遺傳初始種群,之后可沿用第2節(jié)的遺傳操作步驟進一步尋優(yōu)。4數(shù)值模擬驗證4.1仿真結(jié)果與分析利用VRPWeb上的通用數(shù)據(jù)集p01,取其中的點0-10構成問題n-10(含1個車場與10個災點,見表1);取其中的點0-20構成問題n-20(含1個車場與20個災點,見表2),進行數(shù)值仿真。模型參數(shù):最大工作時間H(28)12h,規(guī)劃周期T(28)3d(一般救援物資需在72h內(nèi)送達),車輛載重Q(28)15,速度20。算法參數(shù):GA:染色體數(shù)50,進化20代,PC=0.7,PM=0.1;ACO-GA:蟻群規(guī)模10,迭代20次,染色體數(shù)30,進化10代;其它參數(shù)不變運行環(huán)境:Matlab8.0,IntelPentiumDualCPUE2160@1.80GHz,2.00GBDDR-IIRAM。4.2單車單次容量無法被服務為便于對比,以問題n-10為例,同時給出三種進化算法的求解結(jié)果:單純遺傳算法(表3),單純蟻群算法(表4)和本文提出的蟻群-遺傳混合算法(表5)。由表3,對于問題n-10,為保證所有災區(qū)需求72小時內(nèi)滿足,GA算法所需車輛數(shù)為6。如果采取基本VRP模型,則至少為15。這是由于本文模型采用分批配送,使車輛得以重復利用,從而節(jié)約了車輛數(shù)。此外,如果不對需求進行拆分,將有部分災點由于需求大于單車單次容量而不能被服務,即產(chǎn)生不可行解。表4顯示了ACO同樣可以較好地求解本文模型,并且尋優(yōu)結(jié)果效果比GA改善了9%,且收斂速度更快,路徑數(shù)更少,這源于蟻群算法的分步求解過程:每次先生成TSP路徑,再根據(jù)災點需求生成配送額,最后根據(jù)車輛容量插入車場,從而避免了遺傳算法初始種群的過度隨機性,降低了重復回路出現(xiàn)的可能性。如圖2,為ACO-GA混合算法針對問題n-10求得的3個周期內(nèi)的配送路徑。結(jié)合表5可以看出,ACO-GA不僅能有效地求解本文模型,而且與單純的GA或ACO相比,尋優(yōu)效能進一步提高。如圖3,為三種算法對問題n-10和n-20的求解結(jié)果(目標函數(shù)值)對照。盡管蟻群規(guī)模及遺傳代數(shù)都較單純ACO,GA有所減少,但ACO-GA的尋優(yōu)效果更佳。進一步求其平均值列于表6。對于問題n-10,ACO-GA的結(jié)果比GA小14.5%,比ACO小6%;對于問題n-20,ACO-GA的結(jié)果比GA小12%,比ACO小7%。這是由于ACO的粗略搜索對GA初始種群的生成起到了良好的指導作用,使得種群更高效地向最優(yōu)解方向進化。另外,由于引入公平度這一評價指標,每條路徑經(jīng)過的災點數(shù)相對增加,而單個災點的單次配送額不大,但這樣提高了物資配送的均衡性,即而每條配送路線覆蓋的災點較多。從而避免部分災點因大量物資同時送達造成囤積,而另一部分災點卻因為缺乏物資而造成災情擴大化的局面。5遺傳算法求解本文應用SDVRP思想,建立應急物流調(diào)度模型,分別針對災點的未滿足需求量、物資配送時間、滿意度差異進行最小化,通過對各目標加權求和,兼顧救援的效果、速度和公平。設計與