論文の概要: A Quantum Annealing Approach for Dynamic Multi-Depot Capacitated Vehicle
Routing Problem
- arxiv url: http://arxiv.org/abs/2005.12478v2
- Date: Wed, 27 May 2020 02:55:52 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-18 07:55:52.388760
- Title: A Quantum Annealing Approach for Dynamic Multi-Depot Capacitated Vehicle
Routing Problem
- Title(参考訳): 動的多点容量車両ルーティング問題に対する量子アニーリング手法
- Authors: Ramkumar Harikrishnakumar, Saideep Nannapaneni, Nam H. Nguyen, James
E. Steck, Elizabeth C. Behrman
- Abstract要約: 本稿では,AQC(Adiabatic Quantum Computation)の原理に基づく量子コンピューティングアルゴリズムを提案する。
従来のアルゴリズムと比較して、車両ルーティング問題(VRP)のような最適化問題の解法において、計算上の利点が顕著に示された。
これは、輸送、物流、サプライチェーン管理の分野における実世界の応用におけるNPハード最適化問題である。
- 参考スコア(独自算出の注目度): 5.057312718525522
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Quantum annealing (QA) is a quantum computing algorithm that works on the
principle of Adiabatic Quantum Computation (AQC), and it has shown significant
computational advantages in solving combinatorial optimization problems such as
vehicle routing problems (VRP) when compared to classical algorithms. This
paper presents a QA approach for solving a variant VRP known as multi-depot
capacitated vehicle routing problem (MDCVRP). This is an NP-hard optimization
problem with real-world applications in the fields of transportation,
logistics, and supply chain management. We consider heterogeneous depots and
vehicles with different capacities. Given a set of heterogeneous depots, the
number of vehicles in each depot, heterogeneous depot/vehicle capacities, and a
set of spatially distributed customer locations, the MDCVRP attempts to
identify routes of various vehicles satisfying the capacity constraints such as
that all the customers are served. We model MDCVRP as a quadratic unconstrained
binary optimization (QUBO) problem, which minimizes the overall distance
traveled by all the vehicles across all depots given the capacity constraints.
Furthermore, we formulate a QUBO model for dynamic version of MDCVRP known as
D-MDCVRP, which involves dynamic rerouting of vehicles to real-time customer
requests. We discuss the problem complexity and a solution approach to solving
MDCVRP and D-MDCVRP on quantum annealing hardware from D-Wave.
- Abstract(参考訳): 量子アニーリング(Quantum annealing, QA)は、AQC(Adiabatic Quantum Computation)の原理に基づく量子コンピューティングアルゴリズムであり、従来のアルゴリズムと比較して、車両ルーティング問題(VRP)のような組合せ最適化問題の解法において、計算上の優位性を示す。
本稿では,MDCVRP (Multi-depot Capacitated Vehicle routing problem) と呼ばれる可変VRP問題に対するQAアプローチを提案する。
これは、輸送、物流、サプライチェーン管理の分野における実世界の応用におけるNPハード最適化問題である。
異種補給所と車体容量の異なる車両について検討する。
ヘテロジニアスデポのセット、各デポ内の車両数、異質デポ/車両容量、空間的に分散した顧客位置のセットが与えられた場合、MDCVRPは、全顧客が提供されるキャパシティの制約を満たす様々な車両のルートを特定しようとする。
MDCVRPを2次非拘束二元最適化(QUBO)問題としてモデル化し,キャパシティ制約を考慮に入れた全車種間距離を最小化する。
さらに,D-MDCVRPとして知られるMDCVRPの動的バージョンに対するQUBOモデルを定式化し,車種をリアルタイムの顧客要求に動的に再ルーティングする。
本稿では,D-Wave の量子アニールハードウェア上での MDCVRP と D-MDCVRP の解法について述べる。
関連論文リスト
- A Multi-Head Ensemble Multi-Task Learning Approach for Dynamical
Computation Offloading [62.34538208323411]
共有バックボーンと複数の予測ヘッド(PH)を組み合わせたマルチヘッドマルチタスク学習(MEMTL)手法を提案する。
MEMTLは、追加のトレーニングデータを必要とせず、推測精度と平均平方誤差の両方でベンチマーク手法より優れている。
論文 参考訳(メタデータ) (2023-09-02T11:01:16Z) - A Feasibility-Preserved Quantum Approximate Solver for the Capacitated
Vehicle Routing Problem [3.2389284835171415]
CVRP(Capacitated Vehicle Routing Problem)は、輸送や物流など様々な分野で発生するNP最適化問題である。
本稿では,CVRPの車載容量制約を回避できる最短経路を最小化する目的関数として,CVRPの新しいバイナリエンコーディングを提案する。
論文 参考訳(メタデータ) (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) - Roulette-Wheel Selection-Based PSO Algorithm for Solving the Vehicle
Routing Problem with Time Windows [58.891409372784516]
本稿では,Roulette Wheel Method (RWPSO) を用いた新しいPSO手法を提案する。
RWPSOのSolomon VRPTWベンチマークデータセットを用いた実験は、RWPSOが文学の他の最先端アルゴリズムと競合していることを示している。
論文 参考訳(メタデータ) (2023-06-04T09:18:02Z) - Quantum-Assisted Solution Paths for the Capacitated Vehicle Routing
Problem [0.0]
我々は、キャパシタントカー問題(CVRP)またはその減量版であるトラベリングセールスパーソン問題(TSP)について議論する。
今日の最も強力な古典的アルゴリズムでさえ、CVRPは古典的解決が難しい。
量子コンピューティングは、ソリューションの時間を改善する手段を提供するかもしれない。
論文 参考訳(メタデータ) (2023-04-19T13:03:50Z) - Supply Chain Logistics with Quantum and Classical Annealing Algorithms [0.0]
ノイズの多い中間スケール量子(NISQ)ハードウェアは、実用上重要なフルスケール最適化問題とほとんど互換性がない。
本研究では,サプライチェーンのロジスティクスにおいて,企業の運用規模において,実質的な商業価値,多輪車経路の問題について検討する。
我々の研究は、NASQデバイスをハイブリッド方式で応用するための車両ルーティング以外のコンテキストに適用可能な一連の技術を提供し、商業的関心事の大規模問題に応用する。
論文 参考訳(メタデータ) (2022-05-09T17:36:21Z) - Collaborative Intelligent Reflecting Surface Networks with Multi-Agent
Reinforcement Learning [63.83425382922157]
インテリジェント・リフレクション・サーフェス(IRS)は将来の無線ネットワークに広く応用されることが想定されている。
本稿では,エネルギー収穫能力を備えた協調型IRSデバイスを用いたマルチユーザ通信システムについて検討する。
論文 参考訳(メタデータ) (2022-03-26T20:37:14Z) - 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) - Deep Policy Dynamic Programming for Vehicle Routing Problems [89.96386273895985]
本稿では,学習ニューラルの強みと動的プログラミングアルゴリズムの強みを組み合わせた深層ポリシー動的プログラミング(d pdp)を提案する。
D PDPは、例の解からエッジを予測するために訓練されたディープニューラルネットワークから派生したポリシーを使用して、DP状態空間を優先し、制限する。
本研究では,旅行セールスマン問題 (TSP) と車両ルーティング問題 (VRP) の枠組みを評価し,ニューラルネットワークが(制限された)DPアルゴリズムの性能を向上させることを示す。
論文 参考訳(メタデータ) (2021-02-23T15:33:57Z) - Reinforcement Learning Based Vehicle-cell Association Algorithm for
Highly Mobile Millimeter Wave Communication [53.47785498477648]
本稿では,ミリ波通信網における車とセルの関連性について検討する。
まず、ユーザ状態(VU)問題を離散的な非車両関連最適化問題として定式化する。
提案手法は,複数のベースライン設計と比較して,ユーザの複雑性とVUEの20%削減の合計で最大15%のゲインが得られる。
論文 参考訳(メタデータ) (2020-01-22T08:51:05Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。