畢業(yè)論文----基于遺傳算法的車輛路徑問題研究

1、<p>　　基于遺傳算法的車輛路徑問題研究</p><p>　　中文摘要：近些年,物流作為“第三利潤源泉”受到國內各行業(yè)的極大重視并得到較大的發(fā)展。物流的目標就在于以最少的費用滿足消費者的需求。配送作為物流中一種特殊的、綜合的活動形式,在當今社會經濟發(fā)展中發(fā)揮著越來越重要的作用。配送的核心為配送車輛的調度、貨物配裝及送貨過程。進行配送系統(tǒng)優(yōu)化,主要是配送車輛調度的優(yōu)化。對配送車輛進行優(yōu)化調度,有利于提高

2、物流經濟效益、實現(xiàn)物流科學化。本文主要對單車場非滿載無時間窗的車輛路徑問題和動態(tài)車輛路徑問題進行了研究。論文首先對現(xiàn)有車輛優(yōu)化調度問題歸類分析。然后對車輛路徑問題的傳統(tǒng)求解算法的基本思想、性能、適用性進行了分析,在此基礎上提出了采用掃描法和遺傳算法相結合的啟發(fā)式算法來求解物流配送車輛優(yōu)化調度問題的思想。在對遺傳算法中的選擇操作、鄰域結構操作進行改進的基礎上,提出了一種求解車輛路徑問題的自適應遺傳算法。應用C語言編程進行實例計算,結果表明

3、改進的遺傳算法明顯增強了群體演化的質量,提高了算法的收斂速度,得到了問題的滿意解。與傳統(tǒng)遺傳算法相比,掃描法和改進遺傳算法的結合,其優(yōu)化能力、運行效率、可靠性均有一定的提高。最后論文在對動態(tài)行駛時間車輛路徑問題進行建模</p><p>　　關鍵詞：物流車輛路徑問題; 掃描法; 遺傳算法</p><p>　　Abstract:Recent years, logistics, taken as

4、 "the third profit resource", has been developing rapidly. The object of logistics is to satisfy the requirements of consumers with least cost. As an especial and integrated activity of logistics, physical dist

5、ribution plays an important role in modern society. Vehicle Routing Problem (VRP) is the main part of the distribution system optimizing. It is benefits to make economic benefits.This paper mainly studied a type of vehic

6、le routing problem with sing</p><p>　　Keyword: Vehicle Routing Problem; sweep method; genetic algorithm</p><p><b>　　1引言</b></p><p>　　車輛路徑問題（Vehicle Routing Problem，VRP）是

7、一類在物流配送調度中具有廣泛應用的優(yōu)化組合問題，在現(xiàn)代物流中居于中心地位。 本文首先介紹了遺傳算法在解決簡單約束車輛路徑問題上的應用，改進了交叉算子，為研究有時間窗裝卸問題的遺傳算法作了充分準備。本文詳細分析了有時間窗裝卸問題的數(shù)學模型，深入研究解決此問題的分組編碼遺傳算法，將禁忌思想用于產生可行解的啟發(fā)式插入搜索算法之中，并構造出適用于多目標的適應度函數(shù)，設計新的數(shù)據結構，對分組編碼遺傳算法進行有效實現(xiàn)。</p><

8、;p>　　在分組編碼遺傳算法中提出路徑調整思想，設計出一種多策略分組編碼遺傳算法。采用多組通用算例測算，將多策略分組編碼遺傳算法與其它算法進行比較，其求解結果和計算時間都有明顯改進，驗證了多策略分組編碼遺傳算法能夠有效穩(wěn)定地收斂到所求問題的解。VRP 最早由Dantzig 和Ramser 于1959 年提出，引起運籌學、應用數(shù)學、組合數(shù)學、圖論與網絡分析、物流科學、計算機應用等學科研究人員的極大重視，成為運籌學與組合優(yōu)化領域的熱點

9、問題。各國研究人員對該問題進行了大量的理論研究及實驗分析，取得了重大進展，</p><p>　　其研究成果在運輸系統(tǒng)、公交車輛路線設計、快遞收發(fā)系統(tǒng)、物資調配系統(tǒng)中都已得到了廣泛應用。</p><p>　　研究車輛路徑問題的特點及算法具有重要的實際意義。本文重點研究解決有時間窗裝卸問題（PDPTW）的遺傳算法，作為前期準備，本文作者對遺傳算法解決具有簡單約束條件的VRP（包括有容量約束的車

10、輛路徑問題CVRP 和有時間窗的車輛路徑問題VRPTW）進行了初步研究。有容量約束的車輛路徑問題（Capacitated Vehicle routing problem，CVRP）是由一個服務中心（或車場）的若干車輛向多個客戶點進行配送服務，在已知待服務客戶點和出發(fā)點的位置、客戶需求及車輛最大負載的前提下，設計車輛配送路徑，規(guī)劃設計方案，使運輸成本最小化，即總代價最小（使用車輛盡量少，行車總距離盡量短）。CVRP 實際是多目標組合優(yōu)化問

