An iterated local search for the travelling salesman problem
Resumo
O Problema do Caixeiro Viajante é um problema clássico da Ciência da Computação, com muitas extensões e variações sendo estudadas ao longo de décadas de pesquisas, principalmente para aplicações relacionadas à logística. Aqui, apresentamos um algoritmo Iterated Local Search (ILS) para encontrar soluções para instâncias do problema proposto pela Competição Brasileira de Descoberta de Conhecimento em Bancos de Dados (KDD-BR). O algoritmo ILS é um algoritmo simples que não depende de nenhuma biblioteca de terceiros. Além disso, foi um dos métodos mais eficazes na competição.
Palavras-chave:
Iterated Local Search algorithm, TSP problem, link prediction
Referências
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.
Publicado
29/11/2021
Como Citar
CASTELLUCCI, Pedro B..
An iterated local search for the travelling salesman problem. In: ENCONTRO NACIONAL DE INTELIGÊNCIA ARTIFICIAL E COMPUTACIONAL (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.
