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