Marcelo Maia, Brazilian Institute of Geography and Statistics

Abstract

Pattern mining techniques have been applied to find components that frequently appear together in high-quality solutions to a combinatorial optimization problem, which can support metaheuristics in several ways.

This talk will discuss two approaches that mine frequent paths from high-quality solutions found by vehicle routing metaheuristics and use them to improve the methods' performance.

The first uses the mined patterns to initialize new solutions by inserting their frequent paths in the routes. The other, named MineReduce, uses them to decompose the solving process in two stages: (i) solving a subproblem obtained by contracting their frequent paths and (ii) searching the original solution space using the subproblem solution as starting point. These approaches have recently been applied to the capacitated VRP and the heterogeneous fleet VRP, improving the underlying metaheuristics' solution quality and convergence speed.

[Video]