論文の概要: A Feasibility-Preserved Quantum Approximate Solver for the Capacitated Vehicle Routing Problem
- arxiv url: http://arxiv.org/abs/2308.08785v3
- Date: Sun, 21 Apr 2024 05:03:01 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-24 00:52:28.776784
- Title: A Feasibility-Preserved Quantum Approximate Solver for the Capacitated Vehicle Routing Problem
- Title（参考訳）: 容量化車両ルーティング問題に対する実現可能性保存型量子近似解法
- Authors: Ningyi Xie, Xinwei Lee, Dongsheng Cai, Yoshiyuki Saito, Nobuyoshi Asai, Hoong Chuin Lau,
- Abstract要約: CVRP(Capacitated Vehicle Routing Problem)は、輸送や物流など様々な分野で発生するNP最適化問題である。
本稿では,CVRPの車両容量制約を回避できる最短経路を最小化する目的機能を備えた,CVRP用の新しいバイナリエンコーディングを提案する。
本稿では,量子交換演算子Ansatzの変種に基づく符号化の有効性について論じる。
- 参考スコア（独自算出の注目度）: 3.0567007573383678
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The Capacitated Vehicle Routing Problem (CVRP) is an NP-optimization problem (NPO) that arises in various fields including transportation and logistics. The CVRP extends from the Vehicle Routing Problem (VRP), aiming to determine the most efficient plan for a fleet of vehicles to deliver goods to a set of customers, subject to the limited carrying capacity of each vehicle. As the number of possible solutions skyrockets when the number of customers increases, finding the optimal solution remains a significant challenge. Recently, the Quantum Approximate Optimization Algorithm (QAOA), a quantum-classical hybrid algorithm, has exhibited enhanced performance in certain combinatorial optimization problems compared to classical heuristics. However, its ability diminishes notably in solving constrained optimization problems including the CVRP. This limitation primarily arises from the typical approach of encoding the given problems as penalty-inclusive binary optimization problems. In this case, the QAOA faces challenges in sampling solutions satisfying all constraints. Addressing this, our work presents a new binary encoding for the CVRP, with an alternative objective function of minimizing the shortest path that bypasses the vehicle capacity constraint of the CVRP. The search space is further restricted by the constraint-preserving mixing operation. We examine and discuss the effectiveness of the proposed encoding under the framework of the variant of the QAOA, Quantum Alternating Operator Ansatz (AOA), through its application to several illustrative examples. Compared to the typical QAOA approach, the proposed method not only preserves the feasibility but also achieves a significant enhancement in the probability of measuring optimal solutions.
- Abstract（参考訳）: CVRP(Capacitated Vehicle Routing Problem)は、輸送や物流など様々な分野で発生するNP最適化問題である。
CVRPは、各車両の輸送能力の制限を受けながら、車両群が顧客に商品を届ける最も効率的な計画を決定することを目的として、車両ルーティング問題(VRP)から拡張されている。
顧客数が増えると、可能なソリューションの数が急増するので、最適なソリューションを見つけることは依然として大きな課題です。
近年,量子古典ハイブリッドアルゴリズムである量子近似最適化アルゴリズム (QAOA) は,古典的ヒューリスティックよりも特定の組合せ最適化問題において高い性能を示した。
しかし、その能力は、CVRPを含む制約付き最適化問題の解決において顕著に低下する。
この制限は主に、与えられた問題をペナルティを含まないバイナリ最適化問題として符号化する典型的なアプローチから生じる。
この場合、QAOAは全ての制約を満たすサンプリングソリューションの課題に直面します。
そこで本研究では,CVRPの車載容量制約を回避できる最短経路を最小化する目的関数として,CVRPの新しいバイナリエンコーディングを提案する。
探索空間は、制約保存混合操作によりさらに制限される。
本稿では,QAOAの変種であるQuantum Alternating Operator Ansatz (AOA) の枠組みの下で提案する符号化の有効性について検討し,その実例を用いて検討する。
従来のQAOA手法と比較して,提案手法は実現可能性を保持するだけでなく,最適解を測定する確率を大幅に向上させる。
関連論文リスト
- Learn to Solve Vehicle Routing Problems ASAP: A Neural Optimization Approach for Time-Constrained Vehicle Routing Problems with Finite Vehicle Fleet [0.0]
車両の車両サイズが有限である時間制約付静電容量VRPを解くためのNCO手法を提案する。
この手法は、柔軟性と堅牢な一般化の両方を示す、適切で費用効率のよい解を見つけることができる。
論文 参考訳（メタデータ） (2024-11-07T15:16:36Z) - Quantum-Assisted Solution Paths for the Capacitated Vehicle Routing
Problem [0.0]
我々は、キャパシタントカー問題(CVRP)またはその減量版であるトラベリングセールスパーソン問題(TSP)について議論する。
今日の最も強力な古典的アルゴリズムでさえ、CVRPは古典的解決が難しい。
量子コンピューティングは、ソリューションの時間を改善する手段を提供するかもしれない。
論文 参考訳（メタデータ） (2023-04-19T13:03:50Z) - Light Unbalanced Optimal Transport [69.18220206873772]
既存の解法は、原理に基づいているか、複数のニューラルネットワークを含む複雑な最適化目標を重み付けしている。
我々は,この解法がUEOT解の普遍近似を提供し,一般化限界を得ることを示す。
論文 参考訳（メタデータ） (2023-03-14T15:44:40Z) - Multiobjective variational quantum optimization for constrained
problems: an application to Cash Management [45.82374977939355]
本稿では,変分量子アルゴリズムを用いた制約付き最適化問題の解法を提案する。
我々は、キャッシュマネジメント問題という、金融の極めて関連性の高い現実世界の問題について、我々の提案を検証した。
実験の結果, 実現したソリューションのコスト, 特に局所最小値の回避に関して, 大幅な改善が見られた。
論文 参考訳（メタデータ） (2023-02-08T17:09:20Z) - Coverage and Capacity Optimization in STAR-RISs Assisted Networks: A
Machine Learning Approach [102.00221938474344]
再構成可能なインテリジェントサーフェス (STAR-RIS) アシストネットワークを同時に送信および反射するカバレッジとキャパシティ最適化のための新しいモデルを提案する。
損失関数ベースの更新戦略はコアポイントであり、各更新時にmin-normソルバによってカバレッジとキャパシティの両方の損失関数の重みを計算することができる。
解析結果から,提案手法は固定重みに基づくMOアルゴリズムよりも優れていることがわかった。
論文 参考訳（メタデータ） (2022-04-13T13:52:22Z) - Applying quantum approximate optimization to the heterogeneous vehicle
routing problem [0.7503129292751939]
異種車両ルーティング問題に対する近似解を求めるために,量子コンピュータの可能性を検討する。
このマッピングに必要なキュービットの数は、顧客数と2倍にスケールすることがわかった。
論文 参考訳（メタデータ） (2021-10-13T15:38:25Z) - Quantum walk-based vehicle routing optimisation [0.0]
本稿では、静電容量化車両ルーティング問題(CVRP)に対する量子ウォークに基づく最適化アルゴリズムの適用性を示す。
効率的なアルゴリズムは、解空間のインデックス化と非インデックス化のために開発され、必要な交互相ウォークのユニタリを実装するために開発された。
QWOAは, ランダムに生成する8つの位置CVRPに対して, ほぼ最適解に収束できるという数値シミュレーション結果を得た。
論文 参考訳（メタデータ） (2021-09-30T08:04:58Z) - Offline Model-Based Optimization via Normalized Maximum Likelihood
Estimation [101.22379613810881]
データ駆動最適化の問題を検討し、一定の点セットでクエリのみを与えられた関数を最大化する必要がある。
この問題は、関数評価が複雑で高価なプロセスである多くの領域に現れる。
我々は,提案手法を高容量ニューラルネットワークモデルに拡張可能なトラクタブル近似を提案する。
論文 参考訳（メタデータ） (2021-02-16T06:04:27Z) - Combining Deep Learning and Optimization for Security-Constrained
Optimal Power Flow [94.24763814458686]
セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。
SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。
本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
論文 参考訳（メタデータ） (2020-07-14T12:38:21Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。