A Populated Iterated Greedy Algorithm with Inver-Over Operator for Traveling Salesman Problem

Abstract

In this study we propose a populated iterated greedy algorithm with an Inver-Over operator to solve the traveling salesman problem. The iterated greedy (IG) algorithm is mainly based on the central procedures of destruction and construction. The basic idea behind it is to remove some solution components from a current solution and reconstruct them in the partial solution to obtain the complete solution again. In this paper we apply this idea in a populated manner (IGP) to the traveling salesman problem (TSP). Since the destruction and construction procedure is computationally expensive we also propose an iteration jumping to an Inver-Over operator during the search process. We applied the proposed algorithm to the well-known 14 TSP instances from TSPLIB. The computational results show that the proposed algorithm is very competitive to the recent best performing algorithms from the literature.