1、廣西工學院畢業設計（論文）說明書第 PAGE 48 頁 共 NUMPAGES 48 頁摘要車輛路徑問題可以分為以點為服務和以邊為服務兩種，灑水車問題是以邊為服務的一個子問題。作為容量限制弦路徑車輛行駛問題(CARP)的一種實際應用，灑水車路線規劃涉及帶有一定容量限制的總行程最小，以及多輛灑水車工作的合理分配問題，屬于復雜的N-P難車輛路徑優化問題。因此，在容量限制下實現作業車的總行駛路徑最小，節約成本，提高效率，成為我們研究的中心環節。本文采用了遺傳算法，對多輛灑水車線路優化問題進行了容量均衡性方面的研究。首先在矩陣計算過程中采用了Floyd和Dijkstra算法求解了作業區域上任意兩點之間的

2、距離，以及指定兩點之間的具體路徑，為車輛的部分路段行駛獲得了指向。接著對灑水車作業圖的奇數度點進行隨機匹配，從而把灑水車的作業圖補成了每個頂點都是偶數，這樣就可以獲得一條Euler回路，即對應一個花費數值。然后通過遺傳算法，初始化，編碼，解碼，適應度函數的計算以及選擇，交叉，變異等一系列操作，最終獲得一條花費最小的Euler回路。最后對這條回路進行分割，從而實現多輛車之間的作業分配。本文通過引用柳州市區的一部分區域地圖進行實驗，獲得了比較理想的結果，并服合一定的現實意義。關鍵詞:路線優化 遺傳算法 匹配 Euler算法AbstractVehicle routing problem can be

3、 divided into the service for points and the service for sides， while sprinkler service is a subset of the side problem. As a practical application of CARP(Capacitated ARC Routing Problem) ，the sprinkler route planning demanks the total trip Minimum with a certain capacity and shares alike the work

4、.So it is the complexity of VRP(Vehicle routing problem).In order to achieve the total trip minimum， to increase the least cost and increase the efficiency that becomes the central link of our research.In this paper， we use the genetic algorithm to research how to finishes the sprinklers work equal.

5、 First of all， we apply the the Floyd and Dijkstra to achieve the distance between any two points and the specific path between two cettain points， which provide a method for the car to some setions road.Then the point of odd-degree random match in the routing graph，in this way， we can change the de

6、gree of every vertex into even.This can be an Euler circuit， which corresponds to a cost value.Whats more， through the genetic algorithm， initialization， encoding， decoding， the calculation of fitness function， as well as selection， crossover， mutation， such as a series of operations, eventually we

7、get the answer.In the paper,we use Part of the liuzhou mapto experiment,and obtain a more satisfactory results,in the same time show the algorithm has practical significance. Key words: path optimization ， Genetic Algorithm，matching; Euler Algorithm目 錄 TOC o 1-3 h z u HYPERLINK l _Toc232048256 Abstr

8、act PAGEREF _Toc232048256 h 2 HYPERLINK l _Toc232048257 1緒論 PAGEREF _Toc232048257 h 4 HYPERLINK l _Toc232048258 1.1 研究的目的和意義 PAGEREF _Toc232048258 h 4 HYPERLINK l _Toc232048259 1.2 車輛路徑問題的國內外研究現狀 PAGEREF _Toc232048259 h 4 HYPERLINK l _Toc232048260 1.3 主要研究內容 PAGEREF _Toc232048260 h 5 HYPERLINK l _To

9、c232048261 2灑水車路線優化問題 PAGEREF _Toc232048261 h 7 HYPERLINK l _Toc232048262 2.1 路徑優化問題 PAGEREF _Toc232048262 h 7 HYPERLINK l _Toc232048263 2.2圖論的相關知識和算法 PAGEREF _Toc232048263 h 7 HYPERLINK l _Toc232048264 2.2.1Floyd與warshall算法 PAGEREF _Toc232048264 h 9 HYPERLINK l _Toc232048265 2.2.2Dijkstra算法 PAGEREF

10、 _Toc232048265 h 9 HYPERLINK l _Toc232048266 2.2.3Euler算法 PAGEREF _Toc232048266 h 10 HYPERLINK l _Toc232048267 2.2.4奇數度路口的匹配 PAGEREF _Toc232048267 h 11 HYPERLINK l _Toc232048268 2.2.5遺傳算法 PAGEREF _Toc232048268 h 11 HYPERLINK l _Toc232048269 3單輛灑水車的路線優化 PAGEREF _Toc232048269 h 14 HYPERLINK l _Toc2320

11、48270 3.1問題及模型描述 PAGEREF _Toc232048270 h 14 HYPERLINK l _Toc232048271 3.2 路徑優化設計思路 PAGEREF _Toc232048271 h 14 HYPERLINK l _Toc232048272 3.3 實例分析 PAGEREF _Toc232048272 h 15 HYPERLINK l _Toc232048273 4多輛灑水車路線優化 PAGEREF _Toc232048273 h 18 HYPERLINK l _Toc232048274 4.1多輛灑水車路線優化的描述 PAGEREF _Toc232048274

