An iterated local search for the travelling salesman problem
Abstract
The Traveling Salesman Problem is a classical problem in Computer Science, with many extensions and variations being studied along decades of research, particularly for applications related to logistics. Here, we present a Iterated Local Search (ILS) algorithm to find solutions for instances of the problem as proposed by The Brazilian competition on Knowledge Discovery in Databases (KDD-BR). The ILS algorithm is a simple algorithm that does not depend on any third-party libraries. Also, it was among most effective methods in the competition.
Keywords:
Iterated Local Search algorithm, TSP problem, meta-heuristics
References
Applegate, D. L., Bixby, R. E., Chvátal, V., and Cook, W. J. (2011). The traveling salesman problem. Princeton university press.
Imamichi, T., Yagiura, M., and Nagamochi, H. (2009). An iterated local search algorithm based on nonlinear programming for the irregular strip packing problem. Discrete Optimization, 6:345–361.
Ishaya, J., Ibrahim, A., and Lo, N. (2019). A comparative analysis of the travelling salesman problem: Exact and machine learning techniques. Open Journal of Discrete Applied Mathematics, 2:23–37.
Joshi, C. K., Laurent, T., and Bresson, X. (2019). An efficient graph convolutional network technique for the travelling salesman problem. arXiv preprint arXiv:1906.01227.
Lourenço, H. R., Martin, O. C., and Stützle, T. (2019). Iterated local search: Framework and applications. In Handbook of metaheuristics, pages 129–168. Springer.
Penna, P. H. V., Subramanian, A., and Ochi, L. S. (2013). An iterated local search heuristic for the heterogeneous fleet vehicle routing problem. Journal of Heuristics, 19:201– 232.
Song, T., Liu, S., Tang, X., Peng, X., and Chen, M. (2018). An iterated local search algorithm for the university course timetabling problem. Applied Soft Computing, 68:597–608.
Stützle, T. and Hoos, H. H. (2002). Analysing the run-time behaviour of iterated local search for the travelling salesman problem. In Essays and Surveys in Metaheuristics, pages 589–611. Springer.
Tinós, R., Helsgaun, K., and Whitley, D. (2018). Efficient recombination in the lin- kernighan-helsgaun traveling salesman heuristic. In International Conference on Parallel Problem Solving from Nature, pages 95–107. Springer.
Vansteenwegen, P., Souffriau, W., Berghe, G. V., and Van Oudheusden, D. (2009). Iterated local search for the team orienteering problem with time windows. Computers & Operations Research, 36:3281–3290.
Vitali, T., Mele, U. J., Gambardella, L. M., and Montemanni, R. (2021). Machine learning constructives and local searches for the travelling salesman problem. arXiv preprint arXiv:2108.00938.
Imamichi, T., Yagiura, M., and Nagamochi, H. (2009). An iterated local search algorithm based on nonlinear programming for the irregular strip packing problem. Discrete Optimization, 6:345–361.
Ishaya, J., Ibrahim, A., and Lo, N. (2019). A comparative analysis of the travelling salesman problem: Exact and machine learning techniques. Open Journal of Discrete Applied Mathematics, 2:23–37.
Joshi, C. K., Laurent, T., and Bresson, X. (2019). An efficient graph convolutional network technique for the travelling salesman problem. arXiv preprint arXiv:1906.01227.
Lourenço, H. R., Martin, O. C., and Stützle, T. (2019). Iterated local search: Framework and applications. In Handbook of metaheuristics, pages 129–168. Springer.
Penna, P. H. V., Subramanian, A., and Ochi, L. S. (2013). An iterated local search heuristic for the heterogeneous fleet vehicle routing problem. Journal of Heuristics, 19:201– 232.
Song, T., Liu, S., Tang, X., Peng, X., and Chen, M. (2018). An iterated local search algorithm for the university course timetabling problem. Applied Soft Computing, 68:597–608.
Stützle, T. and Hoos, H. H. (2002). Analysing the run-time behaviour of iterated local search for the travelling salesman problem. In Essays and Surveys in Metaheuristics, pages 589–611. Springer.
Tinós, R., Helsgaun, K., and Whitley, D. (2018). Efficient recombination in the lin- kernighan-helsgaun traveling salesman heuristic. In International Conference on Parallel Problem Solving from Nature, pages 95–107. Springer.
Vansteenwegen, P., Souffriau, W., Berghe, G. V., and Van Oudheusden, D. (2009). Iterated local search for the team orienteering problem with time windows. Computers & Operations Research, 36:3281–3290.
Vitali, T., Mele, U. J., Gambardella, L. M., and Montemanni, R. (2021). Machine learning constructives and local searches for the travelling salesman problem. arXiv preprint arXiv:2108.00938.
Published
2021-11-29
How to Cite
CASTELLUCCI, Pedro B..
An iterated local search for the travelling salesman problem. In: NATIONAL MEETING ON ARTIFICIAL AND COMPUTATIONAL INTELLIGENCE (ENIAC), 18. , 2021, Evento Online.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2021
.
p. 795-798.
ISSN 2763-9061.
DOI: https://doi.org/10.5753/eniac.2021.18427.
