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

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

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

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