12、h 18 HYPERLINK l _Toc232048275 4.2 多輛灑水車路線優化的設計思想 PAGEREF _Toc232048275 h 19 HYPERLINK l _Toc232048276 4.3 實例的設計與實現 PAGEREF _Toc232048276 h 20 HYPERLINK l _Toc232048279 4.3.1灑水車路線優化問題的編碼 PAGEREF _Toc232048279 h 21 HYPERLINK l _Toc232048280 4.3.2奇數度點的初始化 PAGEREF _Toc232048280 h 21 HYPERLINK l _Toc232

13、048281 4.3.3解碼及灑水車行進路線的獲取 PAGEREF _Toc232048281 h 22 HYPERLINK l _Toc232048282 4.3.4計算目標函數 PAGEREF _Toc232048282 h 25 HYPERLINK l _Toc232048283 4.3.5選擇算子 PAGEREF _Toc232048283 h 26 HYPERLINK l _Toc232048284 4.3.6交叉算子 PAGEREF _Toc232048284 h 27 HYPERLINK l _Toc232048285 4.3.7變異算子 PAGEREF _Toc23204828

14、5 h 28 HYPERLINK l _Toc232048286 4.3.8參數設計 PAGEREF _Toc232048286 h 29 HYPERLINK l _Toc232048287 4.3.9多輛灑水車行進路線的分配 PAGEREF _Toc232048287 h 29 HYPERLINK l _Toc232048288 結束語 PAGEREF _Toc232048288 h 32 HYPERLINK l _Toc232048289 參考文獻 PAGEREF _Toc232048289 h 33 HYPERLINK l _Toc232048290 致謝 PAGEREF _Toc232

15、048290 h 341緒論1.1 研究的目的和意義在經濟高速發達時代，人們絞盡腦汁地節約投入的成本，人們費盡心血地研制出更加高效的生產工具，人們不斷完善人力資源的調度理論，其目的就是為了獲得高效的工作效率，合理地人力資源配置。人們生活方式的自動化水平是一個反映時代的發展的標志，隨著人們生活水平的提高，人們也更加地關注著他們所生存和發展的環境，人們所生活的環境，空氣的清凈度對人們的健康有著重要的意義。為了能夠更地完成城市的除塵工作，實現最低的成本花費，高效的工作效率，合理的人力資源配置這一目標。如何合理地對灑水車的作業線路進行優化將成為本課題的核心。由于灑水車的作業是一個N-P難問題。如何合理

16、地規劃灑水車的作業路線，從而減少不必要的行駛路程，不但可以更好地提高工作效率，而且可以可以有效地節約燃油的成本，對本課題的研究具有重要的現實意義。同時當我們為了提高灑水車對城市除塵工作的效率，而使用了多輛灑水車同時工作時，如何地分配好各輛車之間的作業路線，在保證高效的同時做到燃油的花費最小，將比單輛灑水車的除塵應用更加具有現實意義。1.2 車輛路徑問題的國內外研究現狀灑水車問題是以邊為服務的問題。類似的還有冬季除冰車，城市垃圾回收，以及最古老的中國郵遞員問題都屬于ARP問題，由于它們都存在有一個共同的特點，即容量限制的問題，因此灑水車的問題又稱為CARP問題的一個擴展問題。而CARP問題屬于N

17、-P難問題。對于小數量的(20條邊或弧以內) 還可以用精確算法來來解決(分為整數規則和分枝定界)，但是實際問題往往規模較大，如果仍采用精確算法，在運行時間和計算的復雜度將出現瓶頸。到目前為至，雖然國外對邊服務的論文仍比較少，但較于去年的研究情況。關于灑水車方面的論文開始有一些了，如鄧欣等人在2007年，針對單車場灑水車線路優化問題，將路徑優化問題轉化CARP的擴展，提出了改進遺傳算法OX交叉和局部搜索(local search)的方法，通過實際生活的例子驗證了算法的可靠性和適用性，從而保證算法在解決一定規模的CARP具有一定的實用價值1。李小花等人在2008年針對多車場灑水車路線優化的問題，將

18、傳統遺傳算法的種群結構進行改進，提出了車輛的時間約束來保證各輛車工作時間的均衡性，即使效果并不理想，但仍有一定的參考價值2。劉建輝等人在2008年，針對多車場路線優化的問題，提出了一種雙層遺傳算法，處理了車場與路徑的分配，以及每條路徑的服務弧之間的優化問題，對人力資源的優化和減少車輛總行程，取得了很好的效果3。朱征宇等到人在2008年針對復雜CARP問題中的多車型，多路型等因素，以傳統的遺傳算法為基礎，提出了一種高性能遺傳算法(HEGA)，使得染色體代表的含意截然不同，同時加入了重優化措施的收入，防止了隨著迭代次數的不斷增加，優化曲線逐漸平緩，算法將會收斂，而此時可能并沒有達到全局最優，這些算

