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

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