Operationally Guided Placement-Aware Learning for Industrial Online 3D Bin Packing

あなたは、奇妙な形の箱が山積みになったものを、たった一つの巨大なスーツケースに詰め込もうとしているところだと想像してください。詰め込み始めたら一度も並べ替えることはできず、箱が届くたびに一つずつ入れていかなければなりません。これが「オンライン3次元ビンパッキング問題」であり、食料品から家具まであらゆるものを輸送する物流会社にとっての古典的な頭痛の種です。目標は単に物を詰め込むことではなく、空間を余すことなく使い切り、かつ、積み重ねたものが倒れないようにし、重いものが軽いものの上に載らないようにし、さらに、輸送中に揺れても安定した状態を維持できるようにすることです。数十年もの間、コンピュータは厳格な数学的ルールやパターンの推測を用いてこれを解決しようとしてきましたが、空間の最大化と安全性・安定性のバランスを取ることにしばしば苦戦してきました。

ここに、新しいアプローチであるOPALが登場します。これは、決して疲れることのない、非常に整理整頓された倉庫マネージャーのように振る舞うよう設計されたスマートなシステムです。単に盲目的に箱を詰め込んだり、硬直したルールに頼ったりするのではなく、OPALは意思決定を行うための2段階の「脳」を使用します。第一に、偵察員（スカウト）として機能し、スーツケース内の空きスペースを観察して、次に箱を置くべき「最適な」場所の候補リストを提案します。その際、リスクや不安定さがあると思われる場所はあらかじめ除外しておきます。第二に、審判（ジャッジ）として機能し、学習された「直感」（数千件の実世界の注文データに基づき訓練されたもの）を用いて、その候補リストの中から唯一の最善の場所を選び出します。研究者たちは、コンピュータに単に「どこに」置くかだけでなく、「どのように」置くか（例えば、しっかりとした土台を作るなど）を教えることで、スーツケースを大幅にタイトに梱包できることを発見しました。実際の食料品配送データを用いたテストでは、この新手法は平均して利用可能なスペースの約49%を埋めることができました。これは、以前の内部構成よりも優れた結果であり、GOPT (0.37) や PCT (0ের46) といった外部の手法をも上回り、産業的なルールに特化して最適化されたトップクラスの遺伝的アルゴリズム（GENPACK: 0.47）をも凌駕しました。

問題：不可能なテトリスゲーム

このオンライン3次元ビンパッキング問題を、ハイステークスなテトリスのゲームだと考えてみてください。ただし、次のようなひねりが加わっています。ブロックはランダムな順序でやってくる、ゲームを一時停止して並べ替えることはできない、そして一度でもミスをすれば、タワー全体が崩壊してしまう可能性がある、というものです。現実の世界では、これが毎日倉庫で起きています。トラックがパレットと共に到着し、ロボットや作業員が箱をパレットの上に積み上げなければなりません。課題は、箱のサイズがすべて異なること、そして重さが異なることです。重い箱を壊れやすいものの上に載せることはできませんし、大きな隙間を残すと輸送のために空気を運んでいることになり、コストの無駄になります。

長い間、コンピュータは厳格な幾何学的ルールを用いてこれを解決してきました。コンピュータは、箱が収まる可能性のあるすべての場所を計算し、理論上最も良く見える場所を選びます。しかし、これでは数学的にはタイトであっても、物理的には危険なスタック（積み重ね）が生じることがよくあります。例えば、正面から見ると完璧に見えるけれど、息を吹きかけただけでよろめいてしまう本の塔のような状態です。他の手法も「学習」を利用して改善を試みましたが、それらは多くの場合、最終的な決定（勝者の選択）のみに焦点を当てており、選ぶべき選択肢のリスト自体の質を無視していました。それは、優れた審判を雇いながらも、彼らにひどい候補者のリストを与えているようなものです。審判は、質の低いラインナップを修正することはできません。

解決策：OPALの偵察員と審判

この論文の著者たちは、偵察員（スカウト）と審判（ジャッジ）の両方を改善することでこれを解決するOPAL（Operationally Guided Placement-Aware Learning）を導入しました。

偵察員：OG-EMS
OPALの第一の部分は、彼らがOG-EMSと呼ぶ「偵察員」です。倉庫内の空きスペースを偵察している偵察員を想像してください。単に「どこか」の空いた角を見つけるのではなく、この偵察員は「良い」角を探すように訓練されています。以下の点を確認します：

• 床は平らで頑丈か？（支持：Support）
• 箱は安定するために十分低い位置にあるか？（低高度：Low height）
• 壁や他の箱に対してぴったりと接しているか？（壁との接触：Wall contact）
• 将来の箱のためのスペースを残しているか？（空間の多様性：Spatial diversity）

