資源描述：
《基于Memetic算法的帶時間窗車輛路徑問題研究.pdf》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、第29卷第1期2012年1月計算機應(yīng)用研究ApplicationResearchofComputersV01．29No．1Jan．2012基于Memetic算法的帶時間窗車輛路徑問題研究吳雷，魏臻，葛方振(合肥工業(yè)大學計算機與信息學院，合肥230009)摘要：提出一種模擬文化進化的Memetic算法求解帶時間窗的車輛路徑問題。設(shè)計了一種實數(shù)編碼方案，將離散的問題轉(zhuǎn)為連續(xù)優(yōu)化問題。采用鄰域搜索幫助具備一定學習能力的個體提高尋優(yōu)速度；采用禁忌搜索幫助部分個體跳出局部最優(yōu)點，增強全局尋優(yōu)性能。實驗結(jié)果
2、表明，該算法可以更有效地求出優(yōu)化解，是帶時間窗車輛路徑問題的一種有效求解算法。關(guān)鍵詞：帶時問窗車輛路徑問題；文化基因算法；粒子群算法；禁忌搜索中圖分類號：TP301．6文獻標志碼：A文章編號：1001—3695(2012)01—0060-03doi：10．3969／j．issn．1001—3695．2012．01．016MemeticalgorithmforvehicleroutingproblemwithtimewindowsWULei。WEIZhen，GEFang-zhen(Schoolof
3、Computer＆htformation，HefeiUniversity礦Technology，uPfei230009，China)Abstract：ThispaperproposedaMemeticalgorithm，whichsimulatedtheprocessofcultureevolution，tosolvevehicleroutingproblemwithtimewindows(VRPTW)．ToconvertVR刀Wintocontinuousproblem，itdesigneda
4、realcodingmethod．Thememeticalgorithmhelpedtheparticleswhichhadcertainlearningcapacityaccelerateconvergenceratebylocalsearchstrate-gY．Meanwhile，becauseofhelpingsomeparticleswhichfellintothelocaloptimumescapefromlocaloptimumbytabusearch，itenhancedthedi
5、versityofswarm．Theexperimentalresultshowsthattheproposedalgorithmcmlgetthesolutionmoreeffee．tivelyanditisaneffectivemethodforVR唧．Keywords：VRPTW；Memeticalgorithm；PS0；tabu0引言車輛路徑問題(vehicleroutingproblem，VRP)1959年由Dantzig和Ramser首次提出，一直是組合優(yōu)化領(lǐng)域的熱點和前沿問題”]。
6、隨著VRP研究的不斷深入，考慮到需求點對于車輛到達時間有所要求，因此車輛路徑問題中加人了時間窗的限制，便成為了帶時間窗的車輛路徑問題(VRPwithtimewin-dows，VRFFW)。VRPTW是一個NP難問題，對它的研究越來越受到國內(nèi)外學者的重視，其算法的研究主要集中在粒子群算法、遺傳算法、禁忌搜索法和模擬退火法等各種啟發(fā)式算法上，并取得了一些不錯的效果
7、2“J。Memetic算法是一種模擬文化進化過程的新型進化方法，通過混合局部搜索和進化算子來解決優(yōu)化問題，是一種基于種群的全局搜索和基于
8、個體的局部啟發(fā)式搜索的結(jié)合體。它的這種全局搜索和局部搜索的結(jié)合機制使其搜索效率在某些問題領(lǐng)域比傳統(tǒng)種群優(yōu)化算法(如粒子群算法、禁忌算法等)快幾個數(shù)量級¨1。因此，有必要深入研究如何將Memetic算法應(yīng)用在車輛路徑問題的求解中，使得種群的個體之間能夠通過傳遞有效的知識經(jīng)驗來提高進化速度并快速適應(yīng)復雜的求解環(huán)境，以此彌補標準種群優(yōu)化算法的不足，從而大幅提高算法的尋優(yōu)性能。，本文利用基于Memetic的混合粒子群算法(hybridparticleswa／nloptimizationalgorithm
9、basedonMemetic，HM—PS0)來解決帶時間窗的車輛路徑問題。a)提出了一種新的實數(shù)編碼方案，將離散的帶時間窗車輛路徑問題轉(zhuǎn)換為連續(xù)型的優(yōu)化問題．b)基于拉馬克學習策略，融合了禁忌搜索算法，彌補了單一的粒子群算法在解決優(yōu)化問題時收斂度較慢、易陷于局部最優(yōu)的缺陷；e)通過兩個VR胛w實例的實驗結(jié)果證明，所提算法在搜索準確度和搜索時間花費方面都具有一定的優(yōu)勢。1帶時間窗的車輛路徑問題數(shù)學模型VRPTW描述?為：一個配送中心為n個客戶提供服務(wù)，配送中心擁有車輛數(shù)為m，車輛最大容量為Q，車輛
