GREEVO : a grasp ensemble evolutionary algorithm for the capacitated vehicle routing problem

Abstract

Resumo: Desastres, naturais ou não, causam muitos danos em seu entorno. Em geral, afetam edificações, geram impactos negativos na economia e resultam em perda de vidas. Para minimizar e diminuir os efeitos causados por estes, planos de evacuação eficientes e eficazes são essenciais. Nesse sentido, o processo de evacuação pode ser modelado de acordo com um Problema de Roteamento de Veículos (PRV). Este tipo de problema é um problema NP-difícil de otimização combinatorial, que visa minimizar o custo total (em geral, distância percorrida) na utilização de uma frota de veículos para a realização de um determinado serviço. Portanto, em problemas de otimização combinatória, como PRV, metaheurísticas podem obter soluções ótimas ou quase ótimas. No contexto do PRV, muitas abordagens com metaheurística foram propostas nos últimos anos. Algumas dessas abordagens apresentam excelentes desempenhos, tanto em termos de tempo de processamento quanto de qualidade da solução. Recentemente, as técnicas de ensemble têm chamado a atenção de pesquisadores de outros problemas de otimização combinatorial. As técnicas de ensemble podem tirar vantagem de metaheurísticas robustas existentes através de um mecanismo de seleção inteligente. Desta forma, este trabalho apresenta, diferenciando-se das metodologias convencionais de ensemble, uma abordagem chamada GREEVO (Greedy Randomized Adaptive Search Procedure Ensemble Evolutionary Algorithm) para resolver o Problema de Roteamento de Veículos com Capacitade (CVRP). Nossa abordagem combina um GRASP com o algoritmo Split e usa uma Hiper-Heurística com Aprendizagem por Reforço para selecionar heurísticas de alto nível no ensemble. Nossos experimentos em benchmarks populares da literatura e um estudo de caso mostraram que nossa abordagem supera outras abordagens comparadas, ao mesmo tempo que fornece insights valiosos sobre como utilizar conjuntos e componentes de aprendizado de máquina.

Abstract: Disasters, natural or not, cause a lot of damage to their surroundings. In general, they affect buildings, generate negative impacts on the economy, and result in loss of life. In order to minimize and decrease the effects caused by these, efficient and effective evacuation plans are essential. In this sense, the evacuation process can be modeled according to a Vehicle Routing Problem (VRP). This kind of problem is an NP-hard problem of combinatorial optimization, which aims to minimize the total cost (in general, distance covered) in the use of a vehicle fleet to perform a particular service. Therefore, in combinatorial optimization problems such as VRPs, metaheuristics can obtain optimal or near-optimal solutions. In the VRP context, many approaches that use metaheuristics have been proposed over the past few years. Some of those approaches have excellent performances, both in terms of processing time and quality of the solution. Recently, ensemble techniques have drawn the attention of researchers to other combinatorial optimization problems. Ensemble techniques can take advantage of robust metaheuristics existing through an intelligent selection mechanism. Thus, this work presents, distinguishing from the conventional ensemble methodologies, an approach called GREEVO (Greedy Randomized Adaptive Search Procedure Ensemble Evolutionary Algorithm) to address the Capacitated Vehicle Routing Problem (CVRP). Our approach combines a GRASP with the Split algorithm and uses a Hyper-Heuristic with Reinforcement Learning to select high-level heuristics in the ensemble. Our experiments on the popular literature benchmarks and a case study have shown that our approach outperforms other compared approaches while providing valuable insights on how to utilize ensembles and machine learning components.