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

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

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

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

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