Autor(es)

Chaves, Antonio Augusto ; Vianna, Barbara Lessa ; da Silva, Tiago Tiburcio ; Schenekemberg, Cleder Marcos

• Tipo de documento: Artigo Científico
• Fonte: EXPERT SYSTEMS WITH APPLICATIONS; v. 238, p. 16-pg., 2023-10-04.

Resumo

This paper addresses the Family Traveling Salesman Problem (FTSP), a variant of the Traveling Salesman Problem that group nodes into families. The goal is to select the best route by visiting only a subset of nodes from each family. We developed two methods to solve the FTSP: (i) a parallel branch-and-cut algorithm with an efficient local search procedure (P-B&C) to obtain an optimal solution, and (ii) an adaptive metaheuristic that combines the Biased Random-key Genetic Algorithm (BRKGA) with a reinforcement learning algorithm. In this case, the Q-Learning algorithm controls the parameters of the BRKGA during the evolutionary process. We perform computational experiments on a well-known benchmark dataset with 185 instances. Our P-B&C proves the optimal value for 179 instances, improving the best upper bounds in 19 open instances. The new local search component of the P-B&C finds the best upper bounds for 50% of instances. The BRKGA-QL finds the optimal solution in 131 instances, improving the best upper bounds in 21 open instances. Finally, we compare our results with the best results in the literature, and both methods show robustness and efficiency in solving the FTSP. (AU)

• Processo FAPESP: 18/15417-8 - Desenvolvimento de uma meta-heurística híbrida com fluxo de controle e parâmetros adaptativos
• Beneficiário: Antônio Augusto Chaves
• Modalidade de apoio: Auxílio à Pesquisa - Jovens Pesquisadores - Fase 2
• Processo FAPESP: 20/07145-8 - Uma meta-heurística adaptativa aplicada ao problema dial-a-ride e variantes
• Beneficiário: Cleder Marcos Schenekemberg
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado
• Processo FAPESP: 20/03408-4 - Uma meta-heurística híbrida aplicada a variantes do problema do caixeiro viajante multiproduto com prioridades
• Beneficiário: Bárbara Lessa Vianna
• Modalidade de apoio: Bolsas no Brasil - Mestrado
• Processo FAPESP: 16/01860-1 - Problemas de corte, empacotamento, dimensionamento de lotes, programação da produção, roteamento, localização e suas integrações em contextos industriais e logísticos
• Beneficiário: Reinaldo Morabito Neto
• Modalidade de apoio: Auxílio à Pesquisa - Temático