6533b858fe1ef96bd12b571e

RESEARCH PRODUCT

Multiobjective GRASP with Path Relinking

Vicente CamposAbraham DuarteRafael MartíMauricio G. C. Resende

subject

TheoryofComputation_MISCELLANEOUSMathematical optimizationInformation Systems and ManagementGeneral Computer ScienceBiobjective optimizationGRASPCombinatorial optimization problemOrienteeringManagement Science and Operations ResearchMulti-objective optimizationIndustrial and Manufacturing EngineeringModeling and SimulationPath (graph theory)HeuristicsMetaheuristicMathematics

description

In this paper we review and propose different adaptations of the GRASP metaheuristic to solve multiobjective combinatorial optimization problems. In particular, we describe several alternatives to specialize the construction and improvement components of GRASP when two or more objectives are considered. GRASP has been successfully coupled with Path Relinking for single-objective optimization. Moreover, we propose different hybridizations of GRASP and Path Relinking for multiobjective optimization. We apply the proposed GRASP with Path Relinking variants to two combinatorial optimization problems, the biobjective orienteering problem and the biobjective path dissimilarity problem. We report on empirical tests with 70 instances and 30 algorithms, that show that the proposed heuristics are competitive with the state-of-the-art methods for these problems.

yearjournalcountryeditionlanguage
2015-01-01European Journal of Operational Research
https://doi.org/10.1016/j.ejor.2014.06.042