11、題，一般以派出車輛最少（運輸路線條數(shù)最少）為首要目標，行車總距離最短，即總代價最小為次要目標。CVRP 要求滿足以下條件及假設：</p><p>　?。?）所有的配送車輛以配送中心為起點并最終回到配送中心；</p><p>　?。?）每條配送路徑上各客戶點的需求量之和不超過車輛的負載量；</p><p>　?。?）每個客戶點的需求僅由一輛車一次滿足。</p&g

12、t;<p><b>　　2選題的目的</b></p><p>　　物流已被認為是繼降低原材料消耗和提高勞動生產率之后的“第三利潤源”。通過優(yōu)化物流系統(tǒng),可以降低物流成本,從而增強企業(yè)的市場競爭能力。因此,研究物流系統(tǒng)中的優(yōu)化問題,具有十分重要的意義,是國內外研究的一個熱點。 庫存成本與配送成本是物流系統(tǒng)的核心成本,在物流總成本中占據了很大的比例。如果能降低庫存成本與配送成本,就

13、能有效地降低物流成本。 遺傳算法是一種應用很廣泛的智能優(yōu)化算法,本文對遺傳算法進行了分析研究,針對遺傳算法的一些缺陷提出了相應的改進方法。在上述研究基礎上,本文基于遺傳算法,研究了物流系統(tǒng)中的庫存優(yōu)化問題及車輛路徑問題。本文將庫存仿真優(yōu)化問題與車輛路徑問題都看作是組合優(yōu)化問題,并應用遺傳算法進行求解。 本文的主要研究工作及貢獻可歸納如下: (1)對隨機庫存系統(tǒng)建立了基于離散事件系統(tǒng)的計算機仿真模型。用系統(tǒng)仿真方法求解最優(yōu)庫存策略時,其難

14、點之一在于仿真的優(yōu)化。為此,本文將計算機仿真技術和遺傳算法相結合,應用遺傳算法來優(yōu)化模型的控制參數(shù),即獲得最優(yōu)的庫存控制策略。針對隨機系統(tǒng)的特點,設計了候選解收集器,它能夠收集在仿真優(yōu)化過程中產生的Pareto解;提出了M精英選擇算子,用于保護潛</p><p><b>　　3 問題描述</b></p><p>　　3.1車輛路徑問題定義</p><

15、;p>　　車輛路線問題（VRP）最早是由Dantzig和Ramser于1959年首次提出，它是指一定數(shù)量的客戶，各自有不同數(shù)量的貨物需求，配送中心向客戶提供貨物，由一個車隊負責分送貨物，組織適當?shù)男熊嚶肪€，目標是使得客戶的需求得到滿足，并能在一定的約束下，達到諸如路程最短、成本最小、耗費時間最少等目的。 由此定義不難看出，旅行商問題（Traveling Saleman Problem,TSP）是VRP的特例，由于Gaer

16、y。已證明TSP問題是NP難題，因此，VRP也屬于NP難題。 車輛路線問題自1959年提出以來，一直是網絡優(yōu)化問題中最基本的問題之一，由于其應用的廣泛性和經濟上的重大價值，一直受到國內外學者的廣泛關注。車輛路線問題可以描述如下（如圖1）： </p><p><b>　　圖1 路徑問題描述</b></p><p>　　設有一場站（depot），共有M 輛貨車，車輛容量為

17、Q，有N位顧客（customer），每位顧客有其需求量D。車輛從場站出發(fā)對客戶進行配送服務最后返回場站，要求所有顧客都被配送，每位顧客一次配送完成，且不能違反車輛容量的限制，目的是所有車輛路線的總距離最小。車輛路線的實際問題包括配送中心配送、公共汽車路線制定、信件和報紙投遞、航空和鐵路時間表安排、工業(yè)廢品收集等。</p><p>　　3.2 車輛路徑問題的類型</p><p>　　一般而言

18、車輛路線問題大致可以分為以下三種類型（Ballou，1992）： </p><p>　　1、相異的單一起點和單一終點。 </p><p>　　2、相同的單一起點和終點。 </p><p>　　3、多個起點和終點。 </p><p>　　3.3 車輛路線問題研究現(xiàn)狀</p><p>　　經過幾十年的研究發(fā)展，車輛路線問題

19、研究取得了大量成果。下面從車輛路線問題的現(xiàn)有研究型態(tài)和求解方法兩個方面介紹車輛路線問題的研究現(xiàn)狀。</p><p>　　3.3.1車輛路線問題型態(tài)</p><p>　　在基本車輛路線問題（VRP）的基礎上，車輛路線問題在學術研究和實際應用上產生了許多不同的延伸和變化型態(tài)，包括時窗限制車輛路線問題（vehicle routing problems with time windows，VRPT

20、W）、追求最佳服務時間的車輛路線問題（VRPDT）、多車種車輛路線問題（fleet size and mix vehicle routing problems，F(xiàn)SVRP）、車輛多次使用的車輛路線問題（vehicle routingproblems with multiple use of vehicle，VRPM）、考慮收集的車輛路線問題（vehicle routingproblems with backhauls，VRPB）、隨機需

21、求車輛路線問題（vehicle routing problem with stochastic demand，VRPSD）等。 </p><p><b>　　3.3.2解決方法</b></p><p>　　1、求解方法演進 綜合過去有關車輛路線問題的求解方法，可以分為精確算法（exact algorithm）與啟發(fā)式解法（heuristics），其中精密算法有分支界

