The week's pick
Random Articles
Reseach Article
Parallel Computing Approach to Solve Travelling Salesman Problem
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 157 - Number 7 |
| Year of Publication: 2017 |
| Authors: Harshala C. Ingole, Vivek B. Kute |
10.5120/ijca2017912780
|
Harshala C. Ingole, Vivek B. Kute . Parallel Computing Approach to Solve Travelling Salesman Problem. International Journal of Computer Applications. 157, 7 ( Jan 2017), 47-51. DOI=10.5120/ijca2017912780
Abstract
Travelling Salesman Problem (TSP) is eminent in combinatorial optimization problem. A typical problem in computational mathematics, scientific and business application such as VLSI chip design, social network analysis. TSP, combinatorial optimization problem belongs to the class of NP-Hard, and becomes significant method of verifying the correctness and feasibility of new algorithm. With the accuracy results and efficient cutting branch strategy of branch and bound algorithm, it used to solve TSP. However, branch and bound algorithm not suitable for large scale TSP with sequential execution. In this paper parallel branch and bound algorithm has been improved and proposed to solve the symmetric TSP. This paper uses parallel program code based on multithreading concept to verify TSP. The experimental result shows our algorithm is efficient, and solves the large scale TSP problem which cannot be solved by sequential branch and bound.
References
- Anshul Singh, Devesh narayan “A Survey Paper on Solving Travelling Salesman problem Using Bee colony optimization” International Journal of Emerging Technology and Advanced Engineering Website: www.ijetae.com (ISSN 2250-2459, Volume 2, Issue 5, May 2012). Tavel, P. 2007 Modeling and Simulation Design. AK Peters Ltd.
- Anitha Rao, Sandeep Kumar Hegde “Literature Survey On Travelling Salesman Problem” International Journal of Advance Research in Eduation Technology (IJARET) 42 Vol. 2, Issue 1 (Jan. - Mar. 2015) Using Genetic Algorithms.
- Kai Ma, Jiong Zhang “An Efficient Multicore based Parallel ComputingApproach for TSP Problems” 978-1-4799-3012-8/14 $31.00 © 2014 IEEEDOI 10.1109/SKG.2013.41.
- Klaus Meer, “Simulated Annealing versus Metropolis for a TSP instance”, in Information Processing Letters, vol.104, 2007, pp. 216- 219.
- Thomas H.Cormen,Charles E. Leiserson,Ronald L. Rivest,Clifford SteinIntroduction To Algorithms (3rd Edition).
- M MostaFizur Rahman,Muhammad Foizul Islam Chowdhury, “Examining Branch and Bound Strategy on Multiprocessor Task Scheduling” 12th International Conference on Computers and Information Technology 2009
- Mario Rossainz Lopez Manuel , Capel Tunon “Design and Use of the CPAN Branch and Bound For The Solution Of Travelling Salesman Problem (TSP)” Proceedings 19th European conference On Modelling and Simulation Yuri Merkuryev,Richard Zobel,Eugene Kerckhoffs 2005 ISBN 1-84233-112-4.
- Laleh Haerian Ardekani, Tiru S. Arthanari, Matthias Ehrgott, “Performance of the Branch and Bound Algorithm on the Multistage Insertion Formulation of the Traveling Salesman Problem”, Proceedings of the 45th Annual Conference of the ORSNZ, November 2010, pp. 326-335.
- Paulo Henrique Siqueira, Maria Teresinha Arns Steiner, Sergio Scheer, “Anew approach to solve the traveling salesman problem” in Neurocomputing, vol, 70, 2007, pp. 1013-1021.
- PHAM Dinh Thanh, HUYNH Thi Thanh Binh, BUI Thu Lam “A Surveon Hybridizing Genetic Algorithm with Dynamic Programming forSolving the Traveling Salesman Problem” International Conference ofSoft Computing and Pattern Recognition (SoCPaR), 2013.
- Yongsheng Pan, Yong Xia* “Solving TSP by Dismantling Cross Paths” 2014 IEEE International Conference on Orange Technologies (ICOT).
Index Terms
Keywords