Metaheuristics for the linear ordering problem with cumulative costs
Metaheuristics for the linear ordering problem with cumulative costs
复制标题
具有累积成本的线性排序问题的元启发法
DOI：
10.1016/j.ejor.2011.07.036
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
F. Ángel
中科院分区：
文献类型：
--
作者：
A. Duarte;R. Martí;A. Alvarez;F. Ángel
具有累积成本的线性排序问题(LOPCC)是著名的线性排序问题的一种变体，其中累积传播使得目标函数高度非线性。最近在移动电话电信的背景下引入了LOPCC。本文针对这一NP-Hard问题提出了两种元启发式算法。第一种方法基于GRASH方法，而第二种方法实现了迭代的贪婪-战略振荡过程。我们还提出了一种基于路径重链接的后处理方法，以获得更好的结果。我们将我们的方法与之前报道的218个实例的最先进的程序进行了比较。比较结果表明，迭代贪婪-策略振荡算法与路径重链接后处理算法相比，能够识别出87个新的最佳目标函数值。
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.