22、限法、分支切割法、集合涵蓋法等；啟發(fā)式解法有節(jié)約法、模擬退火法、確定性退火法、禁忌搜尋法、基因算法、神經網絡、螞蟻殖民算法等。1995年，F(xiàn)isher曾將求解車輛路線問題的算法分成三個階段。第一階段是從1960年到1970年，屬于簡單啟發(fā)式方式，包括有各種局部改善啟發(fā)式算法和貪婪法（Greedy）等；第二階段是從1970年到1980年，屬于一種以數(shù)學規(guī)劃為主的啟發(fā)式解法，包括指派法、集合分割法和集合涵蓋法；第三階段是從1990開始至今，

23、屬于較新的方法，包括利用嚴謹啟發(fā)式方法、人工智能方法等。 </p><p>　　2、啟發(fā)式算法 由于VRP是NP-hard問題，難以用精確算發(fā)求解，啟發(fā)式算法是求解車輛運輸問題的主要方法，多年來許多學者對車輛運輸問題進行了研究，提出了各種各樣的啟發(fā)式方法。車輛運輸問題的啟發(fā)式方法可以分為簡單啟發(fā)式算法、兩階段啟發(fā)式算法、人工智能方法建立的啟發(fā)式方法。 </p><p>　　簡單啟發(fā)式方法

24、包括節(jié)省法或插入法、路線內/間節(jié)點交換法、貪婪法和局部搜索法等方法。節(jié)省法或插入法（savings or insertion）是在求解過程中使用節(jié)省成本最大的可行方式構造路線，直到無法節(jié)省為止。交換法則是依賴其他方法產生一個起始路線，然后以迭代的方式利用交換改善法減少路線距離，直到不能改善為止。1960年，Clarke和Wrigh首先提出一種啟發(fā)式節(jié)省法（savings methods）來建立車隊配送路線。簡單啟發(fā)式方法簡單易懂、求解速

25、度快，但只適合求解小型、簡單的VRP問題。 </p><p>　　兩階段方法包括先分組后定路線（clusterfirst-route second）和先定路線后分組（routefirst-cluster second）兩種啟發(fā)式策略。前者是先將所有需求點大略分為幾個組，然后再對各個組分別進行路線排序；后者則是先將所有的需求點建構成一條路線，再根據車輛的容量將這一路線分割成許多適合的單獨路線。 </p>

26、<p>　　1990年以來，人工智能方法在解決組合優(yōu)化問題上顯示出強大功能，在各個領域得到充分應用，很多學者也將人工智能引入車輛路線問題的求解中，并構造了大量的基于人工智能的啟發(fā)式算法。禁忌搜索法（TS）基本上是屬于一種人工智能型（AI）的局部搜尋方法，Willard首先將此算法用來求解VRP ，隨后亦有許多位學者也發(fā)表了求解VRP的TS 算法。西南交通大學的袁慶達等設計了考慮時間窗口和不同車輛類型的禁忌算法，這種算法主要

27、采用GENIUS方法產生初始解，然后禁忌算法對初始解優(yōu)化。模擬退火方法具有收斂速度快，全局搜索的特點，Osman對VRP的模擬退火算法進行了研究，他提出的模擬退火方法主要適合于解決路線分組。遺傳算法具有求解組合優(yōu)化問題的良好特性，Holland首先采用遺傳算法（GA）編碼解決VRPTW 問題?，F(xiàn)在多數(shù)學者采用混合策略，分別采用兩種人工智能方法進行路線分組和路線優(yōu)化。Ombuk提出了用遺傳算法進行路線分組，然后用禁忌搜索方法進行路線優(yōu)化的

28、混合算法。Bent和Van Hentenryck則首先用模擬退火算法將車輛路線的數(shù)量最小化，然后用大鄰域搜索法（largneighborhood </p><p>　　總結幾種人工智能方法可以看出，TS算法所得到的解最接近最優(yōu)解，但其運算時間也最長，是GA算法的2～3倍，SA算法的近20倍；由于GA算法也能較好的逼近最優(yōu)解，同時使運算時間大大縮短，所以GA算法能兼顧運算時間和效率兩方面，是具有較好的發(fā)展前途的方法

29、；SA算法求解速度非?？?，也能提供一定程度上的優(yōu)化方案在求解較小規(guī)模問題上具有較好效果。 </p><p><b>　　4 遺傳算法介紹</b></p><p>　　遺傳算法簡稱 GA(Genetic Algorithm)，在本質上是一種不依賴具體問題的直接搜索方法。它是根據生物進化思想而啟發(fā)得出的一種全局優(yōu)化算法。遺傳算法的概念最早是由Bagley J.D 在196

30、7 年提出的；而開始遺傳算法的理論和方法的系統(tǒng)性研究的是1975 年，這一開創(chuàng)性工作是由Michigan 大學的J.H. Holland 所實行。當時，其主要目的是說明自然和人工系統(tǒng)的自適應過程。</p><p>　　遺傳算法是受生物進化學說和遺傳學說啟發(fā)而發(fā)展起來的，基于適者生存思想的一種較通用的問題求解方法。利用遺傳算法進行尋優(yōu)時，編碼、選擇、交叉、變異是四個重要步驟。遺傳算法作為一種全局優(yōu)化搜索方法，具有簡

