論文の概要: An Advanced Hybrid Quantum Tabu Search Approach to Vehicle Routing Problems
- arxiv url: http://arxiv.org/abs/2501.12652v1
- Date: Wed, 22 Jan 2025 05:29:27 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-01-23 13:28:25.280292
- Title: An Advanced Hybrid Quantum Tabu Search Approach to Vehicle Routing Problems
- Title（参考訳）: ハイブリッド量子タブサーチによる車両ルーティング問題の解法
- Authors: James B. Holliday, Eneko Osaba, Khoa Luu,
- Abstract要約: QCと古典コンピューティングが連携するハイブリッドアプローチは、現実世界のスケール問題を解く上で最も有益であることを示している。
我々は、静電容量化車両ルーティング問題(RPCV)を解決するために、新しいハイブリッド量子古典タブサーチ(HQTS)アルゴリズムを提案する。
HQTSはいくつかのCVRP問題に対して最適あるいはほぼ最適のソリューションを達成し、他のハイブリッドCVRPアルゴリズムよりも優れていた。
- 参考スコア（独自算出の注目度）: 8.542666941016572
- License:
- Abstract: Quantum computing (QC) is expected to solve incredibly difficult problems, including finding optimal solutions to combinatorial optimization problems. However, to date, QC alone is still far to demonstrate this capability except on small-sized problems. Hybrid approaches where QC and classical computing work together have shown the most potential for solving real-world scale problems. This work aims to show that we can enhance a classical optimization algorithm with QC so that it can overcome this limitation. We present a new hybrid quantum-classical tabu search (HQTS) algorithm to solve the capacitated vehicle routing problem (CVRP). Based on our prior work, HQTS leverages QC for routing within a classical tabu search framework. The quantum component formulates the traveling salesman problem (TSP) for each route as a QUBO, solved using D-Wave's Advantage system. Experiments investigate the impact of quantum routing frequency and starting solution methods. While different starting solution methods, including quantum-based and classical heuristics methods, it shows minimal overall impact. HQTS achieved optimal or near-optimal solutions for several CVRP problems, outperforming other hybrid CVRP algorithms and significantly reducing the optimality gap compared to preliminary research. The experimental results demonstrate that more frequent quantum routing improves solution quality and runtime. The findings highlight the potential of integrating QC within meta-heuristic frameworks for complex optimization in vehicle routing problems.
- Abstract（参考訳）: 量子コンピューティング(QC)は、組合せ最適化問題に対する最適解を見つけることを含む、信じられないほど難しい問題を解くことが期待されている。
しかし、現在までQCだけでは、小さな問題を除いて、この能力を示すには程遠い。
QCと古典コンピューティングが協調して動作するハイブリッドアプローチは、現実世界のスケール問題を解く最も可能性を示している。
本研究の目的は,従来の最適化アルゴリズムをQCで拡張することで,この制限を克服できることである。
本稿では, 静電容量化車両ルーティング問題(CVRP)を解決するために, HQTSアルゴリズムを提案する。
HQTSは従来のタブ検索フレームワーク内でのルーティングにQCを活用している。
量子成分は、各ルートの走行セールスマン問題(TSP)をQUBOとして定式化し、D-Waveのアドバンテージシステムを用いて解決する。
量子ルーティング周波数と開始解法の影響を実験的に検討する。
量子ベースおよび古典的ヒューリスティックス法を含む、異なる開始解法は、全体的な影響を最小限に示す。
HQTSは、いくつかのCVRP問題に対して最適またはほぼ最適の解を達成し、他のハイブリッドCVRPアルゴリズムよりも優れ、予備研究と比べて最適なギャップを著しく減らした。
実験により、より頻繁な量子ルーティングは、ソリューションの品質と実行時間を改善することが示された。
この結果は、車両ルーティング問題における複雑な最適化のためのメタヒューリスティックフレームワークにQCを統合する可能性を強調している。
関連論文リスト
- Bayesian Parameterized Quantum Circuit Optimization (BPQCO): A task and hardware-dependent approach [49.89480853499917]
変分量子アルゴリズム(VQA)は、最適化と機械学習問題を解決するための有望な量子代替手段として登場した。
本稿では,回路設計が2つの分類問題に対して得られる性能に与える影響を実験的に示す。
また、実量子コンピュータのシミュレーションにおいて、ノイズの存在下で得られた回路の劣化について検討する。
論文 参考訳（メタデータ） (2024-04-17T11:00:12Z) - Quantum-Assisted Solution Paths for the Capacitated Vehicle Routing
Problem [0.0]
我々は、キャパシタントカー問題(CVRP)またはその減量版であるトラベリングセールスパーソン問題(TSP)について議論する。
今日の最も強力な古典的アルゴリズムでさえ、CVRPは古典的解決が難しい。
量子コンピューティングは、ソリューションの時間を改善する手段を提供するかもしれない。
論文 参考訳（メタデータ） (2023-04-19T13:03:50Z) - Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
単一画像超解像(SISR)問題を解くために,量子コンピューティングに基づくアルゴリズムを提案する。
提案したAQCアルゴリズムは、SISRの精度を維持しつつ、古典的なアナログよりも向上したスピードアップを実現する。
論文 参考訳（メタデータ） (2023-04-18T11:57:15Z) - QNEAT: Natural Evolution of Variational Quantum Circuit Architecture [95.29334926638462]
我々は、ニューラルネットワークの量子対する最も有望な候補として登場した変分量子回路(VQC)に注目した。
有望な結果を示す一方で、バレン高原、重みの周期性、アーキテクチャの選択など、さまざまな問題のために、VQCのトレーニングは困難である。
本稿では,VQCの重みとアーキテクチャの両方を最適化するために,自然進化にインスパイアされた勾配のないアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-04-14T08:03:20Z) - Recommending Solution Paths for Solving Optimization Problems with
Quantum Computing [4.306566710489809]
最適解パスを特定し,推奨するフレームワークを提案する。
最先端のハイブリッドアルゴリズム、エンコーディングおよび分解技術はモジュラー方式で統合することができる。
選択した選択肢の集合に対する我々のアプローチの実証と検証を行い、キャパシタイトされた車両ルーティング問題に対するその適用例を示す。
論文 参考訳（メタデータ） (2022-12-21T15:55:43Z) - Classically-Boosted Quantum Optimization Algorithm [0.0]
我々は、量子最適化を強化するために既存の古典的手法を活用する自然なアプローチを探求する。
具体的には、近似解を見つけるために古典的なアルゴリズムを実行し、量子回路を用いて高品質な解の「近傍」を探索する。
CBQOA の Max 3SAT および Max Bisection への応用を実証し,これらの問題に対する従来のアプローチよりも優れていることを示す実証的証拠を提供する。
論文 参考訳（メタデータ） (2022-03-25T23:36:14Z) - Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
マルチオブジェクト追跡(MOT)は、オブジェクト検出が時間を通して関連付けられているトラッキング・バイ・検出のパラダイムにおいて、最もよくアプローチされる。
これらの最適化問題はNPハードであるため、現在のハードウェア上の小さなインスタンスに対してのみ正確に解決できる。
本手法は,既成整数計画法を用いても,最先端の最適化手法と競合することを示す。
論文 参考訳（メタデータ） (2022-02-17T18:59:20Z) - A Hybrid Quantum-Classical Algorithm for Robust Fitting [47.42391857319388]
本稿では,ロバストフィッティングのためのハイブリッド量子古典アルゴリズムを提案する。
私たちのコアコントリビューションは、整数プログラムの列を解く、新しい堅牢な適合式である。
実際の量子コンピュータを用いて得られた結果について述べる。
論文 参考訳（メタデータ） (2022-01-25T05:59:24Z) - Analysis of Vehicle Routing Problem in Presence of Noisy Channels [0.0]
車両ルーティング問題(VRP)はNPハード最適化問題である。
この研究は、変数 ANSATZ 上の変分量子固有解法を用いて、3 と 4 の都市に基本的な VRP ソリューションを構築する。
論文 参考訳（メタデータ） (2021-12-28T10:20:42Z) - Applying quantum approximate optimization to the heterogeneous vehicle
routing problem [0.7503129292751939]
異種車両ルーティング問題に対する近似解を求めるために,量子コンピュータの可能性を検討する。
このマッピングに必要なキュービットの数は、顧客数と2倍にスケールすることがわかった。
論文 参考訳（メタデータ） (2021-10-13T15:38:25Z) - Cross Entropy Hyperparameter Optimization for Constrained Problem
Hamiltonians Applied to QAOA [68.11912614360878]
QAOA(Quantum Approximate Optimization Algorithm)のようなハイブリッド量子古典アルゴリズムは、短期量子コンピュータを実用的に活用するための最も奨励的なアプローチの1つである。
このようなアルゴリズムは通常変分形式で実装され、古典的な最適化法と量子機械を組み合わせて最適化問題の優れた解を求める。
本研究では,クロスエントロピー法を用いてランドスケープを形作り,古典的パラメータがより容易により良いパラメータを発見でき,その結果,性能が向上することを示す。
論文 参考訳（メタデータ） (2020-03-11T13:52:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。