Meta-heurística para o problema do caixeiro viajante com famílias, múltiplos depósitos e restrições de agrupamento leves

Abstract

Neste trabalho foi feito um estudo do Problema do Caixeiro Viajante com Múltiplos Depósitos, Famílias e Restrições de Agrupamento Leves (em inglês Soft Cluster Muti-Depot Family Traveling Salesman Problem, SC-MDFTSP). Esta escolha prendeu-se com o facto de a variante selecionada ser a que revela uma maior dificuldade quando comparada com as outras variantes do MDFTSP, uma vez que menos ótimos foram obtidos. O objetivo deste estudo é desenvolver um método eficiente e eficaz para este problema. Para isso, foi implementada uma meta-heurística de pesquisa local iterativa (ILS), baseada num conjunto de vizinhanças e duas perturbações: Perturbação Aleatória e Perturbação Frequência na Rota. Estes algoritmos foram aplicados a um conjunto de instâncias com número de nodos entre 50 e 150, cinco a 30 depósitos e 15 a 75 famílias. Os resultados obtidos através de experiências computacionais não foram tão favoráveis como o esperado, no entanto, permitem-nos concluir que instâncias com maior número de nodos apresentam valores de gaps mínimos, máximos e médio menos elevados. No que diz respeito ao tempo médio despendido em segundos, o aumento do número de famílias não teve impacto significativo no tempo de resolução. Quanto ao aumento do número de depósitos, verificou-se um aumento no tempo para instâncias simétricas e uma diminuição para instâncias assimétricas.

This work presents a study of the Muti-Depot Family Traveling Salesman Problem and Soft Cluster Variant (SC-MDFTSP). This choice was due to the fact that the selected variant revealed greater difficulty when compared to the other variants of the MDFTSP, since fewer optima were obtained. The objective of this study is to develop an efficient and effective method for this problem. For this purpose, an Iterated Local Search (ILS) metaheuristic was implemented, based on a set of neighborhoods and two perturbations: Random Perturbation and Route Frequency Perturbation. These algorithms were applied to a set of instances with a number of nodes ranging from 50 to 150, five to 30 depots, and 15 to 75 families. The results obtained through computational experiments were not as favorable as expected, however, they allow us to conclude that instances with a greater number of nodes present lower minimum, maximum and average gap values. Regarding the average time spent, the increase in the number of families had no significant impact on this time. As for the increase in the number of depots, there was an increase in time for symmetric instances and a decrease for asymmetric instances.