Problema do caixeiro viajante com coleta de prêmios e janelas de tempo

Resumo

Este trabalho tem por objetivo tratar o Problema do Caixeiro Viajante com Coleta de Prêmios e Janelas de Tempo (PCVCPJT), usando a metaheurística de Busca em Vizinhança Variável (VNS - Variable Neighborhood Search) [6], [7]. O PCVCPJT é um variante do tão conhecido Problema do Caixeiro Viajante (PCV) - na literatura inglesa, Travelling Salesman Problem (TSP)-, que tem sido objeto de estudo de vários pesquisadores desde o início do século XIX, e continua um forte ramo de pesquisa ate´ hoje, como em [1], [4], tendo em vista o forte impacto do transporte rodoviário no comércio mundial. Apesar de ser uma extensão do PCV, o Problema do Caixeiro Viajante com Coleta de Prêmios (PCVCP) foi primeiramente formulado em 1989 por Egon Balas [2], como um modelo para programação da operação diária de uma fábrica de produção de lâminas de aço, visando a escolha de um numero de lâminas associadas à certas restrições. No PCVCPJT, considera-se um grafo completo G = (V, A), onde a cada aresta (i, j) ∈ A, está associado um custo de travessia cij , e a cada vértice i ∈ V estão associados um prêmio pi, caso ele seja visitado, ou uma penalidade πi, se ele não for visitado, e uma janela de tempo dada pelo intervalo fechado [ai, bi], significando que o atendimento no vértice i deve começar nesse intervalo, mesmo que o caixeiro chegue antes do início da janela de tempo. O problema consiste em encontrar uma rota tal que a função objetivo, dada pela soma dos custos e penalidades por meio dessa rota, tenha valor m´mínimo, e que o requerimento das janelas de tempo seja satisfeito. Propomos uma heurística composta por duas fases: a fase da construção de soluções e a fase da busca local. A primeira fase tenta construir soluções viáveis (se possível) para uma instância do problema. Nesta fase usamos heurísticas de construção que montam rotas por vários critérios como dificuldade de um cliente ser inserido por questões de factibilidade, inserção por menor custo, vizinho mais próximo (ou mais barato), entre outros. No entanto, uma solução inviável - nem todos os clientes são atendidos dentro de suas janelas de tempo - pode ser obtida na primeira fase. Na segunda fase, uma solução obtida pela primeira fase com menor valor na função objetivo é considerada. Se ela for factível, continuamos a partir dela. Caso contrário, a penalizamos, retirando os nos que não são atendidos num tempo admissível, e usamos o caminho obtido com essa retirada de nós para continuar. Neste momento, aplicamos a metaheur´ıstica VNS visando obter a cada iteração uma solução melhor do que a corrente. Isso e´ feito explorando a cada iteração, vizinhanças da solução corrente. Cada vizinhança de uma solução, é um conjunto composto por caminhos obtidos a partir dela, por uma regra comum, como por exemplo, troca de dois nós, reinserção de arco, entre outras. Encontrada uma solução de valor objetivo melhor do que a da corrente, tal solução passa a ser a corrente, e o processo e´ retomado sobre o novo caminho, repetindo este procedimento ate´ que nenhuma melhoria seja possível. Ao final, devemos obter uma solução que tem pelo menos tantos nós quanto a solução inicial (caminho obtido na fase um). Assim, mesmo que a melhor solução obtida na fase um não seja factível (sendo necessário, penalizá-la), é possível que ao final da fase dois, tenhamos uma factível e sem penalização. Em geral, o método tem garantido ao menos uma solução factível, sempre que o problema admite soluções factíveis.Em [8] são fornecidas instancias do problema e uma solução para cada instância. O nosso método conseguiu resolver mais de vinte instancias da biblioteca AFG e, para algumas delas,  encontramos soluções com mesmo valor de função objetivo, comparando com as soluções fornecidas por [8]. Para as instancias resolvidas pelo nosso método, as soluções encontradas são quase tão boas quanto as ótimas fornecidas, tendo ate´  o momento desvio médio inferior a 1,5%.