[pt] MODELOS E ALGORITMOS PARA O TEAM ORIENTEERING PROBLEM - FRANCISCO HENRIQUE DE FREITAS VIANA (2012)
[pt] 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.