Ant Colony Optimization For Solving Travelling Salesman Problem- Final Year Project Report (CSC-404) 

Abstract

The travelling salesman problem is one of the most important combinatorial problems
and a NP-hard problem whose challenge is to complete Hamilton circle selecting the
shortest path without leaving any cities behind.
Nature is the solution to every problem and creatures are the actor. In ant colony, real
ants are able to create successively shorter feasible tours to their food, by using
information accumulated in the form of a pheromone trail deposited on their path. The
intelligence of the colony arises from indirect communication between individual ants
through pheromones in getting food with shorter path. ACO is a heuristic algorithm
which has been proven a successful technique and applied to a number of combinatorial
optimization problems where real ants are represented by the artificial ant. These
artificial ants are placed at random points, which spread pheromone on their travelling
route and with use of information of pheromone on their path, they find the shortest
path.
Among different algorithms of ACO, Ant System and Ant Colony System are the most
used algorithm in solving TSP, which uses probability calculation and global
pheromone update. Here in our project also we researched on the ACO, and adopt it to
solve the TSP problem. The simulation results show how this ACO algorithm is able
to solve TSP with varying city numbers.
We have selected the C# as programming language and Visual Studio as our platform
and for designing the application of our project. For user friendly, we have designed
the graphical user interface that can take input either map image or the manual input of
the nodes. User can enter the required parameter value as desired and save the generated
output either on local directory. Our project’s application can be used to determine the
optimal path for the other development project like road construction, water
distribution, network routing, etc.