《應(yīng)急物流路徑優(yōu)化問(wèn)題研究9800字（論文）》

\o"79296:基于遺傳算法的震后軍事應(yīng)急物流路徑優(yōu)化的研究"\t"3:81/Crm/Task/_blank"基于遺傳算法的應(yīng)急物流路徑優(yōu)化的研究目錄TOC\o"1-3"\h\u301541.緒論 .緒論1.1研究背景面對(duì)頻繁的自然災(zāi)害，不斷完善防災(zāi)體系，必須繼續(xù)改善自然災(zāi)害發(fā)生后的應(yīng)急管理。在發(fā)生自然災(zāi)害時(shí)，救災(zāi)工作的有效性在很大程度上取決于應(yīng)急后勤系統(tǒng)的有效運(yùn)作。目前，應(yīng)急物流領(lǐng)域的研究已引起社會(huì)各界的關(guān)注。中國(guó)目前在應(yīng)急物流領(lǐng)域的研究可以分為：應(yīng)急資源的分配與規(guī)劃，應(yīng)急物流網(wǎng)絡(luò)，應(yīng)急物流計(jì)劃，評(píng)估應(yīng)急物流的有效性，應(yīng)急物流系統(tǒng)和應(yīng)急物流決策支持。作為自然災(zāi)害后緊急救援行動(dòng)的重要組成部分，對(duì)應(yīng)急資源的分配和調(diào)度的研究主要包括為武警部隊(duì)在應(yīng)急后勤運(yùn)送車(chē)輛和物資分配的問(wèn)題。其中，緊急情況下車(chē)輛路徑任務(wù)的有效優(yōu)化實(shí)施，是提高應(yīng)急救援水平，提高應(yīng)急能力的重要保證[1]。盡管近年來(lái)，中國(guó)各級(jí)政府在應(yīng)對(duì)自然災(zāi)害時(shí)的緊急情況管理方面做得非常出色而富有成果，但應(yīng)對(duì)重大災(zāi)害的被動(dòng)形勢(shì)卻揭示了應(yīng)急機(jī)制，物資儲(chǔ)備和優(yōu)化的決策過(guò)程。缺乏尊重。同時(shí)，中國(guó)的公共衛(wèi)生基礎(chǔ)設(shè)施發(fā)展欠佳，在緊急情況下缺乏經(jīng)驗(yàn)。為了最大程度地減少自然災(zāi)害造成的損失并確保受影響人員的生命和財(cái)產(chǎn)安全，不僅需要對(duì)實(shí)施緊急物流的內(nèi)涵、法律機(jī)制和方法進(jìn)行系統(tǒng)的研究，而且還需要在銷(xiāo)售渠道中緊急運(yùn)輸物料的車(chē)輛。進(jìn)一步研究了優(yōu)化決策理論和任務(wù)路由方法，以提高應(yīng)急物流的效率。1.2研究意義基于應(yīng)急物流的特點(diǎn)和車(chē)輛路徑問(wèn)題的模型，建立了應(yīng)急車(chē)輛路徑優(yōu)化的優(yōu)化系統(tǒng)。根據(jù)該優(yōu)化系統(tǒng)，建立了適當(dāng)?shù)臄?shù)學(xué)模型，并在車(chē)輛路徑問(wèn)題的優(yōu)化過(guò)程中添加了建模解決方案的幾個(gè)參數(shù)，例如：各種運(yùn)輸材料的重要權(quán)重，時(shí)間限制，交通擁堵條件和懲罰函數(shù)參數(shù)，對(duì)各種影響的定量評(píng)估關(guān)于運(yùn)輸計(jì)劃有效性的可變決策。本文將目標(biāo)距離最小的傳統(tǒng)運(yùn)輸車(chē)輛問(wèn)題轉(zhuǎn)化為運(yùn)輸規(guī)劃效率最高的應(yīng)急物流車(chē)輛的多用途任務(wù)，為進(jìn)一步研究武警部隊(duì)在應(yīng)急物流運(yùn)輸車(chē)輛的多用途問(wèn)題提供了理論依據(jù)。本文具有重要的實(shí)踐意義。1.3國(guó)內(nèi)外研究現(xiàn)狀1.3.1國(guó)外研究現(xiàn)狀Fiedrich(2000)[2]探討了在有限的時(shí)間，資源的數(shù)量和質(zhì)量的情況下，討論了資源的有效利用以提高救援質(zhì)量并最大程度地減少死亡人數(shù)，并開(kāi)發(fā)了一種優(yōu)化的計(jì)劃模型，以將資源分配和運(yùn)輸?shù)降卣鸷笫転?zāi)的多個(gè)地方。JaeYoungChoi(2003)[3]介紹了在未定義道路網(wǎng)絡(luò)的情況下如何分配有限的資源（例如救護(hù)車(chē)和其他應(yīng)急設(shè)備）以將受害者運(yùn)送到醫(yī)院，目標(biāo)是最大程度地增加受救者人數(shù)。Linet(2004)[4]討論了緊急運(yùn)輸計(jì)劃，該研究假設(shè)當(dāng)前和將來(lái)的物料供應(yīng)有限，當(dāng)前所需的物料數(shù)量已知，并且可以預(yù)測(cè)未來(lái)所需的物料數(shù)量。假定不應(yīng)將車(chē)輛返回到庫(kù)存點(diǎn)，并且車(chē)輛的分配過(guò)程由一系列“斷點(diǎn)”路線組成。目標(biāo)是在請(qǐng)求的時(shí)間內(nèi)使救援中心的需求最大化。該模型從幾個(gè)要素分為兩個(gè)網(wǎng)絡(luò)流量問(wèn)題。P1是線性的，以使需求點(diǎn)處的項(xiàng)目滿意度最大化，P2是一個(gè)整數(shù)，以使車(chē)輛達(dá)到最大化認(rèn)識(shí)P1。這兩個(gè)模型通過(guò)拉格朗日松弛的迭代同時(shí)求解。Jiuh-BingSheu(2010)如果大規(guī)模自然災(zāi)害發(fā)生后沒(méi)有足夠的信息，本文提出了一種用于應(yīng)急物流運(yùn)作的動(dòng)態(tài)緊急需求管理模型，包括以下步驟：①數(shù)據(jù)集中以預(yù)測(cè)受災(zāi)地區(qū)的物質(zhì)需求；②使用模糊聚類(lèi)將所有災(zāi)難分為幾組：③使用幾組標(biāo)準(zhǔn)來(lái)確定這些組的優(yōu)先級(jí)。他還通過(guò)實(shí)例驗(yàn)證了信息不完全的模型的動(dòng)態(tài)預(yù)測(cè)和需求分配效果，實(shí)驗(yàn)結(jié)果表明模型總誤差小于10％。1.3.2國(guó)內(nèi)研究現(xiàn)狀繆成、許維勝、吳啟迪(2006)[5]結(jié)合救援物資的運(yùn)輸和商業(yè)運(yùn)輸?shù)母鞣N特點(diǎn)，表明了救援物資的運(yùn)輸問(wèn)題將幾個(gè)貨運(yùn)網(wǎng)絡(luò)中的流動(dòng)問(wèn)題與多個(gè)起止點(diǎn)和幾種運(yùn)輸方式結(jié)合起來(lái)，并規(guī)劃了車(chē)輛的滿載問(wèn)題，并以此為基礎(chǔ)描述這個(gè)問(wèn)題。通過(guò)遞延計(jì)算成本和時(shí)間的方法，由分層網(wǎng)絡(luò)構(gòu)建多功能數(shù)學(xué)編程模型。本文提出了一種基于拉格朗日松弛法的解決方案，將原始問(wèn)題分解為兩個(gè)子任務(wù)：貨物流和交通流，分別使用混合貨物流和低成本流算法來(lái)解決。計(jì)算示例證實(shí)了該解決方案具有良好的收斂性和計(jì)算效率。盧茜(2009)[6]采用最短路徑理論選擇地震發(fā)生時(shí)應(yīng)急車(chē)輛的路徑，以最短時(shí)間和最大數(shù)量為主要思想。該模型考慮了時(shí)間、交通量、交通強(qiáng)度和其他因素之間的內(nèi)部關(guān)系，以及交通流和影響安全性的因素的理論，定量確定了實(shí)際任務(wù)中時(shí)間和交通量的數(shù)學(xué)表達(dá)式，并建立了地震緊急情況的物流系統(tǒng)。用于選擇平均道路上的運(yùn)輸路線的模型。鄧敏皓、文振華(2011)[7]由于對(duì)企業(yè)和個(gè)人的緊急物流有嚴(yán)格的時(shí)間要求，因此提出了一種改進(jìn)的層次分析法來(lái)解決此類(lèi)問(wèn)題。為了減少判斷矩陣的一致性檢查的計(jì)算，對(duì)可以獲取精確值的因子進(jìn)行加權(quán)平均計(jì)算。通過(guò)測(cè)試，改進(jìn)的AHP建模的結(jié)果變得更加合理。2.相關(guān)概念2.1應(yīng)急物流概述2.1.1應(yīng)急物流的定義應(yīng)急物流是一項(xiàng)特殊的物流活動(dòng)，可根據(jù)緊急情況為材料，人員和設(shè)施的需求提供緊急支持。緊急情況包括嚴(yán)重的自然災(zāi)害，應(yīng)急公共衛(wèi)生事件，公共安全事件和軍事沖突的建設(shè)。與常規(guī)物流不同，緊急物流包括液體、載體、流向、過(guò)程、流量和其他因素以及時(shí)空的利用。在大多數(shù)情況下，應(yīng)急物流通過(guò)物流效率實(shí)現(xiàn)其物流優(yōu)勢(shì)，而常規(guī)物流則強(qiáng)調(diào)效率和有效性。2.1.2應(yīng)急物流的性質(zhì)與特點(diǎn)(1)應(yīng)急物流的性質(zhì)應(yīng)急物流系統(tǒng)受社會(huì)利益驅(qū)動(dòng)，為受災(zāi)地區(qū)的人們提供服務(wù)。當(dāng)前，中國(guó)應(yīng)急物流的特點(diǎn)如下：政府高度重視企業(yè)的積極參與，軍民相互配合，軍方擁有強(qiáng)大的登陸部隊(duì)，通常需要提前進(jìn)行準(zhǔn)備工作并進(jìn)行前期準(zhǔn)備。(2)應(yīng)急物流的特點(diǎn)①突發(fā)性和不可預(yù)測(cè)性。這是應(yīng)急物流區(qū)別于一般物流的最明顯特征。②時(shí)間約束緊迫性。應(yīng)急物流的服務(wù)對(duì)象,即受災(zāi)群眾對(duì)物資的需求非常緊迫,關(guān)系到生命安全。③弱經(jīng)濟(jì)性。應(yīng)急后勤的原則是通過(guò)科學(xué)合理地分配勞動(dòng)力、物資、設(shè)施和其他資源，在自然災(zāi)害影響的地方盡可能地挽救人們，并執(zhí)行后勤任務(wù)。物流速度的重要性高于物流成本，這與一般物流不同。④政府與市場(chǎng)共同參與。2.1.3應(yīng)急物流的主要缺陷 面對(duì)突發(fā)的自然災(zāi)害,應(yīng)急物流過(guò)程當(dāng)中最主要的問(wèn)題是出現(xiàn)“救援真空”?！熬仍婵铡北硎緸?zāi)害發(fā)生后到災(zāi)民得到救援的這段時(shí)間。導(dǎo)致“救援真空”出現(xiàn)的原因主要有以下幾點(diǎn):(1)信息不暢通。重大災(zāi)害發(fā)生后通信設(shè)備一般會(huì)再短時(shí)間處于癱瘓狀態(tài),使得災(zāi)區(qū)與外界信息的交流中段。(2)物流路段不暢通。災(zāi)害發(fā)生后,尤其是大地震往往會(huì)伴隨山體崩塌,造成道路中段,導(dǎo)致部分物流路段通行受阻,影響了物資運(yùn)輸進(jìn)度。(3)災(zāi)區(qū)物資需求點(diǎn)的需求時(shí)間限制。災(zāi)害發(fā)生后,各受災(zāi)區(qū)需求點(diǎn)對(duì)物資的需求具有時(shí)間限制,而由于總體運(yùn)輸任務(wù)重、人員及車(chē)輛不充等原因,難以將物資及時(shí)送往各個(gè)受災(zāi)點(diǎn)。此外,在制定貨運(yùn)代理工作計(jì)劃的過(guò)程中，考慮到災(zāi)區(qū)人們對(duì)各種材料的緊迫性也很重要。例如，地震后的早期階段的應(yīng)急后勤應(yīng)集中于運(yùn)輸醫(yī)療材料，隨后集中于食品，帳篷，毯子和其他生活材料。在一定時(shí)間段內(nèi)，如果在此時(shí)間間隔內(nèi)無(wú)法滿足需求，則將影響災(zāi)區(qū)人民的生命和安全以及緊急安全隱患的相關(guān)費(fèi)用。各種材料需求的緊迫性應(yīng)與緊急安全隱患的成本線性相關(guān)。在宏觀層面上存在的不足主要在于:(1)應(yīng)急平臺(tái)系統(tǒng)不完善,影響應(yīng)急物流效率。(2)應(yīng)急預(yù)案不完善。(3)國(guó)家應(yīng)急救援物資儲(chǔ)備不足。(4)缺少第三方物流企業(yè)的參與。(5)缺少應(yīng)急救援專(zhuān)業(yè)隊(duì)伍。2.2車(chē)輛路徑優(yōu)化理論概述2.2.1車(chē)輛路徑問(wèn)題的定義車(chē)輛路徑問(wèn)題(VehicleRoutingProblem,簡(jiǎn)稱(chēng)VRP)是指在一定的約束下,根據(jù)已知的待服務(wù)客戶(hù)的網(wǎng)點(diǎn)布局、物流配送中心的位置、車(chē)輛的最大負(fù)荷等信息,為車(chē)隊(duì)組織出適當(dāng)?shù)男熊?chē)路線分送貨物。在滿足客戶(hù)的需求的同時(shí),實(shí)現(xiàn)諸如路程最短、成本最小、耗費(fèi)時(shí)間最少等目標(biāo)。車(chē)輛路徑問(wèn)題是現(xiàn)代物流系統(tǒng)研究中的一項(xiàng)重要內(nèi)容。通過(guò)規(guī)劃合理的運(yùn)輸路線,優(yōu)化配置各類(lèi)資源,可以提升對(duì)客戶(hù)的響應(yīng)速度,降低運(yùn)輸成本并提高服務(wù)質(zhì)量。2.2.2車(chē)輛路徑問(wèn)題需滿足的前提條件車(chē)輛路徑問(wèn)題存在不同的優(yōu)化模型,但一般而言車(chē)輛路徑問(wèn)題的研究需滿足一下條件假設(shè):(1)客戶(hù)即需求點(diǎn)的位置可知;(2)配送中心與各個(gè)客戶(hù)即需求點(diǎn)的距離矩陣可知;(3)所有參與配送任務(wù)的車(chē)輛都以配送中心為起點(diǎn),并在完成運(yùn)輸任務(wù)后返回配送中心;(4)每一條配送路徑上各個(gè)客戶(hù)即需求點(diǎn)的總需求量不超過(guò)車(chē)輛負(fù)載;(5)每個(gè)客戶(hù)即需求點(diǎn)的需求由且僅由一輛車(chē)來(lái)滿足。2.2.3車(chē)輛路徑問(wèn)題的模型分類(lèi)按照車(chē)輛路徑問(wèn)題所涉及的各類(lèi)因素,可以對(duì)車(chē)輛路徑問(wèn)題的模型進(jìn)行劃分:(1)按照供應(yīng)點(diǎn)與需求點(diǎn)數(shù)量劃分:包括單供應(yīng)點(diǎn)多需求點(diǎn)的簡(jiǎn)單車(chē)輛路徑問(wèn)題與多供應(yīng)點(diǎn)多需求點(diǎn)的復(fù)雜車(chē)輛路徑問(wèn)題;(2)按有無(wú)時(shí)間限制劃分:包括有時(shí)間窗限制的車(chē)輛路徑問(wèn)題(VehicleRoutingProblemwithTimeWindow,VRPTW)與無(wú)時(shí)間窗限制的車(chē)輛路徑問(wèn)題。其中時(shí)間窗限制有分為硬時(shí)間窗限制與軟時(shí)間窗限制,硬時(shí)間窗車(chē)輛路徑問(wèn)題要求每項(xiàng)運(yùn)輸任務(wù)必須在指定的時(shí)間內(nèi)完成;軟時(shí)間窗車(chē)輛路徑問(wèn)題指對(duì)于未在指定時(shí)間內(nèi)完成運(yùn)輸任務(wù)給以一定的懲罰。如果將對(duì)單個(gè)點(diǎn)的運(yùn)輸任務(wù)效率與到達(dá)時(shí)間的線性關(guān)系作比較,能夠更加直觀地分析硬時(shí)間窗與軟時(shí)間窗的區(qū)別,如下圖2.1與圖2.2:圖中,p表示對(duì)于單個(gè)需求點(diǎn)運(yùn)輸任務(wù)完成的效率,t表示貨物到達(dá)的時(shí)間,et表示時(shí)間窗的最早到達(dá)時(shí)間,lt表示時(shí)間窗的最晚到達(dá)時(shí)間,M表示運(yùn)輸任務(wù)的效率值。其中硬時(shí)間窗VRP問(wèn)題中,如果貨物在時(shí)間窗外到達(dá),則此需求點(diǎn)任務(wù)完成的效率為0。而軟時(shí)間窗VRP問(wèn)題中,如果貨物在時(shí)間窗外到達(dá),任務(wù)完成的效率呈線性關(guān)系遞減。圖2.1硬時(shí)間窗中效率與時(shí)間的關(guān)系圖2.2軟時(shí)間窗中效率與時(shí)間的關(guān)系(3)按客戶(hù)需求量與車(chē)輛負(fù)載大小劃分:包括滿載車(chē)輛路徑問(wèn)題和非滿載車(chē)輛路徑問(wèn)題。當(dāng)單個(gè)客戶(hù)需求量大于單車(chē)的載重負(fù)荷時(shí),這個(gè)需求點(diǎn)的運(yùn)輸任務(wù)要由一輛以上的車(chē)來(lái)完成,此類(lèi)車(chē)輛路徑問(wèn)題稱(chēng)為滿載車(chē)輛路徑問(wèn)題。當(dāng)單個(gè)客戶(hù)需求量小于單車(chē)的載重負(fù)荷時(shí),這個(gè)需求點(diǎn)的運(yùn)輸任務(wù)只需要由一輛車(chē)來(lái)完成,而一輛車(chē)可以完成一個(gè)以上的需求點(diǎn)的運(yùn)輸任務(wù),此類(lèi)車(chē)輛路徑問(wèn)題稱(chēng)為非滿載車(chē)輛路徑問(wèn)題。按客戶(hù)需求類(lèi)型劃分:包括確定型需求車(chē)輛路徑問(wèn)題、模糊需求車(chē)輛路徑問(wèn)題(FuzzyVehicleRoutingProblem,FVRP)以及隨機(jī)需求車(chē)輛路徑問(wèn)題(VehicleRoutingProblemwithStochasticDemand,VRPSD)。隨機(jī)需求車(chē)輛路徑問(wèn)題是指雖然明白客戶(hù)即需求點(diǎn)的位置,但無(wú)法準(zhǔn)確地指定客戶(hù)的需求量。模糊需求車(chē)輛路徑問(wèn)題是指在車(chē)輛調(diào)度的過(guò)程當(dāng)中,面對(duì)某些客戶(hù)無(wú)法給出準(zhǔn)確需求信息的情況,將模糊概念引入模型來(lái)解決此類(lèi)問(wèn)題。確定性需求車(chē)輛路徑問(wèn)題則指對(duì)客戶(hù)即需求點(diǎn)的位置、需求量等信息都明確的車(chē)輛路徑問(wèn)題。2.3遺傳算法的概念遺傳算法(GeneticAlgorithm,GA)是模擬達(dá)爾文生物進(jìn)化論的自然選擇和遺傳學(xué)機(jī)理的生物進(jìn)化過(guò)程的計(jì)算模型,是一種通過(guò)模擬自然進(jìn)化過(guò)程搜索最優(yōu)解的方法,它最初由美國(guó)Michigan大學(xué)約翰·霍蘭德(J.Holland)教授于1975年首先提出來(lái)的,并出版了頗有影響的專(zhuān)著《AdaptationinNaturalandArtificialSystems》,來(lái)的,并出版了頗有影響的專(zhuān)著《AdaptationinNaturalandArtificialSystems》,GA這個(gè)名稱(chēng)才逐漸為人所知,J.Holland教授所提出的GA通常為簡(jiǎn)單遺傳算法(SimpleGeneticAlgorithm,SGA)。1975年,J.Holland的學(xué)生DeJong在其博士論文“Ananalysisofthebehaviorofaclassofgeneticadaptivesystems”一文中結(jié)合Holland的模式定理進(jìn)行了大量的函數(shù)優(yōu)化試驗(yàn),將遺傳算法的思想運(yùn)用于最優(yōu)化問(wèn)題當(dāng)中。20世紀(jì)80年代是遺傳算法的發(fā)展階段,Holland實(shí)現(xiàn)了第一個(gè)基于遺傳算法的及其學(xué)習(xí)系統(tǒng)——分類(lèi)系統(tǒng),提出了遺傳算法的機(jī)器學(xué)習(xí)的新概念,為分類(lèi)器在構(gòu)造上提出了一個(gè)完整的框架。1989年,美國(guó)伊利諾大學(xué)的古爾德伯格(Goldberg)所著的“GeneticAlgorithminSearch,OptimizationandMachineLearning”對(duì)于遺傳算法的理論及其多領(lǐng)域的應(yīng)用展開(kāi)了較為全面的分析和例證,奠定了現(xiàn)代遺傳算法的科學(xué)基礎(chǔ)[42]。此后,許多專(zhuān)家與學(xué)者對(duì)簡(jiǎn)單遺傳算法提出了改進(jìn)措施,建立了許多遺傳算法的模型,從而使遺傳算法更加完善,被廣泛的應(yīng)用與各個(gè)領(lǐng)域。3.應(yīng)急物流車(chē)輛路徑問(wèn)題的優(yōu)化系統(tǒng)及模型構(gòu)建3.1應(yīng)急物流車(chē)輛路徑問(wèn)題的優(yōu)化系統(tǒng)構(gòu)建3.1.1系統(tǒng)的輸入(1)車(chē)輛信息:包括車(chē)輛行駛的平均速度、車(chē)輛的最大載重量、單位車(chē)輛行駛的固定成本與可變成本。對(duì)于所有成本最小化的車(chē)輛路徑問(wèn)題,車(chē)輛速度和載重負(fù)荷都是必須考慮的變量。另外在本系統(tǒng)的車(chē)輛單位成本中,劃分了固定成本與可變成本。固定成本即啟動(dòng)一輛車(chē)所需的必要成本,如駕駛車(chē)輛產(chǎn)生的人力成本;可變成本即為單位油耗、車(chē)輛磨損等,與車(chē)輛行駛路程呈線性關(guān)系的成本。(2)道路網(wǎng)絡(luò)信息:包括網(wǎng)絡(luò)中各配送點(diǎn)與災(zāi)區(qū)需求點(diǎn)的運(yùn)輸距離矩陣與道路阻塞情況。在車(chē)輛路徑問(wèn)題的一般模型中,道路網(wǎng)絡(luò)信息主要是指供應(yīng)點(diǎn)與需求點(diǎn)之間的距離,車(chē)輛行駛距離是成本最小化與最短時(shí)間優(yōu)化目標(biāo)需考慮的一般因素。(3)受災(zāi)區(qū)需求點(diǎn)信息:包括各需求點(diǎn)對(duì)各種物資需求量、物資需求的時(shí)間窗限制以及各物資的需求緊急程度。對(duì)于應(yīng)急類(lèi)的車(chē)輛路徑問(wèn)題,需要明確各災(zāi)區(qū)的需求量與各災(zāi)區(qū)的需求時(shí)間窗。作為考慮運(yùn)輸不同類(lèi)物資的車(chē)輛路徑問(wèn)題,需要引入需求緊急程度,以此量化不同物資的需求對(duì)于時(shí)間的敏感度。3.1.2系統(tǒng)的優(yōu)化過(guò)程(1)優(yōu)化目標(biāo):使總體應(yīng)急物流調(diào)度計(jì)劃的運(yùn)輸效率最高。在應(yīng)急物流車(chē)輛路徑問(wèn)題所需實(shí)現(xiàn)的多目標(biāo)優(yōu)化問(wèn)題當(dāng)中,既要考慮車(chē)輛行駛產(chǎn)生的成本,又要考慮時(shí)間的緊迫性。因?yàn)檐?chē)輛行駛成本最小化與時(shí)間窗限制不能同時(shí)得到滿足。運(yùn)輸計(jì)劃往往因?yàn)檫_(dá)不到時(shí)間窗的要求,所以在系統(tǒng)的優(yōu)化過(guò)程中加入超過(guò)時(shí)間窗的安全違背成本,將車(chē)輛的行駛成本與安全違背成本之和作為系統(tǒng)優(yōu)化的總體目標(biāo)。車(chē)輛的行駛成本與安全違背成本之和越小,則總體的運(yùn)輸效率越高。圖3.1應(yīng)急物流車(chē)輛路徑問(wèn)題的優(yōu)化系統(tǒng)(2)量化指標(biāo):對(duì)未滿足需求點(diǎn)時(shí)間窗要求的運(yùn)輸線路乘以相應(yīng)的懲罰因子,從而使得該運(yùn)輸路線產(chǎn)生相應(yīng)的應(yīng)急安全違背成本。對(duì)于不同物資的需求緊急程度賦于權(quán)重值,度量運(yùn)輸不同物資的車(chē)輛路線出現(xiàn)未滿足時(shí)間窗情況下的應(yīng)急安全違背成本。3.2應(yīng)急物流車(chē)輛路徑問(wèn)題的模型構(gòu)建3.2.1問(wèn)題描述本文所構(gòu)建的模型屬于多供應(yīng)點(diǎn)多需求點(diǎn)的帶軟時(shí)間窗非滿載類(lèi)車(chē)輛路徑優(yōu)化問(wèn)題。非滿載車(chē)輛路徑問(wèn)題指各個(gè)需求點(diǎn)的需求量都小于運(yùn)輸車(chē)輛的載重負(fù)荷,每輛車(chē)可以完成一個(gè)以上需求點(diǎn)的運(yùn)輸任務(wù)。應(yīng)急物流車(chē)輛路徑問(wèn)題模型可以描述為m個(gè)供應(yīng)點(diǎn),n個(gè)需求點(diǎn)。供應(yīng)點(diǎn)與需求點(diǎn)依次從1至m+n排序。運(yùn)輸計(jì)劃的車(chē)輛行駛成本為車(chē)輛的固定成本(與使用車(chē)輛的數(shù)量呈正比)以及車(chē)輛行駛的可變成本(與總行駛距離呈正比)之和。運(yùn)輸計(jì)劃的安全違背成本為各需求點(diǎn)的安全違背成本之和(考慮到達(dá)需求點(diǎn)的時(shí)間是否在時(shí)間窗內(nèi))。運(yùn)輸計(jì)劃的總成本即為車(chē)輛行駛成本與安全違背成本之和?？偝杀驹叫　⒖傂试酱?。求:總體效率最大化的應(yīng)急物流車(chē)輛路徑問(wèn)題的調(diào)度計(jì)劃。3.2.2問(wèn)題假設(shè)(1)要求每輛車(chē)的子路徑上送往各需求點(diǎn)的貨物重量總和Gk<q;k表示第k輛車(chē),Gk表示車(chē)輛k運(yùn)輸線路上經(jīng)過(guò)的所有需求點(diǎn)的需求總量;(2)每輛車(chē)同時(shí)運(yùn)輸兩種物資,每個(gè)需求點(diǎn)的物資運(yùn)輸任務(wù)只能由一輛車(chē)來(lái)完成,非滿載類(lèi)VRP問(wèn)題需求點(diǎn)的需求量小于車(chē)輛載重負(fù)荷;(3)每輛車(chē)可從任一供應(yīng)點(diǎn)出發(fā),并返回任一供應(yīng)點(diǎn);(4)每輛車(chē)不重復(fù)經(jīng)過(guò)任何一點(diǎn)。完成運(yùn)輸任務(wù)的車(chē)輛返回到距離最后一運(yùn)輸任務(wù)所到達(dá)需求點(diǎn)最近的供應(yīng)點(diǎn)。(5)未考慮運(yùn)輸任務(wù)過(guò)程當(dāng)中裝貨與卸貨的時(shí)間損耗;(6)所使用的車(chē)輛類(lèi)型一致,即載重負(fù)荷相等;(7)運(yùn)輸過(guò)程當(dāng)中,所有車(chē)輛只單向運(yùn)輸,即只送貨而不在需求點(diǎn)裝貨。3.2.3應(yīng)急安全違背成本的量化應(yīng)急安全違背成本就是因運(yùn)輸過(guò)程當(dāng)中,需求點(diǎn)對(duì)不同物資的需求的時(shí)間窗限制未得到滿足而產(chǎn)生的影響到相應(yīng)災(zāi)區(qū)群眾生命安全的成本。在本文的模型當(dāng)中,結(jié)合各災(zāi)區(qū)需求點(diǎn)的時(shí)間窗限制、不同物資的需求緊急程度,通過(guò)懲罰函數(shù)的形式將應(yīng)急安全違背成本量化,以完善目標(biāo)模型。(1)時(shí)間窗限制的懲罰函數(shù)對(duì)于未滿足時(shí)間窗限制的運(yùn)輸路線調(diào)度方案,所產(chǎn)生的應(yīng)急安全違背成本將通過(guò)懲罰函數(shù)表達(dá)出來(lái),到達(dá)某一指定需求點(diǎn)的時(shí)間距時(shí)間窗越久,那么這一點(diǎn)的應(yīng)急安全違背成本就越高,而在時(shí)間窗內(nèi)到達(dá)某一指定需求點(diǎn),則這一點(diǎn)不產(chǎn)生應(yīng)急安全違背成本,所有需求點(diǎn)的應(yīng)急安全違背成本之和即為運(yùn)輸線路調(diào)度計(jì)劃的應(yīng)急安全違背成本。對(duì)于某一指定的需求點(diǎn)其應(yīng)急安全違背成本的懲罰函數(shù)可以按如下方式表示:本文所采用的時(shí)間窗限制為軟時(shí)間窗限制(第二章中已做介紹),即未滿足時(shí)間窗限制所產(chǎn)生的懲罰隨到達(dá)時(shí)間距時(shí)間窗的間隔改變。從上述公式可以看出單個(gè)需求點(diǎn)的應(yīng)急安全違背成本與懲罰參數(shù)、到達(dá)時(shí)間與時(shí)間窗的兩端臨界值的差成正比例關(guān)系。不同物資的應(yīng)急安全違背成本量化。對(duì)于不同物資的應(yīng)急安全違背成本的度量，對(duì)物資需求緊急度高的物資,如果運(yùn)輸計(jì)劃的到達(dá)時(shí)間未滿足其時(shí)間窗要求,則應(yīng)急安全違背成本的增加相對(duì)彈性更大,需求緊急度低的物資,應(yīng)急安全違背成本的增加相對(duì)彈性較小。對(duì)于任何一個(gè)需求點(diǎn)來(lái)說(shuō),都同時(shí)存在對(duì)物資A與物資B的需求。因此,對(duì)于任何一個(gè)運(yùn)輸調(diào)度計(jì)劃,每個(gè)災(zāi)區(qū)需求點(diǎn)上的應(yīng)急安全違背成本都同時(shí)包括物資A與物資B各自引起的應(yīng)急安全違背成本,具體表述如下:3.2.4車(chē)輛載重負(fù)荷與道路阻塞(1)車(chē)輛載重負(fù)荷對(duì)于3.1節(jié)問(wèn)題描述中的車(chē)輛載重負(fù)荷限制,如果車(chē)輛出現(xiàn)超重行駛,則相應(yīng)引發(fā)安全違背成本的增加。這對(duì)此問(wèn)題的量化,在本模型中同樣采取懲罰函數(shù)的形式表述:當(dāng)車(chē)輛實(shí)際載重小于車(chē)輛載重負(fù)荷時(shí),安全違背成本為0。當(dāng)車(chē)輛實(shí)際載重大于車(chē)輛載重負(fù)荷時(shí),安全違背成本產(chǎn)生,并且本文模型假設(shè)中硬性規(guī)定車(chē)輛不得超負(fù)荷行駛,故M*的取值是一個(gè)足夠大的正整數(shù),以保證一旦發(fā)生超載行駛,運(yùn)輸調(diào)度計(jì)劃的效率將降到足夠低,從而在優(yōu)化過(guò)程中杜絕車(chē)輛超載行駛的出現(xiàn)。(2)道路阻塞道路阻塞情況的出現(xiàn),必然導(dǎo)致應(yīng)急物流車(chē)輛路徑在優(yōu)化過(guò)程當(dāng)中的路徑選擇上存在限制。本模型中將道路阻塞情況考慮為阻塞路段不可行駛,具體表述如下:3.2.5模型的建立分別介紹了應(yīng)急安全違背成本、車(chē)輛行駛總成本、車(chē)輛超載行駛以及道路阻塞的量化過(guò)程。模型的總目標(biāo)函數(shù)可以通過(guò)上述的幾部分綜合而得出:運(yùn)輸調(diào)度計(jì)劃的總成本=車(chē)輛行駛成本+應(yīng)急安全違背成本單個(gè)災(zāi)區(qū)需求點(diǎn)的應(yīng)急安全違背成本包括物資A與物資B兩種物資所引起的違背成本之和,總體運(yùn)輸調(diào)度計(jì)劃的應(yīng)急安全違背成本為各個(gè)災(zāi)區(qū)需求點(diǎn)的應(yīng)急安全違背成本之和?？梢酝瞥鲞\(yùn)輸調(diào)度計(jì)劃的應(yīng)急安全違背成本:可得到應(yīng)急物流車(chē)輛路徑問(wèn)題的優(yōu)化模型的目標(biāo)函數(shù):4.求解應(yīng)急物流車(chē)輛路徑問(wèn)題的自適應(yīng)遺傳算法設(shè)計(jì)4.1染色體構(gòu)造對(duì)于應(yīng)急物流車(chē)輛路徑問(wèn)題中的多供應(yīng)點(diǎn)多需求點(diǎn)運(yùn)輸模型,算法在染色體的構(gòu)造上采取自然數(shù)的序號(hào)編碼形式,在遺傳空間內(nèi)的染色體結(jié)構(gòu)為長(zhǎng)度為需求點(diǎn)數(shù)量的隨機(jī)自然數(shù)編碼,而遺傳空間的染色體經(jīng)過(guò)一定的規(guī)則可言轉(zhuǎn)換為實(shí)際問(wèn)題的運(yùn)輸計(jì)劃,具體如下:(1)根據(jù)運(yùn)輸網(wǎng)絡(luò)的路段長(zhǎng)度,判斷g中第一點(diǎn)距離供應(yīng)點(diǎn)“1”近還是距供應(yīng)點(diǎn)“2”近,將較近的供應(yīng)點(diǎn)加入到第一個(gè)序號(hào)之間,如果點(diǎn)“19”距供應(yīng)點(diǎn)“1”較近,則:根據(jù)車(chē)輛負(fù)載的限制,計(jì)算從第一個(gè)供應(yīng)點(diǎn)開(kāi)始運(yùn)輸線路上的需求點(diǎn)的累積需求量是否超過(guò)車(chē)輛負(fù)載。假設(shè)需求點(diǎn)“19”、“11”、“14”、“9”的需求總和重超過(guò)了車(chē)輛負(fù)載,則在需求點(diǎn)“9”之間插入距上一個(gè)需求點(diǎn)“14”較近的供應(yīng)點(diǎn),假設(shè)為“3”,則 4.2種群初始化對(duì)于本文中應(yīng)急物流車(chē)輛路徑問(wèn)題的遺傳算法求解過(guò)程的種群初始化,需結(jié)合上一小節(jié)中染色體的構(gòu)造、種群規(guī)模的設(shè)定來(lái)完成。在Matlab7.1軟件中,單個(gè)染色體的生產(chǎn)采用randperm函數(shù)隨機(jī)生成代表需求點(diǎn)的序號(hào)排列。初始種群可以表示為：4.3適應(yīng)度函數(shù)由于本文中應(yīng)急物流車(chē)輛路徑問(wèn)題的目標(biāo)函數(shù)為最小化的優(yōu)化目標(biāo),所以其遺傳算法的適應(yīng)度函數(shù)可以取目標(biāo)函數(shù)的倒數(shù),即目標(biāo)函數(shù)的值越小,適應(yīng)度越大,個(gè)體越優(yōu)秀。為了簡(jiǎn)化算法流程,在遺傳算法的操作過(guò)程中,直接將適應(yīng)值,即目標(biāo)函數(shù)的值作為評(píng)價(jià)指標(biāo);目標(biāo)函數(shù)越小,個(gè)體性能越優(yōu)秀。染色體的適應(yīng)值的計(jì)算流程如下:(1)劃分子路徑。根據(jù)每段子路徑上各需求點(diǎn)需求的重量之和不能超過(guò)車(chē)輛載重的原則,將染色體劃分為若干個(gè)子基因段,每條基因段代表一條子路徑。得到的子路徑數(shù)量即為所需的車(chē)輛數(shù)量。(2)子路徑連接供應(yīng)點(diǎn)。將每條子路徑的首尾兩端的需求點(diǎn)連接上距離最近的供應(yīng)點(diǎn)。(3)計(jì)算各子路徑運(yùn)輸成本。各條子路徑的運(yùn)輸距離乘以單位運(yùn)輸成本(4)計(jì)算運(yùn)輸計(jì)劃的總車(chē)輛運(yùn)輸成本。包括單位運(yùn)輸成本與車(chē)輛啟動(dòng)成本。對(duì)于種群規(guī)模為popsize的群體,其適應(yīng)度的評(píng)價(jià)流程如圖4.1所示。圖4.1適應(yīng)度評(píng)價(jià)函數(shù)流程圖4.4選擇算子本文采取輪盤(pán)賭法與最佳個(gè)體保存法相結(jié)合的選擇算子。它能夠使適應(yīng)度高的個(gè)體以較大的概率進(jìn)入下一代,能提高種群的平均適應(yīng)度。但是輪盤(pán)賭法采取概率的隨機(jī)選擇方式,這樣就不能保證在每一代的選擇過(guò)程中,優(yōu)秀的個(gè)體都能被復(fù)制進(jìn)入下一代,從而不能夠保證每一代種群的最優(yōu)個(gè)體的適應(yīng)值逐步減小,收斂性得不到保證。為此,本文將最佳個(gè)體保存法進(jìn)入選擇算子中,將每一代種群中排名在前兩位的個(gè)體直接進(jìn)入到下一代中,不進(jìn)行交叉、變異操作。這樣就能夠使最優(yōu)個(gè)體不被破壞,使進(jìn)化過(guò)程最優(yōu)解逐步收斂。選擇算子的操作步驟如下:(1)將種群按個(gè)體適應(yīng)值由小到大進(jìn)行排序。適應(yīng)值低,適應(yīng)度高。(2)保證排名前2位的最佳個(gè)體,直接進(jìn)入下一代。(3)從排名第三的個(gè)體開(kāi)始運(yùn)用輪盤(pán)賭法進(jìn)行選擇復(fù)制,產(chǎn)生中間群體。4.5交叉算子1.適應(yīng)交叉算子本文采用自適應(yīng)的交叉算子,其交叉概率不是固定的0到1的某一值,而是由每一代種群中最優(yōu)個(gè)體的適應(yīng)值與其它個(gè)體的差額關(guān)系所決定的。交叉概率的計(jì)算步驟如下:(1)搜索種群中個(gè)體的最小適應(yīng)值,記為min;(2)搜索種群中適應(yīng)值小于平均適應(yīng)值的所有個(gè)體;(3)計(jì)算適應(yīng)值小于平均適應(yīng)值的所有個(gè)體的平均值,記為f;(4)交叉概率表示如下:2.兩點(diǎn)、順序交叉法本文采取兩點(diǎn)、順序交叉法,對(duì)于任意的兩條染色體,具體的交叉過(guò)程如下:(1)根據(jù)隨機(jī)生成的兩點(diǎn)交叉點(diǎn)講兩條染色體分別劃分為三段;(2)分別將兩染色體的中間基因段復(fù)制到另一染色體的首端;(3)將復(fù)制前的兩染色體中的與所復(fù)制的基因段中有重復(fù)的序號(hào)逐步刪除。例如以下兩條染色體的交叉過(guò)程,假設(shè)交叉點(diǎn)未5和15:5.結(jié)論 本文對(duì)于應(yīng)急物流車(chē)輛路徑問(wèn)題的研究是以探索的目的進(jìn)行的,由于理論與水平、時(shí)間與硬件水平的限制,本文的研究還有一些不足與有待完善之處。以下幾點(diǎn)可作為未來(lái)的研究方向:(1)