31、單、通用普適性強，適用于并行處理和應用范圍廣等優(yōu)點。遺傳算法在優(yōu)化領域表現(xiàn)出了其強大的能力，遺傳算法仿照生物進化和遺傳的規(guī)律，利用復制、交換和突變等操作，使優(yōu)勝者繁殖，劣敗者消失，一代代重復同樣的操作，最終找出最優(yōu)解。具有如下特點：(1) 遺傳算法運算的是解集的編碼，而不是解集本身；(2) 遺傳算法的搜索始于解的一個種群，而不是單個解；(3) 遺傳算法只使用報酬信息（適值函數(shù)），不使用導數(shù)或其他輔助知識；(4) 遺傳算法采用概率

32、的，而不是確定的狀態(tài)轉移規(guī)則。 遺傳算法特別適用于傳統(tǒng)搜索方法難以解決的復雜的和非線性的問題，可廣泛用于組合優(yōu)化、自適應控制、規(guī)劃設計和人工生命等領域。作為一種隨機優(yōu)化技術在解優(yōu)化問題中顯示了優(yōu)于傳統(tǒng)優(yōu)化算法的性能，遺傳算法的一個顯著優(yōu)勢是不需要目標函數(shù)明確的數(shù)學方程和導數(shù)表達式，同時又是一種全局尋優(yōu)算法，不會象某些傳統(tǒng)算法易于陷入局部最優(yōu)解。 </p><p><b>　　1)參數(shù)編碼；

33、</b></p><p>　　2)初始群體的設定；</p><p>　　3)適應度函數(shù)的設計；</p><p><b>　　4)遺傳操作設計；</b></p><p>　　5）控制參數(shù)設定(主要是指群體大小和使用遺傳操作的概率等)。</p><p>　　這5個要素構成了遺傳算法的核心內

34、容。</p><p>　　4.1 遺傳算法的基本思想</p><p>　　遺傳算法是受生物進化學說和遺傳學說啟發(fā)而發(fā)展起來的，基于適者生存思想的一種較通用的問題求解方法。利用遺傳算法進行尋優(yōu)時，編碼、選擇、交叉、變異是四個重要步驟。遺傳算法作為一種全局優(yōu)化搜索方法，具有簡單、通用普適性強，適用于并行處理和應用范圍廣等優(yōu)點。遺傳算法在優(yōu)化領域表現(xiàn)出了其強大的能力，遺傳算法仿照生物進化和遺傳的

35、規(guī)律，利用復制、交換和突變等操作，使優(yōu)勝者繁殖，劣敗者消失，一代代重復同樣的操作，最終找出最優(yōu)解。具有如下特點：(1) 遺傳算法運算的是解集的編碼，而不是解集本身；(2) 遺傳算法的搜索始于解的一個種群，而不是單個解；(3) 遺傳算法只使用報酬信息（適值函數(shù)），不使用導數(shù)或其他輔助知識；(4) 遺傳算法采用概率的，而不是確定的狀態(tài)轉移規(guī)則。</p><p>　　4.2 遺傳算法流程圖</p>

36、<p>　　圖2 遺傳算法流程圖</p><p>　　5 模型建立求解及實例應用</p><p><b>　　5.1車輛調度模型</b></p><p>　　根據上述對問題的描述，可以采用混合整數(shù)規(guī)劃方法對車輛調度進行建模"設N為最小成本，則目標函數(shù)為</p><p><b>　　滿足約束

37、條件1：</b></p><p>　　式中：K為所有車輛的集合， ；G為所有客戶的集合， </p><p>　　， ，其中{0}代表配送中心； 為由車輛k服務的客戶的集合； 為車輛到達客戶i的時間；為懲罰函數(shù)，車輛在時間 到達客戶i時所對應的懲罰成本；為車輛從客戶i到客戶j的所有運輸成本；為車輛從客戶i到客戶

38、j的行車時間；為客戶i的需求量；Q為車輛k的最大裝載量；為車輛在客戶i處的停留的時間。</p><p>　　另外，變量和的值為0或1。若車輛k為客戶i服務，則1，否則為0，即：此變量表示車輛分配方案，可用布爾矩陣表示；若車輛k經由客戶i到客戶j，則為1，否則為0，即：，表示車輛路線安排。</p><p>　　約束條件2：保證每個客戶均被服務，而且每輛車都從配送中心出發(fā)；</p>

39、<p>　　約束條件3：表示每輛車負責的客戶點的貨物需求量總和不超過該車輛的最大裝載量；</p><p>　　約束條件4、5：表示對任一由k服務的客戶點j必定有另一(而且只有一個)由k服務的客戶點(包括配送中心)I,車輛k從客戶點i到達客戶點j,而對由k服務的客戶點i同樣存在由k服務的另一客戶點,車輛k是從該客戶點到達客戶點i的,依次類推；</p><p>　　約束條件6：保

