Please use this identifier to cite or link to this item: http://repositorio.ufersa.edu.br/handle/prefix/5216
metadata.dc.type: Dissertação
Title: Uma abordagem por hiperheurística com aprendizado para o problema de roteamento de veículos com janela de tempo
metadata.dc.creator: Souza, Daniel Vieira
metadata.dc.contributor.advisor1: Lima Júnior, Francisco Chagas de
metadata.dc.contributor.advisor-co1: Liberalino, Carlos Heitor Pereira
metadata.dc.contributor.referee1: Campos, Gustavo Augusto Lima de
metadata.dc.contributor.referee2: Medeiros Neto, Francisco Dantas de
metadata.dc.contributor.referee3: Fernandes Neto, André Pedro
metadata.dc.description.resumo: O conceito de hiperheurística é um tanto novo no ramo da otimização, se trata de um método que propõe uma estratégia de resolução que opera em um novo nível de abstração, onde sem a utilização de informações específicas do problema tratado o método é capaz de oferecer soluções através do gerenciamento de um conjunto de métodos heurísticos disponíveis, podendo ainda serem empregados mecanismos de aprendizado e/ou treinamento. Essas características permitem que esse tipo de abordagem possa se adaptar a diversos domínios de problemas ou a diferentes classes de instâncias. Principalmente em problemas onde dispondo de um conjunto de métodos heurísticos não se sabe que técnica de resolução é a mais adequada. O presente trabalho propõe como abordagem uma hiperheurística com aprendizado integrada à Metaheurística GRASP (Greedy Randomized Adaptive Search Procedure) aplicada à uma variante do clássico Problema de Roteamento de Veículos (PRV), o Problema de Roteamento de Veículos com Janela de Tempo (PRVJT). Tendo esse método como mecanismo de aprendizado uma técnica de Aprendizado por Reforço (AR), o algoritmo Q-Learning, que terá a tarefa de indicar que método heurístico mais adequado irá compor a fase construtiva do GRASP. Assim como a hiperheurística com aprendizado foi implementado um outro método hiperheurístico de gerenciamento de heurísticas aleatório, buscando comparar e analisar o desempenho do método de aprendizado. Os algoritmos foram testados em experimentos computacionais com instâncias conhecidas da literatura para o PRVJT e os resultados obtidos comparados ao custo de solução, tempo de execução e escolha do método heurístico construtivo utilizado na fase de construção do GRASP
Abstract: The concept of hyperheuristics is somewhat new in the field of optimization, it is a method that proposes a strategy of resolution that operates in a new level of abstraction, where without the use of specific information of the treated problem the method is able to o er solutions through the management of a set of available heuristic methods, and learning and / or training mechanisms may be employed. These characteristics allow this type of approach to adapt to di erent problem domains or to di erent classes of instances. Especially in problems where having a set of heuristic methods is not known which technique of resolution is the most adequate. The present work proposes as approach a hyperheuristic with learning integrated to GRASP (Greedy Randomized Adaptive Search Procedure) Metaheuristic applied to a variant of the classic Vehicle Routing Problem (PRV), the Vehicle Routing with TimeWindow (PRVJT). Having this method as learning mechanism a Reinforcement Learning (RA) technique, the algorithm Q-Learning that will have the task of indicating which heuristic method is most suitable to compose the constructive phase of GRASP. Like hyperheuristics with learning, another hyperheuristic method of managing random heuristics was implemented, trying to compare and analyze the performance of the learning method. The algorithms were tested in computational experiments with known instances in the literature for the PRVJT and the results obtained compared to the cost of solution, execution time and choice of the constructive heuristic method used in the GRASP construction phase
Keywords: Hiperheurística com aprendizado
Metaheurística GRASP
Problema de roteamento de veículos com janela de tempo
Aprendizado por reforço
Hyperheuristics with learning
GRASP metaheuristics
Vehicle routing problem with time window
Reinforcement learning
metadata.dc.subject.cnpq: CNPQ::CIENCIAS EXATAS E DA TERRA
metadata.dc.language: por
metadata.dc.publisher.country: Brasil
Publisher: Universidade Federal Rural do Semi-Árido
metadata.dc.publisher.initials: UFERSA
metadata.dc.publisher.department: Centro de Ciências Exatas e Naturais - CCEN
metadata.dc.publisher.program: Programa de Pós-Graduação em Ciência da Computação
Citation: Citação com autor incluído no texto: Souza (2019) Citação com autor não incluído no texto: (SOUZA, 2019)
metadata.dc.rights: Acesso Aberto
URI: http://repositorio.ufersa.edu.br/handle/prefix/5216
Issue Date: 22-Mar-2019
Appears in Collections:MESTRADO EM CIÊNCIA DA COMPUTAÇÃO

Files in This Item:
File Description SizeFormat 
DanielVS_DISSERT.pdf1.39 MBAdobe PDFView/Open


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