Scatter Search with Multiple Improvement Methods for the Linear Ordering Problem

Abstract

In this work, the Linear Ordering Problem (LOP) is approached. This is an NP-hard problem which has been solved with different metaheuristic algorithms. Particularly, it has been solved with a Scatter Search algorithm that applies the traditional approach which incorporates a single improvement method. In this paper, we propose a Scatter Search algorithm which uses multiple improvement methods to achieve a better balance of intensification and diversification. To validate our approach, a statistically-supported experimental study of its performance was carried out using the most challenging standard instances. The overall performance of the proposed Scatter Search algorithm was compared with the state-of-the-art algorithm solution for LOP. The experimental evidence shows that our algorithm outperforms the best algorithm solution for LOP, improving 2.89% the number of best-known solutions obtained, and 71% the average percentage error. It is worth noticing that it obtains 53 new best-known solutions for the instances used. We claim that the combination of multiple improvement methods (local searches) can be applied to improve the balance between intensification and diversification in other metaheuristics to solve LOP and problems in other domain.