It is an old claim that, in order to design a (meta)heuristic algorithm for solving a given optimization problem, algorithm designers need first to gain a deep insight into the structure of the problem. Nevertheless, in recent years, we have seen an incredible rise of “new” meta-heuristic paradigms that have been applied to any type of optimization problem without even considering the features of these problems. In this work, we put this initial claim into practice and try to solve a classical permutation problem: the Linear Ordering Problem (LOP). To that end, first, we study the structure of the LOP by focusing on the relation between the pairwise precedences of items in the solution and its objective value. In a second step, we design a new meta-heuristic scheme, namely CD-RVNS, that incorporates critical information about the problem in its three key algorithmic components: a variable neighborhood search algorithm, a construction heuristic, and a destruction procedure. Conducted experiments, on the most challenging LOP instances available in the literature, reveal an outstanding performance when compared to existing algorithms. Moreover, we also demonstrate (experimentally) that the developed heuristic procedures perform individually better than their state-of-the-art counterparts.