Meta-heurísticas híbridas para problemas de roteamento

Abstract

Problems involving vehicle routing often appear in the logistics area. A classic problem is the Traveling Salesman Problem (TSP) that determines the best route to travel through a sequence of cities, visiting all of them once, and returning to the starting city. Due to the fact that it is a combinatorial optimization problem, this work proposes solution strategies called metaheuristics. In this way, different techniques were studied and implemented, among them Genetic Algorithms, Tabu Search and Neighborhood Search. Nevertheless, meta-heuristics can present some problems, which can be easily solved through a Artificial Neural Network that are computational techniques that present a mathematical model inspired by the neural structure. Only then, through this join, will it be possible to create a hybrid system to correct any meta-heuristic problems. Analyzes were made to study the advantages and disadvantages of each method, as well as an in-depth study with the hybrid system.

Problemas que envolvem a roteirizarão de veículos aparecem frequentemente na área de logística. Um problema clássico é o Problema do Caixeiro Viajante (PCV) que determina a melhor rota para percorrer uma sequência de cidades, visitando todas elas uma única vez, e retornando à cidade inicial. Por se tratar de um problema de otimização combinatória, esse trabalho propõe estratégias de solução denominadas meta-heurísticas. Dessa forma, diferentes técnicas foram estudadas e implementadas, entre elas Algoritmos Genéticos, Busca Tabu e VNS. Apesar disso, as meta-heurísticas podem apresentar alguns problemas, que podem ser facilmente resolvidas através de uma Rede Neural Artificial, que são técnicas computacionais que apresentam um modelo matemático inspirado na estrutura neural. Assim, através desta junção, é possível criar um sistema hibrido para corrigir eventuais problemas das meta-heurísticas. Analises foram feitas para estudar vantagens e desvantagens de cada método, bem como um estudo aprofundado com o sistema híbrido.