論文の概要: Deep Reinforcement Learning for Traveling Purchaser Problems

• arxiv url: http://arxiv.org/abs/2404.02476v1
• Date: Wed, 3 Apr 2024 05:32:10 GMT
• ステータス: 処理完了
• システム内更新日: 2024-04-04 18:29:43.545728
• Title: Deep Reinforcement Learning for Traveling Purchaser Problems
• Title（参考訳）: 旅行購入問題に対する深層強化学習
• Authors: Haofeng Yuan, Rongping Zhu, Wanlu Yang, Shiji Song, Keyou You, Yuli Zhang,
• Abstract要約: 旅行購入問題(TPP)は幅広いアプリケーションにおいて重要な最適化問題である。 本稿では,ルート構築と購入計画を個別に扱う,深層強化学習(DRL)に基づく新しいアプローチを提案する。 メタラーニング戦略を導入することで、大規模なTPPインスタンス上で安定してポリシーネットワークをトレーニングすることができる。
• 参考スコア（独自算出の注目度）: 25.28040225019598
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The traveling purchaser problem (TPP) is an important combinatorial optimization problem with broad applications. Due to the coupling between routing and purchasing, existing works on TPPs commonly address route construction and purchase planning simultaneously, which, however, leads to exact methods with high computational cost and heuristics with sophisticated design but limited performance. In sharp contrast, we propose a novel approach based on deep reinforcement learning (DRL), which addresses route construction and purchase planning separately, while evaluating and optimizing the solution from a global perspective. The key components of our approach include a bipartite graph representation for TPPs to capture the market-product relations, and a policy network that extracts information from the bipartite graph and uses it to sequentially construct the route. One significant benefit of our framework is that we can efficiently construct the route using the policy network, and once the route is determined, the associated purchasing plan can be easily derived through linear programming, while, leveraging DRL, we can train the policy network to optimize the global solution objective. Furthermore, by introducing a meta-learning strategy, the policy network can be trained stably on large-sized TPP instances, and generalize well across instances of varying sizes and distributions, even to much larger instances that are never seen during training. Experiments on various synthetic TPP instances and the TPPLIB benchmark demonstrate that our DRL-based approach can significantly outperform well-established TPP heuristics, reducing the optimality gap by 40%-90%, and also showing an advantage in runtime, especially on large-sized instances.
• Abstract（参考訳）: 旅行購入問題(TPP)は、幅広い応用において重要な組合せ最適化問題である。 ルーティングと購入の結合のため、既存のTPPの作業はルート構築と購入計画を同時に扱うことが一般的であり、高い計算コストと厳密な設計を伴うヒューリスティックな手法をもたらすが、性能は限られている。 対照的に、我々はルート構築と購入計画を個別に扱う深層強化学習(DRL)に基づく新しいアプローチを提案し、グローバルな視点からソリューションを評価し、最適化する。 提案手法の主な構成要素は,TPP が市場生産関係を捉えるための二部グラフ表現と,その二部グラフから情報を抽出し,それを用いて経路を逐次構築するポリシネットワークである。 このフレームワークの重要な利点は、ポリシーネットワークを用いて効率的にルートを構築することができ、ルートが決定されると、関連する購入計画は線形プログラミングにより容易に導出でき、DRLを利用することで、ポリシーネットワークをトレーニングして、グローバルなソリューションの目的を最適化することができることである。 さらに、メタラーニング戦略を導入することで、ポリシーネットワークは大規模TPPインスタンス上で安定してトレーニングすることができ、トレーニング中に見たことのないはるかに大きなインスタンスであっても、さまざまなサイズや分布のインスタンスに対して適切に一般化することができる。 様々な合成TPPインスタンスとTPPLIBベンチマークの実験により、DRLベースのアプローチは、確立されたTPPヒューリスティックスを大幅に上回り、最適性ギャップを40%-90%削減し、特に大規模インスタンスにおいて実行時に有利であることを示す。

関連論文リスト

• Enhancing Large-scale UAV Route Planing with Global and Local Features via Reinforcement Graph Fusion [8.03678640864589]
  本稿では,現在のUAVRPソルバを大規模インスタンスに堅牢に拡張するための一般化フレームワークを提案する。 グローバルな特徴を保ちながら,大規模な事例から部分グラフを抽出するために,Delaunay三角測量を用いる。 ユーザの要求に応じてカスタマイズ可能なデコード戦略を実装し,高品質なソリューションを実現する。
  論文  参考訳（メタデータ） (2024-12-20T03:54:43Z)
