UM ALGORITMO BASEADO EM BRKGA E VND PARA O PROBLEMA DE ORIENTAÇÃO COM SELEÇÃO DE HOTÉIS
Detalhes
- Tipo de apresentação: Trabalho completo (oral)
- Eixo temático: 13. MH – Metaheurísticas
- Palavras chaves: POSH; BRKGA; VND;
- 1 Universidade Federal de Viçosa - Rio Paranaíba
UM ALGORITMO BASEADO EM BRKGA E VND PARA O PROBLEMA DE ORIENTAÇÃO COM SELEÇÃO DE HOTÉIS
Jordi Henrique Marques da Silva
Universidade Federal de Viçosa - Rio Paranaíba
Resumo
No Problema de Orientação com Seleção de Hotéis - 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. Levando em consideração este limite de jornada diário, torna-se 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 finalmente finalizando em um hotel também predefinido. O objetivo do POSH é encontrar uma rota cujo lucro obtido seja maximizado. Para solucionar o POSH é proposto um algoritmo heurístico baseado em Algoritmo Genético de Chaves Aleatórias Viciadas (BRKGA) e Descida em Vizinhança Variável (VND). O algoritmo foi aplicado nas instâncias da literatura e obteve resultados competitivos, atingindo 132 soluções ótimas.
Discussões Científicas de Qualidade
Com ~200 mil publicações revisadas por pesquisadores do mundo todo, o Galoá impulsiona cientistas na descoberta de pesquisas de ponta por meio de nossa plataforma indexada.
Confira nossos produtos e como podemos ajudá-lo a dar mais alcance para sua pesquisa:
Jordi Henrique Marques da Silva
Olá, Simone.
A escolha de se usar o BRKGA se deve a dois motivos, um deles é que esta metodologia ainda não havia sido utilizada para solução deste problema. O outro é aproveitar o decodificador para criação de soluções com alta diversidade, explorando melhor o espaço de busca. Na representação que utilizamos cada cliente de uma instância recebe uma chave aleatória entre 0 e 1. Quando a soluções passam pelo decodificador as chaves são ordenadas, e os clientes que receberam as menores chaves são visitados primeiramente.
Temos algumas ideias para melhorar o desempenho em tempo e obter melhores resultados, uma delas é a modificar a forma que o VND é aplicado, a metodologia utilizada neste trabalho utilizou de forma abusiva deste recurso o aplicando em todas gerações em todas soluções resultantes do cruzamento. Então estudar uma maneira condicionada de aplicar o VND de acordo com a necessidade de obter melhoria no decorrer das gerações reduzirá consideravelmente o custo computacional. Outra ideia é a implementação do decodificador no framework do BRKGA proposto por Resende afim de avaliar o desempenho utilizando as estratégias já implementadas.
Para terminar nós temos todos os resultados ótimos e se tiver interesse estão disponíveis no site da OR-Library.
Agradeço atenção !
Simone de Lima Martins
Excelente Jordi!
Continuem investindo no trabalho!