A simplified ant colony algorithm for capacity-constrained vehicle routing problem

With the ant colony algorithm for solving the traveling salesman problem (TSP) as a prototype, a simplified algorithm was developed which considered a capacity-constrained vehicle routing problem as several independent TSPs with the depot serving as one of the cities in each TSP. Pheromone update was analyzed and it was found in the searching process that, if the current solution is best of all so far, then increase of the pheromone of the path found by the elitist ants further improves the solution and speeds up the convergence. Moreover, allowing more degree of freedom at the initial stage results in better solution . Experimental results show that the simplified algorithm can efficiently find a satisfactory solution, with an error of no more then 1.5% of the optimal one.