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

• -

GEZGİN SATICI PROBLEMİNİ ÇÖZMEK İÇİN YENİ BİR HİBRİD SEZGİSEL ALGORİTMA

Öz

Anahtar Kelimeler

• Gezgin satıcı problemi, Hibrid sezgisel algoritma, Yakın komşu algoritması, Açgözlü algoritma

Kaynakça

1. Climer, S., Zhang, W. (2006). Rearrangement Clustering: Pitfalls, Remedies, and Applications. Journal of Machine Learning Research, 7, 919 – 943.
2. Gutin, G., Punnen, A. (eds.). (2002). The Traveling Salesman Problem and Its Variations. Vol. 12 of Combinatorial Optimization. Kluwer, Dordrecht.
3. Held, M., Karp, R. (1962). A Dynamic Programming Approach to Sequencing Problems. Journal of SIAM, 10, 196 – 210.
4. 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.
5. Johnson, D., Papadimitriou, C. (1985a). Computational Complexity. In Lawler et al, Chapter 3, 37- 86.
6. Johnson, D., Papadimitriou, C. (1985b). Performance Guarantees for Heuristics. In Lawler et al, Chapter 5,145-180.
7. 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.
8. Johnson, O., Liu, J. (2006). A Traveling Salesman Approach for Predicting Protein Functions. Source Code for Biology and Medicine, 1(3), 1-7.

9. Land, A., Doig, A. (1960). An Automatic Method for Solving Discrete Programming Problems. Econometrica, 28, 497-520.
10. 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.
11. Lenstra, J. K. (1974). Clustering a Data Array and The Traveling-Salesman Problem. Operations Research, 22(2), 413-414.
12. Lin, S., Kernighan, B. (1973). An Effective Heuristic Algorithm for The Traveling-Salesman Problem. Operations Research, 21(2), 498-516.
13. Ray, S. S., Bandyopadhyay, S., Pal, S. K. (2007). Gene Ordering in Partitive Clustering using Microar- ray Expressions. Journal of Biosciences, 32(5), 1019-1025.
14. Rego, C., Glover, F. (2002). Local Search and Metaheuristics. In Gutin and Punnen (2002), Chapter 8, 309-368.
15. Reinelt, G. (1994). The Traveling Salesman: Computational Solutions for TSP Applications. Springer- Verlag, Germany.
16. http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/tsp/