An Ant Colony Optimization approach to solve Travelling Salesman Problem

Abstract

Ant Colony Optimization algorithms (ACO) are meta-heuristic algorithms inspired from the cooperative behavior of real ants that could be used to achieve complex computations and have been proven to be very efficient to many different discrete optimization problems. One such problem is the Travelling Salesman Problem (TSP) which belongs to the class of NP-hard problems, which means that there is no exact algorithm to solve it in polynomial time. The importance of this problem appears in many application areas such as telecommunications, electronics, logistics, transportation, astronomy, industry and scheduling problem. Many algorithms had been proposed to solve TSP each with its own merits and demerits. In this paper, we propose a theoretical overview of TSP and ACO and also an implementation of how ACO can be used to solve TSP.