Meta Heurística para o Problema do Caixeiro Viajante com Famílias, Múltiplos Depósito e Restrições de Agrupamento Leves

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.