【正文】 做畢業(yè)設計以前覺得畢業(yè)設計只是對這幾年來所學知識的單純總結(jié)，但是通過這次做畢業(yè)設計發(fā)現(xiàn)自己的看法有點太片面。而且大大提高了動手的能力，使我充分體會到了在創(chuàng)造過程中探索的艱難和成功時的喜悅。由于物流配送路徑優(yōu)化問題是一個NP難題，因此，采用啟發(fā)式算法求解是一個重要的研究方向。的經(jīng)驗值為,~。在本問題中，對于種群數(shù)目為N的染色體群，其個體染色體i的適配值的值越小,則表示個體適配值越高。其操作方法如下：首先，隨機在父代染色體中選擇一個交配區(qū)域，如兩個父代染色體及交配區(qū)域選定為：A=3 5|6 2 9 8|4 7 1B=8 3|2 9 5 4|1 6 7其次，將B 的交配區(qū)域加到A 的前面，A 的交配區(qū)域加到B 的前面，得到：39。為了在編碼中反映車輛配送的路徑，采用了增加m－1 個虛擬配送中心的方法，分別用L＋L＋…、L＋K－l 表示。具有如下特點：(1) 遺傳算法運算的是解集的編碼，而不是解集本身；(2) 遺傳算法的搜索始于解的一個種群，而不是單個解；(3) 遺傳算法只使用報酬信息（適值函數(shù)），不使用導數(shù)或其他輔助知識；(4) 遺傳算法采用概率的，而不是確定的狀態(tài)轉(zhuǎn)移規(guī)則。遺傳算法的概念最早是由Bagley 在1967 年提出的；而開始遺傳算法的理論和方法的系統(tǒng)性研究的是1975 年，這一開創(chuàng)性工作是由Michigan . Holland 所實行。交換法則是依賴其他方法產(chǎn)生一個起始路線，然后以迭代的方式利用交換改善法減少路線距離，直到不能改善為止。車輛路線問題可以描述如下（如圖1）： 圖1 路徑問題描述設有一場站（depot），共有M 輛貨車，車輛容量為Q，有N位顧客（customer），每位顧客有其需求量D。 (3)將單配送中心,多輛運輸車且無約束的車輛路徑問題建模成具有總路徑長度最短、子路徑長度均衡性好這兩個目標的雙目標多旅行商問題(MTSP),并基于HGATSP算法,研究了三種求解上述問題的解決方案。因此,研究物流系統(tǒng)中的優(yōu)化問題,具有十分重要的意義,是國內(nèi)外研究的一個熱點。 遺傳算法Abstract:Recent years, logistics, taken as 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 distribution 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 paper mainly studied a type of vehicle routing problem with single depot, nonfull load and without time windows and a dynamic vehicle routing problem. The restrictions and math models of vehicle routing problem is analyzed. This paper also pared and analyzed the basic ideas, capabilities and applicability of tradition method heuristics of VRP. Based on this, this paper put forward an improved genetic algorithm for vehicle routing problem, through changing its select operation and neighborhood structure operation, an adaptive genetic algorithm was presented for solving this problem. Computational results based on C language programming demonstrated that the adaptative algorithm improved the quality of the results and can solve the problem effectively. Exemplifications proved that this algorithm can enhance capability of optimization, solving efficiency and reliability of running. Finally, a dynamic vehicle routing problem with random time window is modeled. This problem is also solved by sweep and genetic algorithms method. The method have made good effect in ensuring customer service level.Keyword: Vehicle Routing Problem?；谶z傳算法的車輛路徑問題研究中文摘要：近些年,物流作為“第三利潤源泉”受到國內(nèi)各行業(yè)的極大重視并得到較大的發(fā)展。 sweep method。 庫存成本與配送成本是物流系統(tǒng)的核心成本,在物流總成本中占據(jù)了很大的比例。 (4)對于帶能力約束的車輛路徑問題(CVRP),提出了一種新的雙層染色體編碼方案和一種子路徑交換算法。車輛從場站出發(fā)對客戶進行配送服務最后返回場站，要求所有顧客都被配送，每位顧客一次配送完成，且不能違反車輛容量的限制，目的是所有車輛路線的總距離最小。1960年，Clarke和Wrigh首先提出一種啟發(fā)式節(jié)省法（savings methods）來建立車隊配送路線。當時，其主要目的是說明自然和人工系統(tǒng)的自適應過程。 遺傳算法流程圖圖2 遺傳算法流程圖5 模型建立求解及實例應用根據(jù)上述對問題的描述，可以采用混合整數(shù)規(guī)劃方法對車輛調(diào)度進行建模設N為最小成本，則目標函數(shù)為滿足約束條件1：式中：K為所有車輛的集合， ；G為所有客戶的集合， ， ，其中{0}代表配送中心； 為由車輛k服務的客戶的集合； 為車輛到達客戶i的時間；為懲罰函數(shù)，車輛在時間 到達客戶i時所對應的懲罰成本；為車輛從客戶i到客戶j的所有運輸成本；為車輛從客戶i到客戶j的行車時間；為客戶i的需求量；Q為車輛k的最大裝載量；為車輛在客戶i處的停留的時間。這樣，l、…、L＋m－l 這L＋m－l 個互不重復的自然數(shù)的隨機排列就構(gòu)成一個個體，并對應一種配送路徑方案。A=2 9 5 4|3 5 6 2 9 8 4 7 139。個