In the combinatorial optimization field, Knowledge Discovery (KD) mechanisms (e.g., data mining, neural networks) have received increasing interest over the years. KD mechanisms are based upon two main procedures, being the extraction of knowledge from solutions, and the injection of such knowledge into solutions. However, in a multi-objective (MO) context, the simultaneous optimization of many conflicting objectives can lead to the learning of contradictory knowledge. We propose to develop a Solution-based KD (SKD) mechanism suited to MO optimization. It is integrated within two existing metaheuristics: the Iterated MO Local Search (IMOLS) and the MO Evolutionary Algorithm based on Decomposition (MOEA/D). As a case study, we consider a bi-objective Vehicle Routing Problem with Time Windows (bVRPTW), to define accordingly the problem-dependent knowledge of the SKD mechanism. Our experiments show that using the KD mechanism we propose increases the performance of both IMOLS and MOEA/D algorithms.