物流会社で働いていたときに、同様のプログラムを作成しました。これは 3 次元のビン パッキング問題であり、古典的な 1 次元のビン パッキング問題よりも少しトリッキーです。私が置き換えようとしていた古いボックス パッキング プログラムを書いた私の職場の人は、すべてを減らすという間違いを犯しました。を 1 次元のビンパッキング問題 (箱の体積とパッケージの体積) に変換しますが、これは機能しません。この問題の定式化では、8x8x8 のパッケージ 3 つが 12x12x12 のボックスに収まると述べていますが、これではパッケージが重なってしまいます。
私の解決策は、ギロチン カット ヒューリスティックと呼ばれるものを使用することでした。パッケージを輸送用コンテナに入れると、3 つの新しい空のサブコンテナが生成されます。パッケージをコンテナの左下に置いたと仮定すると、次のようになります。パッケージの前のスペースに新しい空のサブコンテナ、パッケージの右側のスペースに新しい空のサブコンテナ、パッケージの上に新しい空のサブコンテナ。同じ空きスペースを複数のサブコンテナに割り当てないように注意してください。たとえば、注意を怠ると、コンテナの右前のセクションを前のサブコンテナと右のサブコンテナに割り当ててしまいます。 、割り当て先を 1 つだけ選択する必要があります。このヒューリスティックはいくつかの最適解を除外しますが、高速です。（具体例として、たとえば、12x12x12 のボックスに 8x8x8 のパッケージを入れたとします。これにより、4x12x12 の空のサブコンテナ、4x8x12 の空のサブコンテナ、4x8x8 の空のサブコンテナが残ります。注意してください空き領域を分割する間違った方法は、3 つの 4x12x12 の空のサブコンテナーを持つことです。これにより、パッケージが重複することになります。ボックスまたはパッケージが立方体でない場合、空きスペースを分割する方法は複数あります。1 つまたは 2 つのサブコンテナーのサイズを最大化するか、代わりに 3 つのサブコンテナーを作成するかを決定する必要があります。サブコンテナの順序付け/選択には妥当な基準を使用する必要があります。そうしないと、サブコンテナの数が指数関数的に増加します。この問題を解決するには、最初に最小のサブコンテナを充填し、小さすぎてパッケージを収容できないサブコンテナを削除しました。これにより、サブコンテナの量が妥当な数に保たれました。
いくつかのオプションがあります: 使用するコンテナー、コンテナーに入るパッケージをローテーションする方法 (通常、パッケージをローテーションするには 6 つの方法がありますが、一部のパッケージではすべてのローテーションが有効であるとは限りません。サブコンテナをどのように分割するか (例えば、オーバーラップするスペースを右側のサブコンテナに割り当てるか、前のサブコンテナに割り当てるか)、およびコンテナを梱包する順序。最適な減少ヒューリスティック (ヒューリスティックにはボリュームを使用) に近似するランダム化されたアルゴリズムを使用し、3 つの中サイズのサブコンテナーよりも 1 つの大きなサブコンテナーと 2 つの小さなサブコンテナーを作成することを好みましたが、ランダムなアルゴリズムを使用しました。数ジェネレーターを使用して物事を混同します (したがって、最大のパッケージを最初に選択する可能性が最も高く、しかし、2 番目に大きいパッケージを最初に選択する可能性は低くなり、以下同様に、最小のパッケージを最初に選択する可能性が最も低くなります。同様に、大 1 つと小 2 つではなく 3 つの中サイズのサブコンテナーを作成することを好む可能性がありました。また、2 つの大きなボックスの代わりに 3 つの中サイズのボックスを使用する可能性もありました。次に、これを数十回並行して実行し、コストが最も低い結果を選択しました。d 大きな箱 2 つではなく、中型の箱 3 つを使用するなど）。次に、これを数十回並行して実行し、コストが最も低い結果を選択しました。d 大きな箱 2 つではなく、中型の箱 3 つを使用するなど）。次に、これを数十回並行して実行し、コストが最も低い結果を選択しました。
私が検討した他のヒューリスティックがあります。たとえば、極値ヒューリスティックは低速です (まだ多項式時間で実行されていますが、IIRC は立方時間のソリューションですが、ギロチン カット ヒューリスティックは線形時間であり、他の極値では分岐限定アルゴリズムが検出します指数時間で実行されます) しかし、より正確です (具体的には、ギロチン カット ヒューリスティックによって除外されるいくつかの最適解を見つけます)。ただし、私のユースケースは、迅速な配送見積もりを作成することになっていたため、極値ヒューリスティックは適切ではありませんでした（遅すぎて「正確すぎる」ため、10％または20を追加する必要がありました実際に箱を梱包する人々が必然的に次善の選択をするという事実を説明するために、その結果に % を追加します)。
プログラムの名前はわかりませんが、適切なソリューションがどれだけの価値があるかに応じて、これを解決する商用ソフトウェアがおそらくあるでしょう。