A Memetic Algorithm for the Linear Ordering Problem with Cumulative Costs
This work addresses an optimization problem in operations research, but it is incremental as it builds on existing methods for this specific domain.
The authors tackled the linear ordering problem with cumulative costs by developing a memetic algorithm that combines order-based recombination with improved local search, achieving competitive results by identifying 46 new upper bounds on 118 benchmark instances.
This paper introduces an effective memetic algorithm for the linear ordering problem with cumulative costs. The proposed algorithm combines an order-based recombination operator with an improved forward-backward local search procedure and employs a solution quality based replacement criterion for pool updating. Extensive experiments on 118 well-known benchmark instances show that the proposed algorithm achieves competitive results by identifying 46 new upper bounds. Furthermore, some critical ingredients of our algorithm are analyzed to understand the source of its performance.