| A Very Large-Scale Neighborhood Search Algorithm (2007) | |||||||||||||||||
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 e#ciently 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 e#ective, especially for type D and E instances, which are known to be quite di#cult. | |||||||||||||||||
Publication details | |||||||||||||||||
| |||||||||||||||||