Uma abordagem por hiperheurística com aprendizado para o problema de roteamento de veículos com janela de tempo

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