| 講演名 | 2005-04-18 矩形パッキング問題に対する厳密解法 剱持 光俊, 今道 貴司, 野々部 宏司, 柳浦 睦憲, 永持 仁, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | ストリップパッキング問題は, 与えられたすべての矩形を互いに重なり合わないように幅の固定された容器に高さが最小となるように詰め込む問題であり, 様々な応用を持つ問題として広く研究されている. 本論文では, 矩形数が比較的小さなストリップパッキング問題に焦点を置き, 厳密解を求めることを目的とする. まず初めに, 順列対と呼ばれる解の表現法を用いて, 分枝限定法により厳密解を探索する. さらに, より制限のある問題として, 完全パッキングと呼ばれる問題を扱う. 完全パッキング問題とは, 与えられたすべての矩形を幅と高さの決まった容器に隙間なく敷き詰めることができるか否かを判定する問題である. この問題に対し, 分枝規則や限定操作を提案し, 分枝限定法を適用することを考える. 提案手法により, 矩形数30以内のベンチマーク問題に対して, 従来手法よりも高速に解を求めることに成功した. |
| 抄録(英) | We examine various strategies for exact approaches to the 2-dimensional strip packing problem (2SP) with and without rotations. We first develop branch-and-bound algorithms based on seqence-pair representation. We then consider the perfect packing problem (PP), which is a special case of 2SP in that it calls for a packing of given rectangles without wasted space, and propose new branching rules and bounding operations in branch-and-bound algorithms for PP. Computationed results on benchmark instances with up to 30 rectangles discloses that one of these rules is very effective especially for feasible instances of PP. |
| キーワード(和) | ストリップパッキング / 分枝限定法 / 厳密解法 / 完全パッキング / 順列対 |
| キーワード(英) | strip packing / branch-and-bound / exact approach / perfect paking / sequence-pair |
| 資料番号 | COMP2005-2 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2005/4/11(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 矩形パッキング問題に対する厳密解法 |
| サブタイトル（和） | |
| タイトル（英） | Exact Algorithms for Two-Dimensional Strip Packing Problems |
| サブタイトル（和） | |
| キーワード(1)（和/英） | ストリップパッキング / strip packing |
| キーワード(2)（和/英） | 分枝限定法 / branch-and-bound |
| キーワード(3)（和/英） | 厳密解法 / exact approach |
| キーワード(4)（和/英） | 完全パッキング / perfect paking |
| キーワード(5)（和/英） | 順列対 / sequence-pair |
| 第 1 著者 氏名（和/英） | 剱持 光俊 / Mitsutoshi KENMOCHI |
| 第 1 著者 所属（和/英） | 京都大学大学院情報学研究科数理工学専攻 Department of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto University |
| 第 2 著者 氏名（和/英） | 今道 貴司 / Takashi IMAMICHI |
| 第 2 著者 所属（和/英） | 京都大学大学院情報学研究科数理工学専攻 Department of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto University |
| 第 3 著者 氏名（和/英） | 野々部 宏司 / Koji NONOBE |
| 第 3 著者 所属（和/英） | 京都大学大学院情報学研究科数理工学専攻 Department of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto University |
| 第 4 著者 氏名（和/英） | 柳浦 睦憲 / Mutsunori YAGIURA |
| 第 4 著者 所属（和/英） | 京都大学大学院情報学研究科数理工学専攻 Department of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto University |
| 第 5 著者 氏名（和/英） | 永持 仁 / Hiroshi NAGAMOCHI |
| 第 5 著者 所属（和/英） | 京都大学大学院情報学研究科数理工学専攻 Department of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto University |
| 発表年月日 | 2005-04-18 |
| 資料番号 | COMP2005-2 |
| 巻番号（vol） | vol.105 |
| 号番号（no） | 7 |
| ページ範囲 | pp.- |
| ページ数 | 10 |
| 発行日 | |