Hyper-GRASP: A Hypervolume-Based Constructive Heuristic

This article proposes a novel constructive heuristic approach, Hyper-GRASP, that integrates the hypervolume indicator and GRASP principles to solve multiobjective combinatorial optimization problems. The approach constructs solutions iteratively by generating and evaluating candidate extensions of the current partial solution, guided by an optimistic bound on the hypervolume contribution of the future complete solution. The most promising extension is selected from a pool according to a parameter α, which balances greediness and exploration during the solution construction phase. Throughout the procedure, only feasible and nondominated solutions are retained. The proposed approach is tested on the multiobjective knapsack problem and the biobjective minimum spanning tree problem to assess its performance. The results show that the best-performing Hyper-GRASP variant effectively approximates the Pareto front across various instances. Moreover, it can also outperform state-of-the-art exact algorithms for the multiobjective knapsack problem as the problem size increases and across various time budgets.