A very large-scale neighborhood search algorithm for the multi-resource generalized assignment problem

A very large-scale neighborhood search algorithm for the multi-resource generalized assignment problem

0.00 Avg rating0 Votes
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: , , ,
Keywords: heuristics
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.