| 大会名称 |
|---|
| 2009年 情報科学技術フォーラム(FIT) |
| 大会コ－ド |
| F |
| 開催年 |
| 2009 |
| 発行日 |
| 2009/8/20 |
| セッション番号 |
| 4A |
| セッション名 |
| 最適化 |
| 講演日 |
| 2009/09/03 |
| 講演場所(会議室等) |
| A会場（9号館1F 911教室） |
| 講演番号 |
| A-017 |
| タイトル |
| 厳密解法と発見的手法の組合せによるサイズ可変ビンパッキング問題の解法 |
| 著者名 |
| 三橋 一郎, 大山口 通夫, 野呂 耕三, |
| キーワード |
| サイズ可変ビンパッキング問題, 組合せ最適化, 分枝限定法, 組込み法 |
| 抄録 |
|
ビンパッキング問題とは,与えられたアイテムをビン（箱）につめる際に 使用するビンの数を最小化する問題である. サイズ可変ビンパッキング問題とは,サイズの違うビンが複数種類存在し, すべてのアイテムをつめたときのビンのサイズの総和を最小化する問題である. これらの問題は,建築資材から部材を切り出すときの計画作成など 産業的に非常に大きな意味を持つ問題であるが, NP困難問題であることが知られており, 入力の規模が大きいと最適解を計算することが困難になる. 理論的な近似精度の解析を伴う近似アルゴリズムがこれまでにいくつか提案されているが, 本研究では現実的な入力に対して高精度な解を高速に計算することを目的とし, 厳密解法と発見的手法を組み合わせた新しいアルゴリズムを提案する. |
| 本文pdf |
| PDF download (117.8KB) |