論文の概要: Solving Capacitated Vehicle Routing Problem with Quantum Alternating Operator Ansatz and Column Generation

• arxiv url: http://arxiv.org/abs/2503.17051v1
• Date: Fri, 21 Mar 2025 11:09:48 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-24 15:40:10.406452
• Title: Solving Capacitated Vehicle Routing Problem with Quantum Alternating Operator Ansatz and Column Generation
• Title（参考訳）: 量子交互演算子アンザッツとカラム生成による静電容量化車両ルーティング問題の解法
• Authors: Wei-hao Huang, Hiromichi Matsuyama, Yu Yamashiro,
• Abstract要約: 本研究では,キャパシタン化車両ルーティング問題(CVRP)の解くためのハイブリッド量子古典的アプローチを提案する。 カラム生成(CG)法と量子交換演算子Ansatz(QAOAnsatz)を結合する。 小型CVRPインスタンスの実験結果から,QAOAnsatzはQAOAアプローチよりも高速に最適経路に収束することが示された。
• 参考スコア（独自算出の注目度）: 1.474723404975345
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This study proposes a hybrid quantum-classical approach to solving the Capacitated Vehicle Routing Problem (CVRP) by integrating the Column Generation (CG) method with the Quantum Alternating Operator Ansatz (QAOAnsatz). The CG method divides the CVRP into the reduced master problem, which finds the best combination of the routes under the route set, and one or more subproblems, which generate the routes that would be beneficial to add to the route set. This method is iteratively refined by adding new routes identified via subproblems and continues until no improving route can be found. We leverage the QAOAnsatz to solve the subproblems. Our algorithm restricts the search space by designing the QAOAnsatz mixer Hamiltonian to enforce one-hot constraints. Moreover, to handle capacity constraints in QAOAnsatz, we employ an Augmented Lagrangian-inspired method that obviates the need for additional slack variables, reducing the required number of qubits. Experimental results on small-scale CVRP instances (up to 6 customers) show that QAOAnsatz converges more quickly to optimal routes than the standard QAOA approach, demonstrating the potential of this hybrid framework in tackling real-world logistical optimization problems on near-term quantum hardware.
• Abstract（参考訳）: 本研究では,Clumn Generation (CG) 法とQuantum Alternating Operator Ansatz (QAOAnsatz) を統合し,CVRP(Capacitated Vehicle Routing Problem) を解くためのハイブリッド量子古典的手法を提案する。 CG法は、CVRPをルートセットの下にあるルートと1つ以上のサブプロブレムの最良の組み合わせを見つける縮小マスター問題と、ルートセットに追加するのに有益なルートを生成するサブプロブレムに分割する。 この方法は、サブプロブレムによって同定された新しいルートを追加して反復的に洗練され、改良されたルートが見つからないまで継続される。 サブプロブレムを解くためにQAOAnsatzを利用する。 このアルゴリズムはQAOAnsatzmixer Hamiltonian を設計して一点制約を強制することによって探索空間を制限している。 さらに,QAOAnsatzのキャパシティ制約に対処するため,拡張ラグランジアンにインスパイアされた手法を用い,スラック変数の追加の必要性を回避し,必要なキュービット数を削減した。 小型のCVRPインスタンス(最大6顧客)の実験結果から、QAOAnsatzは標準的なQAOAアプローチよりも高速に最適なルートに収束し、このハイブリッドフレームワークが短期量子ハードウェアの現実の論理的最適化問題に対処する可能性を示している。

関連論文リスト

• Self-Supervised Transformers as Iterative Solution Improvers for Constraint Satisfaction [44.67050228129961]
  制約満足度問題(CSP)のためのトランスフォーマーベースのフレームワークを提案する。 CSPは多くのアプリケーションで利用されており、機械学習によるソリューションの高速化は幅広い関心を集めている。 本稿では,Transformerをソリューションリファインダとして活用する自己教師型フレームワークであるConsFormerを提案する。
  論文  参考訳（メタデータ） (2025-02-18T16:51:01Z)
• Solving Drone Routing Problems with Quantum Computing: A Hybrid Approach Combining Quantum Annealing and Gate-Based Paradigms [34.4581898633922]
  提案手法はQuantum for Drone Routing(Q4DR)と呼ばれ、この分野でもっとも顕著な2つのパラダイムを統合している。 Q4DRの有効性は、複雑さが増大する3つのユースケースを通して示される。
  論文  参考訳（メタデータ） (2025-01-30T15:38:40Z)
• Digitized Counterdiabatic Quantum Algorithms for Logistics Scheduling [33.04597339860113]
  本稿では,2つのスケジューリング問題に対して,ディジタル化された反断熱量子最適化(DCQO)アルゴリズムを提案する。 ジョブショップスケジューリング問題では,特定の制約下で複数のタスクを実行するロボットの最適なスケジュールを見つけることを目的としている。 旅行セールスパーソンの問題は、すべての都市をカバーし、最短の旅行距離と関連する経路を見つけることである。
  論文  参考訳（メタデータ） (2024-05-24T16:53:30Z)
