論文の概要: A Feasibility-Preserved Quantum Approximate Solver for the Capacitated
Vehicle Routing Problem
- arxiv url: http://arxiv.org/abs/2308.08785v2
- Date: Tue, 19 Sep 2023 10:02:10 GMT
- ステータス: 処理完了
- システム内更新日: 2023-09-20 19:10:55.626528
- 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によってさらに制限されている。
提案手法の有効性を,いくつかの実例に応用して検討し,検討した。
関連論文リスト
- An Efficient Learning-based Solver Comparable to Metaheuristics for the
Capacitated Arc Routing Problem [67.92544792239086]
我々は,高度メタヒューリスティックスとのギャップを著しく狭めるため,NNベースの解法を導入する。
まず,方向対応型注意モデル(DaAM)を提案する。
第2に、教師付き事前学習を伴い、堅牢な初期方針を確立するための教師付き強化学習スキームを設計する。
論文 参考訳(メタデータ) (2024-03-11T02:17:42Z) - Quantum-Assisted Solution Paths for the Capacitated Vehicle Routing
Problem [0.0]
我々は、キャパシタントカー問題(CVRP)またはその減量版であるトラベリングセールスパーソン問題(TSP)について議論する。
今日の最も強力な古典的アルゴリズムでさえ、CVRPは古典的解決が難しい。
量子コンピューティングは、ソリューションの時間を改善する手段を提供するかもしれない。
論文 参考訳(メタデータ) (2023-04-19T13:03:50Z) - Unbalanced penalization: A new approach to encode inequality constraints
of combinatorial problems for quantum optimization algorithms [58.720142291102135]
余分なスラック変数を必要としない代替手法を提案する。
我々は,旅行セールスマン問題,ビン包装問題,ナプサック問題に対するアプローチを評価した。
この新しいアプローチは、リソースの少ない不等式制約の問題を解決するために使用できる。
論文 参考訳(メタデータ) (2022-11-25T06:05:18Z) - 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) - Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
マルチオブジェクト追跡(MOT)は、オブジェクト検出が時間を通して関連付けられているトラッキング・バイ・検出のパラダイムにおいて、最もよくアプローチされる。
これらの最適化問題はNPハードであるため、現在のハードウェア上の小さなインスタンスに対してのみ正確に解決できる。
本手法は,既成整数計画法を用いても,最先端の最適化手法と競合することを示す。
論文 参考訳(メタデータ) (2022-02-17T18:59:20Z) - 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) - Deep Reinforcement Learning for Solving the Heterogeneous Capacitated
Vehicle Routing Problem [13.389057146418056]
現実のシナリオにおける車両は、その能力(または走行速度)に影響を与える異なる特徴を持つ異種である可能性が高い
異種艦隊制約を考慮した車両選択デコーダと経路構成を考慮したノード選択デコーダとを併用した注意機構に基づくDRL手法を提案し,各ステップで車両とノードの両方を自動的に選択して解を構築することを学習する。
論文 参考訳(メタデータ) (2021-10-06T10:05:19Z) - An Overview and Experimental Study of Learning-based Optimization
Algorithms for Vehicle Routing Problem [49.04543375851723]
車両ルーティング問題(VRP)は典型的な離散最適化問題である。
多くの研究は、VRPを解決するための学習に基づく最適化アルゴリズムについて検討している。
本稿では、最近のこの分野の進歩を概観し、関連するアプローチをエンドツーエンドアプローチとステップバイステップアプローチに分割する。
論文 参考訳(メタデータ) (2021-07-15T02:13:03Z) - 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) - Reinforcement Learning Based Vehicle-cell Association Algorithm for
Highly Mobile Millimeter Wave Communication [53.47785498477648]
本稿では,ミリ波通信網における車とセルの関連性について検討する。
まず、ユーザ状態(VU)問題を離散的な非車両関連最適化問題として定式化する。
提案手法は,複数のベースライン設計と比較して,ユーザの複雑性とVUEの20%削減の合計で最大15%のゲインが得られる。
論文 参考訳(メタデータ) (2020-01-22T08:51:05Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。