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

• arxiv url: http://arxiv.org/abs/2404.02476v3
• Date: Fri, 2 Aug 2024 15:30:14 GMT
• ステータス: 処理完了
• システム内更新日: 2024-08-05 18:13:29.870296
• Title: Deep Reinforcement Learning for Traveling Purchaser Problems
• Title（参考訳）: 旅行購入問題に対する深層強化学習
• Authors: Haofeng Yuan, Rongping Zhu, Wanlu Yang, Shiji Song, Keyou You, Yuli Zhang, C. L. Philip Chen,
• Abstract要約: 旅行購入問題(TPP)は幅広いアプリケーションにおいて重要な最適化問題である。 本稿では,ルート構築と購入計画を個別に扱う,深層強化学習(DRL)に基づく新しいアプローチを提案する。 メタラーニング戦略を導入することで、大規模なTPPインスタンス上で安定してポリシーネットワークをトレーニングすることができる。
• 参考スコア（独自算出の注目度）: 61.76626371929574
• 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%削減し、特に大規模インスタンスにおいて実行時に有利であることを示す。

関連論文リスト

• OffRIPP: Offline RL-based Informative Path Planning [12.705099730591671]
  IPPはロボット工学において重要なタスクであり、ターゲット環境に関する貴重な情報を収集するためには、エージェントが経路を設計する必要がある。 トレーニング中のリアルタイムインタラクションを必要とせずに情報ゲインを最適化するオフラインRLベースのIPPフレームワークを提案する。 我々は、広範囲なシミュレーションと実世界の実験を通して、この枠組みを検証する。
  論文  参考訳（メタデータ） (2024-09-25T11:30:59Z)
• An Efficient Learning-based Solver Comparable to Metaheuristics for the Capacitated Arc Routing Problem [67.92544792239086]
  我々は,高度メタヒューリスティックスとのギャップを著しく狭めるため,NNベースの解法を導入する。 まず,方向対応型注意モデル(DaAM)を提案する。 第2に、教師付き事前学習を伴い、堅牢な初期方針を確立するための教師付き強化学習スキームを設計する。
  論文  参考訳（メタデータ） (2024-03-11T02:17:42Z)
• 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)
• Higher-Order Generalization Bounds: Learning Deep Probabilistic Programs via PAC-Bayes Objectives [0.0]
  DPP法を用いてPAC-Bayes一般化境界をプログラムとして表現するためのフレームワークを提供する。 特に, DPP の手法は DPP 表現の構成性に基づく一般化境界の導出に有効であることを示す。 そこで本研究では,高次確率的プログラムに対する原則的学習目標について紹介する。
  論文  参考訳（メタデータ） (2022-03-30T01:14:56Z)
• 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)

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

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