Investigação da adição de métodos de aprendizado e programação matemática em uma arquitetura de hibridização de meta-heurísticas para problemas de otimização com decisões em múltiplos níveis

Abstract

The hybridization of metaheuristics is a topic that several researchers have studied due to its potential to produce more efficient heuristics than those based on a single technique. However, hybridization is not easy, as there are several ways to operationalize it. The task becomes even more challenging when three or more metaheuristic methods need to hybridize or when someone wants to add Mathematical Programming methods, thus creating “matheuristics.” Various methods have been proposed to hybridize metaheuristics, including some techniques that automate hybridization, such as multi-agent architectures. A few of these architectures use learning techniques, and an even smaller number deal with matheuristics. This work extends the capabilities of the Multi-agent Architecture for Metaheuristic Hybridization by including learning techniques and Mathematical Programming. The application of learning techniques is innovative, considering the agents’ choice of heuristics to apply at different search stages. This work proposes a new form of hierarchical hybridization for Combinatorial Optimization problems with multiple decision levels. The algorithmic proposals are tested on the Traveling Car Renter with Passengers and the Cable Routing Problem in Wind Farms. These problems belong to the NP-hard class and require decision-making at multiple levels. In the case of the Traveling Car Renter with Passengers, there are three decision levels: route, car types, and customers’ transport demand. Cable routing in wind farms requires decisions concerning the cable locations and the cable type used in each section. The experiments for the Traveling Car Renter with Passengers were conducted on three classes of instances, totaling ninety-nine test cases ranging from four to eighty cities, two to five vehicles, and ten to a hundred forty people requiring transportation. Experiments for The Cable Routing Problem in Wind Farms involved a set of two hundred instances. These instances are simulations of real situations developed in collaboration with domain experts. The approaches proposed in this work are compared to state-of-the-art algorithms for both problems.