Iterated Local search for the Linear Ordering Problem

This paper addresses the linear ordering problem, which has been solved using different metaheuristics approaches. These algorithms have the common problem of finding a proper balance of the intensification and diversification processes; in this work we propose an iterated local search in which it is incorporated a Becker heuristic strategy for constructing the initial solution, and a search strategy as perturbation process, achieving a better balance between intensification and diversification. The proposed algorithm obtained an improvement greater than 90%, decreasing the average percentage error respect the state of art ILS algorithm. The Wilcoxon nonparametric statistical test shows that the proposed algorithm significantly outperforms the iterated local search solution of the state of the art, ranking it among the top five solutions of the state of the art for the linear ordering problem.