粒子群算法在車(chē)輛路徑問(wèn)題中的應(yīng)用.pdf

1、車(chē)輛路徑問(wèn)題是供應(yīng)鏈研究的一項(xiàng)重要內(nèi)容，是運(yùn)籌學(xué)中的NP難題。粒子群優(yōu)化算法是一種利用群智能技術(shù)的進(jìn)化算法，種群內(nèi)社會(huì)信息的共享使粒子群算法擁有很好的進(jìn)化優(yōu)勢(shì)，粒子通過(guò)跟蹤個(gè)體極值（單個(gè)粒子所經(jīng)歷的最優(yōu)解）和全局極值（整個(gè)種群經(jīng)歷的最優(yōu)解）來(lái)進(jìn)行尋優(yōu)，具有很高的搜索效率；模擬退火算法模擬金屬冷卻過(guò)程，使用概率來(lái)避免陷入局部最優(yōu)。本課題將粒子群優(yōu)化算法與模擬退火算法結(jié)合，提出了一種求解車(chē)輛路徑問(wèn)題的混合粒子群算法。通過(guò)實(shí)例計(jì)算及與遺傳算法

2、的比較，得出結(jié)論：應(yīng)用混合粒子群算法可以快速地求得帶時(shí)間窗車(chē)輛路徑問(wèn)題的優(yōu)化解，是一種求解離散組合優(yōu)化問(wèn)題的有效方法。 本課題將VRP分解為兩個(gè)子問(wèn)題：（1）任務(wù)分配問(wèn)題，即把所有發(fā)貨點(diǎn)任務(wù)分配給可供選擇的車(chē)輛；（2）路徑優(yōu)化問(wèn)題，也就是旅行商問(wèn)題，對(duì)每輛車(chē)所走的路徑進(jìn)行優(yōu)化，以達(dá)到整體路徑最短。應(yīng)用粒子群算法進(jìn)行任務(wù)分配后，用模擬退化算法進(jìn)行路徑優(yōu)化，兩次優(yōu)化運(yùn)算獨(dú)立，根據(jù)其并行性，本課題設(shè)計(jì)了并行混合粒子群算法并用MPI實(shí)現(xiàn)