論文の概要: Quantum Annealing Approaches to Solving the Shipment Rerouting Problems

• arxiv url: http://arxiv.org/abs/2501.05624v1
• Date: Thu, 09 Jan 2025 23:47:23 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-13 15:27:11.147303
• Title: Quantum Annealing Approaches to Solving the Shipment Rerouting Problems
• Title（参考訳）: 量子アニーリングによる出荷遅延問題の解法
• Authors: Fei Li, Arul Rhik Mazumder, Max Zhao,
• Abstract要約: 本稿では,NP-hardシークエンシングおよびパッケージング問題を一般化した出荷再帰問題 (SRP) について検討する。 目的は、トラックのセットを選択し、これらのトラックのルートをスケジュールし、総コストを最小化することである。 我々は、新しい数学的プログラミングの定式化と、シーケンシングとパッケージングの問題を同時に解くための新しい洞察を用いる。
• 参考スコア（独自算出の注目度）: 7.888128236684232
• License:
• Abstract: In this paper, we study a shipment rerouting problem (SRP) which generalizes many NP-hard sequencing and packing problems. A SRP's solution has ample practical applications in vehicle scheduling and transportation logistics. Given a network of hubs, a set of goods must be delivered by trucks from their source-hubs to their respective destination-hubs. The objective is to select a set of trucks and to schedule these trucks' routes so that the total cost is minimized. The problem SRP is NP-hard; only classical approximation algorithms have been known for some of its NP-hard variants. In this work, we design classical algorithms and quantum annealing algorithms for this problem with various capacitated trucks. The algorithms that we design use novel mathematical programming formulations and new insights into solving sequencing and packing problems simultaneously. Such formulations take advantage of network infrastructure, shipments, and truck capacities. We conduct extensive experiments showing that in various scenarios, the quantum annealing solver generates near-optimal or optimal solutions much faster than the classical algorithm solver.
• Abstract（参考訳）: 本稿では,NP-hardシークエンシングおよびパッケージング問題を一般化した出荷再帰問題 (SRP) について検討する。 SRPのソリューションは、車両のスケジューリングと輸送のロジスティクスに多くの実用的応用がある。 ハブのネットワークが与えられた場合、商品のセットは、ソースハブからそれぞれの目的地ハブへトラックによって配達されなければならない。 目的は、トラックのセットを選択し、これらのトラックのルートをスケジュールし、総コストを最小化することである。 SRP の問題は NP-hard であり、NP-hard の変種で知られているのは古典的な近似アルゴリズムのみである。 本研究では, 様々な静電容量トラックを用いて, 古典的アルゴリズムと量子アニールアルゴリズムを設計する。 私たちが設計するアルゴリズムは、新しい数学的プログラミングの定式化と、シーケンシングとパッケージングの問題を同時に解くための新たな洞察を使用する。 このような定式化は、ネットワークインフラストラクチャ、出荷、トラックの容量を活用する。 我々は、様々なシナリオにおいて、量子アニール解法が古典的アルゴリズム解法よりもはるかに高速に近似的あるいは最適解を生成することを示す広範な実験を行った。

関連論文リスト

• A Multiagent Path Search Algorithm for Large-Scale Coalition Structure Generation [61.08720171136229]
  結合構造生成はマルチエージェントシステムにおける基本的な計算問題である。 我々はCSGの多エージェントパス探索アルゴリズムであるSALDAEを開発し、連立構造グラフ上で運用する。
  論文  参考訳（メタデータ） (2025-02-14T15:21:27Z)
• Quantum Annealing based Hybrid Strategies for Real Time Route Optimization [0.0]
  本稿では,複雑性を低減しつつ,問題を高速に解決する手法を提案する。 ハイブリッド2ステップ(H2S)とハイブリッド3ステップ(H3S)の2つのアルゴリズムを用いる。 どちらのアルゴリズムも、ソリューション時間とソリューションコストの両面で、有望な結果をもたらす。
  論文  参考訳（メタデータ） (2024-11-21T14:45:40Z)
