蟻群算法求解MDVRP的設(shè)計(jì)與實(shí)現(xiàn).pdf

1、多中心車輛路徑問題(MDVRP)是一個(gè)復(fù)雜的組合優(yōu)化問題，其復(fù)雜性甚于車輛路徑問題(VRP)，該問題在現(xiàn)實(shí)生活中普遍存在，與人們的生活息息相關(guān)。蟻群算法(ACO)作為一種比較新的元啟發(fā)算法，目前在一些路徑優(yōu)化問題上的應(yīng)用效果卓著，但是關(guān)于ACO在MDVRP問題上應(yīng)用的論述還很少。本論文中針對(duì)MDVRP的特征，提出了兩種ACO求解MDVRP的算法模型：分治法和綜合法。前者是采用分治的求解思路，用分配算法將一個(gè)MDVRP分割成幾個(gè)VRP，然

2、后用ACO求解VRP，再將它組合成MDVRP的解，這是一種多蟻群算法。綜合法則是另起爐灶，即和其他的用ACO求解的NP-hard問題一樣，不需要將問題分割，而將MDVRP作為一個(gè)有機(jī)的整體來對(duì)待，這是一種單蟻群算法。本文在MDVRP標(biāo)準(zhǔn)測(cè)試集上進(jìn)行了測(cè)試，兩種算法各有特點(diǎn)，分治法在4個(gè)測(cè)試實(shí)例上得到了最優(yōu)解，綜合法在6個(gè)測(cè)試實(shí)例上得到了最優(yōu)解。對(duì)于其余實(shí)例，在小規(guī)模的測(cè)試實(shí)例(顧客節(jié)點(diǎn)數(shù)n≤100)上綜合法獲得的結(jié)果優(yōu)于分治法，大規(guī)模的