40、證每輛車的行車路線的總耗時不超過一個事先定下的數(shù)值；</p><p>　　約束條件7：對某個客戶點，車輛到達時間限制在某一時間段內。</p><p>　　根據實際情況，本文采用軟限制時間窗，其懲罰函數(shù)如圖2所示。其中，為客戶所要求的送貨時區(qū)，為時間窗，超過該范圍客戶將拒絕收貨，因此設定一個極大的懲罰成本以避免此情況的發(fā)生。</p><p><b>　　圖3

41、 懲罰函數(shù)</b></p><p>　　5.2 帶時間窗的物流配送問題優(yōu)化問題</p><p>　　帶時間窗 VRP（VRP with Time Windows，VRPTW）是帶裝載能力約束的CVRP(Capacitated VRP，CVRP)的擴展。在該類問題中，有車輛裝載能力約束，且每個客戶i 都有一個與之相聯(lián)系的時間區(qū)間[ai ,bi]，稱為時間窗。客戶的服務必須在相應的

42、時間窗內開始，車輛必須在客戶點停留的時間長度為si。按客戶對物流中心違反時間窗約束規(guī)定時的接受程度，可分為硬時間窗、軟時間窗和混合型時間窗。硬時間窗(Hard Time Windows)：指配送車輛必須在特定時間區(qū)段，將貨物送達顧客手中，不論是遲到或早到都完全不予接受；軟時間窗(Soft Time Windows)：允許服務的開始時間有所偏離時間窗，則必須按照違反時間的長短施以一定的罰金或其他懲罰法則；混合型時間窗（Mixed Time

43、 Windows）：是指系統(tǒng)中有些客戶只接受硬時間窗服務，有些客戶接受軟時間窗服務，或者同一客戶，往往軟、硬兩種時間窗服務混合使用。</p><p>　　如問題為硬時間窗問題，則必須滿足到客戶i 的時間要比承諾到達時間早，即到達i 的時間≤到達i 的最晚時間限制；</p><p>　　如有緊急貨物（高優(yōu)先級客戶）時，則自動將優(yōu)先級高的貨物按優(yōu)先級順序排入隊列前端，然后將其它普通貨物再進行優(yōu)

44、化；即如有N 個客戶，其中有一個為緊急運單，則自動將其放在隊首，其他N-1 個客戶進行優(yōu)化，即將問題降為N-1 階的路徑優(yōu)化問題；</p><p>　　任一客戶只由一臺運輸車輛提供服務，即算法解決的是任一客戶的貨物需求均小于車輛最大負載（容積）的情況。如出現(xiàn)某客戶需求量大于車輛負載（容積）的情況時，需要先派車為其運輸，直至該客戶剩余貨物需求量小于車輛最大負載（容積）即可參加優(yōu)化調度。</p><

45、;p>　　5.3帶時間窗的物流配送路徑問題的遺傳算法</p><p>　　5.3.1染色體結構編碼</p><p>　　根據物流配送路徑優(yōu)化問題的特點，本文采用了簡單直觀的自然數(shù)編碼方法，用0表示配送中心，用1、2、…、L 表示各需求點。由于在配送中心有m 輛汽車，則最多存在m 條配送路徑，每條配送路徑都始于配送中心，也終于配送中心。為了在編碼中反映車輛配送的路徑，采用了增加m－1

46、個虛擬配送中心的方法，分別用L＋1、L＋2、…、L＋K－l 表示。這樣，l、2、…、L＋m－l 這L＋m－l 個互不重復的自然數(shù)的隨機排列就構成一個個體，并對應一種配送路徑方案。例如，對于一個有6 個需求點，用2 輛汽車完成配送任務的問題，</p><p>　　則可用0、2、…、6 (0 表示配送中心)這7 個自然數(shù)的隨機排列表示物流配送路徑方案。如個體0l26354 表示的配送路徑方案為：路徑1：0-1-2-6

47、，路徑2：3-5-4共有2條配送路徑；</p><p>　　5.3.2 種群的初始化</p><p>　　群體初始化時，采用兩種機制，一種是隨機生成個體，一種是按前相插入啟發(fā)式算法。本文采用隨機產生一種l～L＋m－l 這L＋m－l 個互不重復的自然數(shù)的排列，即形成一個個體。設群體規(guī)模為M，則通過隨機產生M 個這樣的個體，即形成初始群體。</p><p>　　5.3.

48、3 適應度分析</p><p>　　初始種群形成以后，需要通過種群的適應度函數(shù)，對種群中的每個染色體進評價，并以此為標準選擇最優(yōu)解。由于適應度函數(shù)通常越大越好，而物流車輛路徑優(yōu)化問題則是求最小經濟成本，為了便于計算且增大區(qū)分度，算法采用的是目標函數(shù)的倒數(shù)乘以區(qū)分度系數(shù)β作為適應度函數(shù)，即</p><p>　　maxF = 1 / S * β (3-2-3-1)</p><

49、;p>　　5.3.4 遺傳算子</p><p><b>　　1. 遺傳選擇</b></p><p>　　選擇是用來確定重組或交叉?zhèn)€體，以及被選個體將產生多少個子代個體。新種群的產生是在上一代的基礎上對原有的各染色體按其適應度大小進行保留，并將其進行交叉和變異形成新一代的個體；適應度計算之后是實際的選擇，按照適應度進行父代個體的選擇，本文由輪盤賭算法進行種子的選取

