English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Este trabalho tem por objetivo tratar o Problema do Caixeiro Viajante com Coleta de Premios e Janelas de Tempo (PCVCPJT), usando a metaheuristica de Busca em Vizinhanca Variavel (VNS - V ariable Neighborhood Search ) [6], [7]. O PCVCPJT e um variante do tao conhecido Problema do Caixeiro Viajante (PCV) - na literatura inglesa, T r avelling Salesman Problem (TSP)-, que tem sido objeto de estudo de varios pesquisadores desde o inicio do seculo XIX, e continua um forte ramo de pesquisa ate´ hoje, como em [1], [4], tendo em vista o forte impacto do transporte rodoviario no comercio mundial. Apesar de ser uma extensao do PCV, o Problema do Caixeiro Viajante com Coleta de Premios (PCVCP) foi primeiramente formulado em 1989 por Egon Balas [2], como um modelo para programacao da operacao diaria de uma fabrica de producao de lâminas de aco, visando a escolha de um numero de lâminas associadas a certas restricoes. No PCVCPJT, considera-se um grafo completo G = ( V, A ), onde a cada aresta ( i, j ) ∈ A , esta associado um custo de travessia c ij , e a cada vertice i ∈ V estao associados um premio p i , caso ele seja visitado, ou uma penalidade π i , se ele nao for visitado, e uma janela de tempo dada pelo intervalo fechado [ a i , b i ], significando que o atendimento no vertice i deve comecar nesse intervalo, mesmo que o caixeiro chegue antes do inicio da janela de tempo. O problema consiste em encontrar uma rota tal que a funcao objetivo, dada pela soma dos custos e penalidades por meio dessa rota, tenha valor m´minimo, e que o requerimento das janelas de tempo seja satisfeito. Propomos uma heuristica composta por duas fases: a fase da construcao de solucoes e a fase da busca local. A primeira fase tenta construir solucoes viaveis (se possivel) para uma instância do problema. Nesta fase usamos heuristicas de construcao que montam rotas por varios criterios como dificuldade de um cliente ser inserido por questoes de factibilidade, insercao por menor custo, vizinho mais proximo (ou mais barato), entre outros. No entanto, uma solucao inviavel - nem todos os clientes sao atendidos dentro de suas janelas de tempo - pode ser obtida na primeira fase. Na segunda fase, uma solucao obtida pela primeira fase com menor valor na funcao objetivo e considerada. Se ela for factivel, continuamos a partir dela. Caso contrario, a penalizamos, retirando os nos que nao sao atendidos num tempo admissivel, e usamos o caminho obtido com essa retirada de nos para continuar. Neste momento, aplicamos a metaheur´istica VNS visando obter a cada iteracao uma solucao melhor do que a corrente. Isso e´ feito explorando a cada iteracao, vizinhancas da solucao corrente. Cada vizinhanca de uma solucao, e um conjunto composto por caminhos obtidos a partir dela, por uma regra comum, como por exemplo, troca de dois nos, reinsercao de arco, entre outras. Encontrada uma solucao de valor objetivo melhor do que a da corrente, tal solucao passa a ser a corrente, e o processo e´ retomado sobre o novo caminho, repetindo este procedimento ate´ que nenhuma melhoria seja possivel. Ao final, devemos obter uma solucao que tem pelo menos tantos nos quanto a solucao inicial (caminho obtido na fase um). Assim, mesmo que a melhor solucao obtida na fase um nao seja factivel (sendo necessario, penaliza-la), e possivel que ao final da fase dois, tenhamos uma factivel e sem penalizacao. Em geral, o metodo tem garantido ao menos uma solucao factivel, sempre que o problema admite solucoes factiveis.Em [8] sao fornecidas instancias do problema e uma solucao para cada instância. O nosso metodo conseguiu resolver mais de vinte instancias da biblioteca AFG e, para algumas delas,  encontramos solucoes com mesmo valor de funcao objetivo, comparando com as solucoes fornecidas por [8]. Para as instancias resolvidas pelo nosso metodo, as solucoes encontradas sao quase tao boas quanto as otimas fornecidas, tendo ate´  o momento desvio medio inferior a 1,5%.

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