包装

問題のパッキングpackingの目的は、指定されたサイズのアイテムのセットを、固定されたpackingを持つコンテナにパッキングする最適な方法を見つけることです。一般的なアプリケーションは、配送トラックに効率的に箱を積み込むことです。容量の制約により、すべてのアイテムを梱包できないことがよくあります。その場合、問題はコンテナに収まる最大合計サイズを持つアイテムのサブセットを見つけることです。

梱包の問題にはさまざまな種類があります。最も重要なのは、ナップサックの問題とビンパッキングの 2 つです。

ナップサックに関する問題

単純なナプサックの問題では、コンテナが 1 つ（ナプサック）になります。アイテムには値とサイズがあり、合計値が最大であるアイテムのサブセットをパックすることが目標です。

値がサイズに等しい特別なケースでは、パックされたアイテムの合計サイズを最大化することが目標です。

OR-Tools のアルゴリズム ライブラリには、ナプサックの問題に対する解法がいくつか用意されています。

ナプサックの問題には、より一般的なバージョンもあります。次に例を示します。

• 多次元ナップサック問題。アイテムに複数の物理量（重量や体積など）があり、ナップサックには数量ごとの容量があります。ここで言う「寸法」という用語は、必ずしも高さ、長さ、幅の通常の空間次元を指すものではありません。ただし、長方形のボックスを長方形のストレージビンにパッキングする最適な方法を見つけるなど、空間寸法に関する問題もあります。

• 複数のナプサックの問題。複数のナプサックがあり、すべてのナプサックに収められたアイテムの合計価値を最大化することが目標です。

1 つのナップサックに関する多次元問題や、1 つの次元のみに関する複数のナプサックの問題が発生する可能性があります。

ビンパッキング問題

パッキングの問題としてよく知られているものの一つがビンパッキングです。ビンパッキングでは、容量が等しい複数のコンテナ（ビンと呼ばれます）があります。bin-packingbin-packing複数ナプサックの問題とは異なり、ビンの数は固定されていません。その代わりに、すべてのアイテムを保持する最小数のビンを見つけることが目標です。

以下に、複数ナプサックの問題とビンパッキングの問題の違いを示す簡単な例を示します。ある会社が配達トラックを運用しており、各トラックの耐荷重は 18,000 ポンド、荷重は 130,000 ポンドです。

• 複数のナップサック: トラックが 5 台あり、それらに最大の重量があるアイテムのサブセットを読み込むとします。

• ビンパッキング: トラックが 20 台あり（すべての品物を収納するのに十分な数以上）あり、すべてを収納できる最小限のトラックを使用するとします。

以下のセクションでは、OR-Tools を使用してさまざまな種類のパッキング問題を解決する方法について説明します。まず、ナップサックの問題について説明します。