Parallel Ant Colony Optimization Algorithm For Vehicle Routing Problem

摘要

This paper presents a parallel ant colony algorithm based on Message Passing Interface (MPI) for vehicle routing problem (VRP). At the beginning of the algorithm, a sub-colony is simulated in each processor which independently computes to ensure population diversity. In order to overcome the shortcoming of the ant colony algorithm that is easy to fall into local optimum, a method is designed to judge weather the parallel algorithm get into premature stage. Once premature phenomenon turns up in the whole colony, the local search strategy is used to help the algorithm search the better solution. When the iterative process is over, the optimal solution of all ant colony computed is improved by the neighborhood exchange strategy. Experimental results show that the algorithm is effective and feasible especially for the VRP of large scale cities.