50、；計算每個個體的相對適應度值，以之作為概率，將[0,1]空間劃分成n 份。生成一個[0,1]范圍內的隨機數(shù)，看它落在哪個區(qū)域，則選擇該個體。</p><p>　　2. 遺傳基因的交叉</p><p>　　對通過選擇操作產生的新群體，需要進行配對交叉重組。簡單的說就是人為選取較好的一對染色體作為新染色體的父母，按染色體按長度分為前后兩段，取其中一個染色體的前半部分放在另一個染色體的前邊，再順

51、序遍歷新染色體的基因并剔除重復基因，從而得到新的染色體child1。同理，可以得到另一個新染色體child2。在得到新的兩個染色體后，為了使下一代染色體具有更高的適應度，算法加入了淘汰機制，即比較兩個新染色體，保留較好的一個進入下一代，同時將較差的一個舍棄。在此引入新的 CX 交叉算子。實施交叉操作。其操作方法如下：首先，隨機在父代染色體中選擇一個交配區(qū)域，如兩個父代染色體及交配區(qū)域選定為：</p><p>　　

52、A=3 5|6 2 9 8|4 7 1</p><p>　　B=8 3|2 9 5 4|1 6 7</p><p>　　其次，將B 的交配區(qū)域加到A 的前面，A 的交配區(qū)域加到B 的前面，得到：</p><p>　　'A=2 9 5 4|3 5 6 2 9 8 4 7 1</p><p>　　'B=6 2 9 8|8 3 2

53、9 5 4 1 6 7</p><p>　　最后在'A， 'B 中自交配區(qū)域后依次刪除與交配區(qū)域相同的自然數(shù)，得到最終的兩個后代：</p><p>　　C1=2 9 5 4 3 6 8 7 1</p><p>　　C2=6 2 9 8 3 8 4 1 7</p><p>　　3. 遺傳基因的變異</p><

54、p>　　基因的變異是在選出的染色體中按其變異概率隨機找出若干基因位置，再隨機產生一個基因替換原有位置基因，并查找因替換基因產生的此基因的另一重復位置，修改使之成為一個不重復基因染色體。為了使后代繼承更多的父代的基因信息，本文取變異概率Pm 為0.02 左右。</p><p>　　5.3.5 函數(shù)控制的終止條件</p><p>　　優(yōu)化算法的結束條件是系統(tǒng)設定的最大遺傳代數(shù)。即事先設置

55、一個最大代數(shù)，如當前代數(shù)大于最大代數(shù)時，算法停止。判斷迭代的代數(shù)是否為要求代數(shù)maxt，若是，停止進化，選性能最好的染色體所對應的路徑集合，作為問題的優(yōu)化解輸出。</p><p><b>　　5.3.6 步驟</b></p><p>　　Step1：t=0，利用自然數(shù)編碼方式，采用前相插入啟發(fā)式算法和隨機的方式產生初始種群，并輸入控制參數(shù)；</p>&l

56、t;p>　　Step2：計算個體適應度；</p><p>　　Step3：t <maxt，t=t+1，則轉Step4；否則停止計算，并輸出結果；</p><p>　　Step4：采用基于個體濃度的群體多樣性保持策略來選擇個體；</p><p>　　Step5：對個體進行CX 交叉重組；</p><p>　　Step6：按照變異方法

57、對個體進行變異；</p><p>　　Step7：重復步驟2-6；</p><p><b>　　6算法的建立和求解</b></p><p>　　車輛優(yōu)化調度問題由車輛分配和路線安排這兩個相互關聯(lián)的子問題組成，但關鍵是確定優(yōu)化的車輛分配方案（即求解變量）。一旦車輛分配方案確定，那么路線安排問題也就比較容易求解（即求解變量）。可以采用遺傳算法的思想

58、作為總體框架對該問題進行求解，用遺傳算法求解變量，而變量則用啟發(fā)式算法求解。</p><p><b>　　6.1編碼操作</b></p><p>　　遺傳算法的關鍵之一是確定染色體并對它進行編碼處理。對于車輛調度問題，可將求解變量看作染色體，因此，一條染色體就代表一種可能的車輛分配方案，然后可用布爾矩陣對該染色體的基因鏈進行編碼。對于m輛車、n個客戶的車輛分配,可表示

59、成mn矩陣。例如，圖1的布爾矩陣為</p><p>　　即車輛1負責客戶1和2，車輛2負責客戶3、4和5.</p><p>　　6.2定義適配值計算函數(shù)</p><p>　　適應度函數(shù)是遺傳算法中評價解集好壞的依據,適配值高的個體優(yōu)先培養(yǎng)。在本問題中，對于種群數(shù)目為N的染色體群，其個體染色體i的適配值的值越小,則表示個體適配值越高。個體適配值為</p>

