【正文】 而且大大提高了動手的能力，使我充分體會到了在創(chuàng)造過程中探索的艱難和成功時的喜悅。此外，還得出一個結(jié)論：知識必須通過應(yīng)用才能實現(xiàn)其價值！有些東西以為學會了，但真正到用的時候才發(fā)現(xiàn)是兩回事，所以我認為只有到真正會用的時候才是真的學會了。通過這次畢業(yè)設(shè)計，我才明白學習是一個長期積累的過程，在以后的工作、生活中都應(yīng)該不斷的學習，努力提高自己知識和綜合素質(zhì)。在沒有做畢業(yè)設(shè)計以前覺得畢業(yè)設(shè)計只是對這幾年來所學知識的單純總 結(jié)，但是通過這次做畢業(yè)設(shè)計發(fā)現(xiàn)自己的看法有點太片面。由于物流配送路徑優(yōu)化問題是一個 NP 難題，因此，采用啟發(fā)式算法求解是一個重要的研究方向。種群設(shè)為 40，最大代數(shù)為 400，運輸成本參數(shù)設(shè) 為 3，時間懲罰參數(shù)設(shè)為 6，并且第 4 次及第 7 次實驗中人為設(shè)置較高變異率（分別為 和 ） ,以達到人為增加變異次數(shù)避免局部最優(yōu)解的出現(xiàn)，共進行了八次運算，得到 測試 結(jié)果如下 ： 表 2 優(yōu)化結(jié)果表 最終優(yōu)化結(jié)果為需要調(diào)度兩臺車，得到的優(yōu)化路徑為 OACEHBO 和OFGDO,運輸長度為 ，成本為 。 23 實例分析 本文仍采用的經(jīng)典測試集。算法停止準則的設(shè)計淘汰不符合約束條件 2）、 3） 的染色體 。 的經(jīng)驗值為 ,~ 效果較佳 。 交叉操作 由于復制操作并沒有產(chǎn)生新的車輛分配方案 ， 因此種群中最好的個體的適配值并沒有降低 。 首先對 中的元素按照客戶要求到達的時間從小到大進行排序 ， 如果有兩個以上的客戶要求到達的時間相同 ，則對這些客戶按照配送區(qū)域 （ 時區(qū) ） 從小到大進行排序 。 過 21 大不但增加計算量 ， 而且不能有效地獲得迭代解 。在本問題中 ， 對于種群數(shù)目為 N 的染色體群 ， 其個體染色體 i 的適配值 的值越小 ,則表示個體適配值越高 。 編碼操作 遺傳算法的關(guān)鍵之一是確定染色體并對它進行編碼處理 。判斷迭代的代數(shù)是否為要求代數(shù) maxt，若是，停止進化，選性能最好的染色體所對應(yīng)的路徑集合，作為問題的優(yōu)化解輸出。B 中自交配區(qū)域后依次刪除與交配區(qū)域相同的自然數(shù)，得到最終的兩個后代： C1=2 9 5 4 3 6 8 7 1 C2=6 2 9 8 3 8 4 1 7 3. 遺傳基因的變異 基因的變異是在選出的染色體 中按其變異概率隨機找出若干基因位置，再隨機產(chǎn)生一個基因替換原有位置基因，并查找因替換基因產(chǎn)生的此基因的另一重復位置，修改使之成為一個不重復基因染色體。其操作方法如下：首先，隨機在父代染色體中選擇一個交配區(qū)域，如兩個父代染色體 及交配區(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。同理，可以得到另一個新染色體 child2。新種群的產(chǎn)生是在上一代的基礎(chǔ)上對原有的各染色體按其適應(yīng)度大小進行保留，并將其進行交叉和變異形成新一代的個體；適應(yīng)度計算之后是實際的選擇，按照適應(yīng)度進行父代個體的選擇，本文由輪盤賭算法進行種子的選?。挥嬎忝總€個體的相對適應(yīng)度值，以之作為概率，將 [0,1]空間劃分成 n 份。本文采用隨機產(chǎn)生一種 l～ L＋ m－ l 這 L＋ m－ l 個互不重復的自然 17 數(shù)的排列，即形成一個個體。為了在編碼中反映車輛配送的路徑，采用了增加 m－ 1 個虛擬 配送中心的方法，分別用 L＋ L＋ … 、 L＋ K－ l 表示。 16 如問題為硬時間窗問題，則必須滿足到客戶 i 的時間要比承諾到達時間早，即到達 i 的時間 ≤到達 i 的最晚時間限制； 如有緊急貨物（高優(yōu)先級客戶）時，則自動將優(yōu)先級高的貨物按優(yōu)先級順序排入隊列前端，然后將其它普通貨物再進行優(yōu)化；即如有 N 個客戶，其中有一個為緊急運單，則自動將其放在隊首，其他 N1 個客戶進行優(yōu)化，即將問題降為 N1 階的路徑優(yōu)化問題； 任一客戶只由一臺運輸車輛提供服務(wù)，即算法解決的是任一客戶的貨物需求均小于車輛最大負載（容積）的情況。在該類問題中，有車輛裝載能力約束，且每個客戶 i 都有一個與之相聯(lián)系的時間區(qū)間 [ai ,bi]， 稱為時間窗。 約束條件 2： 保證每個客戶均被服務(wù) ， 而且每輛車都從配送中心出發(fā) ； 約束條件 3： 表示每輛車負責的客戶點的貨物需求量總和不超過該車輛的最大裝載量 ； 15 約束條件 5： 表示對任一由 k服務(wù)的客戶點 j必定有另一 (而且只有一個 )由 k服務(wù)的客戶點 (包括配送中心 )I,車輛 k從客戶點 i到達客戶點 j,而對由 k服務(wù)的客戶點 i同樣存在由 k服務(wù)的另一客戶點 ,車輛 k是從該客戶點到達客戶點 i的 ,依次類推 ； 約束條件 6： 保證每輛車的行車路線的總耗時不超過一個事先定下的數(shù)值 ； 約束條件 7： 對某個客戶點 ， 車輛到達時間限制 在某一時間段內(nèi) 。具有如下特點： (1) 遺傳算法運算的是解集的編碼，而不是解集本身； (2) 遺傳算法的搜索始于解的一個種群，而不是單個解； (3) 遺傳算法只使用報酬 信息（適值函數(shù)），不使用導數(shù)或其他輔助知識； (4) 遺傳算法采用概率的，而不是確定的狀態(tài)轉(zhuǎn)移規(guī)則。 遺傳算法的基本思想 遺傳算法是受生物進化學說和遺傳學說啟發(fā)而發(fā)展起來的，基于 適者生存思想的一種較通用的問題求解方法。作為一種隨機優(yōu)化技術(shù)在解優(yōu)化問題中顯示了優(yōu)于傳統(tǒng)優(yōu)化算法的性能，遺傳算法的一個顯著優(yōu) 勢是不需要目標函數(shù)明確的數(shù)學方程和導數(shù)表達式，同時又是一種全局尋優(yōu)算法，不會象某些傳統(tǒng)算法易于陷入局部最優(yōu)解。遺傳算法作為一種全局優(yōu)化搜索方法，具有簡單、通用普適性強，適用于并行處理和應(yīng)用范圍廣等優(yōu)點。遺傳算法的概念最早是由 Bagley 在 1967 年提出的；而開始遺傳算法的理論和方法的系統(tǒng)性研究的是 1975 年，這一開創(chuàng)性工作是由 Michigan 大學的 . Holland 所實行。 Bent 和 Van Hentenryck 則首先用 模擬退火算法 將車輛路線的數(shù)量最小化，然后用大鄰域搜索法（ largneighborhood search）將運輸費用降到最低。模擬退火方法具有收斂速度快，全局搜索的特點， Osman 對 VRP 的模擬退火算法進行了研究，他提出的模擬退火方法主要適合于解決路線分組。前者是 先將所有需求點大略分為幾個組，然后再對各個組分別進行路線排序；后者則是先將所有的需求點建構(gòu)成一條路線，再根據(jù)車輛的容量將這一路線分割成許多適合的單獨路線。交換法則是依賴其他方法產(chǎn)生一個起始路線，然后以迭代的方式利用交換改善法減少路線距離，直到不能改善為止。 啟發(fā)式算法 由于 VRP 是 NPhard 問題，難以用精確算發(fā)求解，啟發(fā)式算法 9 是求解車輛 運輸問題的主要方法，多年來許多學者對車輛運輸問題進行了研究，提出了各種各樣的啟發(fā)式方法。 車輛路線問題型態(tài) 在基本車輛路線問題（ VRP）的基礎(chǔ)上，車輛路線問題在學術(shù)研究和實際應(yīng)用上產(chǎn)生了許多不同的延伸和變化型態(tài)，包括 時窗限制車輛路線問題 （ vehicle routing problems with time windows， VRPTW）、 追求最佳服務(wù)時間的車輛路線問題 （ VRPDT）、 多車種車輛路線問題 （ fleet size and mix vehicle routing problems， FSVRP）、 車輛多次使用的車輛路線問題 （ vehicle routingproblems with multiple use of vehicle， VRPM）、 考慮收集的車輛路線問題 （ vehicle routingproblems with backhauls， VRPB）、 隨機需求車輛路線問題 （ vehicle routing problem with stochastic demand， VRPSD）等。 相同的單一起點和終點。車輛路線問題可以描述如 下（如圖 1）： 圖 1 路徑問題描述 設(shè)有一場站（ depot），共有 M 輛貨車，車輛容量為 Q，有 N 位 顧客 （ customer），每位顧客有其需求量 D。