BibTex RIS Cite

A NEW HYBRID HEURISTIC ALGORITHM FOR SOLVING TSP

Year 2013, Volume: 2 Issue: 2, 143 - 148, 06.05.2015

Gözde Kızılateş Fidan Nuriyeva

Abstract

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

Keywords

-

References

  • 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.
  • Lenstra, J. K. (1974). Clustering a Data Array and The Traveling-Salesman Problem. Operations Research, 22(2), 413-414.
  • Lin, S., Kernighan, B. (1973). An Effective Heuristic Algorithm for The Traveling-Salesman Problem. Operations Research, 21(2), 498-516.
  • 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.
  • Rego, C., Glover, F. (2002). Local Search and Metaheuristics. In Gutin and Punnen (2002), Chapter 8, 309-368.
  • Reinelt, G. (1994). The Traveling Salesman: Computational Solutions for TSP Applications. Springer- Verlag, Germany.
  • http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/tsp/

Year 2013, Volume: 2 Issue: 2, 143 - 148, 06.05.2015

Gözde Kızılateş Fidan Nuriyeva

Abstract

References

  • 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.
  • Lenstra, J. K. (1974). Clustering a Data Array and The Traveling-Salesman Problem. Operations Research, 22(2), 413-414.
  • Lin, S., Kernighan, B. (1973). An Effective Heuristic Algorithm for The Traveling-Salesman Problem. Operations Research, 21(2), 498-516.
  • 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.
  • Rego, C., Glover, F. (2002). Local Search and Metaheuristics. In Gutin and Punnen (2002), Chapter 8, 309-368.
  • Reinelt, G. (1994). The Traveling Salesman: Computational Solutions for TSP Applications. Springer- Verlag, Germany.
  • http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/tsp/

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

Year 2013, Volume: 2 Issue: 2, 143 - 148, 06.05.2015

Gözde Kızılateş Fidan Nuriyeva

Abstract

Keywords

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

References

  • 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.
  • Lenstra, J. K. (1974). Clustering a Data Array and The Traveling-Salesman Problem. Operations Research, 22(2), 413-414.
  • Lin, S., Kernighan, B. (1973). An Effective Heuristic Algorithm for The Traveling-Salesman Problem. Operations Research, 21(2), 498-516.
  • 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.
  • Rego, C., Glover, F. (2002). Local Search and Metaheuristics. In Gutin and Punnen (2002), Chapter 8, 309-368.
  • Reinelt, G. (1994). The Traveling Salesman: Computational Solutions for TSP Applications. Springer- Verlag, Germany.
  • http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/tsp/
There are 16 citations in total.

Details

Primary Language English
Journal Section Articles
Authors

Gözde Kızılateş

Fidan Nuriyeva

Publication Date May 6, 2015
Published in Issue Year 2013 Volume: 2 Issue: 2

Cite

APA Kızılateş, G., & Nuriyeva, F. (2015). A NEW HYBRID HEURISTIC ALGORITHM FOR SOLVING TSP. Anadolu University Journal of Science and Technology B - Theoretical Sciences, 2(2), 143-148.
AMA Kızılateş G, Nuriyeva F. A NEW HYBRID HEURISTIC ALGORITHM FOR SOLVING TSP. AUBTD-B. May 2015;2(2):143-148.
Chicago Kızılateş, Gözde, and Fidan Nuriyeva. “A NEW HYBRID HEURISTIC ALGORITHM FOR SOLVING TSP”. Anadolu University Journal of Science and Technology B - Theoretical Sciences 2, no. 2 (May 2015): 143-48.
EndNote Kızılateş G, Nuriyeva F (May 1, 2015) A NEW HYBRID HEURISTIC ALGORITHM FOR SOLVING TSP. Anadolu University Journal of Science and Technology B - Theoretical Sciences 2 2 143–148.
IEEE G. Kızılateş and F. Nuriyeva, “A NEW HYBRID HEURISTIC ALGORITHM FOR SOLVING TSP”, AUBTD-B, vol. 2, no. 2, pp. 143–148, 2015.
ISNAD Kızılateş, Gözde - Nuriyeva, Fidan. “A NEW HYBRID HEURISTIC ALGORITHM FOR SOLVING TSP”. Anadolu University Journal of Science and Technology B - Theoretical Sciences 2/2 (May 2015), 143-148.
JAMA Kızılateş G, Nuriyeva F. A NEW HYBRID HEURISTIC ALGORITHM FOR SOLVING TSP. AUBTD-B. 2015;2:143–148.
MLA Kızılateş, Gözde and Fidan Nuriyeva. “A NEW HYBRID HEURISTIC ALGORITHM FOR SOLVING TSP”. Anadolu University Journal of Science and Technology B - Theoretical Sciences, vol. 2, no. 2, 2015, pp. 143-8.
Vancouver Kızılateş G, Nuriyeva F. A NEW HYBRID HEURISTIC ALGORITHM FOR SOLVING TSP. AUBTD-B. 2015;2(2):143-8.
 Download Cover Image