MISC

査読有り
2007年

A path relinking approach for the multi-resource generalized quadratic assignment problem

ENGINEERING STOCHASTIC LOCAL SEARCH ALGORITHMS: DESIGNING, IMPLEMENTING AND ANALYZING EFFECTIVE HEURISTICS
  • Mutsunori Yagiura
  • ,
  • Akira Komiya
  • ,
  • Kenya Kojima
  • ,
  • Koji Nonobe
  • ,
  • Hiroshi Nagamochi
  • ,
  • Toshihide Ibaraki
  • ,
  • Fred Glover

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.

リンク情報
Web of Science
https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000250749700009&DestApp=WOS_CPL
ID情報
  • ISSN : 0302-9743
  • eISSN : 1611-3349
  • Web of Science ID : WOS:000250749700009

エクスポート
BibTeX RIS