| 講演名 | 2017-12-15 多面体パッキング問題のための探索手法の高速化 松下 豊(東京農工大), 藤吉 邦洋(東京農工大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 多面体パッキング問題とは、x,y,zのいずれかの軸に垂直な面のみからなる複数の多面体を互いに重なり合うことなく最も体積の小さい直方体内に配置するという問題である。矩形パッキングを多角形パッキングに拡張した技術を用いることで、直方体パッキングの表現方法であるSequence-Quintuple (SQ)を多面体パッキングに拡張し焼きなまし法などで探索する方法が提案されたが、多面体に拡張すると、対応する配置がない非許容SQを解空間に多く含んでしまい、探索に時間がかかってしまう。そこで、本稿では、閉路の検出を効率良く行い非許容SQを高速に判定し除去する手法と、多角形配置で提案された効率化を多面体に拡張し、非許容SQを高速に判定し除去する手法と、制約グラフの節点を部分直方体でなく多面体に対応させSQに基づく配置を得る時間を短縮する手法を提案する。これらの提案手法を焼きなまし法に組み込み、実験によりその有効性を確かめた。 |
| 抄録(英) | Polyhedral packing problem is to pack given polyhedrons consisting of only planes perpendicular to one of x, y or z in a rectangular box of the minimum volume without overlapping each other. Polyhedral packing represented by Sequence-Quintuple, which is a representation of rectangular box packing, was proposed by using a technique to extend rectangle packing to rectilinear polygon packing. However, solution space includes a lot of SQs with no corresponding packing(infeasible), so that it takes a lot of time to search the solution space for good packing. By extending the method proposed for rectilinear packing to polyhedron, this paper proposes a method to judge quickly and a method to speed up the decode time of SQ. Experiments show the effectiveness of these proposed methods implemented with Simulated Annealing. |
| キーワード(和) | 多面体パッキング / sequence-quintuple / sequence-pair / 多角形パッキング / 焼きなまし法 |
| キーワード(英) | Polyhedral Packing / sequence-quintuple / sequence-pair / Rectilinear Packing / Simulated Annealing |
| 資料番号 | CAS2017-108,ICD2017-96,CPSY2017-105 |
| 発行日 | 2017-12-07 (CAS, ICD, CPSY) |
| 研究会情報 | |
| 研究会 | ICD / CPSY / CAS |
|---|---|
| 開催期間 | 2017/12/14(から2日開催) |
| 開催地（和） | アートホテル石垣島 |
| 開催地（英） | Art Hotel Ishigakijima |
| テーマ（和） | 学生・若手研究会 |
| テーマ（英） | |
| 委員長氏名（和） | 日高 秀人(ルネサス エレクトロニクス) / 中野 浩嗣(広島大) / 平木 充(ルネサス エレクトロニクス) |
| 委員長氏名（英） | Hideto Hidaka(Renesas) / Koji Nakano(Hiroshima Univ.) / Mitsuru Hiraki(Renesas) |
| 副委員長氏名（和） | 永田 真(神戸大) / 入江 英嗣(東大) / 三吉 貴史(富士通研) / 岡崎 秀晃(湘南工科大) |
| 副委員長氏名（英） | Makoto Nagata(Kobe Univ.) / Hidetsugu Irie(Univ. of Tokyo) / Takashi Miyoshi(Fujitsu) / Hideaki Okazaki(Shonan Inst. of Tech.) |
| 幹事氏名（和） | 高宮 真(東大) / 橋本 隆(パナソニック) / 大川 猛(宇都宮大) / 高前田 伸也(北大) / 山口 基(ルネサスシステムデザイン) / 橘 俊宏(湘南工科大) |
| 幹事氏名（英） | Makoto Takamiya(Univ. of Tokyo) / Takashi Hashimoto(Panasonic) / Takeshi Ohkawa(Utsunomiya Univ.) / Shinya Takameda(Hokkaido Univ.) / Motoi Yamaguchi(Renesas) / Toshihiro Tachibana(Shonan Inst. of Tech.) |
| 幹事補佐氏名（和） | 夏井 雅典(東北大) / 柘植 政利(ソシオネクスト) / 伊藤 浩之(東工大) / 範 公可(電通大) / 伊藤 靖朗(広島大) / 津邑 公暁(名工大) / 中村 洋平(日立) |
| 幹事補佐氏名（英） | Masanori Natsui(Tohoku Univ.) / Masatoshi Tsuge(Socionext) / Hiroyuki Ito(Tokyo Inst. of Tech.) / Pham Konkuha(Univ. of Electro-Comm.) / Yasuaki Ito(Hiroshima Univ.) / Tomoaki Tsumura(Nagoya Inst. of Tech.) / Yohei Nakamura(Hitachi) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Integrated Circuits and Devices / Technical Committee on Computer Systems / Technical Committee on Circuits and Systems |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 多面体パッキング問題のための探索手法の高速化 |
| サブタイトル（和） | |
| タイトル（英） | A faster searching method for polyhedral packing problem |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 多面体パッキング / Polyhedral Packing |
| キーワード(2)（和/英） | sequence-quintuple / sequence-quintuple |
| キーワード(3)（和/英） | sequence-pair / sequence-pair |
| キーワード(4)（和/英） | 多角形パッキング / Rectilinear Packing |
| キーワード(5)（和/英） | 焼きなまし法 / Simulated Annealing |
| 第 1 著者 氏名（和/英） | 松下 豊 / Yutaka Matsushita |
| 第 1 著者 所属（和/英） | 東京農工大学(略称：東京農工大) Tokyo University of Agriculture and Technology(略称：TUAT) |
| 第 2 著者 氏名（和/英） | 藤吉 邦洋 / Kunihiro Fujiyoshi |
| 第 2 著者 所属（和/英） | 東京農工大学(略称：東京農工大) Tokyo University of Agriculture and Technology(略称：TUAT) |
| 発表年月日 | 2017-12-15 |
| 資料番号 | CAS2017-108,ICD2017-96,CPSY2017-105 |
| 巻番号（vol） | vol.117 |
| 号番号（no） | CAS-343,ICD-344,CPSY-345 |
| ページ範囲 | pp.181-186(CAS), pp.181-186(ICD), pp.181-186(CPSY), |
| ページ数 | 6 |
| 発行日 | 2017-12-07 (CAS, ICD, CPSY) |