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