Use este identificador para citar ou linkar para este item:
https://repositorio.ufms.br/handle/123456789/14027| Tipo: | Outros |
| Título: | Comparação de estratégias de vizinhança em buscas locais para PRVC |
| Autor(es): | FELIPE DOS SANTOS MOREIRA VITOR DE ASSIS RAMOS CAIO MIGUEL GÔNGORA DARZI |
| Primeiro orientador: | BIANCA DE ALMEIDA DANTAS |
| Resumo: | Neste trabalho investigamos como diferentes estratégias de vizinhança influenciam o desempenho do Simulated Annealing na resolução do PRVC. Testamos quatro movimentos de busca local (relocate, exchange, or-opt e 2-opt/swap) em instâncias clássicas do conjunto CMT, realizando múltiplas repetições para reduzir variância. Avaliamos custo final médio, robustez por desvio padrão e tempo de execução. Observamos que exchangeMove e relocateMove são superiores em qualidade de solução, destacando-se na maioria das instâncias, enquanto orOptMove e swap2Opt são mais estáveis, porém ficam presos em ótimos locais de pior custo. Assim, a vizinhança escolhida altera significativamente a dinâmica do SA, e os dados sugerem que combinar vizinhanças exploratórias em altas temperaturas com vizinhanças intensificadoras em baixas temperaturas pode melhorar ainda mais os resultados. |
| Abstract: | Este projeto avalia o desempenho do algoritmo Simulated Annealing (SA) aplicado ao Problema de Roteamento de Veículos com Capacidade (PRVC) sob diferentes funções de mudança de vizinhança. Foram testadas quatro vizinhanças clássicas — relocateMove, exchangeMove, orOptMove e swap2Opt — em 10 instâncias do conjunto CMT, com 30 repetições por instância, totalizando 1200 execuções. A análise compara qualidade média das soluções, estabilidade (desvio padrão) e tempo computacional. Os resultados indicam que exchangeMove e relocateMove obtêm sistematicamente os menores custos finais, enquanto orOptMove e swap2Opt apresentam maior estabilidade porém convergem para soluções de pior qualidade. Conclui-se que a escolha da vizinhança é decisiva no SA para PRVC e que uma abordagem híbrida combinando múltiplas vizinhanças ao longo do resfriamento tende a ser uma estratégia promissora. |
| Palavras-chave: | Movimentação Simulated Annealing CVPR |
| 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/14027 |
| Data do documento: | 2025 |
| Aparece nas coleções: | Engenharia de Computação - Bacharelado (FACOM) |
Arquivos associados a este item:
| Arquivo | Tamanho | Formato | |
|---|---|---|---|
| 33953.pdf | 193,74 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.