An ant system with direct communication for the capacitated vehicle routing problem

Abstract

— Ant colony optimization (ACO) algorithms are population-based algorithms where ants communicate via their pheromone trails. Usually, this indirect communication leads the algorithm to a stagnation behaviour, where the ants follow the same path from early stages. This is because high levels of pheromone are generated into a single trail, where all the ants are influenced and follow it. As a result, the population gets trapped into a local optimum solution, which is difficult for the ACO algorithm to escape from it. In this paper, a direct communication scheme is proposed and applied to ACO for the capacitated vehicle routing problem (CVRP), which is a difficult NP-hard optimization problem. The direct communication scheme allows the ants to exchange customers from different routes, with other ants that belong to their communication range. Experiments show that the direct communication scheme significantly improves the solution quality of a conventional ACO algorithm regarding CVRP with and without service time constraints.