Metaheuristics for the linear ordering problem with cumulative costs. Duarte, A., Martí, R., Álvarez, A., & Ángel-Bello, F. European Journal of Operational Research, 216(2):270-277, Elsevier B.V., 1, 2012.
Metaheuristics for the linear ordering problem with cumulative costs [pdf]Paper  Metaheuristics for the linear ordering problem with cumulative costs [link]Website  abstract   bibtex   
The linear ordering problem with cumulative costs (LOPCC) is a variant of the well-known linear ordering problem, in which a cumulative propagation makes the objective function highly non-linear. The LOPCC has been recently introduced in the context of mobile-phone telecommunications. In this paper we propose two metaheuristic methods for this NP-hard problem. The first one is based on the GRASP methodology, while the second one implements an Iterated Greedy-Strategic Oscillation procedure. We also propose a post-processing based on Path Relinking to obtain improved outcomes. We compare our methods with the state-of-the-art procedures on a set of 218 previously reported instances. The comparison favors the Iterated Greedy - Strategic Oscillation with the Path Relinking post-processing, which is able to identify 87 new best objective function values. © 2011 Elsevier B.V. All rights reserved.

Downloads: 0