Improved Genetic and Simulating Annealing Algorithms to Solve the Traveling Salesman Problem Using Constraint Programming
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 ReductionDownloads
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
License
Authors who publish with this journal agree to the following terms:
- Authors retain the copyright and grant the journal the right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) after its publication in ETASR with an acknowledgement of its initial publication in this journal.
