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