• SCoTT: Wireless-Aware Path Planning with Vision Language Models and Strategic Chains-of-Thought [78.53885607559958]
  複雑な無線環境における経路計画を実現するために,視覚言語モデル(VLM)を用いた新しい手法を提案する。 この目的のために、実世界の無線レイトレーシングデータを用いたデジタルツインからの洞察を探索する。 その結果, SCoTT はDP-WA* と比較して非常に近い平均経路ゲインを実現し, 同時に一貫した経路長が得られることがわかった。
  論文  参考訳（メタデータ） (2024-11-27T10:45:49Z)
• OffRIPP: Offline RL-based Informative Path Planning [12.705099730591671]
  IPPはロボット工学において重要なタスクであり、ターゲット環境に関する貴重な情報を収集するためには、エージェントが経路を設計する必要がある。 トレーニング中のリアルタイムインタラクションを必要とせずに情報ゲインを最適化するオフラインRLベースのIPPフレームワークを提案する。 我々は、広範囲なシミュレーションと実世界の実験を通して、この枠組みを検証する。
  論文  参考訳（メタデータ） (2024-09-25T11:30:59Z)
• Pointerformer: Deep Reinforced Multi-Pointer Transformer for the Traveling Salesman Problem [67.32731657297377]
  トラベリングセールスマン問題(TSP)は、もともと輸送と物流の領域で発生した古典的な経路最適化問題である。 近年, 深層強化学習は高い推論効率のため, TSP の解法として採用されている。 本稿では,多点変換器をベースとした新しいエンドツーエンドDRL手法であるPointerformerを提案する。
  論文  参考訳（メタデータ） (2023-04-19T03:48:32Z)
• MARLIN: Soft Actor-Critic based Reinforcement Learning for Congestion Control in Real Networks [63.24965775030673]
  そこで本研究では,汎用的な渋滞制御(CC)アルゴリズムを設計するための新しい強化学習(RL)手法を提案する。 我々の解であるMARLINは、Soft Actor-Criticアルゴリズムを用いてエントロピーとリターンの両方を最大化する。 我々は,MARLINを実ネットワーク上で訓練し,実ミスマッチを克服した。
  論文  参考訳（メタデータ） (2023-02-02T18:27:20Z)
• Sequential Information Design: Markov Persuasion Process and Its Efficient Reinforcement Learning [156.5667417159582]
  本稿では,逐次情報設計の新たなモデル,すなわちマルコフ説得過程(MPP)を提案する。 MPPのプランニングは、ミオピックレシーバーに同時に説得されるシグナルポリシーを見つけ、送信者の最適な長期累積ユーティリティを誘導する、というユニークな課題に直面している。 我々は,楽観主義と悲観主義の両原理の新たな組み合わせを特徴とする,実証可能な効率のよい非回帰学習アルゴリズム,Optimism-Pessimism Principle for Persuasion Process (OP4) を設計する。
  論文  参考訳（メタデータ） (2022-02-22T05:41:43Z)
• Towards Deployment-Efficient Reinforcement Learning: Lower Bound and Optimality [141.89413461337324]
  展開効率は、強化学習(RL)の多くの実世界の応用にとって重要な基準である 本稿では,「制約付き最適化」の観点から,デプロイ効率の高いRL(DE-RL)の理論的定式化を提案する。
  論文  参考訳（メタデータ） (2022-02-14T01:31:46Z)
• A Deep Reinforcement Learning Approach for Constrained Online Logistics Route Assignment [4.367543599338385]
  物流業界にとって、各出荷区画に適切な物流ルートを割り当てる方法が不可欠である。 このオンライン経路割り当て問題は、制約付きオンライン意思決定問題とみなすことができる。 我々はPPO-RAと呼ばれるモデルフリーDRLアプローチを開発し、経路割当(RA)の課題に対処する専用の技術を用いてPPO(Pximal Policy Optimization)を改善した。
  論文  参考訳（メタデータ） (2021-09-08T07:27:39Z)

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

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