A NEW HYBRID HEURISTIC ALGORITHM FOR SOLVING TSP
Öz
The Traveling Salesman Problem (TS P) is an important and well known combinatoriyal opti- mization problem. The goal of the problem is to find the shortest tour that visits each city in a given list exactly once and then returns to the starting city. Although the definition of the travelling salesman problem is easy, it belongs to NP-Hard class. In this paper, a new hybrid heurist ic algorithm based on Nearest Neighbour (NN) and Greedy heur istic algorithms is proposed for s olving the TSP. This proposed hybrid heuristic algorithm is compared with NN and Greedy heuristi cs. The experimental results show that the proposed algorithm is efficient
Anahtar Kelimeler
Kaynakça
- Climer, S., Zhang, W. (2006). Rearrangement Clustering: Pitfalls, Remedies, and Applications. Journal of Machine Learning Research, 7, 919 – 943.
- Gutin, G., Punnen, A. (eds.). (2002). The Traveling Salesman Problem and Its Variations. Vol. 12 of Combinatorial Optimization. Kluwer, Dordrecht.
- Held, M., Karp, R. (1962). A Dynamic Programming Approach to Sequencing Problems. Journal of SIAM, 10, 196 – 210.
- Hubert, L. J., Baker, F. B. (1978). Applications of Combinatorial Programming to Data Analysis: The Traveling Salesman and Related Problems. Psychometrika, 43(1), 81-91.
- Johnson, D., Papadimitriou, C. (1985a). Computational Complexity. In Lawler et al, Chapter 3, 37- 86.
- Johnson, D., Papadimitriou, C. (1985b). Performance Guarantees for Heuristics. In Lawler et al, Chapter 5,145-180.
- Johnson, D. S. and McGeoch, L. A. (1997). “The Traveling Salesman Problem: A Case Study”, Local Search in Combinatorial Optimization, 215-310, John Wiley & Sons.
- Johnson, O., Liu, J. (2006). A Traveling Salesman Approach for Predicting Protein Functions. Source Code for Biology and Medicine, 1(3), 1-7.
- Land, A., Doig, A. (1960). An Automatic Method for Solving Discrete Programming Problems. Econometrica, 28, 497-520.
- Lawler, E. L., Lenstra, J. K., Rinnoy, Kan A. H. G., Shmoys D. B. (1986). The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, John Wiley & Sons.