International Research Journal of Innovations in Engineering and Technology - IRJIET International Open Access, Monthly, Peer Reviewed, Reputed Journal ISSN (online): 2581-3048

Impact Factor (2025): 6.9

DOI Prefix: 10.47001/IRJIET

Travelling Salesman Problem: A Review on Optimization Techniques and Genetic Algorithm

Abstract

The Travelling Salesman Problem (TSP) is an optimization problem which might look simple to understand but faces difficulty in precise calculation. Solving TSP includes an imaginary salesman who finds the most efficient path sequence from the starting location and covers the entire destination by stopping only once at each destination. Several techniques to solve TSP have been proposed by many scholars like, Genetic Algorithm (GA), Particle Swarm Optimization (PSO), Ant Colony Optimization Algorithm (ACO), and Bacteria forging etc. that work on the principle of survival of the fittest. Similarly, various heuristics algorithm, stochastic approach, fuzzy conditions are set up to solve TSP. This paper deals with review on different techniques or group of techniques that are used by several researchers in order to have optimized path solution using various languages and software like java, Python MATLAB etc.

Country : India

1 Miss. Priti Vilas Jadhav2 Dr. S. M. Badave

  1. M. Tech (EDC), MIT Aurangabad, (MS), India 431001
  2. Professor, Department of Electrical Engineering, MIT Aurangabad (MS), India 431001

IRJIET, Volume 4, Issue 6, June 2020 pp. 41-46

doi.org/10.47001/IRJIET/2020.406005

Full Paper
Download

References

  1. Biggs N. L.; Lloyd E. Keith & Wilson Robin J. (1986). “Graph Theory 1736-1936”, Clarendon Press, Oxford, ISBN 978-0-19-853916-2.
  2. S. Kim and I. Moon, “Traveling salesman problem with a drone station”, IEEE Trans. Syst., Man, Cybern. Syst., vol. 49, no. 1, pp. 42–52, May 2019.
  3. Jerome Le Ny, Eric Feron, Emilio Frazzoli, Member, ‘‘On the Dubins Traveling Salesman Problem,” IEEE Trans. Autom. Control, vol. 57, no. 1, Jan. 2012, pp. 265-270.
  4. Neil Mathew, Stephen L. Smith, Senior Member, Steven L. Waslander, “Planning Paths for Package Delivery in Heterogeneous Multirobot Teams,” IEEE Transactions on Automation Science and Engineering, vol. 12, no. 4, Oct. 2015, pp. 1298-1308.
  5. Q. M. Haa, D. Yves, D. P.Quang and H.H. Minh,“On the min cost Traveling Salesman Problem with Drone,” Transportation Research, pp. 597-621, 2018.
  6. W.P. Coutinho, M. Battarra, J. Fliege, “The unmanned aerial vehicle routing and trajectory optimisation problem, a taxonomic review,” Comput. Ind. Eng., vol. 120, pp. 116-128, 2018.
  7. L. Evers, K. Glorie, S. van der Ster, A.I. Barros, H. Monsuur, “A two stage approach to the orienteering problem with stochastic weights,” Comput. Oper. Res., vol. 43, pp. 248-260, 2014.
  8. Bifan Li, Lipo Wang & Wu Song “Ant Colony Optimization for the Traveling Salesman Problem Based On Ants with Memory” Fourth International Conference on Natural Computation (2009).
  9. L. Li, S. Ju, Y. Zhang, Improved Ant Colony Optimization for the Traveling Salesman Problem, International Conference on Intelligent Computation Technology and Automation, IEEE, 2008.
  10. Zar Chi Su SuHlaing and May Aye Khine, “Solving Traveling Salesman Problem by Using Improved Ant Colony Optimization Algorithm”, International Journal of Information and Education Technology, Vol. 1, No. 5, December 2011.
  11. Hingrajiya KH, Gupta RK, Chandel GS. “An Ant Colony Optimization Algorithm for Solving Traveling Salesman Problem” International Journal of Scientific and Research Publications. 2012; 2(8):1–6.
  12. J. Kennedy, R. Eberhart, “Particle Swarm Optimization,” IEEE International Conference on Neural Network, Perth, Australia, 27 Nov –1 Dec, vol. 4, pp. 1942-1948, 1995.
  13. X.H. Shi , Y.C. Liang, H.P. Lee, C. Lu, Q.X. Wang,” Particle swarm optimization-based algorithms for TSP and generalized TSP”, Information Processing Letters 103 (2007) 169–176,2007.
  14. Huilian FAN,” Discrete Particle Swarm Optimization for TSP based on Neighborhood”, Journal of Computational Information Systems 6:10 (2010) 3407-3414.
  15. Xuesong Yan, Can Zhang, WenjingLuo, Wei Li, Wei Chen and Hanmin Liu “Solve Traveling Salesman Problem Using Particle Swarm Optimization Algorithm” International Journal of Computer Science Issues, Vol. 9, Issue 6, No 2, November 2012.
  16. Chiung Moon, Jongsoo Kim, GyunghyunChoi ,YoonhoSeo,” An efficient genetic algorithm for the traveling salesman problem with precedence constraints”, European Journal of Operational Research 140 (2002) 606–617.
  17. Dwivedi, TarunaChauhan, SanuSaxena and PrincieAgrawal, “Travelling Salesman Problem using Genetic Algorithm”, International Journal of Computer Applications (IJCA), 2012, pp. 25-30.
  18. Kumar N, Karambir, Kumar R. “A Genetic algorithm approach to study Traveling salesman problem”, Journal of Global Research in Computer Science. 2012; 3(3):33–8.
  19. Gupta S, Panwar P. “Solving Traveling salesman problem using genetic algorithm”, International Journal of Advanced Research in Computer Science and Software Engineering (IJARCSSE). 2013; 3(6):376–80.

Copyright @ 2026-2017 IRJIET. All Right Reserved.

Developed by Byzero Technologies