Total views : 181

Solving Travelling Salesman Problem Using Improved Genetic Algorithm

Affiliations

  • Department of Computer Science, Swami Keshvan Institute of Technology, Management and Gramothan, Ramnagaria, Jagatpura, Jaipur – 302017, Rajasthan, India

Abstract


Objectives: Travelling Salesman Problem is a well known NP-Complete problem. It has many application areas in science and engineering. NP-Complete problems are most difficult problems in computer science. Methods/Statistical Analysis: These problems are not solvable using tradition algorithms till date. Soft computing techniques such as Genetic Algorithm (GA) can be used to solve such problems. In this paper Travelling Salesman problem has been solved using Genetic Algorithm. The proposed algorithm modifies the traditional genetic algorithm. Proposed algorithm generates some chromosome using greedy approach and adds these chromosomes in initial population. It also proposes a new greedy cross over operator for genetic algorithm. Findings: The implementation results of proposed algorithm prove that proposed algorithm performs better as it find out paths of less path length as compared to the optimal path known till date. Application/Improvements: This work is helpful in finding optimal or near optimal solutions of TSP. The algorithm can find application in all the relevant areas of science and engineering where TSP is used such as robot arm movement, drilling electronic boards etc.

Keywords

Travelling Salesman Problem, Genetic Algorithm, Crossover, NP-Complete Problems

Full Text:

 |  (PDF views: 131)

References


  • Wikipedia. Travelling salesman problem [Internet]. 2015 [updated 2017 Jun 2; cited 2015 Jul 1]. Available from: Crossref.
  • Wikipedia. NP-completeness [Internet]. 2015 [updated 2017 May 10; cited 2015 Jul 15]. Available from: Crossref.
  • Dwivedi V, Chauhan T, Saxena S, Agrawal P. Travelling salesman problem using genetic algorithm. In the Proceedings of the National Conference on Development of Reliable Information Systems, Techniques and Related Issues; 2012. p. 25–30.
  • Wikipedia. Genetic algorithm [Internet]. 2015 [updated 2017 Apr 10; cited 2015 Jul 15]. Available from: Crossref.
  • Mi M, Huifeng X, Ming Z, Yu G. An improved differential evolution algorithm for TSP problem. In the Proceedings of the Institute of Electrical and Electronics Engineers (IEEE) International Conference on Intelligent Computation Technology and Automation. 2010 May 11–12; 1:544–7.Crossref.
  • Gupta S, Panwar P. Solving travelling salesman problem using genetic algorithm. International Journal of Advanced Research in Computer Science and Software Engineering.2013 Jun; 3(6):376–80.
  • Maity S, Roy A, Maity M. A modified genetic algorithm for solving uncertain constrained solid travelling salesman problems. Computers and Industrial Engineering, Elsevier, ScienceDirect. 2015 May; 83:273–96. Crossref.
  • Ahmed ZH. Genetic Algorithm for the travelling salesman problem using sequential constructive crossover operator.International Journal of Biometrics and Bioinformatics (IJBB). 2010 Jan; 3(6):96–105.
  • Sathyan A, Boone N, Cohen K. Comparison of approximate approaches to solving the travelling salesman problem and its application to UAV swarming. International Journal of Unmanned Systems Engineering. 2015 Jan; 3(1):1–16.Crossref.
  • Vahdati G, Ghouchani SY, Yaghoobi M. A hybrid Search Algorithm with Hopfield Neural Network and GeneticAlgorithm for Solving Traveling Salesman Problem. In the Proceedings of the Institute of Electrical and Electronics Engineers (IEEE) 2nd International Conference on Computer and Automation Engineering (ICCAE). 2010 Feb 26–28; 1:435–9.
  • Jia H. A novel hybrid optimization algorithm and its application in solving complex problem. International Journal of Hybrid Information Technology. 2015; 8(2):1–10. Crossref.
  • Reinelt G.TSPLIB—A Travelling Salesman Problem Library. ORSA Journal on Computing. 1991 Nov 1; 3(4):376–84.

Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.