Local search-based heuristics for the multiobjective multidimensional knapsack problem
AUTOR(ES)
Vianna, Dalessandro Soares, Vianna, Marcilene de Fátima Dianin
FONTE
Prod.
DATA DE PUBLICAÇÃO
30/10/2012
RESUMO
In real optimization problems it is generally desirable to optimize more than one performance criterion (or objective) at the same time. The goal of the multiobjective combinatorial optimization (MOCO) is to optimize simultaneously r > 1 objectives. As in the single-objective case, the use of heuristic/metaheuristic techniques seems to be the most promising approach to MOCO problems because of their efficiency, generality and relative simplicity of implementation. In this work, we develop algorithms based on Greedy Randomized Adaptive Search Procedure (GRASP) and Iterated Local Search (ILS) metaheuristics for the multiobjective knapsack problem. Computational experiments on benchmark instances show that the proposed algorithms are very robust and outperform other heuristics in terms of solution quality and running times.
Documentos Relacionados
- An algorithm for determining the K-best solutions of the one-dimensional Knapsack problem
- STOCHASTIC KNAPSACK PROBLEM: APPLICATION TO TRANSPORTATION PROBLEMS
- THE MULTIDIMENSIONAL PREDICTION PROBLEM*
- The Compartmentalized Knapsack Problem
- A SURVEY ON HEURISTICS FOR THE TWO-DIMENSIONAL RECTANGULAR STRIP PACKING PROBLEM