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

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

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

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