SavedAdd your journal

Journals / Mathematical and Computational Applications / 2009 / Cilt: 14 - Sayı: 3

Genetic algorithm based solution for TSP on a sphere

AYBARS UĞUR
MUSTAFA SERDAR KORUKOĞLU
ALİ ÇALIŞKAN
MUHAMMET GÖKHAN CİNSDİKİCİ
Ali ALP
Pages
219–228
DOI
—
🏛️Bibliographic metadata and full text access for this article are provided via DergiPark.
DergiPark Record ↗
✨

AI Summary & Key Takeaways

AI Insight
⚡ TL;DR(Too Long; Didn't Read)

A Java-based interactive visualization tool is also developed using Java 3D and optimization results obtained for different problem sizes are presented.

📌 3 Key Takeaways

🎯
Objective & Hypothesis:The Traveling Salesman Problem (TSP) is one of the extensively studied combinatorial optimization problems.
📊
Key Findings & Data:Various exact or approximation algorithms are devised for solving Euclidean TSP that determine the shortest route through a given set of points in 3-dimensional Euclidean space.
💡
Conclusion & Impact:A Java-based interactive visualization tool is also developed using Java 3D and optimization results obtained for different problem sizes are presented.
🔬Design:Modeling & Simulation
📍Scope:Comprehensive Sample
⚙️Variables:Domain Parameters

Abstract

The Traveling Salesman Problem (TSP) is one of the extensively studied combinatorial optimization problems. Various exact or approximation algorithms are devised for solving Euclidean TSP that determine the shortest route through a given set of points in 3-dimensional Euclidean space. In this paper, we proposed a genetic algorithm-based solution for TSP where all points are on the surface of a sphere. A Java-based interactive visualization tool is also developed using Java 3D and optimization results obtained for different problem sizes are presented.

🔖

Cite This Article

UĞUR, A., KORUKOĞLU, M. S., ÇALIŞKAN, A., CİNSDİKİCİ, M. G., ALP, A. (2009). Genetic algorithm based solution for TSP on a sphere. Mathematical and Computational Applications, Cilt: 14 - Sayı: 3, 219–228. https://ajindex.com/articles/280045

📄 Full Text PDF Viewer

📄

PDF görüntüleyici hazırlanıyor...

References (17)

  1. S. Arora, Polynomial time approximation schemes for Euclidean TSP and other geometric problems, Proc. 37th Ann. Symp. Foundations of Computer Sci., IEEE Computer Soc., 2–11, 1996
  2. Wikipedia, The Free Encyclopedia, http://en.wikipedia.org/wiki/Main_Page, 2006
  3. L.M. Gambardella and M. Dorigo, Solving Symmetric and Asymmetric TSPs by Ant Colonies, International Conference on Evolutionary Computation, 622-627, 1996
  4. K. Shinozawa, T. Uchiyama and K. Shimohara, An approach for solving dynamic TSPs using neural networks, Neural Networks, IEEE International Joint Conference 3, 2450-2454, 1991
  5. Y. Tsujimura, M. Gen, Entropy-based genetic algorithm for solving TSP, Knowledge-Based Intelligent Electronic Systems 2, 285-290, 1998
  6. D.S. Johnson and L.A. McGeoch, The traveling salesman problem: A case study in local optimization, In E. H. L. Aarts and J. K. Lenstra, editors, Local Search in Combinatorial Optimization, John Wiley & Sons, New York, 215–310, 1997
  7. T. A. Feo and M. G. C. Resende, Greedy randomized adaptive search procedure, Journal of Global Optimization 6, 109–133, 1995
  8. Y. Marinakis, A. Migdalas, P. M. Pardalos, Expanding neighborhood GRASP for the traveling salesman problem, Computational Optimization and Applications 32 (3), 231-257, 2005
  9. Z. J. Lee, A hybrid algorithm applied to travelling salesman problem, Networking, Sensing and Control, IEEE International Conference 1, 237-242, 2004
  10. C. M. White and G. G. Yen, A hybrid evolutionary algorithm for traveling salesman problem, Congress on Evolutionary Computation (CEC2004) 2, 1473- 1478, 2004
  11. Y. Marinakis, A. Migdalas and P. M. Pardalos, A Hybrid Genetic-GRASP Algorithm Using Lagrangean Relaxation for the Traveling Salesman Problem, J. Comb. Optim. 10(4), 311-326, 2005
  12. S. Takahashi, K. Fujimura and H. Tokutaka, The SOM-TSP method for the three-dimension city location problem, Neural Information Processing 5, 2552- 2555, 2002
  13. H. Sengoku and I. Yoshigara, A Fast TSP Solver Using GA on Java, Third International Symposium on Artificial Life, and Robotics (AROB III’98), 1998
  14. S. Lin, Computer solutions of the traveling salesman problem, Bell Systems Journal 44, 2245–2269, 1965
  15. A. Uğur, Path Planning On A Cuboid Using Genetic Algorithms, Information Sciences 178, 3275-3287, 2008
  16. D. Hearn and M.P. Baker, Computer Graphics with OpenGL, 3rd Edition, Prentice Hall, 2004
  17. Z. Pan, J. Zhu, W. Hu, H. P. Lun and X. Zhou, Interactive learning of CG in netw