【正文】 終于做完了有種如釋重負(fù)的感覺(jué)。雖然這個(gè)設(shè)計(jì)做的也不太好，但是在設(shè)計(jì)過(guò)程中所學(xué)到的東西是這次畢業(yè)設(shè)計(jì)的最大收獲和財(cái)富，使我終身受益。在這次畢業(yè)設(shè)計(jì)中也使我們的同學(xué)關(guān)系更進(jìn)一步了，同學(xué)之間互相幫助，有什么不懂的大家在一起商量，聽(tīng)聽(tīng)不同的看法對(duì)我們更好的理解知識(shí)，所以在這里非常感謝幫助我的同學(xué)。所構(gòu)造的物流配送路徑優(yōu)化的遺傳算法，包括設(shè)計(jì)個(gè)體編碼方法、個(gè)體適應(yīng)度值的計(jì)算方法以及選擇、交叉和變異算子，對(duì)解決類(lèi)似的組合優(yōu)化問(wèn)題具有一定的參考價(jià)值。用上述的帶時(shí)間窗的遺傳算法，對(duì)一個(gè)有8 個(gè)客戶和1個(gè)配送中心，兩輛車(chē)（容量均為8 噸）的配送系統(tǒng)的車(chē)輛路徑問(wèn)題進(jìn)行求解。變異操作mutation（）以概率對(duì)染色體群中的某些染色體的某些位進(jìn)行變異，產(chǎn)生新的個(gè)體染色體、作為交叉運(yùn)算的補(bǔ)充，變異操作可增加車(chē)輛分配方案的多樣性，克服求解可能出現(xiàn)的早熟和陷入局部最優(yōu)解的現(xiàn)象。淘汰不符合約束條件的解，調(diào)整次序重新搜索，直到找到較佳的可行解為止。個(gè)體適配值為式中，所以，目標(biāo)函數(shù)生成初始染色體種群初始化遺傳世代；每一代的染色體群的種群數(shù)目；交叉概率，變異概率 等參數(shù)。 步驟Step1：t=0，利用自然數(shù)編碼方式，采用前相插入啟發(fā)式算法和隨機(jī)的方式產(chǎn)生初始種群，并輸入控制參數(shù)；Step2：計(jì)算個(gè)體適應(yīng)度；Step3：t maxt，t=t+1，則轉(zhuǎn)Step4；否則停止計(jì)算，并輸出結(jié)果；Step4：采用基于個(gè)體濃度的群體多樣性保持策略來(lái)選擇個(gè)體；Step5：對(duì)個(gè)體進(jìn)行CX 交叉重組；Step6：按照變異方法對(duì)個(gè)體進(jìn)行變異；Step7：重復(fù)步驟26；6算法的建立和求解車(chē)輛優(yōu)化調(diào)度問(wèn)題由車(chē)輛分配和路線安排這兩個(gè)相互關(guān)聯(lián)的子問(wèn)題組成，但關(guān)鍵是確定優(yōu)化的車(chē)輛分配方案（即求解變量）。A=2 9 5 4|3 5 6 2 9 8 4 7 139。生成一個(gè)[0,1]范圍內(nèi)的隨機(jī)數(shù)，看它落在哪個(gè)區(qū)域，則選擇該個(gè)體。這樣，l、…、L＋m－l 這L＋m－l 個(gè)互不重復(fù)的自然數(shù)的隨機(jī)排列就構(gòu)成一個(gè)個(gè)體，并對(duì)應(yīng)一種配送路徑方案?？蛻舻姆?wù)必須在相應(yīng)的時(shí)間窗內(nèi)開(kāi)始，車(chē)輛必須在客戶點(diǎn)停留的時(shí)間長(zhǎng)度為si。 遺傳算法流程圖圖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í)間。 遺傳算法是具有“生成+檢測(cè)”(generateandtest)的迭代過(guò)程的搜索算法。當(dāng)時(shí)，其主要目的是說(shuō)明自然和人工系統(tǒng)的自適應(yīng)過(guò)程。遺傳算法具有求解組合優(yōu)化問(wèn)題的良好特性，Holland首先采用遺傳算法（GA）編碼解決VRPTW 問(wèn)題。1960年，Clarke和Wrigh首先提出一種啟發(fā)式節(jié)省法（savings methods）來(lái)建立車(chē)隊(duì)配送路線。 求解方法演進(jìn) 綜合過(guò)去有關(guān)車(chē)輛路線問(wèn)題的求解方法，可以分為精確算法（exact algorithm）與啟發(fā)式解法（heuristics），其中精密算法有分支界限法、分支切割法、集合涵蓋法等；啟發(fā)式解法有節(jié)約法、模擬退火法、確定性退火法、禁忌搜尋法、基因算法、神經(jīng)網(wǎng)絡(luò)、螞蟻殖民算法等。車(chē)輛從場(chǎng)站出發(fā)對(duì)客戶進(jìn)行配送服務(wù)最后返回場(chǎng)站，要求所有顧客都被配送，每位顧客一次配送完成，且不能違反車(chē)輛容量的限制，目的是所有車(chē)輛路線的總距離最小。 (6)綜合應(yīng)用了面向?qū)ο蠓治雠c設(shè)計(jì)、多線程、UML等先進(jìn)的軟件開(kāi)發(fā)方法與技術(shù),設(shè)計(jì)并開(kāi)發(fā)了VRP仿真實(shí)驗(yàn)室,這是一個(gè)用于研究車(chē)輛路徑問(wèn)題的軟件包,具有使用簡(jiǎn)便、界面美觀的特點(diǎn)。 (4)對(duì)于帶能力約束的車(chē)輛路徑問(wèn)題(CVRP),提出了一種新的雙層染色體編碼方案和一種子路徑交換算法。針對(duì)隨機(jī)系統(tǒng)的特點(diǎn),設(shè)計(jì)了候選解收集器,它能夠收集在仿真優(yōu)化過(guò)程中產(chǎn)生的Pareto解。 庫(kù)存成本與配送成本是物流系統(tǒng)的核心成本,在物流總成本中占據(jù)了很大的比例。研究車(chē)輛路徑問(wèn)題的特點(diǎn)及算法具有重要的實(shí)際意義。 sweep method。然后對(duì)車(chē)輛路徑問(wèn)題的傳統(tǒng)求解算法的基本思想、性能、適用性進(jìn)行了分析,在此基礎(chǔ)上提出了采用掃描法和遺傳算法相結(jié)合的啟發(fā)式算法來(lái)求解物流配送車(chē)輛優(yōu)化調(diào)度問(wèn)題的思想?；谶z傳算法的車(chē)輛路徑問(wèn)題研究中文摘要：近些年,物流作為“第三利潤(rùn)源泉”受到國(guó)內(nèi)各行業(yè)的極大重視并得到較大的發(fā)展。論文首先對(duì)現(xiàn)有車(chē)輛優(yōu)化調(diào)度問(wèn)題歸類(lè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