基于遺傳算法的車輛路徑問題研究

基于遺傳算法的車輛路徑問題研究中文摘要：近些年,物流作為“第三利潤源泉〞受到國內(nèi)各行業(yè)的極大重視并得到較大的開展。物流的目標(biāo)就在于以最少的費(fèi)用滿足消費(fèi)者的需求。配送作為物流中一種特殊的、綜合的活動(dòng)形式,在當(dāng)今社會(huì)經(jīng)濟(jì)開展中發(fā)揮著越來越重要的作用。配送的核心為配送車輛的調(diào)度、貨物配裝及送貨過程。進(jìn)行配送系統(tǒng)優(yōu)化,主要是配送車輛調(diào)度的優(yōu)化。對(duì)配送車輛進(jìn)行優(yōu)化調(diào)度,有利于提高物流經(jīng)濟(jì)效益、實(shí)現(xiàn)物流科學(xué)化。本文主要對(duì)單車場非滿載無時(shí)間窗的車輛路徑問題和動(dòng)態(tài)車輛路徑問題進(jìn)行了研究。論文首先對(duì)現(xiàn)有車輛優(yōu)化調(diào)度問題歸類分析。然后對(duì)車輛路徑問題的傳統(tǒng)求解算法的根本思想、性能、適用性進(jìn)行了分析,在此根底上提出了采用掃描法和遺傳算法相結(jié)合的啟發(fā)式算法來求解物流配送車輛優(yōu)化調(diào)度問題的思想。在對(duì)遺傳算法中的選擇操作、鄰域結(jié)構(gòu)操作進(jìn)行改良的根底上,提出了一種求解車輛路徑問題的自適應(yīng)遺傳算法。應(yīng)用C語言編程進(jìn)行實(shí)例計(jì)算,結(jié)果說明改良的遺傳算法明顯增強(qiáng)了群體演化的質(zhì)量,提高了算法的收斂速度,得到了問題的滿意解。與傳統(tǒng)遺傳算法相比,掃描法和改良遺傳算法的結(jié)合,其優(yōu)化能力、運(yùn)行效率、可靠性均有一定的提高。最后論文在對(duì)動(dòng)態(tài)行駛時(shí)間車輛路徑問題進(jìn)行建模的根底上,嘗試采用掃描法和改良遺傳算法相結(jié)合的方法對(duì)此類問題進(jìn)行求解,在保證客戶效勞水平的要求下,取得了比擬好的結(jié)果。關(guān)鍵詞：物流車輛路徑問題;掃描法;遺傳算法Abstract:Recentyears,logistics,takenas"thethirdprofitresource",hasbeendevelopingrapidly.Theobjectoflogisticsistosatisfytherequirementsofconsumerswithleastcost.Asanespecialandintegratedactivityoflogistics,physicaldistributionplaysanimportantroleinmodernsociety.VehicleRoutingProblem(VRP)isthemainpartofthedistributionsystemoptimizing.Itisbenefitstomakeeconomicbenefits.Thispapermainlystudiedatypeofvehicleroutingproblemwithsingledepot,non-fullloadandwithouttimewindowsandadynamicvehicleroutingproblem.Therestrictionsandmathmodelsofvehicleroutingproblemisanalyzed.Thispaperalsocomparedandanalyzedthebasicideas,capabilitiesandapplicabilityoftraditionmethodheuristicsofVRP.Basedonthis,thispaperputforwardanimprovedgeneticalgorithmforvehicleroutingproblem,throughchangingitsselectoperationandneighborhoodstructureoperation,anadaptivegeneticalgorithmwaspresentedforsolvingthisproblem.ComputationalresultsbasedonClanguageprogrammingdemonstratedthattheadaptativealgorithmimprovedthequalityoftheresultsandcansolvetheproblemeffectively.Exemplificationsprovedthatthisalgorithmcanenhancecapabilityofoptimization,solvingefficiencyandreliabilityofrunning.Finally,adynamicvehicleroutingproblemwithrandomtimewindowismodeled.Thisproblemisalsosolvedbysweepandgeneticalgorithmsmethod.Themethodhavemadegoodeffectinensuringcustomerservicelevel.Keyword:VehicleRoutingProblem;sweepmethod;geneticalgorithm1引言車輛路徑問題〔VehicleRoutingProblem，VRP〕是一類在物流配送調(diào)度中具有廣泛應(yīng)用的優(yōu)化組合問題，在現(xiàn)代物流中居于中心地位。本文首先介紹了遺傳算法在解決簡單約束車輛路徑問題上的應(yīng)用，改良了交叉算子，為研究有時(shí)間窗裝卸問題的遺傳算法作了充分準(zhǔn)備。本文詳細(xì)分析了有時(shí)間窗裝卸問題的數(shù)學(xué)模型，深入研究解決此問題的分組編碼遺傳算法，將禁忌思想用于產(chǎn)生可行解的啟發(fā)式插入搜索算法之中，并構(gòu)造出適用于多目標(biāo)的適應(yīng)度函數(shù)，設(shè)計(jì)新的數(shù)據(jù)結(jié)構(gòu)，對(duì)分組編碼遺傳算法進(jìn)行有效實(shí)現(xiàn)。在分組編碼遺傳算法中提出路徑調(diào)整思想，設(shè)計(jì)出一種多策略分組編碼遺傳算法。采用多組通用算例測算，將多策略分組編碼遺傳算法與其它算法進(jìn)行比擬，其求解結(jié)果和計(jì)算時(shí)間都有明顯改良，驗(yàn)證了多策略分組編碼遺傳算法能夠有效穩(wěn)定地收斂到所求問題的解。VRP最早由Dantzig和Ramser于1959年提出，引起運(yùn)籌學(xué)、應(yīng)用數(shù)學(xué)、組合數(shù)學(xué)、圖論與網(wǎng)絡(luò)分析、物流科學(xué)、計(jì)算機(jī)應(yīng)用等學(xué)科研究人員的極大重視，成為運(yùn)籌學(xué)與組合優(yōu)化領(lǐng)域的熱點(diǎn)問題。各國研究人員對(duì)該問題進(jìn)行了大量的理論研究及實(shí)驗(yàn)分析，取得了重大進(jìn)展，其研究成果在運(yùn)輸系統(tǒng)、公交車輛路線設(shè)計(jì)、快遞收發(fā)系統(tǒng)、物資調(diào)配系統(tǒng)中都已得到了廣泛應(yīng)用。研究車輛路徑問題的特點(diǎn)及算法具有重要的實(shí)際意義。本文重點(diǎn)研究解決有時(shí)間窗裝卸問題〔PDPTW〕的遺傳算法，作為前期準(zhǔn)備，本文作者對(duì)遺傳算法解決具有簡單約束條件的VRP〔包括有容量約束的車輛路徑問題CVRP和有時(shí)間窗的車輛路徑問題VRPTW〕進(jìn)行了初步研究。有容量約束的車輛路徑問題〔CapacitatedVehicleroutingproblem，CVRP〕是由一個(gè)效勞中心〔或車場〕的假設(shè)干車輛向多個(gè)客戶點(diǎn)進(jìn)行配送效勞，在待效勞客戶點(diǎn)和出發(fā)點(diǎn)的位置、客戶需求及車輛最大負(fù)載的前提下，設(shè)計(jì)車輛配送路徑，規(guī)劃設(shè)計(jì)方案，使運(yùn)輸本錢最小化，即總代價(jià)最小〔使用車輛盡量少，行車總距離盡量短〕。CVRP實(shí)際是多目標(biāo)組合優(yōu)化問題，一般以派出車輛最少〔運(yùn)輸路線條數(shù)最少〕為首要目標(biāo)，行車總距離最短，即總代價(jià)最小為次要目標(biāo)。CVRP要求滿足以下條件及假設(shè)：〔1〕所有的配送車輛以配送中心為起點(diǎn)并最終回到配送中心；〔2〕每條配送路徑上各客戶點(diǎn)的需求量之和不超過車輛的負(fù)載量；〔3〕每個(gè)客戶點(diǎn)的需求僅由一輛車一次滿足。2選題的目的物流已被認(rèn)為是繼降低原材料消耗和提高勞動(dòng)生產(chǎn)率之后的“第三利潤源〞。通過優(yōu)化物流系統(tǒng),可以降低物流本錢,從而增強(qiáng)企業(yè)的市場競爭能力。因此,研究物流系統(tǒng)中的優(yōu)化問題,具有十分重要的意義,是國內(nèi)外研究的一個(gè)熱點(diǎn)。庫存本錢與配送本錢是物流系統(tǒng)的核心本錢,在物流總本錢中占據(jù)了很大的比例。如果能降低庫存本錢與配送本錢,就能有效地降低物流本錢。遺傳算法是一種應(yīng)用很廣泛的智能優(yōu)化算法,本文對(duì)遺傳算法進(jìn)行了分析研究,針對(duì)遺傳算法的一些缺陷提出了相應(yīng)的改良方法。在上述研究根底上,本文基于遺傳算法,研究了物流系統(tǒng)中的庫存優(yōu)化問題及車輛路徑問題。本文將庫存仿真優(yōu)化問題與車輛路徑問題都看作是組合優(yōu)化問題,并應(yīng)用遺傳算法進(jìn)行求解。本文的主要研究工作及奉獻(xiàn)可歸納如下:(1)對(duì)隨機(jī)庫存系統(tǒng)建立了基于離散事件系統(tǒng)的計(jì)算機(jī)仿真模型。用系統(tǒng)仿真方法求解最優(yōu)庫存策略時(shí),其難點(diǎn)之一在于仿真的優(yōu)化。為此,本文將計(jì)算機(jī)仿真技術(shù)和遺傳算法相結(jié)合,應(yīng)用遺傳算法來優(yōu)化模型的控制參數(shù),即獲得最優(yōu)的庫存控制策略。針對(duì)隨機(jī)系統(tǒng)的特點(diǎn),設(shè)計(jì)了候選解收集器,它能夠收集在仿真優(yōu)化過程中產(chǎn)生的Pareto解;提出了M精英選擇算子,用于保護(hù)潛在的最優(yōu)個(gè)體,使它們?cè)诮徊?、變異算子中不被破壞。針?duì)兩種常用的庫存控制策略進(jìn)行了仿真優(yōu)化的實(shí)驗(yàn),結(jié)果說明本文提出的仿真優(yōu)化方法是有效的。(2)旅行商問題(TSP)是車輛路徑問題的子問題。為了求解TSP問題,研究了常用于TSP問題的三種交叉算子的優(yōu)化效果,提出了一種求解TSP問題的高效混合遺傳算法HGA-TSP。在該算法中以變形的OX算子作為交叉算子,以2-opt算法作為遺傳算法的變異算子;提出了K近鄰點(diǎn)集的概念以縮減搜索空間并提高算法的時(shí)間效率。(3)將單配送中心,多輛運(yùn)輸車且無約束的車輛路徑問題建模成具有總路徑長度最短、子路徑長度均衡性好這兩個(gè)目標(biāo)的雙目標(biāo)多旅行商問題(MTSP),并基于HGA-TSP算法,研究了三種求解上述問題的解決方案。(4)對(duì)于帶能力約束的車輛路徑問題(CVRP),提出了一種新的雙層染色體編碼方案和一種子路徑交換算法。雙層染色體編碼方案不需要預(yù)先知道最優(yōu)解所需要的車輛數(shù),并能確保染色體不違反能力約束,這更適合求解實(shí)際物流配送系統(tǒng)中的車輛路徑問題。此外,相對(duì)于常用的單層染色體編碼方案,該編碼方案還能降低搜索空間的大小,從而提高搜索效率并降低計(jì)算時(shí)間。子路徑交換算法可以有效提高遺傳算法的求解精度?；谏鲜鲭p層染色體編碼方案和子路徑交換算法,設(shè)計(jì)了兩種求解CVRP問題的混合遺傳算法,分別是HGA-CVRP算法和HGA-SE-CVRP算法。(5)對(duì)于帶時(shí)間窗約束的車輛路徑問題(VRPTW,首先改良了雙層染色體編碼方案,以便在編程實(shí)現(xiàn)時(shí)更方便地進(jìn)行子路徑的處理。然后研究了遺傳算法與鄰域搜索算法的結(jié)合方式,在遺傳算法中引入了帶克隆操作的鄰域搜索算子。最后提出了一種求解VRPTW問題的新型混合遺傳算法HGA-VRPTW。(6)綜合應(yīng)用了面向?qū)ο蠓治雠c設(shè)計(jì)、多線程、UML等先進(jìn)的軟件開發(fā)方法與技術(shù),設(shè)計(jì)并開發(fā)了VRP仿真實(shí)驗(yàn)室,這是一個(gè)用于研究車輛路徑問題的軟件包,具有使用簡便、界面美觀的特點(diǎn)。VRP仿真實(shí)驗(yàn)室在本文的研究中發(fā)揮了重要的作用,是研究車輛路徑問題的有力工具。本文對(duì)大量的基準(zhǔn)測試實(shí)例(Benchmark)進(jìn)行了仿真計(jì)算,計(jì)算結(jié)果說明,本文所提出的一系列算法能有效求解物流系統(tǒng)中的庫存優(yōu)化問題與車輛路徑問題。3問題描述3.1車輛路徑問題定義車輛路線問題〔VRP〕最早是由Dantzig和Ramser于1959年首次提出，它是指一定數(shù)量的客戶，各自有不同數(shù)量的貨物需求，配送中心向客戶提供貨物，由一個(gè)車隊(duì)負(fù)責(zé)分送貨物，組織適當(dāng)?shù)男熊嚶肪€，目標(biāo)是使得客戶的需求得到滿足，并能在一定的約束下，到達(dá)諸如路程最短、本錢最小、消耗時(shí)間最少等目的。由此定義不難看出，旅行商問題〔TravelingSalemanProblem,TSP〕是VRP的特例，由于Gaery。已證明TSP問題是NP難題，因此，VRP也屬于NP難題。車輛路線問題自1959年提出以來，一直是網(wǎng)絡(luò)優(yōu)化問題中最根本的問題之一，由于其應(yīng)用的廣泛性和經(jīng)濟(jì)上的重大價(jià)值，一直受到國內(nèi)外學(xué)者的廣泛關(guān)注。車輛路線問題可以描述如下〔如圖1〕：圖1路徑問題描述設(shè)有一場站〔depot〕，共有M輛貨車，車輛容量為Q，有N位顧客〔customer〕，每位顧客有其需求量D。車輛從場站出發(fā)對(duì)客戶進(jìn)行配送效勞最后返回場站，要求所有顧客都被配送，每位顧客一次配送完成，且不能違反車輛容量的限制，目的是所有車輛路線的總距離最小。車輛路線的實(shí)際問題包括配送中心配送、公共汽車路線制定、信件和報(bào)紙投遞、航空和鐵路時(shí)間表安排、工業(yè)廢品收集等。3.2車輛路徑問題的類型一般而言車輛路線問題大致可以分為以下三種類型〔Ballou，1992〕：1、相異的單一起點(diǎn)和單一終點(diǎn)。2、相同的單一起點(diǎn)和終點(diǎn)。3、多個(gè)起點(diǎn)和終點(diǎn)。3.3車輛路線問題研究現(xiàn)狀經(jīng)過幾十年的研究開展，車輛路線問題研究取得了大量成果。下面從車輛路線問題的現(xiàn)有研究型態(tài)和求解方法兩個(gè)方面介紹車輛路線問題的研究現(xiàn)狀。3.3.1車輛路線問題型態(tài)在根本車輛路線問題〔VRP〕的根底上，車輛路線問題在學(xué)術(shù)研究和實(shí)際應(yīng)用上產(chǎn)生了許多不同的延伸和變化型態(tài)，包括時(shí)窗限制車輛路線問題〔vehicleroutingproblemswithtimewindows，VRPTW〕、追求最正確效勞時(shí)間的車輛路線問題〔VRPDT〕、多車種車輛路線問題〔fleetsizeandmixvehicleroutingproblems，F(xiàn)SVRP〕、車輛屢次使用的車輛路線問題〔vehicleroutingproblemswithmultipleuseofvehicle，VRPM〕、考慮收集的車輛路線問題〔vehicleroutingproblemswithbackhauls，VRPB〕、隨機(jī)需求車輛路線問題〔vehicleroutingproblemwithstochasticdemand，VRPSD〕等。3.3.2解決方法1、求解方法演進(jìn)綜合過去有關(guān)車輛路線問題的求解方法，可以分為精確算法〔exactalgorithm〕與啟發(fā)式解法〔heuristics〕，其中精密算法有分支界限法、分支切割法、集合涵蓋法等；啟發(fā)式解法有節(jié)約法、模擬退火法、確定性退火法、禁忌搜尋法、基因算法、神經(jīng)網(wǎng)絡(luò)、螞蟻殖民算法等。1995年，F(xiàn)isher\o""曾將求解車輛路線問題的算法分成三個(gè)階段。第一階段是從1960年到1970年，屬于簡單啟發(fā)式方式，包括有各種局部改善啟發(fā)式算法和貪婪法〔Greedy〕等；第二階段是從1970年到1980年，屬于一種以數(shù)學(xué)規(guī)劃為主的啟發(fā)式解法，包括指派法、集合分割法和集合涵蓋法；第三階段是從1990開始至今，屬于較新的方法，包括利用嚴(yán)謹(jǐn)啟發(fā)式方法、人工智能方法等。2、啟發(fā)式算法由于VRP是NP-hard問題，難以用精確算發(fā)求解，啟發(fā)式算法是求解車輛運(yùn)輸問題的主要方法，多年來許多學(xué)者對(duì)車輛運(yùn)輸問題進(jìn)行了研究，提出了各種各樣的啟發(fā)式方法。車輛運(yùn)輸問題的啟發(fā)式方法可以分為簡單啟發(fā)式算法、兩階段啟發(fā)式算法、人工智能方法建立的啟發(fā)式方法。簡單啟發(fā)式方法包括節(jié)省法或插入法、路線內(nèi)/間節(jié)點(diǎn)交換法、貪婪法和局部搜索法等方法。節(jié)省法或插入法〔savingsorinsertion〕是在求解過程中使用節(jié)省本錢最大的可行方式構(gòu)造路線，直到無法節(jié)省為止。交換法那么是依賴其他方法產(chǎn)生一個(gè)起始路線，然后以迭代的方式利用交換改善法減少路線距離，直到不能改善為止。1960年，Clarke和Wrigh首先提出一種啟發(fā)式節(jié)省法〔savingsmethods〕來建立車隊(duì)配送路線。簡單啟發(fā)式方法簡單易懂、求解速度快，但只適合求解小型、簡單的VRP問題。兩階段方法包括先分組后定路線〔clusterfirst-routesecond〕和先定路線后分組〔routefirst-clustersecond〕兩種啟發(fā)式策略。前者是先將所有需求點(diǎn)大概分為幾個(gè)組，然后再對(duì)各個(gè)組分別進(jìn)行路線排序；后者那么是先將所有的需求點(diǎn)建構(gòu)成一條路線，再根據(jù)車輛的容量將這一路線分割成許多適合的單獨(dú)路線。1990年以來，人工智能方法在解決組合優(yōu)化問題上顯示出強(qiáng)大功能，在各個(gè)領(lǐng)域得到充分應(yīng)用，很多學(xué)者也將人工智能引入車輛路線問題的求解中，并構(gòu)造了大量的基于人工智能的啟發(fā)式算法。禁忌搜索法〔TS〕根本上是屬于一種人工智能型〔AI〕的局部搜尋方法，Willard首先將此算法用來求解VRP，隨后亦有許多位學(xué)者也發(fā)表了求解VRP的TS算法。西南交通大學(xué)的袁慶達(dá)等設(shè)計(jì)了考慮時(shí)間窗口和不同車輛類型的禁忌算法，這種算法主要采用GENIUS方法產(chǎn)生初始解，然后禁忌算法對(duì)初始解優(yōu)化。模擬退火方法具有收斂速度快，全局搜索的特點(diǎn)，Osman對(duì)VRP的模擬退火算法進(jìn)行了研究，他提出的模擬退火方法主要適合于解決路線分組。遺傳算法具有求解組合優(yōu)化問題的良好特性，Holland首先采用遺傳算法〔GA〕編碼解決VRPTW問題?，F(xiàn)在多數(shù)學(xué)者采用混合策略，分別采用兩種人工智能方法進(jìn)行路線分組和路線優(yōu)化。Ombuk提出了用遺傳算法進(jìn)行路線分組，然后用禁忌搜索方法進(jìn)行路線優(yōu)化的混合算法。Bent和VanHentenryck那么首先用模擬退火算法將車輛路線的數(shù)量最小化，然后用大鄰域搜索法〔largneighborhoodsearch〕將運(yùn)輸費(fèi)用降到最低?？偨Y(jié)幾種人工智能方法可以看出，TS算法所得到的解最接近最優(yōu)解，但其運(yùn)算時(shí)間也最長，是GA算法的2～3倍，SA算法的近20倍；由于GA算法也能較好的逼近最優(yōu)解，同時(shí)使運(yùn)算時(shí)間大大縮短，所以GA算法能兼顧運(yùn)算時(shí)間和效率兩方面，是具有較好的開展前途的方法；SA算法求解速度非?？欤材芴峁┮欢ǔ潭壬系膬?yōu)化方案在求解較小規(guī)模問題上具有較好效果。4遺傳算法介紹遺傳算法簡稱GA(GeneticAlgorithm)，在本質(zhì)上是一種不依賴具體問題的直接搜索方法。它是根據(jù)生物進(jìn)化思想而啟發(fā)得出的一種全局優(yōu)化算法。遺傳算法的概念最早是由BagleyJ.D在1967年提出的；而開始遺傳算法的理論和方法的系統(tǒng)性研究的是1975年，這一開創(chuàng)性工作是由Michigan大學(xué)的J.H.Holland所實(shí)行。當(dāng)時(shí)，其主要目的是說明自然和人工系統(tǒng)的自適應(yīng)過程。遺傳算法是受生物進(jìn)化學(xué)說和遺傳學(xué)說啟發(fā)而開展起來的，基于適者生存思想的一種較通用的問題求解方法。利用遺傳算法進(jìn)行尋優(yōu)時(shí)，編碼、選擇、交叉、變異是四個(gè)重要步驟。遺傳算法作為一種全局優(yōu)化搜索方法，具有簡單、通用普適性強(qiáng)，適用于并行處理和應(yīng)用范圍廣等優(yōu)點(diǎn)。遺傳算法在優(yōu)化領(lǐng)域表現(xiàn)出了其強(qiáng)大的能力，遺傳算法仿照生物進(jìn)化和遺傳的規(guī)律，利用復(fù)制、交換和突變等操作，使優(yōu)勝者繁殖，劣敗者消失，一代代重復(fù)同樣的操作，最終找出最優(yōu)解。具有如下特點(diǎn)：

