Publicado no Encontro de Saberes 2015
Evento: XXIII Seminário de Iniciação Científica
Área: ENGENHARIAS
Subárea: Engenharia de Controle e Automação
| Título |
| IMPLEMENTAÇÃO DA METAHEURÍSTICA BUSCA TABU REATIVA PARA RESOLVER O PROBLEMA DE COLETA E ENTREGA COM JANELA DE TEMPO |
| Autores |
|
ANDRE LUIZ VIANA DA SILVA (Autor) ERICK VICTOR DE OLIVEIRA GUEDES (Autor) GUSTAVO PEIXOTO SILVA (Orientador) |
| Resumo |
| Este trabalho aborda o Problema de Coleta e Entrega com Janelas de Tempo (PDPTW), o qual requer que uma frota de veículos atenda a um determinado número de pedidos com o menor custo possível. Um pedido consiste em coletar uma mercadoria em um determinado local e entregá-lo em outro, dentro de um determinado intervalo de tempo. Todos os pedidos devem ser atendidos respeitando a capacidade dos veículos e as janelas de tempo de coleta e entrega. O trabalho proposto tem como objetivo implementar a metaheurística Busca Tabu para resolver o PDPTW, usando três vizinhanças distintas que tiram proveito das relações de precedência e acoplamento inerentes ao problema. Foi empregada, ainda, uma metodologia de pesquisa hierárquica para, dinamicamente, alternar entre vizinhanças para explorar diferentes regiões e ajustar trajetórias de busca. Esta estratégia permite fugir de ótimos locais e aumenta sua capacidade de percorrer todo o espaço de soluções. O método foi testado com uma série de problemas benchmark largamente utilizados na literatura. Os resultados alcançados estão em conformidade com os melhores encontrados na literatura, apesar de haver uma pequena margem de erro, sendo esta em média 7,30% dos melhores resultados conhecidos na literatura. Assim, é possível considerar que o método implementado é eficiente para resolver o problema. Uma maior precisão no balanceamento dos pesos das penalidades aplicadas é, possivelmente, uma forma capaz de levar a melhores resultados. |