• Qubit efficient quantum algorithms for the vehicle routing problem on NISQ processors [48.68474702382697]
  時間窓付き車両ルーティング問題(VRPTW)は、ロジスティクス業界で直面する一般的な最適化問題である。 そこで本研究では,以前に導入した量子ビット符号化方式を用いて,バイナリ変数の数を削減した。
  論文  参考訳（メタデータ） (2023-06-14T13:44:35Z)
• The Basis of Design Tools for Quantum Computing: Arrays, Decision Diagrams, Tensor Networks, and ZX-Calculus [55.58528469973086]
  量子コンピュータは、古典的コンピュータが決して起こらない重要な問題を効率的に解決することを約束する。 完全に自動化された量子ソフトウェアスタックを開発する必要がある。 この研究は、今日のツールの"内部"の外観を提供し、量子回路のシミュレーション、コンパイル、検証などにおいてこれらの手段がどのように利用されるかを示す。
  論文  参考訳（メタデータ） (2023-01-10T19:00:00Z)
• Quantum Neural Networks for a Supply Chain Logistics Application [0.0]
  複数のトラックと複雑な需要構造を備えたサプライチェーンロジスティクスのための車両ルーティングという,重要な問題に関する1つのハイブリッドアルゴリズムについて検討する。 量子回路を組み込んだニューラルネットワークを用いて強化学習を行う。 人間のトラックの割り当てに匹敵する結果が得られます。
  論文  参考訳（メタデータ） (2022-11-30T15:35:53Z)
• Supply Chain Logistics with Quantum and Classical Annealing Algorithms [0.0]
  ノイズの多い中間スケール量子(NISQ)ハードウェアは、実用上重要なフルスケール最適化問題とほとんど互換性がない。 本研究では,サプライチェーンのロジスティクスにおいて,企業の運用規模において,実質的な商業価値,多輪車経路の問題について検討する。 我々の研究は、NASQデバイスをハイブリッド方式で応用するための車両ルーティング以外のコンテキストに適用可能な一連の技術を提供し、商業的関心事の大規模問題に応用する。
  論文  参考訳（メタデータ） (2022-05-09T17:36:21Z)
• Optimizing Tensor Network Contraction Using Reinforcement Learning [86.05566365115729]
  本稿では,グラフニューラルネットワーク(GNN)と組み合わせた強化学習(RL)手法を提案する。 この問題は、巨大な検索スペース、重い尾の報酬分布、そして困難なクレジット割り当てのために非常に難しい。 GNNを基本方針として利用するRLエージェントが,これらの課題にどのように対処できるかを示す。
  論文  参考訳（メタデータ） (2022-04-18T21:45:13Z)
• Analysis of Vehicle Routing Problem in Presence of Noisy Channels [0.0]
  車両ルーティング問題(VRP)はNPハード最適化問題である。 この研究は、変数 ANSATZ 上の変分量子固有解法を用いて、3 と 4 の都市に基本的な VRP ソリューションを構築する。
  論文  参考訳（メタデータ） (2021-12-28T10:20:42Z)
• Deep Policy Dynamic Programming for Vehicle Routing Problems [89.96386273895985]
  本稿では,学習ニューラルの強みと動的プログラミングアルゴリズムの強みを組み合わせた深層ポリシー動的プログラミング(d pdp)を提案する。 D PDPは、例の解からエッジを予測するために訓練されたディープニューラルネットワークから派生したポリシーを使用して、DP状態空間を優先し、制限する。 本研究では,旅行セールスマン問題 (TSP) と車両ルーティング問題 (VRP) の枠組みを評価し,ニューラルネットワークが(制限された)DPアルゴリズムの性能を向上させることを示す。
  論文  参考訳（メタデータ） (2021-02-23T15:33:57Z)
• 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)

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

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