Call for Paper - January 2023 Edition
IJCA solicits original research papers for the January 2023 Edition. Last date of manuscript submission is December 20, 2022. Read More

Parallel Computing Approach to Solve Travelling Salesman Problem

Print
PDF
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Year of Publication: 2017
Authors:
Harshala C. Ingole, Vivek B. Kute
10.5120/ijca2017912780

Harshala C Ingole and Vivek B Kute. Parallel Computing Approach to Solve Travelling Salesman Problem. International Journal of Computer Applications 157(7):47-51, January 2017. BibTeX

@article{10.5120/ijca2017912780,
	author = {Harshala C. Ingole and Vivek B. Kute},
	title = {Parallel Computing Approach to Solve Travelling Salesman Problem},
	journal = {International Journal of Computer Applications},
	issue_date = {January 2017},
	volume = {157},
	number = {7},
	month = {Jan},
	year = {2017},
	issn = {0975-8887},
	pages = {47-51},
	numpages = {5},
	url = {http://www.ijcaonline.org/archives/volume157/number7/26847-2017912780},
	doi = {10.5120/ijca2017912780},
	publisher = {Foundation of Computer Science (FCS), NY, USA},
	address = {New York, USA}
}

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

  1. 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.
  2. 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.
  3. 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.
  4. Klaus Meer, “Simulated Annealing versus Metropolis for a TSP instance”, in Information Processing Letters, vol.104, 2007, pp. 216- 219.
  5. Thomas H.Cormen,Charles E. Leiserson,Ronald L. Rivest,Clifford SteinIntroduction To Algorithms (3rd Edition).
  6. 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
  7. 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.
  8. 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.
  9. 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.
  10. 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.
  11. Yongsheng Pan, Yong Xia* “Solving TSP by Dismantling Cross Paths” 2014 IEEE International Conference on Orange Technologies (ICOT).

Keywords

Travelling Salesman Problem, Branch and Bound Algorithm, Parallel Computing