用多種群遺傳算法求解車(chē)輛路徑問(wèn)題

摘要

車(chē)輛路徑問(wèn)題（Vehicle Routing Problems,VRP），即如何利用有限的運(yùn)輸資源來(lái)完成1定量的運(yùn)輸任務(wù)，并且使得運(yùn)輸成本最低的問(wèn)題。車(chē)輛路徑問(wèn)題由于其巨大的經(jīng)濟(jì)效益，在過(guò)去的40多年間得到了突飛猛進(jìn)的發(fā)展。本文在已有方法研究的基礎(chǔ)上，針對(duì)標(biāo)準(zhǔn)遺傳算法在解決車(chē)輛路徑問(wèn)題上容易出現(xiàn)早熟，容易陷入局部最優(yōu)解的缺點(diǎn)，對(duì)傳統(tǒng)的遺傳算法進(jìn)行改進(jìn)，提出了多種群遺傳算法（Multiple_population Genetic Algorithms）。即在求解過(guò)程中將初始化兩個(gè)種群，分別選取不同的交叉變異概率，在每1次迭代完后將第1個(gè)種群之中的適應(yīng)度較低的個(gè)體與第2個(gè)種群中適應(yīng)度較高的個(gè)體進(jìn)行交換，并且保存每個(gè)種群的最優(yōu)解到精英種群，以解決傳統(tǒng)遺傳算法容易出現(xiàn)早熟，容易陷入局部最優(yōu)解的問(wèn)題。實(shí)驗(yàn)結(jié)果表明，經(jīng)過(guò)改進(jìn)的遺傳算法比1般算法收斂速度更快，求解質(zhì)量更為優(yōu)良。

關(guān)鍵字：遺傳算法；物流調(diào)度；多種群；遺傳算子

Multi- Populations Genetic Algorithms for Vehicle Routing Problems

Abstract

Vehicle Routing Problems, how namely use the limited transportation resources to complete the ration the transportation duty, and causes the transportation cost lowest question. Vehicle Routing Problems as a result of its huge economic efficiency, obtained the development during more than 40 years in the past which progresses by leaps and bounds. This article in by has in the foundation which the method studies, is easy in view of the standard genetic algorithms in the solution Vehicle Routing Problems to appear precociously, is easy to fall into the partial optimal solution shortcoming, makes the improvement to the traditional genetic algorithms, proposed the multi- populations genetic algorithms. In the solution process the initialization two populations, separately will select the different overlapping variation probability, after each time will iterate the sufficiency high individual carries on the first populations in sufficiency low individual with the second population in the exchange, and will preserve each center group the optimal solution to the outstanding person population, by will solve the tradition genetic algorithms to be easy to appear precociously, will be easy to fall into the partial optimal solution question. The experimental result indicated that, after improvement genetic algorithms compared to general algorithm convergence rate quicker, the solution quality is finer.

Key word: Genetic Algorithms, Vehicle Routing Problems, Good Population and Bad Population, Elite Population

【用多種群遺傳算法求解車(chē)輛路徑問(wèn)題】相關(guān)文章：

遺傳算法及其在求解TSP中的應(yīng)用09-22

車(chē)輛路徑調(diào)度問(wèn)題的啟發(fā)式算法綜述09-07

物體平衡問(wèn)題的求解方法08-02

改進(jìn)logit多路徑分配模型及其求解算法研究07-23

圖書(shū)資料管理問(wèn)題及解決路徑07-02

應(yīng)用遺傳算法解決車(chē)間作業(yè)調(diào)度問(wèn)題07-24

冷鏈物流多溫配送路徑優(yōu)化研究10-23

我國(guó)電子政務(wù)發(fā)展問(wèn)題及路徑選擇09-14

引進(jìn)國(guó)外技術(shù)與設(shè)備：正視問(wèn)題后的路徑05-28

軟件工程多模式融合教學(xué)路徑分析08-22