A metaheurística colônia de formigas aplicada a um problema de roteamento de veículos : caso da Itaipu Binacioanal

Abstract

Resumo: O problema do roteamento de veículos é um dos problemas mais estudados da área de Pesquisa Operacional, tendo como objetivo designar pontos de paradas a veículos, bem como a determinação da seqüência em que estes pontos de parada serão visitados, estabelecendo assim as rotas para os veículos. Para determinação da solução existem três métodos: os métodos exatos, os métodos aproximativos e os métodos heurísticos ou metaheurísticos. Neste trabalho é proposta uma solução para o transporte de funcionários da empresa Hidrelétrica Itaipu Binacional, localizada no município de Foz do Iguaçu. Para resolver o problema, primeiramente, foi necessária a aplicação do algoritmo das p-Medianas de Teitz e Bart, medianas essas que representam o número de veículos a serem utilizados. Em seguida, aplicou-se o Algoritmo de Designação de Gillet e Johnson Modificado com o objetivo de designar os pontos de parada de cada veículo. Finalmente, o algoritmo de Otimização por Colônias de Formigas aplicado ao Problema do Caixeiro Viajante foi aplicado com a finalidade de determinar a ordem em que os pontos serão visitados, construindo desta maneira as rotas. Os resultados obtidos em comparação com os adotados pela empresa se mostraram melhores.

Abstract: The vehicle routing problem has been largely studied in research operational area aiming to set vehicle stops, as well as the determination of the sequence where the location of stops will be visited, establishing thus the routes of vehicle. There are three methods for the solution: The metaheuristic or heuristic problem, the approaching method and the exact method. This paper presents a solution for the transportation of workers of Itaipu Power Plant, located in Foz do Iguaçu. To solve the problem, firstly, was necessary to apply the algorithm of the p-Median by Teitz and Bart, these medians represents the numbers of vehicle that will be used. Then, was applied the algorithm of designation by Gillet and Johnson modified with the goal of designate the locations of the stop of each vehicle. Finally, the algorithm Ant Colony Optimization applied on the traveling salesman problem was developed to determine the visited points order, constructing this way, the routes. The results obtained in comparison with the adopted ones for the company appear to be better.