A Modified ANT System Optimization Algorithm for theCapacitated Vehicle Routing Problem

Abstract

In this paper we use a modified algorithm of the ant system optimization (ASO) to solve the
capacitated vehicle routing problem (CVRP), i.e., finding the (approximate) optimum routes, the
main modifications consist of, (1) Adding pheromone to the best three routes found by the ants
instead of adding pheromone to the global best route only, (2) Introducing the concept of
probability of stagnation which represent the probability of having the previous solution in the next
iteration, (3) Adding a local optimizer to improve the global best routes found by artificial ants. We
test our modified algorithm on some benchmark problems that have been also tested by other ant
colony optimization (ACO) metaheuristics, our results was best in the sense that it is closer to the
known optimum routes for these benchmark problems except one problem.