論文の概要: Applying quantum approximate optimization to the heterogeneous vehicle
routing problem
- arxiv url: http://arxiv.org/abs/2110.06799v1
- Date: Wed, 13 Oct 2021 15:38:25 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-11 14:32:33.345096
- Title: Applying quantum approximate optimization to the heterogeneous vehicle
routing problem
- Title（参考訳）: 不均一車両経路問題への量子近似最適化の適用
- Authors: David Fitzek, Toheed Ghandriz, Leo Laine, Mats Granath, Anton Frisk
Kockum
- Abstract要約: 異種車両ルーティング問題に対する近似解を求めるために,量子コンピュータの可能性を検討する。
このマッピングに必要なキュービットの数は、顧客数と2倍にスケールすることがわかった。
- 参考スコア（独自算出の注目度）: 0.7503129292751939
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Quantum computing offers new heuristics for combinatorial problems. With
small- and intermediate-scale quantum devices becoming available, it is
possible to implement and test these heuristics on small-size problems. A
candidate for such combinatorial problems is the heterogeneous vehicle routing
problem (HVRP): the problem of finding the optimal set of routes, given a
heterogeneous fleet of vehicles with varying loading capacities, to deliver
goods to a given set of customers. In this work, we investigate the potential
use of a quantum computer to find approximate solutions to the HVRP using the
quantum approximate optimization algorithm (QAOA). For this purpose we
formulate a mapping of the HVRP to an Ising Hamiltonian and simulate the
algorithm on problem instances of up to 21 qubits. We find that the number of
qubits needed for this mapping scales quadratically with the number of
customers. We compare the performance of different classical optimizers in the
QAOA for varying problem size of the HVRP, finding a trade-off between
optimizer performance and runtime.
- Abstract（参考訳）: 量子コンピューティングは組合せ問題に対する新しいヒューリスティックを提供する。
小型および中規模の量子デバイスが利用可能になると、小規模問題に対してこれらのヒューリスティックを実装してテストすることができる。
このような組み合わせの問題の候補はヘテロジニアス車両ルーティング問題 (HVRP) であり、様々な積載能力を持つ異種車両群を与えられた顧客に対して商品を届けるために最適な経路群を見つけるという問題である。
本研究では,量子近似最適化アルゴリズム (qaoa) を用いて,hvrp に対する近似解を求めるための量子コンピュータのポテンシャルについて検討する。
この目的のために、HVRPのイジング・ハミルトニアンへの写像を定式化し、最大21キュービットの問題インスタンス上でアルゴリズムをシミュレートする。
このマッピングに必要なキュービットの数は、顧客数と2倍にスケールすることがわかった。
我々は、HVRPの様々な問題サイズに対するQAOAにおける古典的オプティマイザの性能を比較し、オプティマイザのパフォーマンスと実行時のトレードオフを見つける。
関連論文リスト
- Bayesian Parameterized Quantum Circuit Optimization (BPQCO): A task and hardware-dependent approach [49.89480853499917]
変分量子アルゴリズム(VQA)は、最適化と機械学習問題を解決するための有望な量子代替手段として登場した。
本稿では,回路設計が2つの分類問題に対して得られる性能に与える影響を実験的に示す。
また、実量子コンピュータのシミュレーションにおいて、ノイズの存在下で得られた回路の劣化について検討する。
論文 参考訳（メタデータ） (2024-04-17T11:00:12Z) - 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) - Quantum-Assisted Solution Paths for the Capacitated Vehicle Routing
Problem [0.0]
我々は、キャパシタントカー問題(CVRP)またはその減量版であるトラベリングセールスパーソン問題(TSP)について議論する。
今日の最も強力な古典的アルゴリズムでさえ、CVRPは古典的解決が難しい。
量子コンピューティングは、ソリューションの時間を改善する手段を提供するかもしれない。
論文 参考訳（メタデータ） (2023-04-19T13:03:50Z) - Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
提案されたハイブリッドアルゴリズムは、コスト関数をハミルトニアン問題にエンコードし、回路の複雑さの低い一連の状態によってエネルギーを最適化する。
レベル$p=2,ldots, 6$の場合、予想される近似比をほぼ維持しながら、レベル$p$を1に減らすことができる。
論文 参考訳（メタデータ） (2022-03-01T19:47:16Z) - Scaling Quantum Approximate Optimization on Near-term Hardware [49.94954584453379]
我々は、様々なレベルの接続性を持つハードウェアアーキテクチャのための最適化回路により、期待されるリソース要求のスケーリングを定量化する。
問題の大きさと問題グラフの次数で指数関数的に増大する。
これらの問題は、ハードウェア接続性の向上や、より少ない回路層で高い性能を達成するQAOAの変更によって緩和される可能性がある。
論文 参考訳（メタデータ） (2022-01-06T21:02:30Z) - Analysis of Vehicle Routing Problem in Presence of Noisy Channels [0.0]
車両ルーティング問題(VRP)はNPハード最適化問題である。
この研究は、変数 ANSATZ 上の変分量子固有解法を用いて、3 と 4 の都市に基本的な VRP ソリューションを構築する。
論文 参考訳（メタデータ） (2021-12-28T10:20:42Z) - Space-efficient binary optimization for variational computing [68.8204255655161]
本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。
また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
論文 参考訳（メタデータ） (2020-09-15T18:17:27Z) - 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) - Cross Entropy Hyperparameter Optimization for Constrained Problem
Hamiltonians Applied to QAOA [68.11912614360878]
QAOA(Quantum Approximate Optimization Algorithm)のようなハイブリッド量子古典アルゴリズムは、短期量子コンピュータを実用的に活用するための最も奨励的なアプローチの1つである。
このようなアルゴリズムは通常変分形式で実装され、古典的な最適化法と量子機械を組み合わせて最適化問題の優れた解を求める。
本研究では,クロスエントロピー法を用いてランドスケープを形作り,古典的パラメータがより容易により良いパラメータを発見でき,その結果,性能が向上することを示す。
論文 参考訳（メタデータ） (2020-03-11T13:52:41Z) - Solving Vehicle Routing Problem Using Quantum Approximate Optimization
Algorithm [0.0]
車両ルーティング問題(VRP)と呼ばれる整数プログラミング課題を解決するために,量子近似最適化アルゴリズム(QAOA)について述べる。
我々はVRPのIsing定式化について概説し、IBM Qiskitプラットフォームを用いてシミュレーションしたIsing Hamiltonianを最小化することでVRPを解くための詳細な手順を示す。
論文 参考訳（メタデータ） (2020-02-02T18:12:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。