Bioeconomia: Diversidade e Riqueza para o Desenvolvimento Sustentável
22 a 24 de outubro de 2019
Trabalho 12791
| 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 | Instituto de Ciências Exatas e Tecnológicas |
| Conclusão de bolsa | Não |
| Primeiro autor | Christian Rodrigues Moura |
| Orientador | MATHEUS NOHRA HADDAD |
| Outros membros | Jordi Henrique Marques da Silva |
| Título | Problema de Orientação com Seleção de Hotéis |
| Resumo | No último século houve um grande aumento da população mundial e com isso novas necessidades surgiram, como o desenvolvimento de novos métodos para a fabricação de recursos, objetos e produção de alimentos. Visando este aumento na produção de recursos, uma ampla variação de problemas logísticos foram surgindo, como a organização e gerenciamento das rotas para distribuição dos mesmos. Empresas que trabalham com distribuição ou atendimento a clientes necessitam gerenciar e otimizar rotas de forma que elevem a lucratividade e diminuam os custos. Dentre os problemas de atendimento a clientes destaca-se o Problema de Orientação com Seleção de Hotéis (POSH), que é uma variante do problema de roteamento de veículos e do problema do caixeiro viajante. No POSH, existe um veículo disponível que deve realizar uma rota para atender um número de clientes, sem exceder um tempo limite de jornada diária. Por conta deste limite de jornada diário, fica necessária a seleção de um hotel mais próximo para realizar uma pausa, e assim, posteriormente retornar para uma nova jornada. Com base nessa restrição, uma rota de atendimento é composta inicialmente por um hotel preestabelecido, vários atendimentos a clientes, com os hotéis respectivos para descanso, e finalizando em um hotel também predefinido. O objetivo do POSH é encontrar a rota de atendimento cujo lucro obtido pelos atendimentos aos clientes seja o máximo possível, isto torna o POSH um problema NP-Difícil. Sendo assim, é proposta uma abordagem de solução para o POSH através da utilização do algoritmo genético com chaves aleatórias (BRKGA) em conjunto com a heurística de refinamento descida em vizinhança variável (VND). O BRKGA proporciona uma vantagem para os operadores genéticos, como o cruzamento, por sua representação com números reais, pois não se torna necessária a implementação de métodos de cruzamento específicos para problemas de permutação, sendo assim uma nova abordagem para a resolução do problema. Neste trabalho foram encontradas soluções de boa qualidade para o POSH em instâncias disponíveis da literatura, além de obter resultados competitivos com resultados da literatura, obtidos por um algoritmo memético e um algoritmo baseado no método busca em vizinhança variável (VNS). Portanto é possível concluir que o algoritmo desenvolvido é bastante eficiente para aplicações práticas do problema. |
| Palavras-chave | POSH, BRKGA, VND |
| Forma de apresentação..... | Painel |