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

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

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