Modified Ant System with Threshold for the Vehicle Routing Problem

Abstract

Vehicle routing problem is a combinatorial optimization problem. Ant system, one of the most popular algorithms for solving the combinatorial optimization problem, is inspired by the ant foraging behavior. However, Ant system has the problem of premature convergence and easily getting trapped into local optimum. This paper proposes the modified ant system with threshold. In the beginning, the proposed algorithm randomly generates the initial population. To obtain a more diverse population, the transition probability and the threshold are used to determine which city should be next in the path. Moreover, the improved pheromone updating process is introduced to help reducing the rate of convergence. Three local searches, swap, insert, and reverse, are used in the proposed algorithm to prevent getting trapped in a local optimum. The datasets used in this research were taken from TSPLIB, the standard benchmark datasets for TSP. The performance of the algorithm was compared with that of the other 3 algorithms: GA-PSO-ACO, FOGS-ACO, and Hybrid VNS. The results on 20 datasets showed that the proposed method outperformed or at least at par with the others on 15 datasets. On the other hand, there was one dataset, rd100, on which the proposed algorithm was better than the best-known solution. According to the result, our modified ant system with threshold was very effective for the small- and medium-sized vehicle routing datasets.