Use este identificador para citar ou linkar para este item:
https://repositorio.ufms.br/handle/123456789/13922| Tipo: | Trabalho de Conclusão de Curso |
| Título: | Metaheurísticas para o Problema de Roteamento de Veículos: Um Estudo Comparativo entre ILS e GRASP |
| Autor(es): | ISAAC KOSLOSKI OLIVEIRA |
| Primeiro orientador: | BIANCA DE ALMEIDA DANTAS |
| Resumo: | O presente trabalho avaliou empiricamente as meta-heurísticas Busca Local Iterada (ILS) e Procedimento de Busca Adaptativa Gulosa Aleatória (GRASP) para resolver o Problema de Roteamento de Veículos Capacitados (CVRP). O CVRP é um problema NP-difícil crucial para a logística, visando a minimização do custo total das rotas, respeitando a capacidade dos veículos. A implementação modular utilizou dois operadores de busca local, como 2-Opt e Swap*, nas duas meta-heurísticas propostas. Os resultados comparativos em 100 instâncias do benchmark X revelaram que o ILS obteve soluções de custo superior em 98% das instâncias e foi, em média, 13, 5 vezes mais rápido que o GRASP. A diferença de desempenho foi atribuída à estratégia de intensificação do ILS com a perturbação Double-Bridge, contra o custo computacional da reconstrução gulosa aleatória do GRASP a cada iteração. |
| Abstract: | This work empirically evaluated the Iterated Local Search (ILS) and Greedy Randomized Adaptive Search Procedure (GRASP) metaheuristics for solving the Capacitated Vehicle Routing Problem (CVRP). CVRP is an NP-hard problem critical for logistics, aiming to minimize the total cost of routes while respecting vehicle capacities. The modular implementation used two local search operators, such as 2-Opt and Swap*, in the two proposed metaheuristics. Comparative results on 100 instances of the X benchmark showed that ILS achieved superior cost solutions in 98% of the instances and was, on average, 13.5 times faster than GRASP. The performance difference was attributed to the ILS intensification strategy with the Double-Bridge perturbation, contrasting with the computational cost of GRASP’s randomized greedy reconstruction at each iteration |
| Palavras-chave: | CVRP ILS GRASP Otimização Combinatória |
| País: | |
| Editor: | Fundação Universidade Federal de Mato Grosso do Sul |
| Sigla da Instituição: | UFMS |
| Tipo de acesso: | Acesso Aberto |
| URI: | https://repositorio.ufms.br/handle/123456789/13922 |
| Data do documento: | 2025 |
| Aparece nas coleções: | Engenharia de Computação - Bacharelado (FACOM) |
Arquivos associados a este item:
| Arquivo | Tamanho | Formato | |
|---|---|---|---|
| 21918.pdf | 672,15 kB | Adobe PDF | Visualizar/Abrir |
Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.