19、法和設計思想均對現實問題的考慮提供了很有價值的參考4。但正剛等人在2006年針對CARP的求解問題，研究了CARP與CVRP的轉化，提出了小環路方法(實質為禁忌)來求解CARP，驗證了算法的準確性和效率，為實際應用奠定了基礎5。 同時針對車輛線路優化的均衡性問題，認識到了LU算法在時間對車輛的均衡性的約束不夠，從而提出了一種新的算法，主要的思想為犧牲了車輛路徑的飽和來實現車輛路徑的均衡性6。賈立雙等人在2008年針對，單車場車輛調度問題，提出了一種綜合運用最鄰近算法和遺傳算法的相關原理組合實現了單車場多車型的調度7。李松等人在2007年針對大規模車輛路徑中存在的缺陷，提出了Sweep分區技術和

20、分區的禁忌搜索算法與相鄰區域的優化技術相結合，有效解決了大規模車輛路徑的優化問題8。付彤等人在2006年針對一般網絡上單車型車輛配送問題，借鑒Floyd算法與節約路徑法，構造出一種在所用車輛數最少的條件下，使總配送里程最短9。張濤等人在2002年針對車輛數目不確定的車輛路徑優化問題，提出了遺傳算法GA和禁忌搜索算法TSA相結合，主要以GA為主，把TSA用在GA的變異操作中，從而獲得了最小化距離和最小化車輛的雙目標優化10。陳文蘭在2007年討論了VRP問題的分類，以及介紹了近年來的相關算法的主要成果11.。相對于(容量限制弧的邊路徑問題)CARP，國外的應用相對國內而言，就多一點。Maria

21、Candida Mourao在2004年針對垃圾回收問題的求解，提出了一種新穎的HM啟發式算法12。Anita Amberg等人針對M-CARP問題提出了一種禁忌搜索算法，不過對于M-CARP的問題的研究還處于初步探索階段，能查到的相關文獻不多13。Dino Ahr在06年針對中國郵遞員問題利用了一種禁忌搜索算法，但是中國郵遞員的最大最小解屬于N-P難問題，因此，在論文中主要依賴啟發式算法產生近似解。同時，在許多情況下人們所能得到的解也是近似或更優的解14。Jose Brandao在2006年針對CARP問題提出一種基于禁忌搜索的啟發式算法，在應用到標準例子的各種情況下，得到結果，說明了算法處

22、理的過程可以在合理的計算時間內得到較高的準確性15。 灑水車的路徑優化的問題，要考慮的問題還是有很多的。就單一的目標:要求路徑最短而言。當道路的情況多種時，如單行道(要求只能從某個方向行駛)，雙邊道路(中間有綠化帶)，道路中有上下坡的(要求下坡時灑水)，還有在某個十字路口只能左轉或右轉的限制是時，都需要對算法作出一定的修改。當在城市的道路中加入了一定數量的加水點(水樁)時，就要對灑水車加水點選擇的優先性進行考慮。當為了提高灑水車除塵的效率，引入多車輛同時工作時，就要對灑水車間的路徑分配的均衡性問題進行考慮。還有當有多個車場時，道路與車場的分配問題，對道路除塵時，對車型容量的選擇(多車型)等等都

23、會限制算法的適用性1.3 主要研究內容在原來單輛灑水車的基礎上，實現多輛灑水車的線路優化問題。由于原來做的是單輛灑水車在無限容量下的情況，這樣一來，只要形成一條最短回路就可以了。現在要做的是，把這種無限容量下的路線優化變得現實一點，即把無限容量的的情況考慮成有容量限制的情況，這樣不但增加了課題的復雜性，而且實現了課題的現實性，在單輛灑水車現實性的前提下，為了可以更好地提高灑水車的作業效率，實現多輛灑水車同時進行城市的除塵工作。本文的研究內容主要有以下幾個方面首先從線路優化問題出發，介紹了常見的兩類線路優化問題VRP和CARP，分析了兩者的應用區別，明確灑水車線路優化問題的數學模型，并說明了灑水

24、車在線路優化的具體設計時用到的一些算法，其中遺傳算法是整個尋優求解的中心環節，而warshall，Dijkstra，Euler算法只是作為遺傳算法解碼計算的輔助算法。其次介紹了單輛灑水車線路優化的總體設計思路結果。最后對多輛灑水車線路優化問題以多輛車作業分配和總行程最小為目標，提出了容量分割的方法并進行了詳細的設計，包括路線優化的模型描述，設計原理，編碼的方式與確定，種群的初始化，如何對染色體進行解碼，轉換到問題的現實解(難點)，計算目標函數及適應度函數和各種操作算子進化方式的確定(重點)。本文用MATLAB7.0在Window XP下進行編程并調試，并對實驗結果進行了比較和分析。2灑水車路線

25、優化問題2.1 路徑優化問題說到路徑優化問題，我們會很自然地就想起車輛路徑問題(Vehicle Routing Problem，VRP)，因為配送問題在商業領域的應用十分廣泛。VRP的一般描述為:用于送貨的若干輛相同型號的車從配送中心出發，到不同的地理位置的客戶那里去送貨，然后返回配送中心，要求每輛車只能出發一次，任何一個客戶有且只有一輛車訪問，并且所配送的貨物不能超過車輛的載重量，求解一種配送方案使得配送總成本最少。VRP問題根據不同的標準可以分為不同的類別。根據車輛是否有容量約束，可分為有容量約束的VRP問題(貨擔郎問題)，和無容量約束的VRP問題(TSP問題);根據貨運任務的完成是否有時

