Meta-heurística híbrida de algoritmo genético e algoritmo vagalume para otimização do problema da colheita florestal

Abstract

RESUMO: O setor florestal brasileiro contribui com cerca de 5% na formação do PIB Nacional e com 8% das exportações; gera uma receita anual de R$ 20 bilhões e recolhe anualmente R$ 3 bilhões de impostos. A colheita florestal, em geral, envolve grandes áreas, e o transporte representa um dos maiores custos operacionais presentes no processo logístico de uma empresa. O planejamento florestal é crucial para a otimização dos custos, pois consiste em encontrar uma solução viável considerando diversos fatores existentes no processo de produção, tais como: distância, número de veículos e tempo de espera. Para solucionar problemas que envolvem otimização de planejamento florestal, frequentemente são utilizadas as meta-heurísticas Algoritmos Genético e Vagalume (firefly). O Algoritmo Genético (GA) utiliza conceitos originários da biologia evolutiva de Charles Darwin para tratar problemas de otimização e busca na computação. O Algoritmo Vagalume baseia-se no comportamento dos vagalumes, imitando comportamentos existentes na natureza como a atração pela emissão luminosa. Entretanto, isoladamente essas meta-heurísticas possuem pressupostos que restringem as soluções que serão avaliadas no espaço de busca o que pode causar um viés na solução. O uso de meta-heurísticas híbridas pode reduzir o viés, possibilitando que o método encontre soluções que não seriam alcançadas usando uma única meta-heurística. Neste trabalho, propomos a otimização do transporte de madeira em uma colheita florestal utilizando uma versão híbrida de duas meta-heurísticas, Algoritmo Genético e Algoritmo Firefly (vagalumes) visando reduzir o viés da solução. Desenvolvemos um modelo heurístico híbrido (GA e Vagalume) que simula um possível conjunto de caminhões que trafegam entre os talhões e a fábrica e um possível conjunto de empilhadeiras que trafegam entre os talhões. O sistema recebe como entrada a distância entre os talhões e a fábrica, a distância entre os talhões e a quantidade de caminhões e empilhadeiras, e retorna o melhor tempo de atendimento e a programação otimizada das empilhadeiras e caminhões. Nas simulações computacionais avaliamos 30 instâncias, divididas em 6 grupos, que buscam analisar as soluções obtidas pela meta-heurística em situações diferentes. Os resultados numéricos mostraram que os algoritmos analisados se adaptaram a diferentes cenários e com tempo computacional viável para instâncias de tamanhos reais. Contudo, apesar de ser o método mais antigo dos métodos analisados, o algoritmo genético obteve o melhor resultado.

ABSTRACT: The Brazilian forestry sector contributes around 5% to the formation of the National GDP and 8% of exports; generates annual revenue of R$20 billion and annually collects R$3 billion in taxes. Forest harvesting, in general, involves large areas, and the transport represents one of the biggest operational costs present in the logistic process of a company. Forest planning is crucial for cost optimization, as it consists of finding a viable solution considering several factors existing in the production process, such as: distance, number of vehicles and waiting time. To solve problems involving optimization of forest planning, the meta-heuristics Genetic Algorithms and Firefly are often used. The Genetic Algorithm (GA) uses concepts from Charles Darwin’s evolutionary biology to solve optimization and search problems in computing. The Firefly Algorithm is based on the behavior of fireflies, imitating behaviors existing in nature, such as attraction to light emission. However, these metaheuristics by themselves have assumptions that restrict the solutions that will be evaluated in the search space, which can cause a bias in the solution. The use of hybrid meta-heuristics can reduce bias, enabling the method to find solutions that would not be achieved using a single meta-heuristic. In this work, we propose the optimization of wood transport in a forest harvest using a hybrid version of two heuristics, Genetic Algorithm and Firefly Algorithm, in order to reduce solution bias. We developed a hybrid heuristic model (GA and Firefly) that simulates a possible set of trucks that travel between the plots and the factory and a possible set of forklifts that travel between the plots. The system receives as input the distance between the plots and the factory, the distance between the plots and the number of trucks and forklifts, and returns the best service time and the optimized schedule of the forklifts and trucks. In computer simulations, we evaluated 30 instances, divided into 6 groups, which seek to analyze the solutions obtained by the meta-heuristic in different situations. Numerical results showed that the analyzed algorithms adapted to different scenarios and with viable computational time for real-sized instances. However, despite being the oldest analyzed method, the genetic algorithm obtained the best result.