基于IA與TS的帶時(shí)間窗車輛路徑優(yōu)化算法研究.pdf

1、研究車輛路徑問(wèn)題(Vehicle Routing Problem，VRP)的相關(guān)理論和算法是為了降低物流的成本。該問(wèn)題通過(guò)規(guī)劃出合理的行駛路線來(lái)實(shí)現(xiàn)運(yùn)輸成本的最小化。這個(gè)問(wèn)題是運(yùn)籌學(xué)和組合優(yōu)化領(lǐng)域的研究熱點(diǎn)。對(duì)這個(gè)問(wèn)題的不斷深入研究使得它已經(jīng)延伸出了許多新的研究分支。本文首先分析了目前車輛路徑問(wèn)題的研究現(xiàn)狀，再結(jié)合實(shí)際提出了本文的研究問(wèn)題--帶時(shí)間窗的車輛路徑問(wèn)題(VRPTW)。通過(guò)對(duì)帶時(shí)間窗車輛路徑問(wèn)題的數(shù)學(xué)建模，明確定義了問(wèn)題的目標(biāo)

2、函數(shù)和約束條件。在考慮了配送的距離、配送的時(shí)間性和配送的車輛數(shù)等因素的影響，最后構(gòu)建了以配送總路徑最短為目標(biāo)。在分析了目前多種求解方法后，本文采用的是免疫禁忌搜索算法的混合策略。
　　 首先，對(duì)禁忌搜索算法和免疫算法分別進(jìn)行了分析。了解了禁忌搜索算法的求解思想，重點(diǎn)是渴望水平的設(shè)計(jì)，針對(duì)車輛路徑問(wèn)題目標(biāo)函數(shù)的特點(diǎn)求解最短路徑，將禁忌搜索算法渴望水平設(shè)計(jì)為與目標(biāo)函數(shù)相同的函數(shù)。對(duì)TSP問(wèn)題分別用禁忌搜索算法、遺傳算法和蟻群算法進(jìn)行

3、了求解。用平均值，方差和平均計(jì)算時(shí)間進(jìn)行了比較，實(shí)驗(yàn)驗(yàn)證了禁忌搜索算法的有效性，同時(shí)驗(yàn)證了對(duì)初始解的依賴性。其次了解了免疫算法的算法思想，免疫算法的特點(diǎn)是疫苗的提取。用TSP問(wèn)題驗(yàn)證了免疫算法能夠在全局范圍內(nèi)求得最優(yōu)解，從實(shí)驗(yàn)的結(jié)果驗(yàn)證了免疫算法改進(jìn)了遺傳算法的不足。最后介紹了免疫禁忌搜索算法的混合策略的算法，本文是通過(guò)免疫算法產(chǎn)生的最優(yōu)解作為禁忌搜索算法的初始解，設(shè)計(jì)了適合建立的數(shù)學(xué)模型的編碼方式和渴望水平和親和度等。