Combining GRASP and Path-Relinking for Solving the Max-Min Knapsack Problem with Multiple Scenarios
Résumé
In this paper, both greedy randomized search procedure and path-relinking are combined for tackling the max-min knapsack problem with multi-scenarios. The proposed method iterates a building phase and an improvement phase that is based upon an extended search process. The first phase yields a (starting) feasible solution for the problem by applying a greedy randomized search procedure. The second phase tries to enhance each current solution by applying the path-relinking based strategy. Finally, the proposed method is evaluated on a set of benchmark instances taken from the literature. The obtained results are compared to those reached by some best algorithms available in the literature. Encouraging results have been obtained.