3次元のビンパッキング問題の概要
箱詰めの計算は、3次元のビンパッキング問題と呼ばれる問題の1つです。問題の形と、詰め方が見つからないことがある理由を解説します。
問題の形
直方体の外箱と、直方体の荷物がいくつか与えられます。荷物どうしが重ならず、どの荷物も外箱の内側に収まるように、荷物ごとの位置と向きを決めます。BeaglePackの計算は、荷物と外箱を入力された寸法の直方体として扱い、荷物の辺を外箱の辺に沿わせて置きます。
直方体の荷物の置き方は、どの辺を高さにするかと、底の向きとで6通りあります。転倒禁止の荷物は、高さを変えない2通りだけです。
組み合わせが急に増える
荷物を詰める順と、荷物ごとの向きの組み合わせは、荷物の数とともに急に増えます。荷物が10個なら、順の並べ方だけで300万通りを超え、それぞれに向きの組み合わせが掛かります。すべてを試して最も良い詰め方を確かめることは、荷物が増えると現実の時間ではできません。BeaglePackの計算は、決めた時間で打ち切ります。そのため、最も少ない外箱の数や最も高い充填率の詰め方を見つけることは約束しません（利用規約 第4章第1条第1項）。
結果の読み方
- 「詰められます」：全部の荷物を詰めた配置が見つかりました。
- 「入りきりません」：荷物の体積の和が外箱の体積を超えるか、どの向きでも外箱に収まらない荷物があり、入らないと分かりました。
- 「詰め方が見つかりませんでした」：時間内に試し終えましたが、全部を詰めた配置は見つかりませんでした。荷物を置く位置の候補を絞って試すので、入らないことは示しません。
- 「時間内に詰め方が見つかりませんでした」：試し終える前に打ち切りの時間になりました。これも、入らないことは示しません。
どの結果が出やすいかは、荷物の量と外箱の大きさの比（充填率とは）で変わります。