帶裝載能力限制的開放式車輛路徑問題及其遺傳算法研究.pdf

1、物流是一個新興學科，配送是現(xiàn)代物流的一個重要內容，合理安排車輛配送路線可以降低運輸成本，提高經濟效益。車輛路徑問題(VRP)是一類在物流配送調度中具有廣泛應用的組合優(yōu)化問題，屬于NP難題。 為了便于對VRP進行系統(tǒng)的研究，運籌學界將其分為兩大類：閉合式VRP和開放式VRP。當車輛完成運輸任務后必須返回原出發(fā)點時，稱之為閉合式VRP，一般就簡稱為車輛路徑問題(VRP)；當不要求車輛完成任務后返回原出發(fā)點，或者是要求其沿原去程路線返

2、回時，稱之為開放式VRP(OVRP)。在不需要嚴格區(qū)分的場合，統(tǒng)稱為車輛路徑問題(VRP)。 由于OVRP問題也是NP難題，高效的精確算法存在的可能性不大，所以尋找近似算法是必要和現(xiàn)實的。遺傳算法就是其中一種很好的解決方法。遺傳算法是一種借鑒生物界自然選擇和進化機制發(fā)展起來的高度并行、隨機搜索算法。 本文的重點是研究如何利用遺傳算法求解開放式車輛路徑問題。首先，分析了目前開放式車輛路徑問題的研究現(xiàn)狀，并在此基礎上簡述了本

3、文要重點研究的最基礎的問題類型——帶裝載能力限制的開放式車輛路徑問題(COVRP)。然后，介紹遺傳算法的基本理論和算法，并以COVRP為例，進行了問題分析、算法設計并且實現(xiàn)了此算法。特別地，在該算法中使用了一種新的交叉算子和幾種改進策略。最后，分別比較和探索了使用該交叉算子后和使用各種改進策略后算法性能的改變情況，證明了該交叉算子和某些改進策略能有效提高遺傳算法的性能。更進一步地，將結果與目前已有的其他算法結果相比較，分析了遺傳算法解決