配置コストをもつ長方形詰込み問題に対する局所探索法の高速化

• Item type: SIG Technical Reports(1)
• 公開日: 2002-11-08
• タイトル: 配置コストをもつ長方形詰込み問題に対する局所探索法の高速化
• タイトル / 言語: en
• タイトル: Improved Local Search Algorithms for the Rectangle Packing Problem with General Spatial Costs
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 京都大学大学院情報学研究科
• 著者所属: 京都大学大学院情報学研究科
• 著者所属: 京都大学大学院情報学研究科
• 著者所属(英): en
• 著者所属(英): Graduate School of Informatics, Kyoto University
• 著者所属(英): en
• 著者所属(英): Graduate School of Informatics, Kyoto University
• 著者所属(英): en
• 著者所属(英): Graduate School of Informatics, Kyoto University
• 著者名: 今堀, 慎治; 柳浦睦憲; 茨木, 俊秀
• 著者名(英): Shinji, Imahori; Mutsunori, Yagiura; Toshihide, Ibaraki
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 長方形詰込み問題とは 様々な大きさの長方形を二次元平面上に互いに重ならないように配置する問題であり NP 困難であることが知られている.我々は 以前この問題に一般的な配置コストを導入し 局所探索法に基づくアルゴリズムを提案した.この問題は非常に汎用的であり 様々な配置問題やスケジューリング問題を扱うことが可能である.また 提案アルゴリズムの特徴として 順列対表現を用いて解を表現し 低次の多項式時間で順列対から配置を求めるという点が挙げられる.本研究では このアルゴリズムをもとに 局所探索における様々な近傍において 解一つ当りの評価を高速に行う手法を提案する.配置問題や実際のスケジューリング問題を用いた数値実験を行い 提案手法が従来のアルゴリズムと比較して優れていることを確認した.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: The rectangle packing problem with general spatial costs is to pack given rectangles without overlap in the plane so that the maximum cost of the rectangles is minimized. This problem is very general, and various types of packing problems and scheduling problems can be formulated in this form. For this problem, we had proposed local search algorithms which used a pair of permutations of rectangles to represent a solution. In this paper, we propose new speed-up techniques to evaluate solutions in various neighborhoods, and report computational results for two types of problems, one is that of area minimization and the other is taken from real-world scheduling, which exhibit good prospects of the proposed techniques.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 2002, 号 103(2002-AL-087), p. 51-58, 発行日 2002-11-08
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会