• Improving Quantum and Classical Decomposition Methods for Vehicle Routing [2.4646794072984477]
  本稿では,2つの分解法,すなわちグラフ縮小と回路切断の精巧な組み合わせを提案する。 この結果から,現在の量子技術の制約内での最適化問題に対するアルゴリズムの性能に関する知見が得られた。
  論文  参考訳（メタデータ） (2024-04-08T14:19:25Z)
• Graph-controlled Permutation Mixers in QAOA for the Flexible Job-Shop Problem [0.0]
  Quantum Alternating Operator Ansatzは制約付き最適化ソリューションのためのアルゴリズムフレームワークを提供する。 既知の標準QAOAプロトコルとは対照的に、最適化問題の制約はアンザッツ回路の混合層に組み込まれている。 フレキシブルなジョブショップ問題を含む幅広いスケジューリング問題に対する混合演算子を開発した。
  論文  参考訳（メタデータ） (2023-11-07T16:16:52Z)
• A Feasibility-Preserved Quantum Approximate Solver for the Capacitated Vehicle Routing Problem [3.0567007573383678]
  CVRP(Capacitated Vehicle Routing Problem)は、輸送や物流など様々な分野で発生するNP最適化問題である。 本稿では,CVRPの車両容量制約を回避できる最短経路を最小化する目的機能を備えた,CVRP用の新しいバイナリエンコーディングを提案する。 本稿では,量子交換演算子Ansatzの変種に基づく符号化の有効性について論じる。
  論文  参考訳（メタデータ） (2023-08-17T05:14:43Z)
• Qubit efficient quantum algorithms for the vehicle routing problem on NISQ processors [48.68474702382697]
  時間窓付き車両ルーティング問題(VRPTW)は、ロジスティクス業界で直面する一般的な最適化問題である。 そこで本研究では,以前に導入した量子ビット符号化方式を用いて,バイナリ変数の数を削減した。
  論文  参考訳（メタデータ） (2023-06-14T13:44:35Z)
• QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum machines [81.4597482536073]
  量子近似最適化アルゴリズム(QAOAs)は、量子マシンのパワーを利用し、断熱進化の精神を継承する。 量子マシンを用いて任意の大規模MaxCut問題を解くためにQAOA-in-QAOA(textQAOA2$)を提案する。 提案手法は,大規模最適化問題におけるQAOAsの能力を高めるために,他の高度な戦略にシームレスに組み込むことができる。
  論文  参考訳（メタデータ） (2022-05-24T03:49:10Z)
• Scaling Quantum Approximate Optimization on Near-term Hardware [49.94954584453379]
  我々は、様々なレベルの接続性を持つハードウェアアーキテクチャのための最適化回路により、期待されるリソース要求のスケーリングを定量化する。 問題の大きさと問題グラフの次数で指数関数的に増大する。 これらの問題は、ハードウェア接続性の向上や、より少ない回路層で高い性能を達成するQAOAの変更によって緩和される可能性がある。
  論文  参考訳（メタデータ） (2022-01-06T21:02:30Z)
• Applying quantum approximate optimization to the heterogeneous vehicle routing problem [0.7503129292751939]
  異種車両ルーティング問題に対する近似解を求めるために,量子コンピュータの可能性を検討する。 このマッピングに必要なキュービットの数は、顧客数と2倍にスケールすることがわかった。
  論文  参考訳（メタデータ） (2021-10-13T15:38:25Z)
• Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
  形状対応を見つけることは、NP-hard quadratic assignment problem (QAP)として定式化できる。 本稿では,アルファ拡大アルゴリズムに触発されたQAPの反復量子法Q-Matchを提案する。 Q-Match は、実世界の問題にスケールできるような長文対応のサブセットにおいて、反復的に形状マッチング問題に適用できる。
  論文  参考訳（メタデータ） (2021-05-06T17:59:38Z)
• Low-Rank Sinkhorn Factorization [45.87981728307819]
  本稿では,テキストサブカップリング係数の積として,低位結合の明示的な因子化を導入する。 このアルゴリズムの非漸近定常収束を証明し、その効率をベンチマーク実験で示す。
  論文  参考訳（メタデータ） (2021-03-08T13:18:45Z)
• A Quantum Annealing Approach for Dynamic Multi-Depot Capacitated Vehicle Routing Problem [5.057312718525522]
  本稿では,AQC(Adiabatic Quantum Computation)の原理に基づく量子コンピューティングアルゴリズムを提案する。 従来のアルゴリズムと比較して、車両ルーティング問題(VRP)のような最適化問題の解法において、計算上の利点が顕著に示された。 これは、輸送、物流、サプライチェーン管理の分野における実世界の応用におけるNPハード最適化問題である。
  論文  参考訳（メタデータ） (2020-05-26T01:47:39Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。