Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/321008
Type: TESE DIGITAL
Title: Problema do caixeiro viajante com coleta de prêmios e janelas de tempo
Title Alternative: Prize collecting traveling salesman problem
Author: Rebouças, Ramom Santana, 1989-
Advisor: Gomes Neto, Francisco de Assis Magalhães, 1964-
Neto, Francisco de Assis Magalhães Gomes
Abstract: 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
Subject: Problema do caixeiro viajante
Janela de tempo
Otimização combinatória
Meta-heurística
Heurística computacional
Editor: [s.n.]
Date Issue: 2016
Appears in Collections:IMECC - Dissertação e Tese

Files in This Item:
File SizeFormat 
Reboucas_RamomSantana_M.pdf600.91 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.