6533b820fe1ef96bd1279930
RESEARCH PRODUCT
Metaheuristics for the linear ordering problem with cumulative costs
Francisco ÁNgel-belloRafael MartíAbraham DuarteAda Alvarezsubject
Mathematical optimizationInformation Systems and ManagementGeneral Computer ScienceOscillationGRASPContext (language use)Management Science and Operations ResearchIndustrial and Manufacturing EngineeringSet (abstract data type)Iterated functionModeling and SimulationPath (graph theory)Combinatorial optimizationMetaheuristicMathematicsdescription
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.
year | journal | country | edition | language |
---|---|---|---|---|
2012-01-01 | European Journal of Operational Research |