【正文】 過這次做畢業(yè)設(shè)計(jì)發(fā)現(xiàn)自己的看法有點(diǎn)太片面。而且大大提高了動(dòng)手的能力，使我充分體會(huì)到了在創(chuàng)造過程中探索的艱難和成功時(shí)的喜悅。由于物流配送路徑優(yōu)化問題是一個(gè) NP 難題，因此，采用啟發(fā)式算法求解是一個(gè)重要的研究方向。 的經(jīng)驗(yàn)值為 ,~ 效果較佳 。在本問題中 ， 對(duì)于種群數(shù)目為 N 的染色體群 ， 其個(gè)體染色體 i 的適配值 的值越小 ,則表示個(gè)體適配值越高 。其操作方法如下：首先，隨機(jī)在父代染色體中選擇一個(gè)交配區(qū)域，如兩個(gè)父代染色體 及交配區(qū)域選定為： 18 A=3 5|6 2 9 8|4 7 1 B=8 3|2 9 5 4|1 6 7 其次，將 B 的交配區(qū)域加到 A 的前面， A 的交配區(qū)域加到 B 的前面，得到： 39。為了在編碼中反映車輛配送的路徑，采用了增加 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 年提出的；而開始遺傳算法的理論和方法的系統(tǒng)性研究的是 1975 年，這一開創(chuàng)性工作是由 Michigan 大學(xué)的 . Holland 所實(shí)行。交換法則是依賴其他方法產(chǎn)生一個(gè)起始路線，然后以迭代的方式利用交換改善法減少路線距離，直到不能改善為止。車輛路線問題可以描述如 下（如圖 1）： 圖 1 路徑問題描述 設(shè)有一場(chǎng)站（ depot），共有 M 輛貨車，車輛容量為 Q，有 N 位 顧客 （ customer），每位顧客有其需求量 D。 (3)將單配送中心 ,多輛運(yùn)輸車且無約束的車輛路徑問題建模成具有總路徑 長(zhǎng)度最短、子路徑長(zhǎng)度均衡性好這兩個(gè)目標(biāo)的雙目標(biāo)多旅行商問題 (MTSP),并基于 HGATSP 算法 ,研究了三種求解上述問題的解決方案。因此 ,研究物流系統(tǒng)中的優(yōu)化問題 ,具有十分重要的意義 ,是國內(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 2 pared and analyzed the basic ideas, capabilities and applicability of tradition method heuristics of VRP. Based on this, this paper put forward an improved geic algorithm for vehicle routing problem, through changing its select operation and neighborhood structure operation, an adaptive geic 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 geic algorithms method. The method have made good effect in ensuring customer service level. Keyword: Vehicle Routing Problem。 1 基于遺傳算法的車輛路徑問題研究 中文摘要 ： 近些年 ,物流作為 “ 第三利潤(rùn)源泉 ” 受到國內(nèi)各行業(yè)的極大重視并得到較大的發(fā)展。 sweep method。 庫存成本與配送成本是物流系統(tǒng)的核心成本 ,在物流總成本中占據(jù)了很大的比例。 (4)對(duì)于帶能力約束的車輛路徑問題 (CVRP),提出了一種新的雙層染色體編碼方案和一種子路徑交換算法。車輛從 場(chǎng)站 出發(fā)對(duì)客戶進(jìn)行配送服務(wù)最后返回場(chǎng)站，要求所有顧客都被配送 ，每位顧客一次配送完成，且不能違反車輛容量的限制，目的是所有車輛路線的總距離最小。 1960 年， Clarke 和 Wrigh 首先提出一種啟發(fā)式節(jié)省法（ savings methods）來建立車隊(duì)配送路線。當(dāng)時(shí)，其主要目的是說明自然和人工系統(tǒng)的自適應(yīng)過程。 遺傳算法流程圖 13 圖 2 遺傳算法流程圖 14 5 模型建立求解及實(shí)例應(yīng)用 車輛調(diào)度模型 根據(jù)上述對(duì)問題的描述 ， 可以采用混合整數(shù)規(guī)劃方法對(duì)車輛調(diào)度進(jìn)行建模 設(shè) N為最小成本 ， 則目標(biāo)函數(shù)為 滿足約束條件 1： 式中： K為所有車輛的集合， ； G為所有客戶的集合， ， ， 其中 {0}代表配送中心 ； 為由車輛 k服務(wù)的客戶的集合； 為車輛到達(dá)客戶 i的時(shí)間； 為懲罰函數(shù)，車輛在時(shí)間 到達(dá)客戶 i時(shí)所對(duì)應(yīng)的懲罰成本； 為車輛從客戶 i到客戶 j的所有運(yùn)輸成本； 為車輛從客戶 i到客戶 j的行車時(shí)間； 為客戶 i的需求量 ； Q為車輛 k的最大裝載量； 為車輛在客戶 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 1 39。 個(gè)體適配值為 式中 ， 所以 ， 目標(biāo)函數(shù) 生成初始染色體種群 初始化遺傳世代 ； 每一代的染色體群的 種群數(shù)目 ； 交叉概率 ， 變異概率 等參數(shù) 。 變異操作 變異操作 mutation（） 以概率 對(duì)染色體群中的某些染色體的某些位進(jìn)行變異 ， 產(chǎn)生