MODELS AND ALGORITHMS TO THE TEAM ORIENTEERING PROBLEM / MODELOS E ALGORITMOS PARA O TEAM ORIENTEERING PROBLEM

AUTOR(ES)

FRANCISCO HENRIQUE DE FREITAS VIANA

FONTE

IBICT - Instituto Brasileiro de Informação em Ciência e Tecnologia

DATA DE PUBLICAÇÃO

12/09/2011

RESUMO

O Team Orienteering Problem é um problema de roteamento de veículos sobre um grafo com durações associadas aos arcos e prêmios atribuídos à visitação de cada vértice. Neste problema, considera-se que as visitas são realizadas por uma frota com um número fixo de veículos idênticos e que existe uma duração total máxima para as rotas serem finalizadas. Cada vértice pode ser visitado no máximo uma vez, não havendo obrigatoriedade de se visitar todos os vértices, devido à restrição que limita o tempo m´aximo de duração das rotas. O objetivo do problema é maximizar o prêmio total ganho por todas as rotas. Neste trabalho, foram propostas duas abordagens: uma exata e uma heurística. Na abordagem exata, foi desenvolvida uma formulação baseada em arcos e uma formulação estendida na qual cada arco tem um índice extra. Esse índice representa o tempo de partida de um veículo ao percorrer o arco. Através de transformações sobre a formulação estendida, foi obtida uma formulação, cuja relaxação, problema mestre restrito, foi resolvida pela técnica de geração de colunas. O subproblema de geração de colunas foi resolvido por programação dinâmica em tempo pseudo-polinomial. Este algoritmo gera rotas não elementares, que são rotas nas quais subciclos são permitidos. Com o objetivo de eliminar os subciclos das rotas não elementares, uma nova classe de desigualdades denominada min cut foi proposta. Aplicando-se um algoritmo Branch-Cut-and-Price (BCP) foram obtidos alguns novos limites superiores. A abordagem exata obteve resultados competitivos quando comparada ao melhor algoritmo exato já proposto para esse problema. Na abordagem heurística, além de uma vizinhança k-opt, foi explorada também uma busca elipsoidal que adiciona um corte à formulação do algoritmo Branch-Cut-and-Price. Esse novo corte reduz o espa¸co de busca a uma vizinhança em torno de um conjunto de soluções conhecidas. Essa busca é utilizada como um operador de crossover executado em todas as iterações de um algoritmo evolutivo. Essa abordagem converge em um tempo computacional razoável e encontra soluções ótimas ou próximas da ótima para algumas instâncias da literatura.

ASSUNTO(S)

column generation heuristica heuristics geracao de colunas

Documentos Relacionados

• MODELOS E ALGORITMOS PARA O PROBLEMA DE ALOCAÇÃO GENERALIZADA (PAG) E APLICAÇÕES
• Models and algorithms for the phone network cabling problem
• MODELS AND ALGORITHMS FOR THE DIAMETER CONSTRAINED MINIMUM SPANNING TREE PROBLEM
• Algoritmos para o problema de particionamento
• Algoritmos para o problema da cobertura por sensores