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

M. Abdul-Niby, M. Alameen, A. Salhieh, A. Radhi

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

Full Text:

PDF

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

C. H. Papadimitriou, “The Euclidean traveling salesman problem is NP-complete”, Theoretical Computer Science, Vol. 4, No. 3, pp. 237–244, 1977

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

R. Martí, G. Reinelt, The Linear Ordering Problem. Exact and Heuristic Methods in Combinatorial Optimization, Springer, Heidelberg, 2011

S. Kirkpatrick, C. D. Gelatt Jr, M. P. Vecchi, “Optimization by Simulated Annealing”, Science, Vol. 220, No. 4598, pp. 671–680, 1983

L. M. Schmitt, “Theory of Genetic Algorithms”, Theoretical Computer Science, Vol. 259, No. 1–61, 2001

F. Benhamou, N. Jussien, B. O' Sullivan, Trends in constraint programming, John Wiley and Sons, 2007

Universität Heidelberg, TSPLIB, 2013 TSP data




eISSN: 1792-8036     pISSN: 2241-4487