A Hybrid Modified Meta-heuristic Algorithm for Solving the Traveling Salesman Problem

Abstract

The traveling salesman problem (TSP) is one of the most important combinational optimization problems that have nowadays received much attention because of its practical applications in industrial and service problems. In this paper, a hybrid two-phase meta-heuristic algorithm called MACSGA used for solving the TSP is presented. At the first stage, the TSP is solved by the modified ant colony system (MACS) in each iteration, and at the second stage, the modified genetic algorithm (GA) and 2-opt local search are used for improving the solutions of the ants for that iteration. This process avoids the premature convergence and makes better solutions. Computational results on several standard instances of TSP show the efficiency of the proposed algorithm compared with the GA, ant colony optimization and other meta-heuristic algorithms.