論文の概要: A Feasibility-Preserved Quantum Approximate Solver for the Capacitated
Vehicle Routing Problem
- arxiv url: http://arxiv.org/abs/2308.08785v1
- Date: Thu, 17 Aug 2023 05:14:43 GMT
- ステータス: 処理完了
- システム内更新日: 2023-08-21 17:55:12.742764
- 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の新しいバイナリエンコーディングを提案する。
- 参考スコア（独自算出の注目度）: 3.2389284835171415
- 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, a
quantum-classical hybrid algorithm known as Quantum Approximate Optimization
Algorithm (QAOA) can provide better solutions in some cases of combinatorial
optimization problems, compared to classical heuristics. However, the QAOA
exhibits a diminished ability to produce high-quality solutions for some
constrained optimization problems including the CVRP. One potential approach
for improvement involves a variation of the QAOA known as the Grover-Mixer
Quantum Alternating Operator Ansatz (GM-QAOA). In this work, we attempt to use
GM-QAOA to solve the CVRP. We present 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 Grover-Mixer. We examine and discuss the effectiveness of the
proposed solver through its application to several illustrative examples.
- Abstract（参考訳）: capacitated vehicle routing problem (cvrp) はnp最適化問題(npo)であり、輸送や物流など様々な分野で発生する。
CVRPは、各車両の輸送能力の制限を受けながら、車両群が顧客に商品を届ける最も効率的な計画を決定することを目的として、車両ルーティング問題(VRP)から拡張されている。
顧客数が増加すると可能なソリューションの数は急増するので、最適なソリューションを見つけることは依然として大きな課題である。
近年、量子近似最適化アルゴリズム (QAOA) と呼ばれる量子古典ハイブリッドアルゴリズムは、古典的ヒューリスティックスと比較して組合せ最適化問題のより良い解を提供することができる。
しかし、qaoaはcvrpを含むいくつかの制約付き最適化問題に対して、高品質なソリューションを作る能力が低下している。
改善の1つの潜在的アプローチは、Grover-Mixer Quantum Alternating Operator Ansatz (GM-QAOA)として知られるQAOAのバリエーションである。
本研究では,GM-QAOAを用いてCVRPを解く。
本稿では,CVRPの車載容量制約を回避できる最短経路を最小化する目的関数として,CVRPの新しいバイナリエンコーディングを提案する。
検索空間はGrover-Mixerによってさらに制限されている。
提案手法の有効性を,いくつかの実例に応用して検討し,検討した。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。