26、間要求，又可分為有時間約束和無時間約束兩種。對于有時間約束的VRP還可以進一步分為帶軟時間窗的VRP和帶硬時間窗的VRP。從1959年的VRP問題的開始提出到現在的半世紀以來，國內外對VRP的研究已經相當成熟，在各類VRP(如有時間窗、多車場等)的研究上都取得了豐富成果，采用的解決方法也多種多樣，可分為精確算法(如整數規劃、分枝定界等)和啟發式算法(禁忌搜索、遺傳算法、蟻群算法等)兩大類。還有另外一種路徑問題，也是本文的路徑優化問題，那就是與VRP相類似的弧路徑規劃問題(Arc Routing Problem，ARP)這類問題在基礎設施中的應用就相對就要多一些。本文研究的灑水車的路徑優化問題就

27、屬于特殊的ARP問題，由于灑水車的城市除塵作業，車輛本身帶有容量限制，因而灑水車路徑優化問題屬于“容量限制弦路徑車輛行駛問題”。有容量限制的ARP，在現實中擁有廣泛的應用背景，如前面提到的灑水車作業路線安排，以及冬季除冰車作業路線安排，城市垃圾車作業路線安排，還有城市輸電線路的檢查等。這時，我們會提出這樣一個疑問:在前面的提到的兩種路線優化問題中(VRP問題與CARP問題)，它們都可以有容量限制方面的約束條件，到底是怎樣的一種分類方式把它們分成了兩種不同的路線優化問題。這個劃分的關鍵就在于它們在線路優化中的具體服務的對象是不一完全一樣的，對于VRP問題而言，它主要是以點的服務主，而對于CARP

28、問題，它主要是以邊的服務為主。如果說到了這里還是不大清楚，也許可以通過一個問題的對比來說明。例如VRP問題中的車輛的配送問題(不帶時間窗的)，因為車輛要裝載貨物，因此有一定的裝載容量。同樣的對于CARP問題中的灑水車路線優化問題，車輛本身就有一定的裝水容量。這是相同的地方。然而不同的就是它們的服務對象是不同的。車輛的配送只要把貨物送到指定的點就可。配送的本質在于遍歷所有的點，所以不用遍歷所有的邊。而灑水車的路線優化則要遍歷完所有的邊。邊集往往包含了點集，而點集不一定可以包含邊集。也正是因為這點的不同這兩類問題在路線優化時，即有相似點，但又不相同。2.2圖論的相關知識和算法圖論中所討論的”圖”，

29、不是微積分，解析幾何，幾何學中討論的圖形，而是客觀世界中某些具體事物間聯系的一個數學抽象。如二元關系圖，在關系圖，在關系圖中，我們不考慮點的位置及邊線的長短曲直，而只關心哪些點之間有線相連通。這種數學抽象就是”圖”的概念。圖論在灑水車路線優化過程中起到的作用是:實現客觀道路網到數學模型上的抽象。圖是一個三元組，包括結點集合，邊集合以及關聯函數。無向圖:每條邊都是無向邊的圖稱為無向圖。有向圖:每一條邊都是有向邊的圖稱為有向圖。連通圖:如果無向圖G中每一對不同的頂點X和Y都有一條路，則稱G是連通圖。強連通圖:如果有向圖D任何一對結點之間都可以相互到達，則稱這個有向圖是強連通的。弱連通圖:若在有向圖

30、D的基礎圖是連通的，則稱有向圖D是弱連通的。簡單圖:無環并且無平行邊的圖稱為簡單圖。環:兩端點相同的邊稱為環或稱為自回路。平行邊:兩個結點間方向相同的若干條邊稱為平行邊或重邊。NP問題:至今既沒有找到多項式算法，又不能證明它不存在多項式算法一類問題稱為NP問題。度數:設G是任意圖，X為G的任意結點，與結點X關聯的邊數(一條環要計算兩次)稱為X的度數(degree)。入度與出度:設D是任意有向圖，X為D的任意一結點，射入X的邊數稱為X的入度(in-degree) ，射入X的邊數稱為X的入度(in-degree)。最短路徑:給定一個起始點S和一個結束頂點T，在圖中找出從S到T的一條最短路徑。我們將

31、起始點稱為”源點”，結束點T稱為”匯點”。單源最短路徑:給定一個起始點S找出從S到圖中其他各頂點的最短路徑。最短路徑的操作實質稱為”淞弛”。開始進行最短路徑算法時，只知道網的邊和權值，隨著要遍歷中間點的加入，可以獲得一條新的路徑距離，如果在這一過程中出現這個新獲得的路徑距離比保存的記錄值小，則把這個新得到的最小值傳送給保存的最小記錄中。這樣的一個不斷比較并更新最小值的遍歷過程。可以形象地這樣來描述，在兩個頂點之間用一根橡皮筋系起來，后把它拉緊繞過另一個頂點，然后在這三個點的內部找到一個新的點，(相當于找到了新的當前最小值)，然后把被繞過的那個頂點拔掉，這樣就在橡皮筋的張力作用下，而收縮，直到橡

