An Optimization Meta-heuristic Algorithm for the Capacitated Vehicle Routing Problem

The Capacitated Vehicle Routing Problem (CVRP) is one of the most famous and widely studied problems in combinatorial optimization that nowadays it has been received much attention by researchers and scientists. So, many exact, heuristic and meta-heuristic algorithms have been proposed to solve it in recent decades. In this paper, aimed at the disadvantages existed in the current Elite Ant System (EAS), a modification of this algorithm called PA is proposed for solving CVRP. This new algorithm can avoid premature convergence and exploit more strong solutions. In order to assess the efficiency of the PA, 26 standard instances involving from 50 to 199 customers from the literature were studied and their results were compared with other well-known meta-heuristic algorithms. The results indicate that the proposed algorithm is competitive with other algorithms. In addition, the PA finds closely the best known solutions for most of the instances in which twenty best known solutions are also found.