【正文】 做畢業(yè)設(shè)計(jì)以前覺(jué)得畢業(yè)設(shè)計(jì)只是對(duì)這幾年來(lái)所學(xué)知識(shí)的單純總結(jié)，但是通過(guò)這次做畢業(yè)設(shè)計(jì)發(fā)現(xiàn)自己的看法有點(diǎn)太片面。而且大大提高了動(dòng)手的能力，使我充分體會(huì)到了在創(chuàng)造過(guò)程中探索的艱難和成功時(shí)的喜悅。由于物流配送路徑優(yōu)化問(wèn)題是一個(gè)NP難題，因此，采用啟發(fā)式算法求解是一個(gè)重要的研究方向。的經(jīng)驗(yàn)值為,~。在本問(wèn)題中，對(duì)于種群數(shù)目為N的染色體群，其個(gè)體染色體i的適配值的值越小,則表示個(gè)體適配值越高。其操作方法如下：首先，隨機(jī)在父代染色體中選擇一個(gè)交配區(qū)域，如兩個(gè)父代染色體及交配區(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。為了在編碼中反映車(chē)輛配送的路徑，采用了增加m－1 個(gè)虛擬配送中心的方法，分別用L＋L＋…、L＋K－l 表示。具有如下特點(diǎn)：(1) 遺傳算法運(yùn)算的是解集的編碼，而不是解集本身；(2) 遺傳算法的搜索始于解的一個(gè)種群，而不是單個(gè)解；(3) 遺傳算法只使用報(bào)酬信息（適值函數(shù)），不使用導(dǎo)數(shù)或其他輔助知識(shí)；(4) 遺傳算法采用概率的，而不是確定的狀態(tài)轉(zhuǎn)移規(guī)則。遺傳算法的概念最早是由Bagley 在1967 年提出的；而開(kāi)始遺傳算法的理論和方法的系統(tǒng)性研究的是1975 年，這一開(kāi)創(chuàng)性工作是由Michigan . Holland 所實(shí)行。交換法則是依賴(lài)其他方法產(chǎn)生一個(gè)起始路線，然后以迭代的方式利用交換改善法減少路線距離，直到不能改善為止。車(chē)輛路線問(wèn)題可以描述如下（如圖1）： 圖1 路徑問(wèn)題描述設(shè)有一場(chǎng)站（depot），共有M 輛貨車(chē)，車(chē)輛容量為Q，有N位顧客（customer），每位顧客有其需求量D。 (3)將單配送中心,多輛運(yùn)輸車(chē)且無(wú)約束的車(chē)輛路徑問(wèn)題建模成具有總路徑長(zhǎng)度最短、子路徑長(zhǎng)度均衡性好這兩個(gè)目標(biāo)的雙目標(biāo)多旅行商問(wèn)題(MTSP),并基于HGATSP算法,研究了三種求解上述問(wèn)題的解決方案。因此,研究物流系統(tǒng)中的優(yōu)化問(wèn)題,具有十分重要的意義,是國(guó)內(nèi)外研究的一個(gè)熱點(diǎn)。 遺傳算法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傳算法的車(chē)輛路徑問(wèn)題研究中文摘要：近些年,物流作為“第三利潤(rùn)源泉”受到國(guó)內(nèi)各行業(yè)的極大重視并得到較大的發(fā)展。 sweep method。 庫(kù)存成本與配送成本是物流系統(tǒng)的核心成本,在物流總成本中占據(jù)了很大的比例。 (4)對(duì)于帶能力約束的車(chē)輛路徑問(wèn)題(CVRP),提出了一種新的雙層染色體編碼方案和一種子路徑交換算法。車(chē)輛從場(chǎng)站出發(fā)對(duì)客戶進(jìn)行配送服務(wù)最后返回場(chǎng)站，要求所有顧客都被配送，每位顧客一次配送完成，且不能違反車(chē)輛容量的限制，目的是所有車(chē)輛路線的總距離最小。1960年，Clarke和Wrigh首先提出一種啟發(fā)式節(jié)省法（savings methods）來(lái)建立車(chē)隊(duì)配送路線。當(dāng)時(shí)，其主要目的是說(shuō)明自然和人工系統(tǒng)的自適應(yīng)過(guò)程。 遺傳算法流程圖圖2 遺傳算法流程圖5 模型建立求解及實(shí)例應(yīng)用根據(jù)上述對(duì)問(wèn)題的描述，可以采用混合整數(shù)規(guī)劃方法對(duì)車(chē)輛調(diào)度進(jìn)行建模設(shè)N為最小成本，則目標(biāo)函數(shù)為滿足約束條件1：式中：K為所有車(chē)輛的集合， ；G為所有客戶的集合， ， ，其中{0}代表配送中心； 為由車(chē)輛k服務(wù)的客戶的集合； 為車(chē)輛到達(dá)客戶i的時(shí)間；為懲罰函數(shù)，車(chē)輛在時(shí)間 到達(dá)客戶i時(shí)所對(duì)應(yīng)的懲罰成本；為車(chē)輛從客戶i到客戶j的所有運(yùn)輸成本；為車(chē)輛從客戶i到客戶j的行車(chē)時(shí)間；為客戶i的需求量；Q為車(chē)輛k的最大裝載量；為車(chē)輛在客戶i處的停留的時(shí)間。這樣，l、…、L＋m－l 這L＋m－l 個(gè)互不重復(fù)的自然數(shù)的隨機(jī)排列就構(gòu)成一個(gè)個(gè)體，并對(duì)應(yīng)一種配送路徑方案。A=2 9 5 4|3 5 6 2 9 8 4 7 139。個(gè)