求解弧路徑問題的遺傳算法研究.pdf

1、車輛弧路徑問題產生于現(xiàn)實生活中的交通運輸服務系統(tǒng)，有著廣泛的應用，近年來逐漸成為研究的熱點。由于它是NP-難問題，精確算法的求解時間呈指數(shù)增長，因此無法處理大規(guī)模的問題，而現(xiàn)有的啟發(fā)式算法雖然求解時間較短，但往往存在解質量效率低下的缺點。隨著遺傳算法的發(fā)展，它已被應用到這一問題的求解。已有結果表明，遺傳算法可以很好地兼顧運算效率和解質量效率這兩方面的要求，在解決車輛弧路徑問題上具有很好的發(fā)展前途。 本文在廣泛深入地查閱國內外文獻

2、的基礎上，對遺傳算法的基礎理論和方法進行了深入的理論研究，并應用遺傳算法對車輛弧路徑問題進行了實驗分析，主要內容如下： 1.系統(tǒng)、詳盡的介紹了遺傳算法的一般流程和基本理論、方法。 2.簡要介紹了弧路徑問題及其起源和發(fā)展歷史，歸納總結了其求解方法。在現(xiàn)有的算法基礎上，提出了一種新的遺傳算法來解決以車輛服務成本為目標的弧路徑問題。新算法采用了改進的局部搜索技術，并對現(xiàn)有算法的其他部件做了一些調整。通過對多個實例的計算證明了該