2007年
A path relinking approach for the multi-resource generalized quadratic assignment problem
ENGINEERING STOCHASTIC LOCAL SEARCH ALGORITHMS: DESIGNING, IMPLEMENTING AND ANALYZING EFFECTIVE HEURISTICS
- ,
- ,
- ,
- ,
- ,
- ,
- 巻
- 4638
- 号
- 開始ページ
- 121
- 終了ページ
- +
- 記述言語
- 英語
- 掲載種別
- 出版者・発行元
- SPRINGER-VERLAG BERLIN
We consider the multi-resource generalized quadratic assignment problem (MR-GQAP), which has many applications in various fields such as production scheduling, and constitutes a natural generalization of the generalized quadratic assignment problem (GQAP) and the multi-resource generalized assignment problem (MRGAP). We propose a new algorithm PR-CS for this problem that proves highly effective. PR-CS features a path relinking approach, which is a mechanism for generating new solutions by combining two or more reference solutions. It also features an ejection chain approach, which is embedded in a neighborhood construction to create more complex and powerful moves. Computational comparisons on benchmark instances show that PR-CS is more effective than existing algorithms for GQAP, and is competitive with existing methods for MRGAP, demonstrating the power of PR-CS for handling these special instances of MR-GQAP without incorporating special tailoring to exploit these instances.
- リンク情報
- ID情報
-
- ISSN : 0302-9743
- eISSN : 1611-3349
- Web of Science ID : WOS:000250749700009