In this paper we propose an adaptation of the GRASP metaheuristic to solve multi-objective 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. In this paper, we propose different hybridizations of GRASP and path-relinking for multi-objective optimization. We apply the proposed GRASP with path-relinking variants to two combinatorial optimization problems, the bi-objective orienteering problem and the bi-objective path dissimilarity problem. We report on empirical tests with 70 instances that show that the proposed heuristics are competitive with the state-of-the-art methods for these problems.
Citation
AT&T Labs Research Technical Report, Florham Park, NJ 07932, June 2011.