Extending the hybridization of metaheuristics with data mining: Dealing with sequences

Abstract

The scope of this work is the application of data mining techniques to improve the performance of metaheuristics in the combinatorial optimization scenario. Data mining techniques have been coupled with metaheuristics in order to obtain patterns of suboptimal solutions that are used to guide the heuristic search for better-cost solutions in less computational time. This kind of hybridization has been successfully explored to solve several optimization problems, for which the solutions and their patterns are limitedly characterized by sets of elements. The challenge of this work is to extend this hybrid approach to a broader domain. We therefore propose a hybrid data mining heuristic to solve the one-commodity pickup-and-delivery traveling salesman problem, for which solutions are defined by sequences of elements. Computational experiments, conducted on a set of instances from the literature, showed that the hybrid heuristic reached better-costs solutions faster than the original strategy. This way, it was evidenced that not only problems whose solutions are represented by sets of elements can benefit from the hybridization of metaheuristics with data mining, but also problems whose solutions are represented by a sequence of elements.