多車批量配送的應(yīng)急物流模型

多車批量配送的應(yīng)急物流模型

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