論文の概要: Learning to Solve Multiple-TSP with Time Window and Rejections via Deep Reinforcement Learning

• arxiv url: http://arxiv.org/abs/2209.06094v1
• Date: Tue, 13 Sep 2022 15:44:48 GMT
• ステータス: 処理完了
• システム内更新日: 2022-09-14 12:23:05.031639
• Title: Learning to Solve Multiple-TSP with Time Window and Rejections via Deep Reinforcement Learning
• Title（参考訳）: 時間窓による多重tsp解の学習と深層強化学習による拒絶
• Authors: Rongkai Zhang, Cong Zhang, Zhiguang Cao, Wen Song, Puay Siew Tan, Jie Zhang, Bihan Wen, Justin Dauwels
• Abstract要約: 本稿では,トラベリングセールスマン問題(TSP)の難易度・難易度に対処するマネージャ・ワーカー・フレームワークを提案する。 提案フレームワークでは,MTSPTWRをグラフアイソモーフィックネットワーク(GIN)ベースのポリシネットワークを通じて,各車両に顧客を割り当てることで,サブルーチンタスクに分割することを学ぶ。 作業者エージェントは、各車両の走行距離と拒絶率の両方の観点からコストを最小化し、サブルーチンタスクの解決を学習し、その最大値を管理者エージェントに送り、より良い課題を学習する。
• 参考スコア（独自算出の注目度）: 36.07067163589422
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose a manager-worker framework based on deep reinforcement learning to tackle a hard yet nontrivial variant of Travelling Salesman Problem (TSP), \ie~multiple-vehicle TSP with time window and rejections (mTSPTWR), where customers who cannot be served before the deadline are subject to rejections. Particularly, in the proposed framework, a manager agent learns to divide mTSPTWR into sub-routing tasks by assigning customers to each vehicle via a Graph Isomorphism Network (GIN) based policy network. A worker agent learns to solve sub-routing tasks by minimizing the cost in terms of both tour length and rejection rate for each vehicle, the maximum of which is then fed back to the manager agent to learn better assignments. Experimental results demonstrate that the proposed framework outperforms strong baselines in terms of higher solution quality and shorter computation time. More importantly, the trained agents also achieve competitive performance for solving unseen larger instances.
• Abstract（参考訳）: 本稿では、時間窓と拒否(mTSPTWR)を備えたトラベリングセールスマン問題(TSP)、複数車両TSP(TSP)の難易度かつ非自明な変種に対応するための、深い強化学習に基づくマネージャ・ワーカー・フレームワークを提案する。 特に,提案フレームワークでは,マネージャエージェントが,グラフ同型ネットワーク(GIN)ベースのポリシネットワークを通じて,各車両に顧客を割り当てることで,mTSPTWRをサブルーチンタスクに分割することを学ぶ。 作業者エージェントは、各車両の走行距離と拒絶率の両方の観点からコストを最小化し、サブルーチンタスクの解決を学習し、その最大値を管理者エージェントに送り、より良い課題を学習する。 実験結果から,提案フレームワークは解の質が向上し,計算時間も短縮された。 さらに重要なことに、訓練されたエージェントは、目に見えない大きなインスタンスを解決するための競争的パフォーマンスも達成します。

関連論文リスト

• PRIMER: Perception-Aware Robust Learning-based Multiagent Trajectory Planner [29.341840232319292]
  まず、PARMとPARM*、認識対応、分散化、非同期マルチエージェント・トラジェクトリ・プランナについて述べる。 次に、PARM*を専門家実証者として用い、模倣学習(IL)を訓練した学習ベースプランナーであるPRIMERを紹介する。
  論文  参考訳（メタデータ） (2024-06-14T14:16:39Z)
• Temporal Transfer Learning for Traffic Optimization with Coarse-grained Advisory Autonomy [4.809821883560606]
  本稿では,人間ドライバーに対してリアルタイム運転アドバイザリを発行するアドバイザリ自律性について検討する。 ゼロショット転送のためのソースタスクを選択するために,TTLアルゴリズムを導入する。 様々な混合交通シナリオでアルゴリズムを検証する。
  論文  参考訳（メタデータ） (2023-11-27T21:18:06Z)
