کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
1141564 957025 2009 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Local search intensified: Very large-scale variable neighborhood search for the multi-resource generalized assignment problem
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات کنترل و بهینه سازی
پیش نمایش صفحه اول مقاله
Local search intensified: Very large-scale variable neighborhood search for the multi-resource generalized assignment problem
چکیده انگلیسی

We introduce a heuristic for the Multi-Resource Generalized Assignment Problem (MRGAP) based on the concepts of Very Large-Scale Neighborhood Search and Variable Neighborhood Search. The heuristic is a simplified version of the Very Large-Scale Variable Neighborhood Search for the Generalized Assignment Problem. Our algorithm can be viewed as a kk-exchange heuristic; but unlike traditional kk-exchange algorithms, we choose larger values of kk resulting in neighborhoods of very large size with high probability. Searching this large neighborhood (approximately) amounts to solving a sequence of smaller MRGAPs either by exact algorithms or by heuristics. Computational results on benchmark test problems are presented. We obtained improved solutions for many instances compared to some of the best known heuristics for the MRGAP within reasonable running time. The central idea of our heuristic can be used to develop efficient heuristics for other hard combinatorial optimization problems as well.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Optimization - Volume 6, Issue 4, November 2009, Pages 370–377
نویسندگان
, ,