Downloads: 136 | Views: 373
Research Paper | Computer Science & Engineering | India | Volume 3 Issue 7, July 2014 | Rating: 6.6 / 10
A Greedy Methodology to Solve Travelling Salesperson Problem Using Ant Colony Optimization
Wrishin Sarkar, Himadri Nath Saha, Arpita Ghosh
Abstract: Travelling Salesperson Problem is a problem where the user have to visit all the cities by using the shortest distance. It is an NP-hard problem in combinatorial optimization, important in operations research and theoretical computer science. TSP is a special case of the travelling purchaser problem. By representing this problem in graphical method we see that it is nothing but a complete graph where user have to visit all the nodes using the shortest distance. Scientist have found that biological ant have an excellent behavior by which they always choose the shortest way between the source and the destination although there are several ways between them. Using these behavior of the biological ant we describe an artificial ant colony capable of solving the traveling salesman problem (TSP). Ants of the artificial colony are able to generate successively shorter feasible tours by using information accumulated in the form of a pheromone trail deposited on the edges of the TSP graph. In this paper we have proposed a new greedy method by which TSP can be solved.
Keywords: Ant colony optimization, ant colony system, greedy function, TSP
Edition: Volume 3 Issue 7, July 2014,
Pages: 329 - 332