Hybrid Sweep Algorithm and Modified Ant System with Threshold for Travelling Salesman Problem

Travelling salesman problem is a special case of the vehicle routing problem. The objective of the travelling salesman problem is to find the shortest path for visiting every city without repeating city. Among metaheuristic algorithms, Ant System has been the most popular algorithm for solving the travelling salesman problem. However, Ant System has a disadvantage of often falling into local optimal solutions. This research proposed a modified Ant System with a modified pheromone density updating to reduce the rate of convergence. A threshold is also used to create a greater variety of routes. Moreover, the proposed algorithm used a Sweep Algorithm to generate initial population so that the next city to visit is close to each other. To prevent the ants from getting trapped at a local optimum, three types of local search, swap, insert, and reverse, are used to veer away the paths towards the higher pheromone density at a local optimum. The tested results of the proposed algorithm were compared to those of other three algorithms: GA-PSO-ACO, Hybrid VNS, and HAACO. On 13 out of 15 small- and medium-sized datasets, the proposed method outperformed or performed as well as the others.