物流配送中車輛路徑問題的多目標優(yōu)化算法研究.pdf

1、VRP(Vehicle Routing Problem,車輛路徑問題)已被證實為NP-Hard問題,由于其應用廣泛,并且相當難解,國內外學者對求解方法的探索和試驗一直是一個研究熱點。NSGAⅡ(Nondominated Sorting in Genetic AlgotithmⅡ,帶精英策略的快速非支配排序遺傳算法)作為近幾年才產生和發(fā)展起來的新興算法,因其高效率而引起重點關注和初步應用,尤其是在求解多目標優(yōu)化問題上,但是將NSGAⅡ算法

2、應用于解決物流配送中VRP問題,目前還未見文獻述及。
　　 本文就是在借鑒國內外研究現(xiàn)狀的基礎上,選用NSGAⅡ作為求解VRP的算法基礎,實現(xiàn)了NSGAⅡ在VRP中的應用和軟件仿真,并針對仿真結果提出改進方案。通過改進前后的對比,驗證了改進方案的可行性。
　　 文本主要完成了以下幾個方面的工作:
　　 (1)實現(xiàn)了NSGAⅡ算法在物流配送中VRP問題多目標優(yōu)化的應用。分析概括出VRP的三個主要目標函數(shù):總的運輸路

3、徑最短、到達時間最準時、使用車輛最少；三個約束條件:每一輛車均不能超出滿載量、任意一條路徑上的客戶目均不超過所有客戶總數(shù)、每個需求點僅由一輛車配送。在此基礎上為VRP建立數(shù)學模型。然后根據NSGAⅡ算法的特點,為求解程序設計每一個環(huán)節(jié):編碼生成(采用自然數(shù)編碼方式)、初始群體的確定(判斷是否超載)、適應度評估(考慮目標函數(shù))、選擇(錦標賽法則)、交叉(隨機產生交叉基因)、變異(隨機產生交叉點)。
　　 (2)實現(xiàn)了軟件仿真。選擇

4、MATLAB作為軟件工具進行代碼編寫,選取BetichmarkProblems中的C101里的數(shù)據作為實驗數(shù)據。分析實驗數(shù)據,得出客戶需求量和客戶需求時間的分布特點。對仿真結果,從收斂代數(shù)和目標函數(shù)(運輸總路程、到達準時性、使用車輛數(shù)目)收斂情況兩個方面,評價算法的運算效率和求解能力,得出NSGAⅡ算法求解能力強、收斂情況較好、收斂速度較快等特點。
　　 (3)提出了對NSGAⅡ算法的改進。通過對仿真結果和NSGAⅡ算法的特點研