60、<p>　　式中，所以，目標函數(shù)</p><p><b>　　生成初始染色體種群</b></p><p>　　初始化遺傳世代；每一代的染色體群的種群數(shù)目；交叉概率，變異概率 等參數(shù)。隨機產生初始車輛分配方案，并淘汰不符合約束條件的染色體,直到染色體群的種群數(shù)達N條。N的取值不宜過大或過小。過大不但增加計算量，而且不能有效地獲得迭代解。過小將不能保證分

61、配方案的多樣性，本算法中取種群大小，交叉概率,變異概。</p><p>　　6.3用啟發(fā)式算法求解單一車輛排序問題</p><p>　　對變量的求解實質上是一個帶時間約束的單一車輛排序問題，即對中的元素進行排序，求解最小的，以滿足約束條件。該子問題可表示為</p><p><b>　　滿足約束條件：</b></p><p&g

62、t;　　本文采用文獻[3]中的啟發(fā)式方法進行求解。首先對中的元素按照客戶要求到達的時間從小到大進行排序，如果有兩個以上的客戶要求到達的時間相同，則對這些客戶按照配送區(qū)域（時區(qū)）從小到大進行排序。淘汰不符合約束條件的解，調整次序重新搜索，直到找到較佳的可行解為止。對每一條染色體，求解變量，并計算每一條染色體的適配值：</p><p><b>　　!</b></p><p&g

63、t;　　6.4種群的選擇與復制</p><p>　　本算法采用與適配值成比例的概率方法，對種群的個體進行選擇與復制。首先根據前面計算的計算個體i在下一代中應復制自身的比例；定義選擇概率為個體適配值所占比例的反向排序$即適配值最小的車輛分配方案其選擇概率最大；依據選擇概率對種群中的個體進行復制，選擇概率大的個體被重復復制的機會大，而選擇概率小的個體則趨向于減少或淘汰，直到復制N條染色體。</p>&l

64、t;p><b>　　6.5交叉操作</b></p><p>　　由于復制操作并沒有產生新的車輛分配方案，因此種群中最好的個體的適配值并沒有降低。對染色體群實施交叉操作crossover（）可以產生新的體。以概率對染色體群隨機地交換兩個個體的某些片段產生新的個體染色體，即對選定的需進行交叉運算的每一組布爾矩陣隨機設定交叉位置$通過交換布爾矩陣中的某些行或列的部分信息（二進制位），其他位不

65、變，從而生成兩個新的布爾矩陣。交叉概率對算法的收斂有較大的影響，越大，優(yōu)秀的個體出現(xiàn)的幾率也越大，新舊個體替換快，算法收斂也快。的經驗值為,0.25~1.000.75效果較佳。</p><p><b>　　6.6變異操作</b></p><p>　　變異操作mutation（）以概率對染色體群中的某些染色體的某些位進行變異，產生新的個體染色體、作為交叉運算的補充，變異

66、操作可增加車輛分配方案的多樣性，克服求解可能出現(xiàn)的早熟和陷入局部最優(yōu)解的現(xiàn)象。變異概率取不同的值對算法性能的影響很大；過大，求解時間明顯增加$但算法收斂于局部最優(yōu)的可能性減少。本文中，取,0.3變異操作mutation（）采用反順序變異法改變布爾矩陣中的某些位（1變成0,0變成1），產生新的布爾矩陣。算法停止準則的設計淘汰不符合約束條件2）、3）的染色體。如果，則轉啟發(fā)式算法求解，否則在染色體群中選擇最小的染色體，作為該問題的求解變量值

67、；與該變量相對應的變量就是優(yōu)化的路線安排。由于該算法屬于種群非重疊&遺傳操作重疊結構的SGA(simple genetic algorithm),并在選擇操作前保留當前最好解:因此以概率收斂到全局最優(yōu)解。</p><p><b>　　6.7 實例分析</b></p><p>　　本文仍采用的經典測試集。用上述的帶時間窗的遺傳算法，對一個有8 個客戶和1個配送中

68、心，兩輛車（容量均為8 噸）的配送系統(tǒng)的車輛路徑問題進行求解。已知各客戶的需求和各客戶之間的距離如表 1(其中0 表示配送中心)，要求合理安排車輛的行駛路線，使總的運距最短。</p><p><b>　　表1客戶間距離表</b></p><p>　　設置車輛數(shù)為 3，最大負載10，車輛容積30，最大行駛距離為200，運輸成本系數(shù)4，平均時速為40，不考慮裝卸及休息時間

69、。種群設為40，最大代數(shù)為400，運輸成本參數(shù)設為3，時間懲罰參數(shù)設為6，并且第4 次及第7 次實驗中人為設置較高變異率（分別為0.089和0.100）,以達到人為增加變異次數(shù)避免局部最優(yōu)解的出現(xiàn)，共進行了八次運算，得到測試結果如下：</p><p><b>　　表2優(yōu)化結果表</b></p><p>　　最終優(yōu)化結果為需要調度兩臺車，得到的優(yōu)化路徑為O-A-C-E-