• Self-regulating Prompts: Foundational Model Adaptation without Forgetting [112.66832145320434]
  本稿では,PromptSRCと呼ばれる自己正規化フレームワークを提案する。 PromptSRCはタスク固有の汎用表現とタスクに依存しない汎用表現の両方に最適化するプロンプトを導く。
  論文  参考訳（メタデータ） (2023-07-13T17:59:35Z)
• Pointerformer: Deep Reinforced Multi-Pointer Transformer for the Traveling Salesman Problem [67.32731657297377]
  トラベリングセールスマン問題(TSP)は、もともと輸送と物流の領域で発生した古典的な経路最適化問題である。 近年, 深層強化学習は高い推論効率のため, TSP の解法として採用されている。 本稿では,多点変換器をベースとした新しいエンドツーエンドDRL手法であるPointerformerを提案する。
  論文  参考訳（メタデータ） (2023-04-19T03:48:32Z)
• Multi-Start Team Orienteering Problem for UAS Mission Re-Planning with Data-Efficient Deep Reinforcement Learning [9.877261093287304]
  我々は、当初車両が補給所から離れた場所にあり、燃料の量が異なるミッション再計画問題について検討する。 そこで我々は,各部分ツアーに対する自己注意と,部分ツアーと残りのノード間のエンコーダ・デコーダの注意を組み込んだポリシーネットワークを構築した。 本稿では,複数の非重複サンプルのロールアウトに基づく局所的なミニバッチベースラインに,グリーディロールアウトベースラインを置き換えたREINFORCEアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-03-02T15:15:56Z)
• 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)
• Multi-Agent Neural Rewriter for Vehicle Routing with Limited Disclosure of Costs [65.23158435596518]
  チームのマルコフゲームとして、部分的に観測可能なコストでマルチサイクルルーティング問題を解く。 我々のマルチエージェント強化学習アプローチである、いわゆるマルチエージェントニューラルリライタは、1エージェントニューラルリライタを利用して、反復的に書き換えるソリューションによって問題を解決する。
  論文  参考訳（メタデータ） (2022-06-13T09:17:40Z)
• DAN: Decentralized Attention-based Neural Network to Solve the MinMax Multiple Traveling Salesman Problem [5.137147284997655]
  我々は、DANと呼ばれるMinMax mTSPを解くために、分散注意に基づくニューラルネットワーク手法を導入する。 DANでは、エージェントは、他のエージェントの将来の決定を予測することによって、ツアーを共同で構築するための完全に分散されたポリシーを学ぶ。 我々は50から1000の都市、5から20のエージェントを含む小規模から大規模mTSPインスタンスで実験を行い、最先端のベースラインと比較した。
  論文  参考訳（メタデータ） (2021-09-09T12:26:04Z)
• Reinforcement Learning for Assignment Problem with Time Constraints [0.0]
  本稿では、労働者グループに複数のタスクをマッピングしたアサインメント問題のためのエンドツーエンドフレームワークを提案する。 我々は,課題に関連する総コストを最小化することにより,問題の最適解を見つけるための強化学習エージェントを訓練する。 また、同じフレームワークを用いて、ビンパッキングおよび静電容量化車両ルーティング問題に関する結果も示す。
  論文  参考訳（メタデータ） (2021-06-05T10:10:52Z)
• TR-BERT: Dynamic Token Reduction for Accelerating BERT Inference [54.791572981834435]
  既存の訓練済み言語モデル(PLM)は推論において計算コストがかかることが多い。 TR-BERT と呼ばれる PLM の推論を高速化する動的トークン削減手法を提案する。 TR-BERTは、トークン削減プロセスを多段階のトークン選択問題として定式化し、強化学習を通じて選択戦略を自動的に学習する。
  論文  参考訳（メタデータ） (2021-05-25T02:28:51Z)

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

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