Travelling Salesman Problem using Bee Colony with SPV
Nishant Pathak1, Sudhanshu Prakash Tiwari2
1Nishant Pathak, Lovely Professional University Phagwara, Punjab
2Sudhanshu Prakash Tiwari Lovely Professional University Phagwara, Punjab.
Manuscript received on July 01, 2012. | Revised Manuscript received on July 04, 2012. | Manuscript published on July 05, 2012. | PP: 410-414 | Volume-2, Issue-3, July 2012. | Retrieval Number: C0716052312 /2012©BEIESP
Open Access | Ethics and Policies | Cite
© The Authors. Published By: Blue Eyes Intelligence Engineering and Sciences Publication (BEIESP). This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/)
Abstract: Challenge of finding the shortest route visiting each member of a collection of locations and returning to starting point is an NP-hard problem. It is also known as Traveling salesman problem, TSP is specific problem of combinatorial optimization studied in computer science and mathematical applications. In our work we present a solution for TSP problem using ABC with SPV rule. In this method we extend Artificial Bee Colony algorithm using SPV rule. Artificial bee colony algorithm solves real coded optimization problems but travelling salesman problem is a discrete optimization problem for converting the ABC algorithm to solve TSP problem SPV rule is used. Artificial Bee Colony (ABC) is an optimization algorithm based on the intelligent behavior of honey bee swarm. In the proposed method we extend ABC with SPV rule for local search strategy. The experimental results show that our proposed ABC with SPV performs better than GA (Genetic Algorithm), our ABC with SPV model can reach broader domains in the search space and show improvements in both precision and computational time.
Keywords: ABC, Artificial Bee Colony, GA, Genetic Algorithm, TSP, SPV.