論文の概要: Advanced Quantum Annealing Approach to Vehicle Routing Problems with Time Windows

• arxiv url: http://arxiv.org/abs/2503.24285v1
• Date: Mon, 31 Mar 2025 16:32:40 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-01 14:33:26.086745
• Title: Advanced Quantum Annealing Approach to Vehicle Routing Problems with Time Windows
• Title（参考訳）: 時間Windowsにおける車両ルーティング問題に対する量子アニーリングの高度化
• Authors: James B. Holliday, Darren Blount, Eneko Osaba, Khoa Luu,
• Abstract要約: 本稿では,Traveing Salesman Problem with Time WindowsとCapacitated Vehicle Routing Problem with Time Windowsの2つのNP-Hard問題に焦点をあてる。 D-WaveのQuantum Annealer と Constrained Quadratic Model (CQM) をハイブリッドフレームワークに利用してこれらの問題を解決する。 我々は、CQMソルバがルートコストを効果的に最小化する一方で、問題のサイズが大きくなるにつれて時間窓の実現可能性を維持するのに苦労していることを示した。
• 参考スコア（独自算出の注目度）: 7.819888986737809
• License:
• Abstract: In this paper, we explore the potential for quantum annealing to solve realistic routing problems. We focus on two NP-Hard problems, including the Traveling Salesman Problem with Time Windows and the Capacitated Vehicle Routing Problem with Time Windows. We utilize D-Wave's Quantum Annealer and Constrained Quadratic Model (CQM) solver within a hybrid framework to solve these problems. We demonstrate that while the CQM solver effectively minimizes route costs, it struggles to maintain time window feasibility as the problem size increases. To address this limitation, we implement a heuristic method that fixes infeasible solutions through a series of swapping operations. Testing on benchmark instances shows our method achieves promising results with an average optimality gap of 3.86%.
• Abstract（参考訳）: 本稿では,現実的なルーティング問題を解くために,量子アニールの可能性を探る。 本稿では,Traveing Salesman Problem with Time WindowsとCapacitated Vehicle Routing Problem with Time Windowsの2つのNP-Hard問題に焦点をあてる。 D-WaveのQuantum Annealer と Constrained Quadratic Model (CQM) をハイブリッドフレームワークに利用してこれらの問題を解決する。 我々は、CQMソルバがルートコストを効果的に最小化する一方で、問題のサイズが大きくなるにつれて時間窓の実現可能性を維持するのに苦労していることを示した。 この制限に対処するため、我々は一連のスワップ操作を通じて実現不可能な解を修正するヒューリスティック手法を実装した。 ベンチマークテストの結果,提案手法は平均最適性ギャップ3.86%で有望な結果が得られることがわかった。

関連論文リスト

• Quantum Annealing based Hybrid Strategies for Real Time Route Optimization [0.0]
  本稿では,複雑性を低減しつつ,問題を高速に解決する手法を提案する。 ハイブリッド2ステップ(H2S)とハイブリッド3ステップ(H3S)の2つのアルゴリズムを用いる。 どちらのアルゴリズムも、ソリューション時間とソリューションコストの両面で、有望な結果をもたらす。
  論文  参考訳（メタデータ） (2024-11-21T14:45:40Z)
• Quantum Algorithms for Drone Mission Planning [0.0]
  ミッションプランニングはしばしば、一連のミッション目標を達成するためにISR(Intelligence, Surveillance and Reconnaissance)資産の使用を最適化する。 このような解を見つけることはNP-Hard問題であり、古典的なコンピュータでは効率的に解けないことが多い。 我々は、現在の古典的手法に対してスピードアップを提供する可能性のある、短期量子アルゴリズムについて検討する。
  論文  参考訳（メタデータ） (2024-09-27T10:58:25Z)
• A Greedy Quantum Route-Generation Algorithm [0.0]
  本稿では,量子コンピュータから得られた全てのサンプルからの情報を用いて,経路を生成するグリーディアルゴリズムを提案する。 有向非巡回グラフ (DAG) としての定式化における量子ビットの関係に気付き, 実現可能な解を適応的に構築するアルゴリズムを設計した。
  論文  参考訳（メタデータ） (2024-05-05T21:20:46Z)
• 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)
• Light Unbalanced Optimal Transport [69.18220206873772]
  理論的に最適化され、軽量で、バランスの取れないEOTソルバを提案する。 我々の進歩は、トラクタブルと非ミニマックス最適化の目的をもたらすUEOT問題の最適化に関する新しい視点の開発である。 我々は,この解法がUEOT解の普遍近似を提供し,一般化限界を得ることを示す。
  論文  参考訳（メタデータ） (2023-03-14T15:44:40Z)
• 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)
• Adversarially Robust Learning for Security-Constrained Optimal Power Flow [55.816266355623085]
  我々は、N-kセキュリティ制約付き最適電力流(SCOPF)の課題に取り組む。 N-k SCOPFは電力網の運用における中核的な問題である。 N-k SCOPF を極小最適化問題とみなす。
  論文  参考訳（メタデータ） (2021-11-12T22:08:10Z)
• Quantum computing approach to railway dispatching and conflict management optimization on single-track railway lines [0.4724825031148411]
  単線鉄道における遅延と競合管理という,実用的な鉄道派遣問題について考察する。 本稿では,量子アニール技術と互換性のある2次非拘束二元最適化(QUBO)モデルを提案する。 概念実証として、D-Wave量子アニールを用いてポーランドの鉄道網から選択した実生活問題を解く。
  論文  参考訳（メタデータ） (2020-10-16T08:17:57Z)
• GACEM: Generalized Autoregressive Cross Entropy Method for Multi-Modal Black Box Constraint Satisfaction [69.94831587339539]
  本稿では,マスク付き自己回帰ニューラルネットワークを用いて解空間上の均一分布をモデル化するクロスエントロピー法(CEM)を提案する。 我々のアルゴリズムは複雑な解空間を表現でき、様々な異なる解領域を追跡できる。
  論文  参考訳（メタデータ） (2020-02-17T20:21:20Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。