32、皮筋打在了那個新的頂點上。這樣的一個過程就好像一張拉滿的弓，慢慢松開的過程。 在灑水車的線路優化過程中，為了得到線路的最小值，在求解一條回路的過程中，首先要把實際的作業圖轉化到圖的模型下，其次通過Floyd求解任意兩點間的距離值，但又因為圖中存在奇數度頂點而無法實現回路，所以要消除奇數度頂點。再次通過Dijkstra獲得在遺傳算法隨機編碼下對應奇數度點間的具體路徑，接著用Euler求得對應編碼下的一條回路，最后通過遺傳算法的尋優思想獲得所有回路中線路值最小的一條。2.2.1Floyd與warshall算法為了在灑水車線路優化中求得求得轉換模式下的任意兩點間距離，使用了Floyd算法已知矩陣A=

33、(aij)m*l，B=(bjk)l*n， C=A*B=(Cij)m*n， 其中 Cij =min(ai1+b1j，ai2+b2j，ail+blj)已知矩陣A=(aij)m*n， B=(bij)m*n， 規定其中dij=min(aij，bij) 可以利用上面定義的運算求任意兩點間的最短矩離。已知N階加權簡單圖G，設D=(dij)n*n是圖G的邊權矩陣，即dij=w(i，j)(若G是有向圖，則dij=w)，若結點i到結點j無邊相連時，則取dij=。 然后依次計算出矩陣D2，D3，Dn及S其中D2=D*D=(d2ij)n*nD3=D2*D=(d3ij)n*nDn=Dn-1*D=(dnij)n*n由定

34、義可知，dkij表示從結點i到j 經k邊的路(在有同圖中即為有向路)中的長度最短者，而Sij為結點i到j的所有路(若是有向圖，即為有向路)中的長度最短者。 不難看出，Floyd算法的時間復雜性是O(n4)，下面看介紹求任意兩點間最短路的Warshall算法。已知n階加權簡單G，設D=(dij)n*n是圖G的邊權矩陣。輸入D;k:=1;i:=1;dij:=min(dij，dik+dkj)，j=1，2，n;i:=i+1，若，轉(4);k:=k+1，若，轉(3);否則停止。該算法是對i，j，k進進行行循環，故它的復雜性是O(n3)，即對矩D進行k次修改。2.2.2Dijkstra算法在灑水車線路優化

35、中，一條Euler回路的獲得要求圖中沒有奇數度頂點，而圖中必定存在奇數度頂點。為了消除圖中奇數度頂點，主要通過Dijkstra的指定點路徑實現來完成。迪克斯屈拉算法求出一個連通加權加權簡單圖中從指定結點(如a)到指定終點(如z)的最短路。邊i，j的權w(i，j)0，且結點x的標號為L(x)。L(z)是從指定結點a到z的最短路的長度。Dijkstra的算法描述:對于一個所有權都為正數的加權連通簡單圖G，G中有頂點a=v0，v1，vn=z和權w(vi，vj)，若vi，vj不是G中的邊，則w(vi，vj)=，(1)初始化標志，令L（a）=0，其余結點為無窮大，并定義一個記錄現實路徑的集合如S為空集。

36、（2）第一次時把起點a存入S中，并逐個比較當前記錄的結點L（a）+w(a，u)與L（u）的大小，u為不屬于S的頂點，如果L（a）+w(a，u)rand所對應的那一條染色體。，表示賭盤指標落入了，則染色體i被選中。重復以上步驟不斷地獲得新的染色體，直到染色體的種群數達到了每一代種群的規模值。這樣對選擇算子這樣設計的另外一個原因是，由于在遺傳算法的優化后期，種群的個體在外形的表現上有很大的相似性，這樣一來， 遺傳算法選擇算子就會由初始時各各染色體之間擁有較大的適應度差異性，隨著進化代數的增加，這種適應度的差異就慢慢被同化了，賭盤選擇就變為了被選擇的概率大體均等的隨機數選擇。這樣不但會使得問題的解總

37、有最優解附近徘徊，而且程序的運算速度大大下降。這不是我們希望看到的。為了克服這一點，我們在前面對適應度的設計時就防范了那就是對染色體進化后期差異不大的適應度值進行有效差異的放大。這種放大是在設計目標函數中去實現。因為我們知道染色體的適應度值是在目標函數的基礎上獲得。從這一個角度去看，我們就會更加清楚，在目標函數的設計時，我們把目標函數值一共分為了三個部分，值得一提的是，把所有服務邊的花費分立為一個部分。并且在計算目標函數時也沒有在程序中去求解出來，這不但是優化了算法，而且還隱含了一個重要的原因:就是在遺傳算法后期對適應度的有效差異進行放大。防范解在最優解附近徘徊。這樣選擇算子的設計就告一個段落

38、了。但如只是選擇而沒有交叉算子的設計還是不可以對種群進行優化。4.3.6交叉算子遺傳算法中的所謂交叉運算，是指兩個相互配對的染色體按某種方式相互交換其部分基因，從而形成兩個形成兩個新的個體。交叉運算是遺傳算法區別于其他進化算法的重要特征，它在遺傳算法中起著關鍵作用，是產生新個體的主要方法。交叉算子的設計包括以下兩個方面的內容:1.如何確定交叉點的位置。2如何進行部分基因的交換。在前面第二章節的介紹中，我們已知道，常用的交叉方式有單點和雙點交叉方式兩種。單點交叉的重要特點是:若鄰接基因座之間的關系能提供較好的個體性狀和較高的個體適應度值的話，則這種單點交叉會破壞這種個體性狀和降低個體適應度的可能

