現実を解決するためのハイブリッドアプローチ

Scientific Reports volume 13、記事番号: 11777 (2023) この記事を引用

418 アクセス

2 オルトメトリック

メトリクスの詳細

物品を効率的に箱に詰め込むことは、日常の一般的な作業です。 ビンパッキング問題として知られるこの問題は、産業界や物流業界からの幅広い関心のおかげで、人工知能の分野で集中的に研究されてきました。 数十年以来、現実世界の使用例に最も近いものとして、3 次元のビン パッキング問題を中心に、多くの変形が提案されてきました。 現実世界の 3 次元ビン パッキング問題 (Q4RealBPP) を解決するためのハイブリッド量子古典フレームワークを導入します。(1) パッケージとビンの寸法、(2) 重量超過制限、(3) パッケージ間の親和性など、さまざまな現実的な特性を考慮します。アイテムのカテゴリと (4) アイテムの順序の設定。 Q4RealBPP は、産業および物流部門で高く評価されている制限を考慮した、3 dBPP の実世界指向のインスタンスの解決を可能にします。

有限数の容器への製品の包装の最適化は、生産および流通の分野において重要な日常業務です。 パッケージとコンテナの両方の特性に応じて、一般にビン梱包問題 (BPP) として知られる複数の梱包問題が定式化されることがあります1。 このカテゴリ内では、1 次元 BPP (1 dBPP) が最も単純なものとみなされます 2。その目標は、すべての項目をできるだけ少ないコンテナに詰め込むことです。 物流や産業の実際の状況に対処するために、可変数の制約を備えた多くのバリアントが提案されています3。 各パッケージが高さ、幅、奥行きの 3 つの寸法を持つ 3 次元 BPP (3 dBPP)4 は、最もよく知られており、最も困難なバリアントです。 いくつかの研究で強調されているように、5、6、7、3 dBPP は多くの産業環境で実際的な関心を持っています。 近年、パレット積載 8、道路輸送 9、航空貨物 10 など、多様で実用的な用途を実現するために策定されています。その複雑さのため、3 dBPP は新しく開発された方法やメカニズムをテストするためのベンチマークとしても繰り返し使用されています 11,12 。

別の面では、量子コンピューティングはまだ初期段階にありますが、研究者や実践者にさまざまな種類の実際的な最適化問題に取り組むための革新的なパラダイムを提供するため、科学界から多くの注目を集めています13、14、15、16。 特に、量子アニーラーは、最近、産業 17、物流 18、経済学 19 の分野に触発されたさまざまな最適化問題に適用されています。 ただし、BPP は最適化問題として古典的に広く研究されてきたにもかかわらず、量子コミュニティで行われた BPP に関する研究はまだ不足しています。

量子コンピューティングの分野における BPP に関する先駆的な研究は、1 dBPP20 を解くためのハイブリッド量子古典手法を提示しています。そのソルバーは 2 つのモジュールで構成されています: (1) 1 つの条件を満たすための実行可能な構成のセットを検索する量子サブルーチン単一ビン、および (2) 量子サブルーチンによって与えられたサブセットを使用して完全なソリューションを構築する古典的な計算ヒューリスティック。 開発された量子サブルーチンのパフォーマンスをさらに高めるために、ランダム サンプリングとランダム ウォーク ベースのヒューリスティックに対してさらなるテストが実施されました21。 これら 2 つの論文に加えて、追加の研究では、原子力産業関連の問題を 1 dBPP として定式化し、D-Wave 量子アニーラを使用して解決しています22。 別の研究では、BPP 関連の問題に取り組むための代替手段として、量子にヒントを得た進化的計算技術を示しています 23、24、25。 量子にインスピレーションを得た技術は、量子物理学を利用して動作を定義する進化的アルゴリズムの特定のクラスであり、古典的なコンピューターで実行されるように設計されています26。 したがって、これらはどの量子マシンでも実行できません。

1 dBPP とは対照的に、量子領域で 3 dBPP に取り組むことは、(1) 現実世界からの制約が考慮されるにつれて増加するその複雑さ、および (2) の初期状態という 2 つの関連する理由により、はるかに困難です。現在の商用量子コンピューターの開発では、デコヒーレンスとエラーによって容量が依然として制限されており、高度に制約された問題を解決する上で障害となる可能性があります。 この論文では、実世界指向の 3 dBPP のためのハイブリッド量子古典コンピューティング フレームワークを紹介します。これは、Quantum for Real Bin Packing 問題 (Q4RealBPP) という造語です。 提案されたフレームワークは、D-Wave の Leap Constrained Quadratic Model (CQM) ハイブリッド ソルバー (LeapCQMHybrid27) を利用します。 同時に、Q4RealBPP は既存の code28 に基づいて構築されています。 このリファレンス コードは優れた出発点であり、この作業で開発された次の 2 つの主要な貢献への道を切り開きました。