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

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

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

3、改進的遺傳算法明顯增強了群體演化的質(zhì)量,提高了算法的收斂速度,得到了問題的滿意解。與傳統(tǒng)遺傳算法相比,掃描法和改進遺傳算法的結(jié)合,其優(yōu)化能力、運行效率、可靠性均有一定的提高。最后論文在對動態(tài)行駛時間車輛路徑問題進行建模</p><p>　　關(guān)鍵詞：物流車輛路徑問題; 掃描法; 遺傳算法</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、一類在物流配送調(diào)度中具有廣泛應(yīng)用的優(yōu)化組合問題，在現(xiàn)代物流中居于中心地位。 本文首先介紹了遺傳算法在解決簡單約束車輛路徑問題上的應(yīng)用，改進了交叉算子，為研究有時間窗裝卸問題的遺傳算法作了充分準備。本文詳細分析了有時間窗裝卸問題的數(shù)學(xué)模型，深入研究解決此問題的分組編碼遺傳算法，將禁忌思想用于產(chǎn)生可行解的啟發(fā)式插入搜索算法之中，并構(gòu)造出適用于多目標的適應(yīng)度函數(shù)，設(shè)計新的數(shù)據(jù)結(jié)構(gòu)，對分組編碼遺傳算法進行有效實現(xiàn)。</p><

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

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

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

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

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

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

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

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

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