39、性最小。這是單點交叉的選用標準。而在多輛灑水車的編碼設計中，我們是用奇數度頂點進行編碼，并且這些奇數度頂點之間有的相距很遠。顯然可知鄰接基因座之間的關系并不一定提供較好的個體性狀和較高的個體適應度值，那么在沒有違背單點交叉的選用標準的前提下。雙點交叉就要比單點交叉提供更多尋優的可能，并且也可以產生出近似單點交叉的情況。所以在多輛灑水車的交叉算子的設計中使用的是雙點交叉。接著要說的是: 如何確定交叉點的位置?1.在任意一條要進行交叉的染色體隨機地生成兩點。在MATLAB中應用rand和floor去實現，其中floor是向小和取整。2.然后用min和max求出這兩個數中小的序號和大的序號，這兩個序

40、號就是進行交叉點的位置然后要說的是: 如何進行部分基因的交換?1)將雙親2中min到max之間的染色體片斷作為子代1的起始片斷。2)順序將雙親1中沒有在子代1中出現的點編號插入到子代1中形成子代染色體一。3) 將雙親1中min到max之間的染色體片斷作為子代2的起始片斷。4)順序將雙親2中沒有在子代2中出現的點編號插入到子代2中形成子代染色體一。其中2)，4)可以在MATLAB中用find來實現。例如parent1=2 9 20 3 5 8 17 4 7 22 14 11 13 16 6 18 21 10 1 19 15 12 Parent2=11 6 7 9 5 13 4 17 2 10 1

41、6 20 22 8 12 3 21 19 1 15 14 18如果得到交叉點為11和19兩點的這兩段代碼為segment1 =16 20 22 8 12 3 21 19 1segment2 =14 11 13 16 6 18 21 10 1對應的子代為:child1=16 20 22 8 12 3 21 19 1 2 9 5 17 4 7 14 11 13 6 18 10 15 child2=14 11 13 16 6 18 21 10 1 7 9 5 4 17 2 20 22 8 12 3 19 15在灑水車的路線優化中parent1中奇數度頂點之間的匹配對應一個現實問題的解。而經過交叉算子

42、之后得到的child1中奇數度頂點之間的匹配由原來的 2-9 20-3 5-8 17-4 7-22 14-11 13-16 6-18 21-10 1-19 15-12變成了16-20 22-8 12-3 21-19 1-2 9-5 17-4 7-14 11-13 6-18 10-15。這是不同于原來的另一條染色體的，相應的現實路徑也不同。另外還有一點需要注意的是，并不是所有指定的兩條染色體之間都可以進行交叉操作，因為在交叉操作中存在一個交叉概率Pc，在程序中要求我們隨機產生的數要小于Pc才可以進行交叉操作。這就好比在生物界中并不是兩個個體相遇了就一定會結合。4.3.7變異算子從前面的介紹，我們

43、已經知道交叉運算是產生新個體的主要方法，它決定了GA的全局搜索能力，而變異運算只是產生新個體的輔助方法，但它也是一個必不可少的一個步驟。因為它決定了GA的局部搜索能力，并維持種群的多樣化。因為在遺傳算法的后期交叉算子無法對搜索空間的細節進行局部搜索。但若此時使用變異算子來調整個體編碼串中的部分基因值，就可以從局部的角度，輕微的變異就使得原來在最優解附近的染色體的細小調整，使得個體更加逼近最優解，從而提高了遺傳算法的局部搜索能力。同樣變異算子的設計也包括兩個方面。1)如何確定變異點的位置?2)如何進行基因值替換?變異點的位置可以通過rand隨機生成生成兩個變異點的序號就可以了。基因值替換就把生成

44、的兩個變異點的序號的基因進行交換就可以了。例如用上面的例子child1=16 20 22 8 12 3 21 19 1 2 9 5 17 4 7 14 11 13 6 18 10 15。如果發生了變異操作，即滿足了隨機數rand小于Pm，則產生兩個變異點序號，如果這兩個點序號是10和18。則把2和13交換。就可以得到新的染色體。16 20 22 8 12 3 21 19 1 13 9 5 17 4 7 14 11 2 6 18 10 15。但通常情況下發生變異的概率都會比較低。因為太多的變異操作必然會使得優良個體遭到破壞，始終記得變異運算只是產生新個體的輔助方法。它的目的是對染色體進行細小的調

45、整，在保證種群多樣性的同時，并使得個體更加逼近最優解。因此變異算子的取值范圍是0.0001-0.1。4.3.8參數設計種群的大小Popsize=50進化代數大小maxgen=200交叉概率Pc=0.8每個基因位變異概率pm=0.01車場位置depot=43灑水車的裝水容量demarkQ=10噸4.3.9多輛灑水車行進路線的分配通過上面對多輛灑水車的分析和設計，每個部分的設計都進行了詳細的闡述。在遺傳算法進行操作算子的作用下，不斷地尋找解空間內的較優解，并且當找到比當前的解更好的解時，就不斷地更新當前保存中的最優解。在遺傳算法結束時，會得到一條總的花費值最小的現實回路。再對這條總的花費最小的現實

