A Modified ANT System Optimization Algorithm for the Capacitated 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.