COMPREHENSIVE STUDY OF ANT COLONIES FOR THE TRAVELING SALESMAN PROBLEM AND COMPARE EFFICIENCY AND PERFORMANCE WITH BASIC ALGORITHM
The travelling salesman problem (TSP) is an NP hard problem in combinatorial optimization studied in operations research and theoretical computer science. Given a list of cities and their pair wise distances, the task is to find the shortest possible tour that visits each city exactly once. It is used as a benchmark for many optimization methods. Even though the problem is computationally difficult, a large number of heuristics and exact methods are known, so that some instances with tens of thousands of cities can be solved. The TSP has several applications even in its purest formulation, such as planning, logistics, and the manufacture of microchips. The ant colony optimization is a probabilistic technique for solving computational problems which can be reduced to finding good paths through graphs. In ACO, a set of software agents called artificial ants search for good solutions to a give optimization problem. The traveling salesman problem (TSP) is the problem of finding a shortest closed tour which visits all the cities in a given set. In this article we will restrict attention to TSPs in which cities are on a plane and a path (edge) exists between each pair of cities (i.e. the TSP graph is completely connected) Ant colony optimization is a metaheuristic in which a colony of artificial ants cooperates in finding good solutions to difficult discrete optimization problems.