46、回路進行容量上的分割就可以得到每輛作業車的除塵分配。其實在這里的分配過程的一個核心問題在于如何找到那個容量的分割點。并準確地分割這條最優回路。在MATLAB程序的設計中值得一提的是:在用for語句使用過程如for j=1:num，for語句每進行一次循環，j就會自行增加1而不受for循環體內如j=j-1或賦值的影響。但是在進行求解分割點的過程，分割的確定主要受兩個方面的影響(1)行駛路徑是服務邊還是非服務邊(對奇數點之間進行匹配的邊)(2)灑水車在那里要回到車場也會受到灑水車的裝水容量的影響。在(1)約束中服務邊和非服務邊有一個明顯的區別，就是在非服務邊中存在虛擬點并且在程序設計中，虛擬點的一

47、個顯著特征為:虛擬點的表示都是在原來圖上頂點數往上加(如在原作業圖中有57個頂點，那么虛擬點的表示就從58開始依次往上表示)，利用這點就可以區分服務邊和非服務邊。要區分這兩種邊的原因在于對服務邊要進行灑水車的容量判斷，而當存在以下情況:即灑水車在for循環中出現了此刻的容量無法完成下一條服務邊(如用A表示)的除塵作業時，for循環的自增一是不可改變的。注意到了這一點，在對回路的分割時就要能夠明確地識別并清楚地做好分割。在此使用前面的回路例子就進行說明:當灑水車的裝水容量使用的是10000時，它的具體意義是demarkQ=10噸，因為我們在設計的過程中，前面作業圖中各各頂點的距離表示單位是”米”

48、，并且我們定義1噸水可以行駛1000米，這樣10000就可以對應demarkQ=10噸了。分割結果如下所示:第一輛車和第二輛車的分配為43-40-41-42-44-45-46-47-48-46-44-11-92-41-91-32-120-33-119-34-78-13-93-27-94-26-95-16-107-15-65-25-66-2-38-3-67-2-58-38-8-59-38-37-52-4-70-52-49-22-88-49 -48-5-68-49-50-53-7-84-3-71-4-83-52-51-43-80-39-79-34-98-39-97-43-81-51-82 -52-

49、69-49-87-52-86-4-85-3-72-38-73-8-60-9-10-53-55-10-110-9-109-25-108-15-112 -35-111-1-2-25-9-8-7-3-4-50-45-42-12-30-18-17-24-19-54-18-104-17-28-26-16-15 -25 -23-16-63-23-21-4343-21-20-54-56-19-116-24-23-62-21-57-20-61-21-105-23-106-16-64-15-35-1-37-36 -35-34-13-99-34-118-35-117-15-113-16-114-23-115-24

50、-102-26-101-27-100-13-14-31 -29-27-13-77-27-26-24-74-17-103-24-75-26-76-27-28-29-30-31-32-12-121-32-33-14 -89-31-90-32-41-11-43-6-49-5-22-47-43-39-34-33-40-39-36-51-6-96-43從以上實驗結果可以看，分配的結果雖然沒有多輛灑水車的程序中做到最優的均等分割。但分配的效果還算可以。沒有做到最優匹配的原因分析如下;一，在城市的除塵作業中，我們對灑水車的裝水容量設置為demarkQ=10噸，這樣灑水車就可以行駛10000米，但由于選取的地

51、圖的范圍不是相對的大，從而使得第一輛灑水車的裝水容量全部用完，第二輛沒有用完水就可以回到車場。但是有一個方面我們又不得不考慮就是當對作業圖的選取過于龐大，用上面的方法就會受到約束。因為隨著作業圖的加大，圖中奇數度頂點也會相應地增加。當圖中的奇數度頂點大大地超過了遺傳算法較好的尋優范圍以后，這樣的設計方法就逐漸表現出設計思想的局限性。而不得不設計另一種編碼方式。(在本論文范圍就加以細說了)如果我們把灑水車的裝水容量設置為demarkQ=5噸，實驗結果如下43-40-41-42-44-45-46-47-48-46-44-11-92-41-91-32-120-33-119-34-78-13-93-2

52、7-94-26-95-16-107-15-65-25-66-2-38-3-67-2-58-38-8-59-38-37-52-4-70-52-49-22-88-49 -48-5-68-49-50-53-7-84-3-71-4-83-52-51-43-80-39-79-34-98-39-97-43-81-51-82 -52-69-49-87-52-86-4-85-3-72-38-73-8-60-9-10-53-55-10-110-9-109-25-108-15-112 -35-111-1-2-25-4343-25-9-8-7-3-4-50-45-42-12-30-18-17-24-19-54-18

53、-104-17-28-26-16-15-25 -23-16-63-23-4343-23-21-20-54-56-19-116-24-23-62-21-57-20-61-21-105-23-106-16-64-15-35-1-37-36-35-3-4-13-99-34-118-35-117-15-113-16-114-23-115-24-102-26-101-27-100-13-14-31-29-27-13-77-27-26-24-74-17-103-24-75-26-76-27-28-29-30-31-32-12-121-32-4343-32-33-14-89-31-90-32-41-11-4