(1)遺傳算法運(yùn)算的是解集的編碼，而不是解集本身；

(2)遺傳算法的搜索始于解的一個(gè)種群，而不是單個(gè)解；

(3)遺傳算法只使用報(bào)酬信息〔適值函數(shù)〕，不使用導(dǎo)數(shù)或其他輔助知識(shí)；

(4)遺傳算法采用概率的，而不是確定的狀態(tài)轉(zhuǎn)移規(guī)那么。

遺傳算法特別適用于傳統(tǒng)搜索方法難以解決的復(fù)雜的和非線性的問題，可廣泛用于組合優(yōu)化、自適應(yīng)控制、規(guī)劃設(shè)計(jì)和人工生命等領(lǐng)域。作為一種隨機(jī)優(yōu)化技術(shù)在解優(yōu)化問題中顯示了優(yōu)于傳統(tǒng)優(yōu)化算法的性能，遺傳算法的一個(gè)顯著優(yōu)勢是不需要目標(biāo)函數(shù)明確的數(shù)學(xué)方程和導(dǎo)數(shù)表達(dá)式，同時(shí)又是一種全局尋優(yōu)算法，不會(huì)象某些傳統(tǒng)算法易于陷入局部最優(yōu)解。

遺傳算法是具有“生成+檢測〞(generate-and-test)的迭代過程的搜索算法。遺傳算法中包含了如下5個(gè)根本要素：1)參數(shù)編碼；2)初始群體的設(shè)定；3)適應(yīng)度函數(shù)的設(shè)計(jì)；4)遺傳操作設(shè)計(jì)；5〕控制參數(shù)設(shè)定(主要是指群體大小和使用遺傳操作的概率等)。這5個(gè)要素構(gòu)成了遺傳算法的核心內(nèi)容。4.1遺傳算法的根本思想遺傳算法是受生物進(jìn)化學(xué)說和遺傳學(xué)說啟發(fā)而開展起來的，基于適者生存思想的一種較通用的問題求解方法。利用遺傳算法進(jìn)行尋優(yōu)時(shí)，編碼、選擇、交叉、變異是四個(gè)重要步驟。遺傳算法作為一種全局優(yōu)化搜索方法，具有簡單、通用普適性強(qiáng)，適用于并行處理和應(yīng)用范圍廣等優(yōu)點(diǎn)。遺傳算法在優(yōu)化領(lǐng)域表現(xiàn)出了其強(qiáng)大的能力，遺傳算法仿照生物進(jìn)化和遺傳的規(guī)律，利用復(fù)制、交換和突變等操作，使優(yōu)勝者繁殖，劣敗者消失，一代代重復(fù)同樣的操作，最終找出最優(yōu)解。具有如下特點(diǎn)：