17、Q，有N位顧客（customer），每位顧客有其需求量D。車輛從場站出發(fā)對客戶進行配送服務(wù)最后返回場站，要求所有顧客都被配送，每位顧客一次配送完成，且不能違反車輛容量的限制，目的是所有車輛路線的總距離最小。車輛路線的實際問題包括配送中心配送、公共汽車路線制定、信件和報紙投遞、航空和鐵路時間表安排、工業(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>　　經(jīng)過幾十年的研究發(fā)展，車輛路線問題

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

20、W）、追求最佳服務(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、求解方法演進 綜合過去有關(guān)車輛路線問題的求解方法，可以分為精確算法（exact algorithm）與啟發(fā)式解法（heuristics），其中精密算法有分支界

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

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

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

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

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

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

28、混合算法。Bent和Van Hentenryck則首先用模擬退火算法將車輛路線的數(shù)量最小化，然后用大鄰域搜索法（largneighborhood </p><p>　　總結(jié)幾種人工智能方法可以看出，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)，在本質(zhì)上是一種不依賴具體問題的直接搜索方法。它是根據(jù)生物進化思想而啟發(fā)得出的一種全局優(yōu)化算法。遺傳算法的概念最早是由Bagley J.D 在196

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

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

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

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

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

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

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

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

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

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

40、證每輛車的行車路線的總耗時不超過一個事先定下的數(shù)值；</p><p>　　約束條件7：對某個客戶點，車輛到達時間限制在某一時間段內(nèi)。</p><p>　　根據(jù)實際情況，本文采用軟限制時間窗，其懲罰函數(shù)如圖2所示。其中，為客戶所要求的送貨時區(qū)，為時間窗，超過該范圍客戶將拒絕收貨，因此設(shè)定一個極大的懲罰成本以避免此情況的發(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]，稱為時間窗。客戶的服務(wù)必須在相應(yīng)的

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

43、 Windows）：是指系統(tǒng)中有些客戶只接受硬時間窗服務(wù)，有些客戶接受軟時間窗服務(wù)，或者同一客戶，往往軟、硬兩種時間窗服務(wù)混合使用。</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>　　任一客戶只由一臺運輸車輛提供服務(wù)，即算法解決的是任一客戶的貨物需求均小于車輛最大負載（容積）的情況。如出現(xiàn)某客戶需求量大于車輛負載（容積）的情況時，需要先派車為其運輸，直至該客戶剩余貨物需求量小于車輛最大負載（容積）即可參加優(yōu)化調(diào)度。</p><

45、;p>　　5.3帶時間窗的物流配送路徑問題的遺傳算法</p><p>　　5.3.1染色體結(jié)構(gòu)編碼</p><p>　　根據(jù)物流配送路徑優(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 個互不重復(fù)的自然數(shù)的隨機排列就構(gòu)成一個個體，并對應(yīng)一種配送路徑方案。例如，對于一個有6 個需求點，用2 輛汽車完成配送任務(wù)的問題，</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ā)式算法。本文采用隨機產(chǎn)生一種l～L＋m－l 這L＋m－l 個互不重復(fù)的自然數(shù)的排列，即形成一個個體。設(shè)群體規(guī)模為M，則通過隨機產(chǎn)生M 個這樣的個體，即形成初始群體。</p><p>　　5.3.

48、3 適應(yīng)度分析</p><p>　　初始種群形成以后，需要通過種群的適應(yīng)度函數(shù)，對種群中的每個染色體進評價，并以此為標準選擇最優(yōu)解。由于適應(yīng)度函數(shù)通常越大越好，而物流車輛路徑優(yōu)化問題則是求最小經(jīng)濟成本，為了便于計算且增大區(qū)分度，算法采用的是目標函數(shù)的倒數(shù)乘以區(qū)分度系數(shù)β作為適應(yīng)度函數(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)€體，以及被選個體將產(chǎn)生多少個子代個體。新種群的產(chǎn)生是在上一代的基礎(chǔ)上對原有的各染色體按其適應(yīng)度大小進行保留，并將其進行交叉和變異形成新一代的個體；適應(yīng)度計算之后是實際的選擇，按照適應(yīng)度進行父代個體的選擇，本文由輪盤賭算法進行種子的選取

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

51、序遍歷新染色體的基因并剔除重復(fù)基因，從而得到新的染色體child1。同理，可以得到另一個新染色體child2。在得到新的兩個染色體后，為了使下一代染色體具有更高的適應(yīng)度，算法加入了淘汰機制，即比較兩個新染色體，保留較好的一個進入下一代，同時將較差的一個舍棄。在此引入新的 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>　　基因的變異是在選出的染色體中按其變異概率隨機找出若干基因位置，再隨機產(chǎn)生一個基因替換原有位置基因，并查找因替換基因產(chǎn)生的此基因的另一重復(fù)位置，修改使之成為一個不重復(fù)基因染色體。為了使后代繼承更多的父代的基因信息，本文取變異概率Pm 為0.02 左右。</p><p>　　5.3.5 函數(shù)控制的終止條件</p><p>　　優(yōu)化算法的結(jié)束條件是系統(tǒng)設(shè)定的最大遺傳代數(shù)。即事先設(shè)置

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

75、了在創(chuàng)造過程中探索的艱難和成功時的喜悅。雖然這個設(shè)計做的也不太好，但是在設(shè)計過程中所學(xué)到的東西是這次畢業(yè)設(shè)計的最大收獲和財富，使我終身受益。</p><p><b>　　8 參考文獻</b></p><p>　　[1] 鐘石泉，賀國光. 單車場復(fù)雜情況下的車輛調(diào)度[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)化調(diào)度問題研究[J]. 鐵道學(xué)報，2003,25(2):15-17.</p><p>　　[4] 李軍，郭耀煌. 物流配送車輛優(yōu)化調(diào)度理論與方法[M]. 北京：中國物資出版社，2

77、001.</p><p>　　[5] 郭惠昕，車曉毅，肖偉躍. 混沌遺傳優(yōu)化算法及其在機械優(yōu)化設(shè)計中的應(yīng)用[J]. 機械設(shè)計，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]. 復(fù)旦大學(xué)學(xué)報，2004(6):87-90.</p><p>　　[8]

79、 陳一永，韓紅，龔延成. 帶時間約束的配載車輛調(diào)度問題研究[J]. 物流技術(shù)，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]，重慶大學(xué), 2007.</p><p>　　[11] 徐天亮. 運輸與配送[M]，北京：中國物資出版社, 2002.</p><p>　　[12] 晏夢君. 遺傳算法在配送線路優(yōu)化系統(tǒng)中的應(yīng)用[J], 吉林大學(xué), 2007.4.</p><p>　　[13]Laporte.GThevehieleroutingp