The experimental results show that the new hybrid algorithm is more effective and efficient than both Greedy and Nearest Neighbor algorithms
📌 3 Key Takeaways
🎯
Objective & Hypothesis:The traveling salesman problem (TSP) is one of the typical NP–Hard problems of combinatorial optimization area.
📊
Key Findings & Data:This paper proposes a new hyper heuristic algorithm named Parametric Hybrid Method (PHM) based on The Farthest Vertex (FV) and Greedy heuristics for solving the traveling salesman problem.
💡
Conclusion & Impact:The experimental results show that the new hybrid algorithm is more effective and efficient than both Greedy and Nearest Neighbor algorithms
🔬Design:Modeling & Simulation
📍Scope:Comprehensive Sample
⚙️Variables:Domain Parameters
Abstract
The traveling salesman problem (TSP) is one of the typical NP–Hard problems of combinatorial optimization area. This paper proposes a new hyper heuristic algorithm named Parametric Hybrid Method (PHM) based on The Farthest Vertex (FV) and Greedy heuristics for solving the traveling salesman problem. In addition, many problem instances from TSPLIB (traveling salesman problem library) were solved with NN, Greedy and PHM algorithms. The experimental results show that the new hybrid algorithm is more effective and efficient than both Greedy and Nearest Neighbor algorithms
🔖
Cite This Article
KIZILATEŞ, G., NURİYEVA, F. (2013). A PARAMETRIC HYBRID METHOD FOR THE TRAVELING SALESMAN PROBLEM. Mathematical and Computational Applications, Cilt: 18 - Sayı: 3, 459–466. https://ajindex.com/articles/279821
D. L. Appligate, R. E. Bixby, V. Chavatal and W. J. Cook, The Traveling Salesman Problem, A Computational Study, Princeton Univesity Press, Princeton and Oxford, 2006
D. Davendra, Traveling Salesman Problem, Theory and Applications, In Tech, 2010
G. Gutin, A. Punnen (eds.), The Traveling Salesman Problem and Its Variations, volume 12 of Combinatorial Optimization, Kluwer, Dordrecht, 2002
L. J. Hubert, F. B. Baker, Applications of Combinatorial Programming to Data Analysis: The Traveling Salesman and Related Problems, Psychometrika 43(1), 81-91, 1978
D. Johnson, C. Papadimitriou (1985b), Performance guarantees for heuristics, In Lawler et al, chapter 5, 145-180, 1985
D. S. Johnson and L. A. McGeoch, The Traveling Salesman Problem: A Case Study, Local Search in Combinatorial Optimization, 215-310, John Wiley & Sons, 1997
E. L. Lawler, J. K. Lenstra, A. H. G. Rinnoy Kan, D. B. Shmoys, The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, John Wiley & Sons, 1986
J. Lenstra, A. R. Kan, Some simple applications of the traveling salesman problem, Operational Research Quarterly 26(4), 717-733, 1975
J. K. Lenstra, Clustering a Data Array and the Traveling-Salesman Problem, Operations Research 22(2), 413-414, 1974
S. Lin, B. Kernighan, An effective heuristic algorithm for the traveling-salesman problem, Operations Research 21(2), 498-516, 1973
F. Nuriyeva, New heuristic algorithms for traveling salesman problem, 25th Conference of European Chapter on Combinatorial Optimization, (ECCO XXV), Antalya, Turkey, April 26 – 28, 2012
F. Nuriyeva, G. Kizilates, M. E. Berberler, Experimental Analysis of New Heuristics for the TSP, IV International Conference “Problems of Cybernetics and Informatics” Baku, Azerbaijan, September 12 – 14, 2012
F. Nuriyeva, G. Kızılateş, A New Hyperheuristic Algorithm for Solving Traveling Salesman Problem, 2 nd World Conference on Soft Computing, p. 528-531 Baku, Azerbaijan, December 3-5, 2012
A. Punnen, The Traveling Salesman Problem: Applications, Formulations and Variations, In Gutin and Punnen (2002), chapter 1, p. 1-28, 2002
G. Reinelt, The Traveling Salesman: Computational Solutions for TSP Applications, Springer-Verlag, Germany, 1994
D. J. Rosenkrantz, R. E. Stearns, P. M. Lewis, An Analysis of Several Heuristics for the Traveling Salesman Problem, SIAM Journal on Computing 6, 563-581 (6.1). 17. http://comopt.ifi.uni-heidelberg.de/software/TSPLIB9