Investigation of the Benefit of Extracting Patterns from Local Optima to Solve a Bi-objective VRPTW

Hybridizing learning and optimization often improves existing algorithms in single-objective optimization. Indeed, high-quality solutions often contain relevant knowledge that can be used to guide the heuristic towards promising areas. Learning from the structure of solutions is challenging in combinatorial problems. Most of the time, local optima are considered for this task since they tend to contain more relevant structural information. If local optima generally contain more interesting information than other solutions, producing them requires a time-consuming process. In this paper, we study the benefits of learning from local optima during the execution of a multi-objective algorithm. To this end, we consider a hybridized MOEA/D (a multi-objective genetic algorithm) with a knowledge discovery mechanism adapted to the problem solved and we conduct experiments on a bi-objective vehicle routing problem with time windows. The knowledge discovery mechanism extracts sequences of customers from solutions. The results show the benefit of using different strategies for the components of the knowledge discovery mechanism and the efficacy of extracting patterns from local optima for larger instances. An analysis of speed-up performance gives deeper conclusions about the use of local optima.