偵察員は潜在的な場所のリストを生成しますが、不適切な場所は即座にフィルタリングします。安全で、コンパクトで、多様性に富んだ場所を優先します。これは大きな進歩です。なぜなら、以前のコンピュータは、幾何学的には有効であっても実用的には役に立たない場所（例えば、スタック全体をぐらつかせるような場所）を提案していた可能性があるからです。これらの場所を早い段階で取り除くことで、システムは「審判」が質の高い選択肢の中からのみ選ぶように保証します。

審判：配置エンコーダー（Placement Encoder）
第二の部分は「審判」です。偵察員が良い場所のリストを提示したら、次は審判が勝者を選ばなければなりません。ここでOPALは、xLSTM（シーケンスの記憶に非常に長けた一種のニューラルネットワーク）と呼ばれる特殊なAIを使用します。

審判は単に箱の形を見るだけではありません。あらゆる可能な場所に対して、15種類の詳細を含む「履歴書」を読み取ります：

• 箱がどこに位置するか（座標）
• 下部からどの程度サポートされているか
• 下の箱が耐えられる重量
• パレットの端からどの程度離れているか
• その箱がどの程度「壊れやすい」か

審判は、数千件の過去のパッキング業務から学習し、スタックが崩れないためには、たとえ少しタイトさに欠ける配置であっても、それがより良い場合があるということを理解しています。審判はこれらすべての要素を考慮して、単一の最善の動きを選び出します。

得られた知見：より優れた梱包、より速い意思決定

研究者たちは、1,500件の実世界の食料品注文（標準的な欧州パレットサイズでシミュレート）を用いてOPALをテストしました。そこで発見されたことは以下の通りです：

1. 偵察員が最も重要である： 単に選択肢のリストを改善すること（偵察員）が、極めて大きな差を生むことが分かりました。従来の標準的な偵察員の代わりに、新しい「操作ガイド付き（Operationally Guided）」の偵察員を使用したところ、パッキング密度（パレットがどれだけ埋まったか）は**15.1%**跳ね上がりました。これは、優れた候補リストを持つことが、賢い審判を持つことと同じくらい重要であることを証明しています。
2. 審判による追加価値： 同じ候補リストがあったとしても、学習された審判（OPAL）は、固定されたルールに基づいて「最善」の選択肢を選ぶ単純なセレクターよりも優れていました。固定ルールに基づくシステムと比較して、パッキング密度をさらに**6.3%**向上させました。
3. 最終スコア： 完全なOPALシステムは、平均的な空間利用率（密度）0.49を達成しました。これは、パレットの利用可能な容積のほぼ半分を実際の品物で満たしたことを意味します。論文では、自身の内部バリアント（TransformerやBase-EMSなど）に対する統計的な有意性は明確に確認されていますが、OPALのスコア0.49は、外部ベンチマークであるGOPT (0.37) や PCT (0.46) よりも顕著に高く、また、高度な遺伝的アルゴリズムを用いるGENPACK (0.47) も上回っています。
4. スピード： スマートであるにもかかわらず、OPALは高速です。AIが1つの注文に対して意思決定を下すのにかかる時間は約0.38秒であり、オプションリストの生成を含む全プロセスは2.88秒です。これは、30秒以上かかったり後処理を必要としたりした古い手法とは異なり、リアルタイムの産業現場で使用できる速度です。

トレードオフ：完璧ではないが、バランスは取れている

論文はまた、あらゆる面で勝利する「完璧な」解決策は存在しないことも指摘しています。

• 密度 vs 支持： OPALは、空間を埋めること（密度）と、スタックの上面の安定性（表面支持）には優れています。しかし、彼らのシステムのより単純な非学習版（Greedy OG-EMS）は、「側面の支持」（箱が横に滑るのを防ぐこと）においては、実はわずかに優れていました。
• 結論： 著者らは、現実世界では、何が最も重要かに応じて異なる設定を選択できるだろうと示唆しています。もし壊れやすいガラスを輸送するのであれば、追加の側面支持が欲しいかもしれません。もし重くて頑丈なレンガを輸送するのであれば、OPALが提供する最大限の密度が欲しいかもしれません。

なぜこれが重要なのか

この論文は、産業物流において、一つのテクニックだけに頼ることはできないことを示しています。優れた「機会を見つける」能力（偵察員）と、最適なものを「選ぶ」能力（審判）の両方を備えたシステムが必要です。安全性を考慮したオプション生成と、重量やバランスを理解する学習済みAIを組み合わせることで、OPALは従来よりもタイトかつ安全にパレットを梱包することができます。これは、サプライチェーンをより効率的にするための前進であり、トラックが空気を運ぶのではなく、より多くの品物を運び、スタックが崩れることなく、より効率的に運用されることを保証するものです。