A swap sequence based Artificial Bee Colony algorithm for Traveling Salesman Problem

摘要

In this research paper, Artificial Bee Colony algorithm is modified with multiple update rules and K-opt operation to solve the Traveling Salesman Problem. Here the features of swap sequences and swap operations on the sequence of cities (solution/path) of the problem are used to create different solution (path) update rules of the algorithm. Eight different rules are proposed to update solutions in the algorithm. Updation of a solution by an employed bee or by an onlooker bee is done by a randomly selected rule from the rule set using Roulette Wheel selection process. In the scout bee phase of the algorithm, the perturbation technique, K-opt operation is applied on any stagnant solution for a fixed number of times for the possible improvement of it. The K-opt operation is again used at the end of the search process to improve the quality of the final solution (if possible). Proposed method is tested with a set of benchmark test problems from TSPLIB and it is observed that the efficiency of the algorithm is adequate with respect to the accuracy and the consistency for solving standard TSPs (Symmetric as well as Asymmetric) compared to the existing algorithms in the literature.