54、3-6-49-5-22-47-43-39-34-33-40-39-36-51-6-96-43從上面結果來看出現了分配的長短不一，其中第一條回路比較長，這是由于在程序設的時候只考慮了容量分配因素，又因為有非服務邊的存在，在程序中這一部分是不計算容量的，這樣即使是每條回路的容量也大體相同(在道路的除塵中所使用的容量)，但由于非服務邊的存在也使得每一條回路的長度不同。如果要克服這這個個問題，就不得不在程序的回路分配，多加入一些約束條件。如加入回路的路程變量去限制，那么就要考慮服務邊的路程以及非服務邊的路程，這樣的效果在回路的均衡性分配上就要比上面的情況要好。但是也不可排除這樣一種情況，有的道路它的路

55、程很長，而有的道路路程很短，那么在其中一條回路中會因為存在某些服務邊的長度較大時，那么這條回路的頂點個數并不是很多。而有另一條回路中會因為存在某些服務邊的長度較小，那么在這條回路中的頂點個數也可能會較多。因此從回路的頂點長度上去判斷多輛灑水車的分配情況也并一定反映回路分配的好壞程度。如果要真正分配得比較好。在分配上還要考慮較多的因素，比如在現實中要考慮的一個很重要的因素，就是用時間來分配。在上面的分配中，存在的一個不足就是多輛灑水車之間的作業的時間分配不均勻，不同的回路擁有的非服務邊數不一致，所以會引起灑水車的作業時，工作時間有長短的差異。一般來說灑水車在除塵作業時，行駛的車速會慢一點，而在非

56、服務邊上行駛時，行駛的車速就會快一點。雖然主要的時間是花在了除塵作業的服務邊上，但是如果把非服務邊的時間也考慮分配中，那么灑水車的作業分配就會更加合乎工況要求。因此這一領域的研究還有待進一步的深入研究。結束語本文中多輛灑水車的設計是在單輛灑水車的基礎上進行的，同時在一定規模的城市道路優化中把灑水車路優化問題轉化成CARP的擴展問題，通過遺傳算法的設計，在單輛灑水車(無限容量)的基礎上，加入了一些約束條件，例如涉及到了車輛的裝載容量以及道路需水量，并提出以灑水車的容量去分割的分配方法，克服單輛灑水車的設計思想在多輛應用的時回路的均衡性問題的不足，并且用容量去分割的分配方法，所得到車輛數的分配也不

57、受停車場度數的限制。另外用容量去分割產生的回路，還可以靈活的組合分配，因此，以容量的分割方法比單輛灑水車的設計是以柳州市某區域道路的實例測試，驗證了算法具有一定的可靠性和實用性。展望今后的工作，以后的學習研究方向如下：(1)由于在現實生活中，在城市的道路上會存在許多的加水點(水柱)這時灑水車加水時就不用都回到車場，這也是一個很現實的問題。因此在多個加水點(多車場)的設計將會更加的接近現實還有多個加水點與線路優化問題也是有待進一步的研究。(2)由于本文的程序的編寫是在MATLAB7.0版本下完成的，同時加上各方面因素(如程序本身在內部過程中并沒有做到好的優化，還有循環次數，循環嵌套，遺傳算法的種

58、群，代數等方面的控制次數)的影響，使得程序在運行的效率上仍需改進。(3)還有在灑水車進行復雜道路的優化問題上也有待進一步的研究。參考文獻1鄧欣，朱征宇，楊永，等 基于進化計算的灑水車路徑優化問題的求解 計算機工程與應用2 李小花 朱征宇 夏夢霜 基于進化計算的多車場灑水車路徑優化問題求解 交通與計算機2008年第3期第26卷3 劉建輝， 朱征宇 基于雙層遺傳算法的灑水車路線優化 河南科學4 朱征宇，謝志華，楊永，夏夢霜，李小花 灑水車作業路線規劃的復雜CARP問題求解 計算機應用5 但正剛，蔡臨寧，呂新福，鄭 力 CARP問題的小環路啟發式求解方法 系統工程學報6 但正剛， 蔡臨寧， 杜麗麗，

59、 鄭 力 車輛路徑優化問題的均衡性 清華人學學報(自然科學版)2006年第46卷第11期7 賈立雙，李靜 基于一種改進算法的單車場多車型車輛調度研究 中國制造業信息化第37卷第19期8 李松，劉興 單車場大規模車輛路徑優化問題研究 鐵路運輸與經濟第29卷第11期9 付彤 郭強 單車型配送問題的研究 計算機工程和應用10 張濤 張玥杰 不確定車輛數的車輛路徑問題模型和混合算法 系統工程理論方法應用第11卷第2期11 陳文蘭 戴樹貴 車輛路徑安排問題算法研究綜述 滁州學院學報2007.512 Maria Candida Mourao Heuristic method for a mixed cap

60、acitated arc routing problem: A refuse collection application European Journal of Operational Research 160 (2005) 139153 13 Anita Amberg ， Wolfgang Domschke ， Multiple center capacitated arc routing problems: A tabu searchalgorithm using capacitated trees European Journal of Operational Research 124