Improved Ant Colony System Algorithm for Waste Collection Vehicle Routing Problem

In order to solve the waste collection vehicle routing problem with intermediate facilities (WCVRP-IF) and reduce the route length and overlaps between two different vehicle routes, a clustering-based multiple ant colony system (CMACS) algorithm was proposed. This CMACS algorithm possesses a set of new strategies to construct solutions, including clustering-based strategy, improved global pheromone update rule and cross operator. Tests on two standard instances were conducted, their deviations being 0 and 2.13% from the best known solution, respectively. In addition, a comparison between calculated results based on different ant colony algorithms was made. The research results show that the length and compactness of the optimal route calculated by the proposed algorithm with a clustering-based strategy is 4.90% shorter and 83.33% smaller respectively than those of the optimal route calculated by the traditional ant colony system algorithm. The contribution degree of different strategies is successively the clustering-based strategy, the global pheromone update rule and the cross operator.