A carregar...
Publicação
Meta-heurística para o problema do caixeiro viajante com famílias, múltiplos depósitos e restrições de agrupamento leves
| Nome: | Descrição: | Tamanho: | Formato: | |
|---|---|---|---|---|
| 1.42 MB | Adobe PDF |
Orientador(es)
Resumo(s)
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.
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.
Descrição
Palavras-chave
Problema do Caixeiro Viajante com Famílias Múltiplos Depósitos Soft Cluster Vizinhanças Pesquisa Local Iterativa Family Traveling Salesman Problem Multi-depot Soft Cluster Neighborhoods Iterative Local Search
Contexto Educativo
Citação
Anacleto, Madalena Almeida Neves Da Silva (2024). “Meta-heurística para o problema do caixeiro viajante com famílias, múltiplos depósitos e restrições de agrupamento leves”. Dissertação de Mestrado. Universidade de Lisboa. Instituto Superior de Economia e Gestão
Editora
Instituto Superior de Economia e Gestão