救援物資運(yùn)輸問題的多模式分層網(wǎng)絡(luò)規(guī)劃模型

救援物資運(yùn)輸問題的多模式分層網(wǎng)絡(luò)規(guī)劃模型

1應(yīng)急救援物資運(yùn)輸?shù)闹饕碚撃Ｐ徒陙恚匀粸?zāi)害、各種事故和公共安全災(zāi)害的發(fā)生頻率和規(guī)模都明顯超過了正常情況。九八洪水、SARS危機(jī)等都對(duì)我國社會(huì)整體生產(chǎn)生活程序造成了巨大沖擊。隨著我國經(jīng)濟(jì)的快速發(fā)展與政府行政體制改革的深化,政府部門逐漸認(rèn)識(shí)到在經(jīng)濟(jì)建立中,加強(qiáng)自身對(duì)大規(guī)模自然災(zāi)害與公共事件的管理,建立有效地應(yīng)急反應(yīng)機(jī)制的重要性。如何利用先進(jìn)的技術(shù)手段,增強(qiáng)政府與社會(huì)團(tuán)體、組織應(yīng)對(duì)大規(guī)模自然災(zāi)害與突發(fā)公共事件的應(yīng)急反應(yīng)能力已成為一個(gè)重要課題。應(yīng)急救援物資的運(yùn)輸是應(yīng)急管理領(lǐng)域中的一個(gè)中心問題。它是在大規(guī)模自然災(zāi)害與突發(fā)性公共事件發(fā)生以后,研究如何調(diào)度不同運(yùn)輸方式下的運(yùn)輸工具(為了簡便,以下所有運(yùn)輸方式中的運(yùn)輸工具都簡稱為車輛)將數(shù)量與種類可能隨時(shí)間變化的救援物資盡快從多個(gè)供應(yīng)點(diǎn)運(yùn)輸?shù)绞录l(fā)生地,以追求時(shí)間效益最大化和災(zāi)害損失最小化為目標(biāo)的特種物流活動(dòng)。應(yīng)急物資運(yùn)輸與商業(yè)運(yùn)輸相比主要差別是:①應(yīng)急救援物資運(yùn)輸具有弱經(jīng)濟(jì)性,它的目標(biāo)是在盡快將救援物資運(yùn)輸?shù)侥康牡氐那疤嵯聦?shí)現(xiàn)運(yùn)輸費(fèi)用最小化,屬于同時(shí)追求貨物運(yùn)輸時(shí)間最小化與費(fèi)用最小化的多目標(biāo)規(guī)劃問題。②由于自然災(zāi)害與公共突發(fā)事件的突發(fā)性與規(guī)模、種類的不確定。所需救援物資種類較多,每種物資的供應(yīng)點(diǎn)與需求點(diǎn)可能都不一致。而且物資的需求量、供應(yīng)量可能會(huì)隨著時(shí)間而變化的。③救援物資運(yùn)輸行動(dòng)是由政府組織的非常規(guī)性活動(dòng),貨物配送中需要的車輛,一般是由政府按照應(yīng)急預(yù)案臨時(shí)征用社會(huì)團(tuán)體或個(gè)人的,它可以出現(xiàn)在網(wǎng)絡(luò)中的任何點(diǎn),完成一項(xiàng)運(yùn)輸任務(wù)后也無需返回出發(fā)點(diǎn),所以需要同時(shí)研究貨物流及配套車輛配送問題。④應(yīng)急救援物資運(yùn)輸需要使用公路、鐵路、航空等多種運(yùn)輸方式,而且會(huì)在不同的運(yùn)輸方式中進(jìn)行轉(zhuǎn)換。因此應(yīng)急物資運(yùn)輸問題是一個(gè)復(fù)雜的集成了多貨物多起止點(diǎn)網(wǎng)絡(luò)流問題與多運(yùn)輸方式滿載車輛無固定起止點(diǎn)運(yùn)輸工具調(diào)度問題的多目標(biāo)規(guī)劃。由于應(yīng)急物資運(yùn)輸問題的復(fù)雜性,國內(nèi)外相關(guān)文獻(xiàn)較少。這其中Kemball-Cook和Stephenson首先提出在救援物資運(yùn)輸時(shí)對(duì)物流管理的需要,以提高運(yùn)輸效率。接著Ray、Rathi、Wael、Eqi、宋明安在不同的約束條件下研究了以最小化運(yùn)輸費(fèi)用為目標(biāo)的應(yīng)急救援物資運(yùn)輸?shù)膯栴};Linet提出了最小化運(yùn)輸時(shí)間為目標(biāo)函數(shù)的救援物資運(yùn)輸模型。計(jì)雷提出了應(yīng)急管理中的救援物資運(yùn)輸問題是最小化運(yùn)輸費(fèi)用與運(yùn)輸時(shí)間的多目標(biāo)組合優(yōu)化問題,但是該文獻(xiàn)并沒有涉及到問題模型的建立與實(shí)現(xiàn)。2應(yīng)急材料運(yùn)輸模式的結(jié)構(gòu)2.1多模式分層網(wǎng)絡(luò)模型應(yīng)急運(yùn)輸?shù)拿糠N物資都可能包括多個(gè)供應(yīng)點(diǎn)與需求點(diǎn),并且經(jīng)常會(huì)用到多種運(yùn)輸方式。據(jù)此設(shè)計(jì)了多模式分層網(wǎng)絡(luò),將每種運(yùn)輸方式分成一個(gè)網(wǎng)絡(luò)層,稱為一個(gè)模式層。在多模式分層網(wǎng)絡(luò)中有四類頂點(diǎn),分別是中轉(zhuǎn)點(diǎn):代表運(yùn)輸樞紐或可進(jìn)行運(yùn)輸方式轉(zhuǎn)換的地點(diǎn),不能貯存物資;映像點(diǎn):代表供應(yīng)點(diǎn)或需求點(diǎn)在某種運(yùn)輸方式下發(fā)送或接收物資,貨物流入量與流出量相等;供應(yīng)點(diǎn):通過映像點(diǎn)向各模式層上發(fā)送物資;需求點(diǎn):產(chǎn)生物資需求的點(diǎn),它通過映像點(diǎn)在各模式層上接收物資。同時(shí)多模式分層網(wǎng)絡(luò)中的弧分為三類。分別是載重弧:代表運(yùn)輸通路,與載重弧關(guān)聯(lián)的費(fèi)用為貨物運(yùn)輸費(fèi),同一模式層所有中轉(zhuǎn)點(diǎn)、映像點(diǎn)彼此連接的弧為載重弧;轉(zhuǎn)換弧:溝通不同運(yùn)輸方式之間的通路,貨物通過轉(zhuǎn)換弧在不同運(yùn)輸方式間轉(zhuǎn)運(yùn),在其上關(guān)聯(lián)了貨物轉(zhuǎn)運(yùn)費(fèi);映像弧:連接映像點(diǎn)與供應(yīng)點(diǎn)或需求點(diǎn),沒有相關(guān)聯(lián)的費(fèi)用與容量,也不消耗時(shí)間。圖1是一個(gè)多模式分層網(wǎng)絡(luò)示例圖,其中a、b是需求點(diǎn);c、d是供應(yīng)點(diǎn);e、f是中轉(zhuǎn)點(diǎn),整個(gè)運(yùn)輸網(wǎng)絡(luò)有三種運(yùn)輸方式,所以示例圖中三個(gè)模式層,c點(diǎn)可以通過運(yùn)輸方式一、二向外運(yùn)輸貨物,所以它在模式層一、二上有映像點(diǎn)c′、c″,代理它發(fā)送貨物。運(yùn)輸方式二與運(yùn)輸方式三可以在中轉(zhuǎn)點(diǎn)f進(jìn)行轉(zhuǎn)運(yùn),在模式層二、三上分別有f″、f?兩個(gè)點(diǎn)代表在運(yùn)輸方式二、三上的f點(diǎn),并在它們之間有轉(zhuǎn)換弧連接,表示貨物可在此點(diǎn)進(jìn)行運(yùn)輸方式二、三的轉(zhuǎn)運(yùn)。車輛作為運(yùn)輸工具需要循環(huán)使用,可以被看為模式層上的循環(huán)流,稱為車輛流。在應(yīng)急物資運(yùn)輸這個(gè)特定場景下車輛流有一些特殊的約束條件。首先是應(yīng)急救援車輛可以在網(wǎng)絡(luò)上的任意點(diǎn)被動(dòng)員征用,所以車輛可在對(duì)應(yīng)模式層上的任意點(diǎn)出發(fā)執(zhí)行運(yùn)輸任務(wù)。其次是車輛沒有固定的車場,完成計(jì)劃任務(wù)后,也不知道是否還有下一項(xiàng)運(yùn)輸任務(wù),所以完成運(yùn)輸任務(wù)后車輛不需要返回出發(fā)地而是在原地待命。再次是車輛流只能在載重弧上流轉(zhuǎn),而不能通過其他類型的弧。同時(shí)車輛流的流量上限就是載重弧的容量,而貨物流的流量上限是分配運(yùn)輸該種貨物的車輛容量。救援物資運(yùn)輸問題的目標(biāo)之一是縮短貨物運(yùn)輸時(shí)間,屬于包括時(shí)間在內(nèi)的四維空間優(yōu)化問題。為了將對(duì)時(shí)間的考量集成到救援物資運(yùn)輸模型中,將整個(gè)救援物資運(yùn)輸?shù)挠?jì)劃周期劃分成多個(gè)等長時(shí)段,模型中與時(shí)間有關(guān)的變量都以時(shí)段數(shù)來表示時(shí)間維度的值。同時(shí)貨物供應(yīng)量、需求量、可用車輛數(shù)等參數(shù)發(fā)生變化時(shí),也可以按照時(shí)段重新調(diào)整計(jì)劃,從而解決了模型參數(shù)隨時(shí)間變化的問題。在模型中時(shí)段的長度設(shè)置必需適中,以盡量減少車輛在完成任務(wù)后的閑置時(shí)間。但是它也不能太短,這將會(huì)使車輛路徑變量以指數(shù)方式增加。加入時(shí)間維度后,多模式分層網(wǎng)絡(luò)可以轉(zhuǎn)換成一個(gè)時(shí)空網(wǎng)絡(luò),圖2就是從圖1示例中的模式二層產(chǎn)生的時(shí)空網(wǎng)絡(luò),在連接不同點(diǎn)對(duì)間的虛線是行駛線路,同一相鄰點(diǎn)之間的點(diǎn)橫線是車輛停靠線路,設(shè)車輛的起點(diǎn)在c與d點(diǎn),虛線與點(diǎn)橫線是車輛的可選路線。從圖2可以看出,車輛流是在在時(shí)空網(wǎng)絡(luò)中單向可行路線中選擇一條滿足目標(biāo)要求的行-停路線,以此為基礎(chǔ)就可以制定詳細(xì)車輛配送計(jì)劃。救援物資運(yùn)輸問題的目標(biāo)是減少運(yùn)輸時(shí)間、降低運(yùn)輸費(fèi)用的多目標(biāo)規(guī)劃,其中運(yùn)輸費(fèi)用是包括車輛在載重弧上行駛的費(fèi)用(包括空駛與重載)和運(yùn)輸方式轉(zhuǎn)換的費(fèi)用。而對(duì)于最小化物資運(yùn)輸時(shí)間的目標(biāo),我們采用了罰函數(shù)方法,根據(jù)每種救援物資在需求點(diǎn)的需求緊迫性制定一個(gè)延期罰函數(shù)系數(shù),它定義為單位未滿足貨物需求量延續(xù)一個(gè)時(shí)段對(duì)目標(biāo)函數(shù)的增加量。這個(gè)方法的優(yōu)點(diǎn)是使用靈活,比如災(zāi)害發(fā)生后情況緊急,這時(shí)應(yīng)急物資運(yùn)輸?shù)闹饕繕?biāo)是減少運(yùn)輸時(shí)間,我們可以將運(yùn)輸費(fèi)用值設(shè)置為0。而如果救援行動(dòng)持續(xù)了一段時(shí)間,救援物資運(yùn)輸已經(jīng)成為日常例行事務(wù),這時(shí)貨物運(yùn)輸?shù)哪繕?biāo)是最小化費(fèi)用,我們就可以將延期罰函數(shù)系數(shù)設(shè)為0。2.2模型的構(gòu)建(1)計(jì)算重負(fù)荷弧的運(yùn)輸時(shí)間①由于大規(guī)模突發(fā)性事件情況下救援物資運(yùn)輸量都較大,因此只考慮車輛滿載情況。②每一載重弧的運(yùn)輸時(shí)間都以時(shí)段數(shù)量來衡量,不足1時(shí)段的以1時(shí)段計(jì)算。③轉(zhuǎn)運(yùn)弧消耗的時(shí)間都是1時(shí)段。④所有的費(fèi)用函數(shù)都假定為線性的。⑤貨物的供應(yīng)量與需求量已知。⑥每一種運(yùn)輸方式下車輛規(guī)格一致。(2)車輛載重量cdgi-運(yùn)輸方式單位段i,i,i,i,i,i,i,i,i,i,i,i,i,i,i,j及車輛參數(shù)決策變量cgi分析E-映像點(diǎn)點(diǎn)集FE-中轉(zhuǎn)點(diǎn)與映像點(diǎn)的集合T-計(jì)劃期的總時(shí)段數(shù)CA-載重弧集SNgit-g種類物在i點(diǎn)t時(shí)段新增供應(yīng)量RNgit-g種貨物在i點(diǎn)t時(shí)段新增需求量M-運(yùn)輸方式集合VAmit-第m種運(yùn)輸方式下在i點(diǎn)t時(shí)段新增車輛數(shù)VCapm-m種運(yùn)輸方式下車輛的載重量G-貨物的種類集tmij-在第m種運(yùn)輸方式從i點(diǎn)到直接相鄰j點(diǎn)所需時(shí)段數(shù)ACapmij-第m種運(yùn)輸方式載重弧(i,j)的道路容量CTm-第m種運(yùn)輸方式單位時(shí)段內(nèi)單位車輛的運(yùn)輸費(fèi)用CFgmm′i-單位g貨物在i點(diǎn)從m到m′運(yùn)輸方式的模式轉(zhuǎn)換費(fèi)用CDgi-在需求點(diǎn)i點(diǎn)單位g貨物需求延期單位時(shí)段滿足的罰函數(shù)系數(shù)Pg-g種類貨物的比重決策變量:Xgmitjt′-t時(shí)段從i點(diǎn)經(jīng)過t′-t時(shí)段到達(dá)j點(diǎn)的g貨物流量Xgmm′it(t+1)-貨物g在t時(shí)段、i點(diǎn)通過從m到m′模式的流量RDgit-需求點(diǎn)i在t時(shí)段g貨物未滿足的需求SDgit-供應(yīng)點(diǎn)i在t時(shí)段g貨物還未運(yùn)輸?shù)墓?yīng)量Ymitjt′-m層車輛在t時(shí)段從i點(diǎn)經(jīng)過tmij時(shí)段到j(luò)點(diǎn)的車輛流量VDmit-模式m層在i點(diǎn)、t時(shí)段未使用的車輛數(shù)(3)貨物流模型的形成根據(jù)以上的符號(hào)定義,可以將應(yīng)急救援物資運(yùn)輸與車輛調(diào)度模型構(gòu)建如下:目標(biāo)函數(shù):min∑m∈Μ∑i∈FE∑j∈FEΤ∑t=1CΤm?Ymitj(t+tmij)?tmij(1)min∑m∈M∑i∈FE∑j∈FE∑t=1TCTm?Ymitj(t+tmij)?tmij(1)+∑g∈G∑i∈FEΤ∑t=1∑m∈Μ∑m′∈ΜCFgmm′i?Xgmm′it(t+1)(2)+∑g∈G∑i∈RΤ∑t=1CDgi?RDgit(3)約束條件:∑m∈Μi′∈EXmgiti′t=SDgi(t-1)+SΝgit-SDgit,i∈S,g∈G,t∈T(4)-∑m∈Μi′∈EXmgi′tit=-RDgi(t-1)-RΝgit+RDgit,i∈R,g∈G,t∈T(5)∑j∈FEXmgj(t-tmji)it+∑m′∈ΜXgm′mi(t-1)t+Xmgi′tit=∑j∈FEXgmitj(t+tmij)+∑m′∈ΜXgmm′it(t+1)+Xmgiti′t,i∈FE,t∈Τ,g∈G,m∈Μ,i′∈R∪S(6)SDgit,SNgit,RDgit,RNgit,Xgmitj(t+tmij),Xgmm′it(t+1)≥0(7)VAmit+∑j∈FEYmj(t-tmji)it+VDmi(t-1)=∑j∈FEYgmitj(t+tmij)+VDmit,i∈FE,t∈T,m∈M(8)Ymitj(t+tmij)≤ACapmij,t∈T,m∈M,(i,j)∈CA(9)Ymitj(t+tmij)≥0且為整數(shù);VDmit≥0且為整數(shù)(10)∑g∈GXgmitj(t+tmij)?Ρg≤VCapm?Ymitj(t+tmij),t∈Τ,m∈Μ,(i,j)∈CA(11)以上模型的開始時(shí)刻可以定為貨物的最早起運(yùn)時(shí)間,它的目標(biāo)函數(shù)分為三部分,分別是:①車輛的行駛費(fèi)用;②改變貨物運(yùn)輸方式所引起的模式轉(zhuǎn)換費(fèi)用;③表示需求延期滿足所引起的目標(biāo)函數(shù)增加值,其中CDgi就是需求貨物的延期罰函數(shù)系數(shù)。它的約束條件可以分為三類,分別是:①貨物流約束;②車輛流約束;③貨物流與車輛流關(guān)聯(lián)約束式。貨物流約束包括模型中(4)~(7)式,其中約束式(4)是供應(yīng)點(diǎn)貨物流引出約束,它表示供應(yīng)點(diǎn)向網(wǎng)絡(luò)發(fā)送救援物資的量與庫存量的關(guān)系,等式左邊是g貨物在i點(diǎn)向其映像點(diǎn)流出的貨物流,等式右邊是i點(diǎn)上一時(shí)段延期到本時(shí)段未起運(yùn)貨物量加上新增供應(yīng)量再減去延期到下一時(shí)段以后起運(yùn)的貨物量。約束式(5)是需求點(diǎn)貨物流引出約束,它表示需求點(diǎn)從網(wǎng)絡(luò)中接收救援物資的量與未滿足及新增貨物需求的關(guān)系,它與(4)式分別定義了供應(yīng)點(diǎn)與需求點(diǎn)的貨物流平衡。約束式(6)是中轉(zhuǎn)點(diǎn)或映像點(diǎn)貨物流平衡約束,等式左邊表示貨物流入量,等式右邊表示貨物流出量,它表示進(jìn)入中轉(zhuǎn)點(diǎn)或映像點(diǎn)的貨物量等于離開該點(diǎn)的貨物量。其中Xmgi′tit表示如果對(duì)于g貨物i點(diǎn)是供應(yīng)映像點(diǎn),從供應(yīng)點(diǎn)向供應(yīng)映像點(diǎn)發(fā)送的貨物量;Xmgiti′t表示如果對(duì)于g貨物i點(diǎn)是需求映像點(diǎn),則需求映像點(diǎn)向需求點(diǎn)發(fā)送的貨物量;約束式(7)是非負(fù)約束。車輛流約束包括模型中的(8)~(10)式,其中約束式(8)是車輛流平衡約束,這個(gè)式子約束進(jìn)入中轉(zhuǎn)點(diǎn)或映像點(diǎn)的車輛數(shù)等于完成任務(wù),停在該點(diǎn)的車輛數(shù)與離開該點(diǎn)的車輛數(shù)之和。(9)式是車輛流上界約束,它表示通過(i,j)弧的車輛數(shù)不能超過道路的容量。(10)約束式是表示車輛流決策變量不為負(fù)并且都為整數(shù)。貨物流與車輛流關(guān)聯(lián)約束式(11)表示的是貨物流與車輛流之間的關(guān)系。上述約束中貨物流約束表示貨物流從供應(yīng)點(diǎn)流向需求點(diǎn)應(yīng)該滿足的條件,車輛流約束是限制車輛的流轉(zhuǎn)關(guān)系,它們從約束式上看是獨(dú)立的,它們之間就是通過關(guān)聯(lián)約束式集成為一個(gè)整體,共同表示為應(yīng)急救援物資運(yùn)輸與車輛調(diào)度問題的數(shù)學(xué)模型。救援物資運(yùn)輸問題是研究如何高效地調(diào)度車輛將救援物資從供應(yīng)點(diǎn)運(yùn)輸?shù)叫枨簏c(diǎn),這里車輛通過“運(yùn)載”與貨物發(fā)生關(guān)系,關(guān)聯(lián)約束式表示通過載重弧(i,j)的貨物重量不能大于通過車輛的載重量來約束貨物流與車輛流的流量關(guān)系,從而將貨物運(yùn)輸與車輛配送統(tǒng)一起來,形成了完整的描述應(yīng)急救援物資運(yùn)輸與車輛調(diào)度問題的約束集。2.3分時(shí)段計(jì)劃方式由于在大規(guī)模自然災(zāi)害發(fā)生時(shí),信息處于不對(duì)稱狀態(tài),這時(shí)向?yàn)?zāi)害發(fā)生地調(diào)運(yùn)救援物資往往帶有一定的盲目性。隨著應(yīng)急反應(yīng)部門相互溝通與信息反饋,這時(shí)上一級(jí)的應(yīng)急管理部門才能夠比較準(zhǔn)確地估計(jì)災(zāi)害發(fā)生地需要物資的種類、數(shù)量等參數(shù)。在此過程中物資供應(yīng)量、需求量以及車輛數(shù)都會(huì)經(jīng)常發(fā)生變化,應(yīng)急物資運(yùn)輸與車輛調(diào)度計(jì)劃也需隨之調(diào)整。對(duì)此在構(gòu)建應(yīng)急物資運(yùn)輸模型時(shí)考慮到上述因素,采用分時(shí)段計(jì)劃方式,加入?yún)?shù)調(diào)整量,從而可以比較方便地根據(jù)參數(shù)變化重新調(diào)整計(jì)劃。對(duì)于應(yīng)急物資運(yùn)輸計(jì)劃按照以下方式調(diào)整:(1)SNgit、RNgit、VAmit按照變化量進(jìn)行調(diào)整,因?yàn)樵跒?zāi)害應(yīng)急場景下,貨物供應(yīng)量與車輛數(shù)都會(huì)隨著動(dòng)員范圍逐漸擴(kuò)大而增加,不需要考慮負(fù)值情況。如果RNgit<0,則取RDgit=max(RNgit+RDgit,0),其中t是上一個(gè)計(jì)劃期的最后一個(gè)時(shí)段。(2)對(duì)于上一階段已分配運(yùn)輸任務(wù)但還沒有到達(dá)目的地的車輛不再調(diào)整其運(yùn)輸任務(wù)。對(duì)貨物需求量與供應(yīng)量調(diào)整如下:本時(shí)段的延期滿足貨物需求量等于上一個(gè)計(jì)劃期最后一個(gè)時(shí)段的未滿足貨物需求量。本時(shí)段的延期運(yùn)輸貨物供應(yīng)量等于上一個(gè)計(jì)劃期最后一個(gè)時(shí)段的貨物供應(yīng)量。(3)調(diào)整計(jì)劃中的可用車輛數(shù)是以下幾部分組成:①本時(shí)段新加入救援物資運(yùn)輸任務(wù)的車輛;②以前時(shí)段征集準(zhǔn)備承擔(dān)救援物資運(yùn)輸任務(wù),但一直沒有使用的車輛;③當(dāng)前時(shí)段停留在當(dāng)?shù)氐却氯蝿?wù)的車輛,因?yàn)檫@一部分車輛可能在上一個(gè)計(jì)劃中就計(jì)劃在以后某時(shí)段離開?？奎c(diǎn),因此車輛數(shù)在后面時(shí)段可能會(huì)減少。因此我們需要根據(jù)前一個(gè)計(jì)劃判斷出該點(diǎn)等待車輛數(shù)不再減少的時(shí)段t′,將t′時(shí)段后在該點(diǎn)原地待命的車輛作為新計(jì)劃該點(diǎn)的可用車輛,將其作為新增車輛加入到新計(jì)劃中。3解決算法的設(shè)計(jì)3.1拉式子問題的求解應(yīng)急物資運(yùn)輸與車輛調(diào)度模型是一個(gè)混合整形規(guī)劃,僅車輛流部分就包括CA·T·Ym個(gè)整形決策變量,如果簡單地采用單純形法與分支定界法解決此問題,車輛數(shù)、運(yùn)輸方式、計(jì)劃周期等變量數(shù)的增加將會(huì)使計(jì)算復(fù)雜性以指數(shù)方式遞增,滿足不了應(yīng)急反應(yīng)過程中快速、高效的需要。從應(yīng)急物資運(yùn)輸與車輛調(diào)度模型分析,整個(gè)模型約束分成可以分成貨物流約束與完成貨物運(yùn)輸任務(wù)而產(chǎn)生的車輛流約束兩部分,而且目標(biāo)函數(shù)也可以分為與貨物流相關(guān)的運(yùn)輸模式轉(zhuǎn)換費(fèi)和需求延期懲罰費(fèi),以及與車輛流相關(guān)的車輛行駛費(fèi)用兩部分。它們通過貨物流與車輛流關(guān)聯(lián)約束式聯(lián)系。如果能夠使用方法松弛該關(guān)聯(lián)約束,就可以將應(yīng)急物資運(yùn)輸與車輛調(diào)度模型分為貨物運(yùn)輸模型與車輛調(diào)度模型兩個(gè)子問題,這將會(huì)大大降低該模型求解的計(jì)算復(fù)雜度。根據(jù)以上分析,以LargangianRelaxation為基礎(chǔ)求解該模型,將關(guān)聯(lián)約束乘上拉氏乘子后加入目標(biāo)函數(shù)中,這個(gè)方法類似在問題的目標(biāo)函數(shù)中對(duì)每一條貨物重量超過車輛容量的弧施以罰數(shù),迭代計(jì)算出合適的拉氏乘子向量組,再求出原問題的最優(yōu)解。應(yīng)用拉式松弛后,目標(biāo)函數(shù)成為min(1)+(2)+(3)+∑m∈Μ∑i∈FE∑j∈FEΤ∑t=1Wmijt(∑g∈GXgm′itj(t+tmij)?Ρg)(12)-∑m∈Μ∑i∈FE∑j∈FEΤ∑t=1Wmijt(VCapm?Ymitj(t+tmij))(13)其中,Wmijt是拉氏乘子向量組。通過以上變化后,應(yīng)急物資運(yùn)輸與車輛調(diào)度模型的拉式子問題由以上目標(biāo)函數(shù)與(4)~(10)約束組成,以下簡稱為Lag(OP)。將關(guān)聯(lián)約束松弛以后可以將Lag(OP)分為Lag1(X)貨物流和Lag2(Y)車輛流兩個(gè)子問題分別計(jì)算,其中Lag1(X)是目標(biāo)函數(shù)為(2)式、(3)式、(12)式組成,約束集由(4)~(7)組成,由于在拉式子問題去掉了關(guān)聯(lián)約束,這就可能會(huì)出現(xiàn)載重弧上的貨物流重量超過弧容量,為了避免這個(gè)問題,在Lag1(X)加入貨物流上界約束(14):∑g∈GXgmitj(t+tmij)?Ρg≤ACapmij?VCapm,m∈M,t∈T,i∈FE,j∈FE(14)Lag2(Y)問題的目標(biāo)函數(shù)由(1)式與(13)式組成,約束集由式(8)~(10)組成。求解Lag(OP)最優(yōu)解的計(jì)算步驟如下:步驟1:求解Lag(OP)整形松弛問題的解,如果沒有得到解,則終止運(yùn)算,原問題沒有可行解。如果得到Lag(OP)整形松弛問題的解S*,則設(shè)置迭代計(jì)數(shù)k=1,問題低界解LB=S*,最初的拉氏乘子W0mijt=0。求任意一個(gè)原問題的可行解S′.設(shè)置Lag(OP)最優(yōu)解OP*=S′.執(zhí)行步驟2。步驟2:通過子梯度法來計(jì)算拉氏乘子問題,首先分別計(jì)算Lag1(X)和Lag2(Y),得到最優(yōu)解Xk與Yk,利用這兩個(gè)解計(jì)算出Lag(OP)的目標(biāo)函數(shù)值Sk.如果Sk>LB,則LB=Sk.判斷Xk和Yk是否滿足關(guān)聯(lián)約束,如果滿足且Sk<OP*,則OP*=Sk,執(zhí)行步驟3;如果不滿足則執(zhí)行步驟3。步驟3:判斷以下循環(huán)退出條件:(a)判斷Xk與Yk是否滿足條件關(guān)聯(lián)約束式左值等于右值;(b)(OP*-LB)/OP*<α;(c)k=TK.其中滿足條件(a),當(dāng)前Sk就是問題的最優(yōu)解,輸出Sk.α為收斂率,如果當(dāng)前OP*距離低界解LB的比率小于α,認(rèn)為OP*是可接受解,且輸出OP*.TK是循環(huán)次數(shù)限制,滿足條件(c)直接退出,將當(dāng)前的最優(yōu)解輸出。如果以上退出條件都不滿足,則執(zhí)行步驟4。步驟4:計(jì)算拉氏乘子的步長θk,設(shè)λ為比例因子,初始值為2,將Xk和Yk計(jì)代入下式計(jì)算步長θk=λ?(ΟΡ*-LB)/∑m∈Μ∑i∈FE∑j∈FEΤ∑t=1(∑g∈GXgmitj(t+tmij)?Ρg-Ymitj(t+tmij)?VCapm)2,為保證目標(biāo)函數(shù)的值收斂,如果在三次循環(huán)中LB值不增加,則減少λ=λ/2。執(zhí)行步驟5。步驟5:計(jì)算拉氏乘子,計(jì)算Wk+1mijt=Wkmijt+θk?(∑g∈GXgmitj(t+tmij)?Ρg-Ymitj(t+tmij)?VCapm),因?yàn)閃kmijt必須滿足非負(fù)條件,所以Wk+1mijt=max(0,Wk+1mijt),設(shè)k=k+1,轉(zhuǎn)步驟2。3.2多模式分層網(wǎng)絡(luò)模型①貨物流問題Lag1(X)的目標(biāo)函數(shù)是(2)式、(3)式與(12)式的和,約束集由(4)~(7)和(14)式組成,在多模式分層網(wǎng)絡(luò)中Lag1(X)可以分析為多種救援物資的多貨物最小費(fèi)用流問題,通過應(yīng)用列生成法等算法可以計(jì)算最小費(fèi)用流。其中(2)與(12)式可以直接表示為弧的費(fèi)用,對(duì)于(3)式需要轉(zhuǎn)換為弧形式,如計(jì)算g貨物到l需求點(diǎn)最短路時(shí),網(wǎng)絡(luò)上弧(i,j)的需求延期滿足費(fèi)率=tmij·CDgi.如果救援物資運(yùn)輸?shù)哪繕?biāo)是時(shí)間最短而不考慮費(fèi)用(這會(huì)在救援物資需求與生命損失密切相關(guān)的情況下出現(xiàn)),則將(2)式移除后求解就得到運(yùn)輸時(shí)間最短的路線。②車輛流問題Lag2(Y)的目標(biāo)函數(shù)是(1)式與(13)式的和,約束集由(8)~(10)式組成的整數(shù)規(guī)劃。解決該問題可以將多模式分層網(wǎng)絡(luò)中每個(gè)模式層單獨(dú)求解。在每個(gè)模式層的時(shí)空網(wǎng)絡(luò)中,增加一個(gè)中轉(zhuǎn)點(diǎn),該點(diǎn)通過入弧與時(shí)空網(wǎng)絡(luò)期末各FE點(diǎn)相連,入弧的關(guān)聯(lián)費(fèi)用為零,上界約束為無窮。通過出弧與時(shí)空網(wǎng)絡(luò)上每一個(gè)VAmit大于零的FE點(diǎn)相連,出弧的關(guān)聯(lián)費(fèi)用為零,上下界約束都為VAmit,這就將Lag2(Y)問題轉(zhuǎn)換為最小費(fèi)用循環(huán)流問題,可