Tesis
Problema do caixeiro viajante com coleta de prêmios e janelas de tempo
Prize collecting traveling salesman problem
Registro en:
Autor
Rebouças, Ramom Santana, 1989-
Institución
Resumen
Orientador: Francisco de Assis Magalhães Gomes Neto Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matemática Estatística e Computação Científica Resumo: O Problema do Caixeiro Viajante tem sido objeto de estudo desde o início do século XIX, mantendo-se como um amplo ramo de pesquisa até hoje, tendo em vista o forte impacto do transporte no comércio mundial. Essa dissertação contém algumas variações esse problema, bem como técnicas para obtenção de sua solução. Como destaque, é apresentado o Problema do Caixeiro Viajante com Coleta de Prêmios e Janelas de Tempo, no qual a função objetivo relaciona custos, penalidades por clientes não atendidos e prêmios por clientes atendidos, os quais devem ser visitados dentro de suas respectivas janelas de tempo. GENIUS é a principal heurística utilizada para obtenção de solução inicial do problema em destaque, a meta-heurística VNS é responsável pelo refinamento da solução inicial. Para o algoritmo que implementamos, são apresentados vários resultados numéricos Abstract: The Traveling Salesman Problem has been studied since the beginning of the XIX century, and it remains a wide research field today, in view of the strong impact of transportation in world trade. This dissertation contains some variations of this problem, as well as techniques to obtain its solution. Most notably, we present the Prize Collecting Traveling Salesman Problem With Time Windows, for which the objective function relates costs, penalties for clients that are not visited, and prizes for visited clients. Costumers who are served must be visited within their respective time windows. GENIUS is the main heuristic used to produce a initial solution for the highlighted problem, and the VNS methaheuristic is responsible for refining the initial solution. For the implemented algorithm, we present several numerical results Mestrado Matematica Aplicada Mestre em Matemática Aplicada CNPQ