倉庫保管および物流における Bin Packing Problem の解決-戦略の比較

Decision Lab からインスピレーションを得たブログ投稿。Damien Lopez による同社のオリジナルの投稿は、Medium で読むことができます-効率的な積載方法を考える?


3D Bin Packing Problem (3D-BPP) は、倉庫保管と物流において最も頻繁に発生する問題の一つです。その解決策は、必要なコンテナの数を最小限に抑えるために、コンテナ (箱またはパレット) に商品をできるだけ隙間なく詰めることです。

大学に行くのに必要な荷物を詰める際に Bin Packing Problem を解き始めたと言ったらどうなるでしょうか?時間のプレッシャー下でスペースを活用する練習ができる有名なテトリス ゲームを覚えていますか?

それとも、新しい場所に引っ越したり、旅行に出かけたりするために荷物をまとめる必要があったときの心境を覚えていますか? どちらの場合も、その箱またはスーツケースの空きスペースが多いほど、より多くの箱またはスーツケースが必要になります。

そのような控えめな量の箱やスーツケースの場合は、(誰もが通常そうしているように) 直感と経験に頼ることができます。しかし、箱が数十個ある場合はどうなるでしょうか? 物流業界では、直感や人間の計算ミスにより、追加のパレットやトラックの購入費が発生し、会社にとっては多額の費用が発生する可能性があります。

そこで、Decision Lab は、数学的最適化、強化学習、およびルールベースのアルゴリズムを比較する 3 つのコンピューターベースのパッキング手法をテストして、最も効果的な手法を特定することにしました。

最適化アルゴリズム

数学的最適化の場合、Decision Lab は目的関数と制約を指定し、数学的オプティマイザーを使用して解を見つけました。同社は、未使用のコンテナ空間を最小限に抑えることを目的関数として設定し、これにより使用されるコンテナの数も削減されます。


Bin Packing Problem の図解
Bin Packing Problem の図解。出典:Decision Lab on Medium

強化学習とシミュレーション

強化学習は、現在の状態で行われた決定が次の状態で行われた決定に影響を与える機械学習のアプローチです。コンテキストが重要なシナリオに適用できます。これは、最適解がコンテキストを考慮しない数学的最適化とは異なります。

強化学習のシナリオでは、状態(state)アクション(action)報酬関数(reward function) が必要になります。

RL エージェントは、特定の状態に対して実行する最適なアクションが何であるかを学習します。環境 (状態) に関する情報を受け取ると、アクションを実行します。このアクションが環境に及ぼす影響に応じて、エージェントはプラスまたはマイナスの報酬を受け取ります。このプロセスは報酬の価値を最大化するために何度も繰り返されます。

RL エージェントをトレーニングするために、Decision Lab は Microsoft Bonsai を使用しました。Bonsai は AnyLogic と適切に統合しており、AI バックグラウンドを持たないシミュレーションおよび対象分野の専門家がプロジェクトで強化学習エージェントを構築、トレーニング、デプロイするのに役立ちます。


AnyLogic と Bonsai を使用した AI トレーニングフロー
AnyLogic と Bonsai を使用した AI トレーニング ワークフロー (クリックして拡大)。ソース:Decision Lab on Medium

Bin Packing Problem を解決するために、同社は商品を梱包エリアに配送するコンベア ベルトのシミュレーション モデルを開発しました。Decision Lab はモデルを Bonsai プラットフォームと統合し、それを使用して RL エージェントが最も効率的な方法で商品を梱包できるようにトレーニングしました。

RL が従ったポリシーの 1 つは、ベルトコンベア上の商品は到着時に処理され、RL エージェントが次の商品に向かう前にコンテナに入れられるというものでした。また、Decision Lab ではエージェントが 1 つ先の項目を確認できるため、限定的な計画を立てることができました。

したがって、これは、梱包されるすべての商品について完全な知識を持つ数学的最適化手法よりもはるかに困難です。RL エージェントは、ランダムに順序付けられたシーケンスの前にある 1 つのみを認識します。
– Decision Lab.

カラフルな商品が載ったベルトコンベア
商品を梱包エリアに運ぶベルトコンベアのシミュレーション。出典:Medium の Decision Lab


すべての設定が完了すると、Decision Lab は最適化および強化学習アルゴリズムを確立されたルールベースのアルゴリズムと比較する実験を実行しました。この結果は、限られた時間内に商品のリストを梱包する際に、どの戦略が最も高い密度率を達成したかを特定するのに役立ちました。

この投稿では、コンピューターベースの 3 つの戦略のうち 2 つを取り上げました。ビデオで、どれが最も成功したかをご確認ください。プロジェクトの詳細と比較結果:


YouTube ビデオプレゼンテーションスライド

プロジェクトの結果を学べば、必勝戦略とテトリスや休暇のための荷造りの経験を組み合わせて、Bin Packing Problem に取り組む方法がわかります。

シミュレーションモデリングのニュースや洞察の詳細を得るために、月刊ニュースレターの購読をおすすめします


関連記事