Open AccessImproved Genetic and Simulating Annealing Algorithms to Solve the Traveling Salesman Problem Using Constraint Programming
Author(s) -
M. Abdul-Niby,
Mamoon Alameen,
Ayad Salhieh,
Ahmed Radhi
Publication year - 2016
Publication title -
engineering, technology and applied science research/engineering, technology and applied science research
Language(s) - English
Resource type - Journals
eISSN - 2241-4487
pISSN - 1792-8036
DOI - 10.48084/etasr.627
Subject(s) - travelling salesman problem , simulated annealing , heuristics , mathematical optimization , computer science , 2 opt , reduction (mathematics) , computation , heuristic , genetic algorithm , algorithm , domain (mathematical analysis) , constraint (computer aided design) , integer programming , bottleneck traveling salesman problem , genetic programming , mathematics , artificial intelligence , mathematical analysis , geometry
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.