(1)遺傳算法運(yùn)算的是解集的編碼，而不是解集本身；

(2)遺傳算法的搜索始于解的一個(gè)種群，而不是單個(gè)解；

(3)遺傳算法只使用報(bào)酬信息〔適值函數(shù)〕，不使用導(dǎo)數(shù)或其他輔助知識(shí)；

(4)遺傳算法采用概率的，而不是確定的狀態(tài)轉(zhuǎn)移規(guī)那么。4.2遺傳算法流程圖圖2遺傳算法流程圖5模型建立求解及實(shí)例應(yīng)用5.1車輛調(diào)度模型根據(jù)上述對(duì)問題的描述，可以采用混合整數(shù)規(guī)劃方法對(duì)車輛調(diào)度進(jìn)行建模"設(shè)N為最小本錢，那么目標(biāo)函數(shù)為滿足約束條件1：式中：K為所有車輛的集合，；G為所有客戶的集合，，，其中{0}代表配送中心；為由車輛k效勞的客戶的集合；為車輛到達(dá)客戶i的時(shí)間；為懲罰函數(shù)，車輛在時(shí)間到達(dá)客戶i時(shí)所對(duì)應(yīng)的懲罰本錢；為車輛從客戶i到客戶j的所有運(yùn)輸本錢；為車輛從客戶i到客戶j的行車時(shí)間；為客戶i的需求量；Q為車輛k的最大裝載量；為車輛在客戶i處的停留的時(shí)間。另外，變量和的值為0或1。假設(shè)車輛k為客戶i效勞，那么1，否那么為0，即：此變量表示車輛分配方案，可用布爾矩陣表示；假設(shè)車輛k經(jīng)由客戶i到客戶j，那么為1，否那么為0，即：，表示車輛路線安排。約束條件2：保證每個(gè)客戶均被效勞，而且每輛車都從配送中心出發(fā)；約束條件3：表示每輛車負(fù)責(zé)的客戶點(diǎn)的貨物需求量總和不超過該車輛的最大裝載量；約束條件4、5：表示對(duì)任一由k效勞的客戶點(diǎn)j必定有另一(而且只有一個(gè))由k效勞的客戶點(diǎn)(包括配送中心)I,車輛k從客戶點(diǎn)i到達(dá)客戶點(diǎn)j,而對(duì)由k效勞的客戶點(diǎn)i同樣存在由k效勞的另一客戶點(diǎn),車輛k是從該客戶點(diǎn)到達(dá)客戶點(diǎn)i的,依次類推；約束條件6：保證每輛車的行車路線的總耗時(shí)不超過一個(gè)事先定下的數(shù)值；約束條件7：對(duì)某個(gè)客戶點(diǎn)，車輛到達(dá)時(shí)間限制在某一時(shí)間段內(nèi)。根據(jù)實(shí)際情況，本文采用軟限制時(shí)間窗，其懲罰函數(shù)如圖2所示。其中，為客戶所要求的送貨時(shí)區(qū)，為時(shí)間窗，超過該范圍客戶將拒絕收貨，因此設(shè)定一個(gè)極大的懲罰本錢以防止此情況的發(fā)生。圖3懲罰函數(shù)5.2帶時(shí)間窗的物流配送問題優(yōu)化問題帶時(shí)間窗VRP〔VRPwithTimeWindows，VRPTW〕是帶裝載能力約束的CVRP(CapacitatedVRP，CVRP)的擴(kuò)展。在該類問題中，有車輛裝載能力約束，且每個(gè)客戶i都有一個(gè)與之相聯(lián)系的時(shí)間區(qū)間[ai,bi]，稱為時(shí)間窗。客戶的效勞必須在相應(yīng)的時(shí)間窗內(nèi)開始，車輛必須在客戶點(diǎn)停留的時(shí)間長度為si。按客戶對(duì)物流中心違反時(shí)間窗約束規(guī)定時(shí)的接受程度，可分為硬時(shí)間窗、軟時(shí)間窗和混合型時(shí)間窗。硬時(shí)間窗(HardTimeWindows)：指配送車輛必須在特定時(shí)間區(qū)段，將貨物送達(dá)顧客手中，不管是遲到或早到都完全不予接受；軟時(shí)間窗(SoftTimeWindows)：允許效勞的開始時(shí)間有所偏離時(shí)間窗，那么必須按照違反時(shí)間的長短施以一定的罰金或其他懲罰法那么；混合型時(shí)間窗〔MixedTimeWindows〕：是指系統(tǒng)中有些客戶只接受硬時(shí)間窗效勞，有些客戶接受軟時(shí)間窗效勞，或者同一客戶，往往軟、硬兩種時(shí)間窗效勞混合使用。如問題為硬時(shí)間窗問題，那么必須滿足到客戶i的時(shí)間要比承諾到達(dá)時(shí)間早，即到達(dá)i的時(shí)間≤到達(dá)i的最晚時(shí)間限制；如有緊急貨物〔高優(yōu)先級(jí)客戶〕時(shí)，那么自動(dòng)將優(yōu)先級(jí)高的貨物按優(yōu)先級(jí)順序排入隊(duì)列前端，然后將其它普通貨物再進(jìn)行優(yōu)化；即如有N個(gè)客戶，其中有一個(gè)為緊急運(yùn)單，那么自動(dòng)將其放在隊(duì)首，其他N-1個(gè)客戶進(jìn)行優(yōu)化，即將問題降為N-1階的路徑優(yōu)化問題；任一客戶只由一臺(tái)運(yùn)輸車輛提供效勞，即算法解決的是任一客戶的貨物需求均小于車輛最大負(fù)載〔容積〕的情況。如出現(xiàn)某客戶需求量大于車輛負(fù)載〔容積〕的情況時(shí)，需要先派車為其運(yùn)輸，直至該客戶剩余貨物需求量小于車輛最大負(fù)載〔容積〕即可參加優(yōu)化調(diào)度。5.3帶時(shí)間窗的物流配送路徑問題的遺傳算法染色體結(jié)構(gòu)編碼根據(jù)物流配送路徑優(yōu)化問題的特點(diǎn)，本文采用了簡單直觀的自然數(shù)編碼方法，用0表示配送中心，用1、2、…、L表示各需求點(diǎn)。由于在配送中心有m輛汽車，那么最多存在m條配送路徑，每條配送路徑都始于配送中心，也終于配送中心。為了在編碼中反映車輛配送的路徑，采用了增加m－1個(gè)虛擬配送中心的方法，分別用L＋1、L＋2、…、L＋K－l表示。這樣，l、2、…、L＋m－l這L＋m－l個(gè)互不重復(fù)的自然數(shù)的隨機(jī)排列就構(gòu)成一個(gè)個(gè)體，并對(duì)應(yīng)一種配送路徑方案。例如，對(duì)于一個(gè)有6個(gè)需求點(diǎn)，用2輛汽車完成配送任務(wù)的問題，那么可用0、2、…、6(0表示配送中心)這7個(gè)自然數(shù)的隨機(jī)排列表示物流配送路徑方案。如個(gè)體0l26354表示的配送路徑方案為：路徑1：0-1-2-6，路徑2：3-5-4共有2條配送路徑；5.3.2種群的初始化群體初始化時(shí)，采用兩種機(jī)制，一種是隨機(jī)生成個(gè)體，一種是按前相插入啟發(fā)式算法。本文采用隨機(jī)產(chǎn)生一種l～L＋m－l這L＋m－l個(gè)互不重復(fù)的自然數(shù)的排列，即形成一個(gè)個(gè)體。設(shè)群體規(guī)模為M，那么通過隨機(jī)產(chǎn)生M個(gè)這樣的個(gè)體，即形成初始群體。5.3.3適應(yīng)度分析初始種群形成以后，需要通過種群的適應(yīng)度函數(shù)，對(duì)種群中的每個(gè)染色體進(jìn)評(píng)價(jià)，并以此為標(biāo)準(zhǔn)選擇最優(yōu)解。由于適應(yīng)度函數(shù)通常越大越好，而物流車輛路徑優(yōu)化問題那么是求最小經(jīng)濟(jì)本錢，為了便于計(jì)算且增大區(qū)分度，算法采用的是目標(biāo)函數(shù)的倒數(shù)乘以區(qū)分度系數(shù)β作為適應(yīng)度函數(shù)，即maxF=1/S*β(3-2-3-1)遺傳算子1.遺傳選擇選擇是用來確定重組或交叉?zhèn)€體，以及被選個(gè)體將產(chǎn)生多少個(gè)子代個(gè)體。新種群的產(chǎn)生是在上一代的根底上對(duì)原有的各染色體按其適應(yīng)度大小進(jìn)行保存，并將其進(jìn)行交叉和變異形成新一代的個(gè)體；適應(yīng)度計(jì)算之后是實(shí)際的選擇，按照適應(yīng)度進(jìn)行父代個(gè)體的選擇，本文由輪盤賭算法進(jìn)行種子的選?。挥?jì)算每個(gè)個(gè)體的相對(duì)適應(yīng)度值，以之作為概率，將[0,1]空間劃分成n份。生成一個(gè)[0,1]范圍內(nèi)的隨機(jī)數(shù)，看它落在哪個(gè)區(qū)域，那么選擇該個(gè)體。2.遺傳基因的交叉對(duì)通過選擇操作產(chǎn)生的新群體，需要進(jìn)行配對(duì)交叉重組。簡單的說就是人為選取較好的一對(duì)染色體作為新染色體的父母，按染色體按長度分為前后兩段，取其中一個(gè)染色體的前半局部放在另一個(gè)染色體的前邊，再順序遍歷新染色體的基因并剔除重復(fù)基因，從而得到新的染色體child1。同理，可以得到另一個(gè)新染色體child2。在得到新的兩個(gè)染色體后，為了使下一代染色體具有更高的適應(yīng)度，算法參加了淘汰機(jī)制，即比擬兩個(gè)新染色體，保存較好的一個(gè)進(jìn)入下一代，同時(shí)將較差的一個(gè)舍棄。在此引入新的CX交叉算子。實(shí)施交叉操作。其操作方法如下：首先，隨機(jī)在父代染色體中選擇一個(gè)交配區(qū)域，如兩個(gè)父代染色體及交配區(qū)域選定為：A=35|6298|471B=83|2954|167其次，將B的交配區(qū)域加到A的前面，A的交配區(qū)域加到B的前面，得到：'A=2954|356298471'B=6298|832954167最后在'A，'B中自交配區(qū)域后依次刪除與交配區(qū)域相同的自然數(shù)，得到最終的兩個(gè)后代：C1=295436871C2=6298384173.遺傳基因的變異基因的變異是在選出的染色體中按其變異概率隨機(jī)找出假設(shè)干基因位置，再隨機(jī)產(chǎn)生一個(gè)基因替換原有位置基因，并查找因替換基因產(chǎn)生的此基因的另一重復(fù)位置，修改使之成為一個(gè)不重復(fù)基因染色體。為了使后代繼承更多的父代的基因信息，本文取變異概率Pm為0.02左右。5.3.5函數(shù)控制的終止條件優(yōu)化算法的結(jié)束條件是系統(tǒng)設(shè)定的最大遺傳代數(shù)。即事先設(shè)置一個(gè)最大代數(shù)，如當(dāng)前代數(shù)大于最大代數(shù)時(shí)，算法停止。判斷迭代的代數(shù)是否為要求代數(shù)maxt，假設(shè)是，停止進(jìn)化，選性能最好的染色體所對(duì)應(yīng)的路徑集合，作為問題的優(yōu)化解輸出。5.3.6步驟Step1：t=0，利用自然數(shù)編碼方式，采用前相插入啟發(fā)式算法和隨機(jī)的方式產(chǎn)生初始種群，并輸入控制參數(shù)；Step2：計(jì)算個(gè)體適應(yīng)度；Step3：t<maxt，t=t+1，那么轉(zhuǎn)Step4；否那么停止計(jì)算，并輸出結(jié)果；Step4：采用基于個(gè)體濃度的群體多樣性保持策略來選擇個(gè)體；Step5：對(duì)個(gè)體進(jìn)行CX交叉重組；Step6：按照變異方法對(duì)個(gè)體進(jìn)行變異；Step7：重復(fù)步驟2-6；6算法的建立和求解車輛優(yōu)化調(diào)度問題由車輛分配和路線安排這兩個(gè)相互關(guān)聯(lián)的子問題組成，但關(guān)鍵是確定優(yōu)化的車輛分配方案〔即求解變量〕。一旦車輛分配方案確定，那么路線安排問題也就比擬容易求解〔即求解變量〕。可以采用遺傳算法的思想作為總體框架對(duì)該問題進(jìn)行求解，用遺傳算法求解變量，而變量那么用啟發(fā)式算法求解。6.1編碼操作遺傳算法的關(guān)鍵之一是確定染色體并對(duì)它進(jìn)行編碼處理。對(duì)于車輛調(diào)度問題，可將求解變量看作染色體，因此，一條染色體就代表一種可能的車輛分配方案，然后可用布爾矩陣對(duì)該染色體的基因鏈進(jìn)行編碼。對(duì)于m輛車、n個(gè)客戶的車輛分配,可表示成mn矩陣。例如，圖1的布爾矩陣為即車輛1負(fù)責(zé)客戶1和2，車輛2負(fù)責(zé)客戶3、4和5.6.2定義適配值計(jì)算函數(shù)適應(yīng)度函數(shù)是遺傳算法中評(píng)價(jià)解集好壞的依據(jù),適配值高的個(gè)體優(yōu)先培養(yǎng)。在本問題中，對(duì)于種群數(shù)目為N的染色體群，其個(gè)體染色體i的適配值的值越小,那么表示個(gè)體適配值越高。個(gè)體適配值為式中，所以，目標(biāo)函數(shù)生成初始染色體種群初始化遺傳世代；每一代的染色體群的種群數(shù)目；交叉概率，變異概率等參數(shù)。隨機(jī)產(chǎn)生初始車輛分配方案，并淘汰不符合約束條件的染色體,直到染色體群的種群數(shù)達(dá)N條。N的取值不宜過大或過小。過大不但增加計(jì)算量，而且不能有效地獲得迭代解。過小將不能保證分配方案的多樣性，本算法中取種群大小，交叉概率,變異概。6.3用啟發(fā)式算法求解單一車輛排序問題對(duì)變量的求解實(shí)質(zhì)上是一個(gè)帶時(shí)間約束的單一車輛排序問題，即對(duì)中的元素進(jìn)行排序，求解最小的，以滿足約束條件。該子問題可表示為滿足約束條件：本文采用文獻(xiàn)[3]中的啟發(fā)式方法進(jìn)行求解。首先對(duì)中的元素按照客戶要求到達(dá)的時(shí)間從小到大進(jìn)行排序，如果有兩個(gè)以上的客戶要求到達(dá)的時(shí)間相同，那么對(duì)這些客戶按照配送區(qū)域〔時(shí)區(qū)〕從小到大進(jìn)行排序。淘汰不符合約束條件的解，調(diào)整次序重新搜索，直到找到較佳的可行解為止。對(duì)每一條染色體，求解變量，并計(jì)算每一條染色體的適配值：!6.4種群的選擇與復(fù)制本算法采用與適配值成比例的概率方法，對(duì)種群的個(gè)體進(jìn)行選擇與復(fù)制。首先根據(jù)前面計(jì)算的計(jì)算個(gè)體i在下一代中應(yīng)復(fù)制自身的比例；定義選擇概率為個(gè)體適配值所占比例的反向排序$即適配值最小的車輛分配方案其選擇概率最大；依據(jù)選擇概率對(duì)種群中的個(gè)體進(jìn)行復(fù)制，選擇概率大的個(gè)體被重復(fù)復(fù)制的時(shí)機(jī)大，而選擇概率小的個(gè)體那么趨向于減少或淘汰，直到復(fù)制N條染色體。6.5交叉操作由于復(fù)制操作并沒有產(chǎn)生新的車輛分配方案，因此種群中最好的個(gè)體的適配值并沒有降低。對(duì)染色體群實(shí)施交叉操作crossover〔〕可以產(chǎn)生新的體。以概率對(duì)染色體群隨機(jī)地交換兩個(gè)個(gè)體的某些片段產(chǎn)生新的個(gè)體染色體，即對(duì)選定的需進(jìn)行交叉運(yùn)算的每一組布爾矩陣隨機(jī)設(shè)定交叉位置$通過交換布爾矩陣中的某些行或列的局部信息〔二進(jìn)制位〕，其他位不變，從而生成兩個(gè)新的布爾矩陣。交叉概率對(duì)算法的收斂有較大的影響，越大，優(yōu)秀的個(gè)體出現(xiàn)的幾率也越大，新舊個(gè)體替換快，算法收斂也快。的經(jīng)驗(yàn)值為,效果較佳。6.6變異操作變異操作mutation〔〕以概率對(duì)染色體群中的某些染色體的某些位進(jìn)行變異，產(chǎn)生新的個(gè)體染色體、作為交叉運(yùn)算的補(bǔ)充，變異操作可增加車輛分配方案的多樣性，克服求解可能出現(xiàn)的早熟和陷入局部最優(yōu)解的現(xiàn)象。變異概率取不同的值對(duì)算法性能的影響很大；過大，求解時(shí)間明顯增加$但算法收斂于局部最優(yōu)的可能性減少。本文中，取,0.3變異操作mutation〔〕采用反順序變異法改變布爾矩陣中的某些位〔1變成0,0變成1〕，產(chǎn)生新的布爾矩陣。算法停止準(zhǔn)那么的設(shè)計(jì)淘汰不符合約束條件2〕、3〕的染色體。如果，那么轉(zhuǎn)啟發(fā)式算法求解，否那么在染色體群中選擇最小的染色體，作為該問題的求解變量值；與該變量相對(duì)應(yīng)的變量就是優(yōu)化的路線安排。由于該算法屬于種群非重疊&遺傳操作重疊結(jié)構(gòu)的SGA(simplegeneticalgorithm),并在選擇操作前保存當(dāng)前最好解:因此以概率收斂到全局最優(yōu)解。6.7實(shí)例分析本文仍采用的經(jīng)典測試集。用上述的帶時(shí)間窗的遺傳算法，對(duì)一個(gè)有8個(gè)客戶和1個(gè)配送中心，兩輛車〔容量均為8噸〕的配送系統(tǒng)的車輛路徑問題進(jìn)行求解。各客戶的需求和各客戶之間的距離如表1(其中0表示配送中心)，要求合理安排車輛的行駛路線，使總的運(yùn)距最短。表1客戶間距離表設(shè)置車輛數(shù)為3，最大負(fù)載10，車輛容積30，最大行駛距離為200，運(yùn)輸本錢系數(shù)4，平均時(shí)速為40，不考慮裝卸及休息時(shí)間。種群設(shè)為40，最大代數(shù)為400，運(yùn)輸本錢參數(shù)設(shè)為3，時(shí)間懲罰參數(shù)設(shè)為6，并且第4次及第7次實(shí)驗(yàn)中人為設(shè)置較高變異率〔分別為0.089和0.100〕,以到達(dá)人為增加變異次數(shù)防止局部最優(yōu)解的出現(xiàn)，共進(jìn)行了八次運(yùn)算，得到測試結(jié)果如下：表2優(yōu)化結(jié)果表最終優(yōu)化結(jié)果為需要調(diào)度兩臺(tái)車，得到的優(yōu)化路徑為O-A-C-E-H-B-O和O-F-G-D-O,運(yùn)輸長度為67.5，本錢為202.5?？山?jīng)驗(yàn)證，該解正是問題的最優(yōu)解。此實(shí)例引用了參考文獻(xiàn)2中的經(jīng)典案例，通過上面的具體實(shí)例，可以讓我們對(duì)遺傳算法在物流配送中的具體應(yīng)用有了更深的理解。在物流配送業(yè)務(wù)中，合理確定配送路徑是提高效勞質(zhì)量、降低配送本錢、增加經(jīng)濟(jì)效益的重要手段。由于物流配送路徑優(yōu)化問題是一個(gè)NP難題，因此，采用啟發(fā)式算法求解是一個(gè)重要的研究方向。所構(gòu)造的物流配送路徑優(yōu)化的遺傳算法，包括設(shè)計(jì)個(gè)體編碼方法、個(gè)體適應(yīng)度值的計(jì)算方法以及選擇、交叉和變異算子，對(duì)解決類似的組合優(yōu)化問題具有一定的參考價(jià)值。7結(jié)束語隨著畢業(yè)日子的到來，畢業(yè)設(shè)計(jì)也接近了尾聲。經(jīng)過幾周的奮戰(zhàn)我的畢業(yè)設(shè)計(jì)終于完成了。在沒有做畢業(yè)設(shè)計(jì)以前覺得畢業(yè)設(shè)計(jì)只是對(duì)這幾年來所學(xué)知識(shí)的單純總結(jié)，但是通過這次做畢業(yè)設(shè)計(jì)發(fā)現(xiàn)自己的看法有點(diǎn)太片面。畢業(yè)設(shè)計(jì)不僅是對(duì)前面所學(xué)知識(shí)的一種檢驗(yàn)，而且也是對(duì)自己能力的一種提高。通過這次畢業(yè)設(shè)計(jì)使我明白了自己原來知識(shí)還比擬欠缺。自己要學(xué)習(xí)的