Multiobjective GRASP with Path Relinking

作者：Marti Rafael^*; Campos Vicente; Resende Mauricio G C; Duarte Abraham

来源：European Journal of Operational Research, 2015, 240(1): 54-71.

DOI：10.1016/j.ejor.2014.06.042

• Multiobjective optimization
• Biobjective optimization
• GRASP
• Path Relinking

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.

• 出版日期2015-1-1
• 单位AT&T Labs