Hibridização de Heurísticas, com Programação Inteira e Mineração de Dados, para a Solução de Duas Variantes do Problema do Caixeiro Viajante
Authors:
Autores
| Person role | Person | |
|---|---|---|
|
6907 |
3077,539
|
|
|
6908 |
3077,539
|
Informations:
Pesc publication
Neste trabalho, são apresentadas estratégias para resolver, de maneira eficiente, duas generalizações do problema do caixeiro viajante. O primeiro, o problema de recobrimento de rotas com coleta de prêmios (PRRCP), é motivado pela necessidade de se obter uma rota de custo mínimo para equipe itinerantes, que prestam assistência a comunidades distantes de grandes centros urbanos. Enquanto o segundo, o problema do caixeiro viajante com coleta de prêmios (PCVCP), possui várias aplicações reais, incluindo o planejamento de rotas de helicópteros para plataformas de petróleo no mar, a criação de rotas para turistas, a distribuição de produtos para revendedores, entre outras.
Para a resolução de tais problemas, propõem-se estratégias heurísticas e exatas. Para o PRRCP, é proposta uma nova formulação matemática, novas desigualdades válidas, sete novas regras de redução, e quatro heurísticas híbridas, que combinam uma heurística estado-da-arte com programação linear inteira (PLI) e mineração de dados. Para o PCVCP, é proposto um procedimento de separação para as restrições cut-sets de uma formulação da literatura, uma heurística híbrida que combina GRASP e RVND com PLI, e um novo conjunto de instâncias.
No intuito de validar as estratégias propostas, foram realizados experimentos computacionais em instâncias já conhecidas da literatura e em novas apresentadas neste trabalho. Os resultados indicam o benefício da nova formulação e das combinações com PLI e mineração de dados, alcançando soluções de melhor qualidade em menor tempo de processamento para a maioria dos testes, e provando otimalidade inédita para vários casos.
In this work, strategies are presented to solve, in an efficient way, two generalizations of the traveling salesman problem. The first, prize-collecting covering tour problem (PCCTP), it is motivated by the need to obtain a minimum cost route for itinerant staff, who assist communities far from large urban centers. While the second, the prize-collecting traveling salesman problem (PCTSP), has several real applications such as planning helicopter routes for offshore oil platforms, creating routes for tourists, and distributing products to resellers.
To solve such problems, heuristic and exact strategies were proposed. For the PCCTP, we proposed a new mathematical formulation, new valid inequalities, seven new reduction rules, and four hybrid heuristics, which combine a state-of-the-art heuristic with integer linear programming (ILP) and data mining. For the PCTSP, a separation procedure is proposed for the cut-sets constraints of a literature’s formulation, a hybrid heuristic that combines GRASP and RVND with PLI, and a new set of instances.
In order to validate the proposed strategies, computational experiments were carried out on instances already known in the literature and new ones presented in this work. The results indicate the benefit of the new formulation and the combinations with ILP and data mining, achieving better quality solutions in less processing time for most tests, and proving unprecedented optimality for several cases.