EJOR 216(2), 2012

Monday, 03 October 2011 14:23 Marc Sevaux

Metaheuristics for the linear ordering problem with cumulative costs

by Abraham Duarte, Rafael Martí, Ada Álvarez and Francisco Ángel-Bell


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.

Keywords: Combinatorial optimization; Metaheuristics; Linear ordering problem

Read this article now.

  title = "Metaheuristics for the linear ordering problem with cumulative costs",
  journal = "European Journal of Operational Research",
  author = "Abraham Duarte and Rafael Martí and Ada Álvarez and Francisco Ángel-Bello"
  volume = "216",
  number = "2",
  pages = "270 - 277",
  year = "2012",

Last Updated on Friday, 07 October 2011 06:09