EU/ME - the metaheuristics community

  • Increase font size
  • Default font size
  • Decrease font size

EJOR 216(2), 2012

E-mail Print PDF

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  


EU/ME 2017

Submit now your abstract.

Metaheuristics Events

<<  November 2017  >>
 Mo  Tu  We  Th  Fr  Sa  Su 
    1  2  3  4  5
  6  7  8  9101112

Who's Online

We have 166 guests online