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 heuristic method by which TSP can be solved.

 

Published In : IJCSN Journal Volume 3, Issue 3

Date of Publication : 01 June 2014

Pages : 132 - 137

Figures :02

Tables : 06

Publication Link : Advanced Heuristic Technique for Solving Travelling Salesperson Problem Using Ant Colony Optimization

 

 

 

Wrishin Sarkar : Computer Science & Engineering, West Bengal University Of Technology Kolkata, West Bengal, India

Himadri Nath Saha : Computer Science & Engineering, West Bengal University Of Technology Kolkata, West Bengal, India

Sourav Kumar Dhar : School Of Mobile Computing & Communication, Jadavpur University Kolkata, West Bengal, India

Sandipan Roy : Software Engineering, Jadavpur University Kolkata, West Bengal, India

 

 

 

 

 

 

 

Ant colony optimization

ant colony system

heuristic function

TSP

From above result it is clear that in each iteration the path that has been traversed by most of the ants is consider as the best solution(local) for that colony but then its path length is compared and checked that whether it is shorter than the previous global best solution or not .

 

 

 

 

 

 

 

 

 

[1] R. Wankar, Grid computing with Globus: An overview and research challenges,International Journal ComputerScience and Applications, vol. 5(3), 2008,pp. 56-69.

[2] F. Magoules, J. Pan, K. A. Tan andA. Kumar, Introduction to grid computing. Boca Raton, FL: Taylor & Francis Group, 2009

[3] S.C.Lin, and E.Yen, Grid Computing(International Symposium on Grid Computing. New York, USA: Springer, 2009.