Use este identificador para citar ou linkar para este item: https://repositorio.ufms.br/handle/123456789/13922
Registro completo de metadados
Campo DCValorIdioma
dc.creatorISAAC KOSLOSKI OLIVEIRA-
dc.date.accessioned2025-12-06T15:27:17Z-
dc.date.available2025-12-06T15:27:17Z-
dc.date.issued2025pt_BR
dc.identifier.urihttps://repositorio.ufms.br/handle/123456789/13922-
dc.description.abstractThis 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-
dc.language.isopt_BRpt_BR
dc.publisherFundação Universidade Federal de Mato Grosso do Sulpt_BR
dc.rightsAcesso Abertopt_BR
dc.subjectCVRP-
dc.subjectILS-
dc.subjectGRASP-
dc.subjectOtimização Combinatória-
dc.subject.classificationCiências Exatas e da Terrapt_BR
dc.titleMetaheurísticas para o Problema de Roteamento de Veículos: Um Estudo Comparativo entre ILS e GRASPpt_BR
dc.typeTrabalho de Conclusão de Cursopt_BR
dc.contributor.advisor1BIANCA DE ALMEIDA DANTAS-
dc.description.resumoO 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.pt_BR
dc.publisher.countrynullpt_BR
dc.publisher.initialsUFMSpt_BR
Aparece nas coleções:Engenharia de Computação - Bacharelado (FACOM)

Arquivos associados a este item:
Arquivo TamanhoFormato 
21918.pdf672,15 kBAdobe PDFVisualizar/Abrir
Mostrar registro simples do item Visualizar estatísticas


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.