A Very Large-Scale Neighborhood Search Algorithm
for the Multi-Resource Generalized Assignment Problem
Mutsunori Yagiura, Shinji Iwasaki, Toshihide Ibaraki and Fred Glover
We propose a metaheuristic algorithm for the multi-resource generalized
assignment problem (MRGAP). MRGAP is a generalization of the generalized
assignment problem, which is one of the representative combinatorial
optimization problems known to be NP-hard.
The algorithm features a very large-scale neighborhood search, which is
a mechanism of conducting the search with complex and powerful moves,
where the resulting neighborhood is efficiently searched via the
improvement graph. We also incorporate an adaptive mechanism for
adjusting search parameters, to maintain a balance between visits to
feasible and infeasible regions.
Computational comparisons on benchmark instances show that the method is
effective, especially for type D and E instances, which are known to be quite
multi-resource generalized assignment problem,
very large-scale neighborhood search,
adaptive parameter adjustment,
Discrete Optimization, 1 (2004) 87-98.
Back to the Paper List