論文の概要: Solving the Team Orienteering Problem with Transformers

• arxiv url: http://arxiv.org/abs/2311.18662v1
• Date: Thu, 30 Nov 2023 16:10:35 GMT
• ステータス: 翻訳完了
• システム内更新日: 2023-12-01 15:56:58.477608
• Title: Solving the Team Orienteering Problem with Transformers
• Title（参考訳）: トランスフォーマーによるチームのオリエンテーリング問題の解決
• Authors: Daniel Fuertes, Carlos R. del-Blanco, Fernando Jaureguizar, Narciso Garc\'ia
• Abstract要約: 本稿では,チームオリエンテーリング問題を高速かつ高精度に解決できる多エージェント経路計画システムを提案する。 提案システムは,シナリオの符号化を学習可能な集中型トランスフォーマーニューラルネットワークに基づいている。 提示されたシステムが、最先端の作業の多くをスピードの観点から上回ることができることを示すために、いくつかの実験が実施されている。
• 参考スコア（独自算出の注目度）: 46.93254771681026
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Route planning for a fleet of vehicles is an important task in applications such as package delivery, surveillance, or transportation. This problem is usually modeled as a Combinatorial Optimization problem named as Team Orienteering Problem. The most popular Team Orienteering Problem solvers are mainly based on either linear programming, which provides accurate solutions by employing a large computation time that grows with the size of the problem, or heuristic methods, which usually find suboptimal solutions in a shorter amount of time. In this paper, a multi-agent route planning system capable of solving the Team Orienteering Problem in a very fast and accurate manner is presented. The proposed system is based on a centralized Transformer neural network that can learn to encode the scenario (modeled as a graph) and the context of the agents to provide fast and accurate solutions. Several experiments have been performed to demonstrate that the presented system can outperform most of the state-of-the-art works in terms of computation speed. In addition, the code is publicly available at \url{http://gti.ssr.upm.es/data}.
• Abstract（参考訳）: 車両群のためのルートプランニングは、荷物の配送、監視、輸送といった応用において重要な課題である。 この問題は、通常、チームオリエンテーリング問題と呼ばれる組合せ最適化問題としてモデル化される。 最も一般的なチームオリエンテーリング問題の解法は、主に線形プログラミングに基づいており、問題の大きさに応じて成長する大きな計算時間を利用することで正確な解を提供する。 本稿では,チームのオリエンテーリング問題を迅速かつ正確な方法で解くことができるマルチエージェント経路計画システムを提案する。 提案システムは、(グラフとしてモデル化された)シナリオとエージェントのコンテキストを符号化して、高速で正確なソリューションを提供することができる集中型トランスフォーマーニューラルネットワークに基づいている。 提案手法が計算速度の面で最先端の著作物の大部分を上回ることができることを示す実験がいくつか行われている。 さらに、コードは \url{http://gti.ssr.upm.es/data} で公開されている。

関連論文リスト

• Accelerating Vehicle Routing via AI-Initialized Genetic Algorithms [55.78505925402658]
  車両ルーティング問題(VRP)は、トラベリングセールスパーソン問題の延長であり、進化的最適化における基本的なNPハードチャレンジである。 遺伝的アルゴリズムによってさらに最適化された初期解を迅速に生成するために、強化学習エージェント(事前インスタンスで訓練された)を使用した新しい最適化フレームワークを導入する。 例えば、EARLIは1秒以内に500カ所の車両ルーティングを処理し、同じソリューション品質の現在のソルバよりも10倍高速で、リアルタイムやインタラクティブなルーティングのようなアプリケーションを可能にする。
  論文  参考訳（メタデータ） (2025-04-08T15:21:01Z)
• Adversarial Generative Flow Network for Solving Vehicle Routing Problems [29.954688883643538]
  我々はTransformerベースのアプローチを超えた新しいフレームワーク、すなわちAdversarial Generative Flow Networks (AGFN)を導入する。 AGFNは生成フローネットワーク(GFlowNet)を統合し、様々なソリューション(ルート)を生成できる確率モデルである。 我々は、AGFNフレームワークを用いて、容量化車両ルーティング問題(CVRP)とトラベリングセールスマン問題(TSP)を解決する。
  論文  参考訳（メタデータ） (2025-03-03T03:06:56Z)
• A Multiagent Path Search Algorithm for Large-Scale Coalition Structure Generation [61.08720171136229]
  結合構造生成はマルチエージェントシステムにおける基本的な計算問題である。 我々はCSGの多エージェントパス探索アルゴリズムであるSALDAEを開発し、連立構造グラフ上で運用する。
  論文  参考訳（メタデータ） (2025-02-14T15:21:27Z)
• Learning Multiple Initial Solutions to Optimization Problems [52.9380464408756]
  厳密なランタイム制約の下で、同様の最適化問題を順次解決することは、多くのアプリケーションにとって不可欠である。 本稿では,問題インスタンスを定義するパラメータが与えられた初期解を多種多様に予測する学習を提案する。 提案手法は,すべての評価設定において有意かつ一貫した改善を実現し,必要な初期解の数に応じて効率よくスケールできることを実証した。
  論文  参考訳（メタデータ） (2024-11-04T15:17:19Z)
• Robotic warehousing operations: a learn-then-optimize approach to large-scale neighborhood search [84.39855372157616]
  本稿では,ワークステーションの注文処理,アイテムポッドの割り当て,ワークステーションでの注文処理のスケジュールを最適化することで,ウェアハウジングにおけるロボット部品対ピッカー操作を支援する。 そこで我々は, 大規模近傍探索を用いて, サブプロブレム生成に対する学習を最適化する手法を提案する。 Amazon Roboticsと共同で、我々のモデルとアルゴリズムは、最先端のアプローチよりも、実用的な問題に対するより強力なソリューションを生み出していることを示す。
  論文  参考訳（メタデータ） (2024-08-29T20:22:22Z)
• Solving Complex Multi-UAV Mission Planning Problems using Multi-objective Genetic Algorithms [4.198865250277024]
  本稿では、複雑なミッション計画問題(MPP)を解決するための多目的遺伝的アルゴリズムを提案する。 ソリューションが有効かどうかを確認するために,制約満足度問題(CSP)を用いてハイブリッドフィットネス関数を設計した。 実験の結果、新しいアルゴリズムは優れた解を得ることができるが、問題がより複雑になると、最適解を見つけることも困難になる。
  論文  参考訳（メタデータ） (2024-02-09T16:13:21Z)
• Symmetry-preserving graph attention network to solve routing problems at multiple resolutions [1.9304772860080408]
  問題解決のために,最初の完全同変モデルとトレーニングを導入する。 入力グラフのマルチスケール構造を捉えることが不可欠である。 本稿では,Equi Graph Attention Network (mEGAT) アーキテクチャと組み合わせたマルチレゾリューション方式を提案する。
  論文  参考訳（メタデータ） (2023-10-24T06:22:20Z)
• Genetic Algorithms with Neural Cost Predictor for Solving Hierarchical Vehicle Routing Problems [20.684353068460375]
  車両の経路決定が高次決定と連動する場合、結果の最適化問題は計算に重大な課題をもたらす。 本稿では,ニューラルコスト予測器を用いた遺伝的アルゴリズム(GANCP)という,ディープラーニングに基づく新しいアプローチを提案する。 特に,提案するニューラルネットワークは,静電容量化車両ルーティング問題を解決するHGS-CVRPオープンソースパッケージの目的値について学習する。
  論文  参考訳（メタデータ） (2023-10-22T02:46:37Z)
• Learning to Optimize Permutation Flow Shop Scheduling via Graph-based Imitation Learning [70.65666982566655]
  置換フローショップスケジューリング(PFSS)は製造業で広く使われている。 我々は,より安定かつ正確に収束を加速する専門家主導の模倣学習を通じてモデルを訓練することを提案する。 我々のモデルのネットワークパラメータはわずか37%に減少し、エキスパートソリューションに対する我々のモデルの解のギャップは平均6.8%から1.3%に減少する。
  論文  参考訳（メタデータ） (2022-10-31T09:46:26Z)
• Scalable Vehicle Re-Identification via Self-Supervision [66.2562538902156]
  自動車再同定は、都市規模の車両分析システムにおいて重要な要素の1つである。 車両再設計のための最先端のソリューションの多くは、既存のre-idベンチマークの精度向上に重点を置いており、計算の複雑さを無視することが多い。 推論時間に1つのネットワークのみを使用する自己教師型学習によって、シンプルで効果的なハイブリッドソリューションを提案する。
  論文  参考訳（メタデータ） (2022-05-16T12:14:42Z)
• Combining Reinforcement Learning and Optimal Transport for the Traveling Salesman Problem [18.735056206844202]
  我々は,従来の自己回帰的アプローチよりもはるかに高速に,監督や推論なしに学習できるモデルを構築することができることを示す。 また、ディープラーニングモデルに最適なトランスポートアルゴリズムを組み込むことで、エンドツーエンドのトレーニング中に割り当て制約を強制する利点を実証的に評価する。
  論文  参考訳（メタデータ） (2022-03-02T07:21:56Z)
• Multi-Agent Path Planning Using Deep Reinforcement Learning [0.0]
  本稿では, 深部強化型マルチエージェントパス計画手法を提案する。 この実験はシミュレーション環境で実現され、この環境では異なるマルチエージェントパス計画問題が発生する。 生成した問題は実際に車両経路問題と類似しており、多エージェント深部強化学習を用いて解かれる。
  論文  参考訳（メタデータ） (2021-10-04T13:56:23Z)
• Deep Policy Dynamic Programming for Vehicle Routing Problems [89.96386273895985]
  本稿では,学習ニューラルの強みと動的プログラミングアルゴリズムの強みを組み合わせた深層ポリシー動的プログラミング(d pdp)を提案する。 D PDPは、例の解からエッジを予測するために訓練されたディープニューラルネットワークから派生したポリシーを使用して、DP状態空間を優先し、制限する。 本研究では,旅行セールスマン問題 (TSP) と車両ルーティング問題 (VRP) の枠組みを評価し,ニューラルネットワークが(制限された)DPアルゴリズムの性能を向上させることを示す。
  論文  参考訳（メタデータ） (2021-02-23T15:33:57Z)
• Multi-Agent Routing Value Iteration Network [88.38796921838203]
  疎結合グラフの学習値に基づいてマルチエージェントルーティングを行うことができるグラフニューラルネットワークに基づくモデルを提案する。 最大25ノードのグラフ上で2つのエージェントでトレーニングしたモデルでは,より多くのエージェントやノードを持つ状況に容易に一般化できることが示されている。
  論文  参考訳（メタデータ） (2020-07-09T22:16:45Z)
• A Novel Multi-Agent System for Complex Scheduling Problems [2.294014185517203]
  本稿では,様々な問題領域に適用可能なマルチエージェントシステムの概念と実装について述べる。 提案手法の有効性を示すため,NP-hardスケジューリング問題をシミュレートする。 本稿では,レイアウトの複雑さの低減,複雑なシステムの制御の改善,拡張性など,エージェントベースのアプローチの利点を強調した。
  論文  参考訳（メタデータ） (2020-04-20T14:04:58Z)
• Multi-Vehicle Routing Problems with Soft Time Windows: A Multi-Agent Reinforcement Learning Approach [9.717648122961483]
  ソフトタイムウインドウ(MVRPSTW)を用いたマルチ車両ルーティング問題は、都市ロジスティクスシステムにおいて不可欠である。 従来の手法は計算効率と解の質のジレンマを引き起こす。 そこで本研究では,ルーティング問題の解決に要する時間的オフライントレーニングのメリットを即時評価する,Multi-Agent Attention Modelと呼ばれる新しい強化学習アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-02-13T14:26:27Z)
• Reinforcement Learning Based Vehicle-cell Association Algorithm for Highly Mobile Millimeter Wave Communication [53.47785498477648]
  本稿では,ミリ波通信網における車とセルの関連性について検討する。 まず、ユーザ状態(VU)問題を離散的な非車両関連最適化問題として定式化する。 提案手法は,複数のベースライン設計と比較して,ユーザの複雑性とVUEの20%削減の合計で最大15%のゲインが得られる。
  論文  参考訳（メタデータ） (2020-01-22T08:51:05Z)

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

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