Improved Genetic and Simulating Annealing Algorithms to Solve the Traveling Salesman Problem Using Constraint Programming

Authors

  • M. Abdul-Niby Department of Engineering, The Australian College of Kuwait, Kuwait
  • M. Alameen Department of Engineering, The Australian College of Kuwait, Kuwait
  • A. Salhieh Department of Engineering, The Australian College of Kuwait, Kuwait
  • A. Radhi Bahbahani Projects, Kuwait city, Kuwait

Abstract

The Traveling Salesman Problem (TSP) is an integer programming problem that falls into the category of NP-Hard problems. As the problem become larger, there is no guarantee that optimal tours will be found within reasonable computation time. Heuristics techniques, like genetic algorithm and simulating annealing, can solve TSP instances with different levels of accuracy. Choosing which algorithm to use in order to get a best solution is still considered as a hard choice. This paper suggests domain reduction as a tool to be combined with any meta-heuristic so that the obtained results will be almost the same. The hybrid approach of combining domain reduction with any meta-heuristic encountered the challenge of choosing an algorithm that matches the TSP instance in order to get the best results.

Keywords:

Traveling Salesman Problem, Genetic Algorithm, Simulating Annealing, Domain Reduction

Downloads

Download data is not yet available.

References

G. Gutin, A. Yeo, A. Zverovich, “Traveling salesman should not be greedy: domination analysis of greedy-type heuristics for the TSP”, Discrete Applied Mathematics, Vol. 117, No. 1–3, pp. 81–86, 2002 DOI: https://doi.org/10.1016/S0166-218X(01)00195-0

C. H. Papadimitriou, “The Euclidean traveling salesman problem is NP-complete”, Theoretical Computer Science, Vol. 4, No. 3, pp. 237–244, 1977 DOI: https://doi.org/10.1016/0304-3975(77)90012-3

A. Corberán, M. Oswald, I. Plana, G. Reinelt, J. M. Sanchis, “New results on the Windy Postman Problem”, Mathematical Programming, Vol. 132, No. 1-2, pp. 309-332, 2012 DOI: https://doi.org/10.1007/s10107-010-0399-x

R. Martí, G. Reinelt, The Linear Ordering Problem. Exact and Heuristic Methods in Combinatorial Optimization, Springer, Heidelberg, 2011 DOI: https://doi.org/10.1007/978-3-642-16729-4_2

S. Kirkpatrick, C. D. Gelatt Jr, M. P. Vecchi, “Optimization by Simulated Annealing”, Science, Vol. 220, No. 4598, pp. 671–680, 1983 DOI: https://doi.org/10.1126/science.220.4598.671

L. M. Schmitt, “Theory of Genetic Algorithms”, Theoretical Computer Science, Vol. 259, No. 1–61, 2001 DOI: https://doi.org/10.1016/S0304-3975(00)00406-0

F. Benhamou, N. Jussien, B. O' Sullivan, Trends in constraint programming, John Wiley and Sons, 2007 DOI: https://doi.org/10.1002/9780470612309

Universität Heidelberg, TSPLIB, 2013 TSP data

Downloads

How to Cite

[1]
M. Abdul-Niby, M. Alameen, A. Salhieh, and A. Radhi, “Improved Genetic and Simulating Annealing Algorithms to Solve the Traveling Salesman Problem Using Constraint Programming”, Eng. Technol. Appl. Sci. Res., vol. 6, no. 2, pp. 927–930, Apr. 2016.

Metrics

Abstract Views: 452
PDF Downloads: 230

Metrics Information
Bookmark and Share

Most read articles by the same author(s)