Metaheuristics for the linear ordering problem with cumulative costs
by Abraham Duarte, Rafael Martí, Ada Álvarez and Francisco Ángel-Bell
Abstract
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.
@article{duarte.marti.ea:2012,
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",
}
