Ciência, saúde e esporte: conhecimento e acessibilidade
21 a 26 de outubro de 2013
Trabalho 1716
| ISSN | 2237-9045 |
|---|---|
| Instituição | Universidade Federal de Viçosa |
| Nível | Graduação |
| Modalidade | Pesquisa |
| Área de conhecimento | Ciências Exatas e Tecnológicas |
| Área temática | Teoria e Tecnologia da informação |
| Setor | Departamento de Informática |
| Bolsa | PIBIC/CNPq |
| Conclusão de bolsa | Sim |
| Apoio financeiro | CNPq |
| Primeiro autor | Denis Moreira Ferreira |
| Orientador | ANDRE GUSTAVO DOS SANTOS |
| Título | Contribuições para o problema do roteamento de múltiplos veículos com entregas obrigatórias e coletas seletivas. |
| Resumo | O problema de roteamento de múltiplos veículos com entregas obrigatórias e coletas seletivas (PRMVEOCS) é uma variação do clássico problema de roteamento de veículos que apesar de possuir muitas aplicações práticas, tem recebido pouca atenção na literatura. O problema ocorre em cenários de logística reversa, como por exemplo, em fábricas de bebidas, que ao mesmo tempo em que há uma demanda de supermercados e outras lojas por garrafas cheias, também existe uma demanda pela coleta de garrafas vazias que devem retornar para o depósito a fim de serem limpas e reutilizadas. Este assunto é de muita importância pois uma das grandes preocupações das empresas e indústrias é propiciar, com custo mínimo, melhor serviço e escoamento das suas mercadorias. O custo de transporte de qualquer tipo de produto tem influência direta nos custos dos mesmos e pode ser a chave do sucesso ou do fracasso de uma empresa. No PRMVEOCS as entregas são efetuadas a uma série de clientes através de múltiplas rotas, dependendo da quantidade de veículos, mas também existem itens que podem ser coletados se possível dependendo da receita gerada por estas coletas. Isto ocorre durante a rota ou criando desvios da rota original de entrega. Também pode ocorrer o caso em que um cliente, por sua necessidade de entrega, seja atendido por uma rota, porém este mesmo cliente ser atendido por outra rota através de sua necessidade de coleta. O PRMVEOCS pertence a classe NP-dificil, uma vez que ele se reduz ao problema do caixeiro-viajante quando existe apenas um veículo e nenhum cliente necessita de serviço de coleta. Assim as abordagens mais sugeridas na literatura para problemas de elevada complexidade são baseados em metaheurísticas, como GRASP. Este trabalho visa produzir algoritmos heurísticos viáveis que permitam a resolução satisfatória deste tipo de problema e que assim esta tecnologia possa ser utilizada em contextos reais. Para resolvê-lo foi proposto um algoritmo parte exato, utilizando reais modelagens matemáticas em subdivisões do problema, e parte heurísticos em subproblemas onde a abordagem heurística já apresentava um resultado satisfatório. Tais métodos foram implementados e encontraram soluções aproximadas para o problema em tempo razoável. |
| Palavras-chave | Algoritmos heurísticos, GRASP, Roteamento de veículos |
| Forma de apresentação..... | Oral |