70、H-B-O 和O-F-G-D-O,運輸長度為67.5，成本為202.5?？山涷炞C，該解正是問題的最優(yōu)解。</p><p>　　此實例引用了參考文獻 2 中的經典案例，通過上面的具體實例，可以讓我們對遺傳算法在物流配送中的具體應用有了更深的理解。在物流配送業(yè)務中，合理確定配送路徑是提高服務質量、降低配送成本、增加經濟效益的重要手段。由于物流配送路徑優(yōu)化問題是一個NP難題，因此，采用啟發(fā)式算法求解是一個重要的研究方向

71、。所構造的物流配送路徑優(yōu)化的遺傳算法，包括設計個體編碼方法、個體適應度值的計算方法以及選擇、交叉和變異算子，對解決類似的組合優(yōu)化問題具有一定的參考價值。</p><p><b>　　7 結束語</b></p><p>　　隨著畢業(yè)日子的到來，畢業(yè)設計也接近了尾聲。經過幾周的奮戰(zhàn)我的畢業(yè)設計終于完成了。在沒有做畢業(yè)設計以前覺得畢業(yè)設計只是對這幾年來所學知識的單純總結，但

72、是通過這次做畢業(yè)設計發(fā)現(xiàn)自己的看法有點太片面。畢業(yè)設計不僅是對前面所學知識的一種檢驗，而且也是對自己能力的一種提高。通過這次畢業(yè)設計使我明白了自己原來知識還比較欠缺。自己要學習的東西還太多，以前老是覺得自己什么東西都會，什么東西都懂，有點眼高手低。通過這次畢業(yè)設計，我才明白學習是一個長期積累的過程，在以后的工作、生活中都應該不斷的學習，努力提高自己知識和綜合素質。</p><p>　　在這次畢業(yè)設計中也使我們的同

73、學關系更進一步了，同學之間互相幫助，有什么不懂的大家在一起商量，聽聽不同的看法對我們更好的理解知識，所以在這里非常感謝幫助我的同學。</p><p>　　我的心得也就這么多了，總之，不管學會的還是學不會的的確覺得困難比較多，真是萬事開頭難，不知道如何入手。最后終于做完了有種如釋重負的感覺。此外，還得出一個結論：知識必須通過應用才能實現(xiàn)其價值！有些東西以為學會了，但真正到用的時候才發(fā)現(xiàn)是兩回事，所以我認為只有到真正

74、會用的時候才是真的學會了。</p><p>　　在此要感謝我的指導老師雷德明對我悉心的指導，感謝老師給我的幫助。在設計過程中，我通過查閱大量有關資料，與同學交流經驗和自學，并向老師請教等方式，使自己學到了不少知識，也經歷了不少艱辛，但收獲同樣巨大。在整個設計中我懂得了許多東西，也培養(yǎng)了我獨立工作的能力，樹立了對自己工作能力的信心，相信會對今后的學習工作生活有非常重要的影響。而且大大提高了動手的能力，使我充分體會到

75、了在創(chuàng)造過程中探索的艱難和成功時的喜悅。雖然這個設計做的也不太好，但是在設計過程中所學到的東西是這次畢業(yè)設計的最大收獲和財富，使我終身受益。</p><p><b>　　8 參考文獻</b></p><p>　　[1] 鐘石泉，賀國光. 單車場復雜情況下的車輛調度[J]. 系統(tǒng)工程，2005,23(5):29-32.</p><p>　　[2]

76、 肖健梅，黃有方，李軍軍,等. 基于離散微粒群優(yōu)化的物流配送車輛路徑問題[J]. 系統(tǒng)工程，2005,23(4):97-100.</p><p>　　[3] 張建勇，郭耀煌，李軍. 基于顧客滿意度的多目標模糊車輛優(yōu)化調度問題研究[J]. 鐵道學報，2003,25(2):15-17.</p><p>　　[4] 李軍，郭耀煌. 物流配送車輛優(yōu)化調度理論與方法[M]. 北京：中國物資出版社，2

77、001.</p><p>　　[5] 郭惠昕，車曉毅，肖偉躍. 混沌遺傳優(yōu)化算法及其在機械優(yōu)化設計中的應用[J]. 機械設計，2003,20(10):23-25.</p><p>　　[6] Yung-Chien Lin, Feng-Sheng Wang, Kao-Shing Hwang. A hybrid method of evolutionary algorithms for mix

78、ed-integer nonlinear optimization problems[C] // Proceedings of the 1999 Congress on Evolutionary Computation, 1999:2160-2166.</p><p>　　[7] 李愛國. 多粒子群協(xié)同優(yōu)化算法[J]. 復旦大學學報，2004(6):87-90.</p><p>　　[8]

79、 陳一永，韓紅，龔延成. 帶時間約束的配載車輛調度問題研究[J]. 物流技術，2005,25(3):48-50.</p><p>　　[9] Savelsbergh M.Local search for routing problem with time windows. Annals of OperationsResearch,1985,16(4): 285-305.</p><p>　

80、　[10] 曾凡超. 車輛路徑問題的改進遺傳算法[J]，重慶大學, 2007.</p><p>　　[11] 徐天亮. 運輸與配送[M]，北京：中國物資出版社, 2002.</p><p>　　[12] 晏夢君. 遺傳算法在配送線路優(yōu)化系統(tǒng)中的應用[J], 吉林大學, 2007.4.</p><p>　　[13]Laporte.GThevehieleroutingp