Article ID: | iaor2005375 |
Country: | Netherlands |
Volume: | 1 |
Issue: | 1 |
Start Page Number: | 87 |
End Page Number: | 98 |
Publication Date: | Jun 2004 |
Journal: | Discrete Optimization |
Authors: | Glover Fred, Ibaraki Toshihide, Yagiura Mutsunori, Iwasaki Shinji |
Keywords: | heuristics |
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 types D and E instances, which are known to be quite difficult.