A new use of the ant system algorithm for the max-mean dispersion problem

Abstract

This study addresses an NP-hard problem known as the max-mean dispersion problem (MaxMeanDP), which belongs to a well-known class of diversity problems. In view of the increasing importance of parallel computing, this study proposes an ant system (AS) approach to the MaxMeanDP in which ants execute the search process in parallel. Moreover, by proposing a rather different use of the pheromone trail and visibility compared to the original AS, a new AS algorithm is introduced that runs in parallel. Our analysis indicates that the new use of the pheromone trail and visibility significantly contributes to the quality of the solution. The results show that the proposed method is effective, efficient and comparable to other approaches.