کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
481766 1446119 2010 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Algorithms for the generalized quadratic assignment problem combining Lagrangean decomposition and the Reformulation-Linearization Technique
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
Algorithms for the generalized quadratic assignment problem combining Lagrangean decomposition and the Reformulation-Linearization Technique
چکیده انگلیسی

In this paper, we propose two exact algorithms for the GQAP (generalized quadratic assignment problem). In this problem, given M facilities and N locations, the facility space requirements, the location available space, the facility installation costs, the flows between facilities, and the distance costs between locations, one must assign each facility to exactly one location so that each location has sufficient space for all facilities assigned to it and the sum of the products of the facility flows by the corresponding distance costs plus the sum of the installation costs is minimized. This problem generalizes the well-known quadratic assignment problem (QAP). Both exact algorithms combine a previously proposed branch-and-bound scheme with a new Lagrangean relaxation procedure over a known RLT (Reformulation-Linearization Technique) formulation. We also apply transformational lower bounding techniques to improve the performance of the new procedure. We report detailed experimental results where 19 out of 21 instances with up to 35 facilities are solved in up to a few days of running time. Six of these instances were open.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 206, Issue 1, 1 October 2010, Pages 54–63
نویسندگان
, , , ,