論文の概要: Hierarchical Neural Constructive Solver for Real-world TSP Scenarios

• arxiv url: http://arxiv.org/abs/2408.03585v1
• Date: Wed, 7 Aug 2024 06:44:47 GMT
• ステータス: 処理完了
• システム内更新日: 2024-08-08 13:43:46.286449
• Title: Hierarchical Neural Constructive Solver for Real-world TSP Scenarios
• Title（参考訳）: 実世界TSPシナリオのための階層型ニューラルコンストラクティブソルバー
• Authors: Yong Liang Goh, Zhiguang Cao, Yining Ma, Yanfei Dong, Mohammed Haroon Dupty, Wee Sun Lee,
• Abstract要約: 本稿では,産業環境に関連する現実的なトラベリングセールスマン問題(TSP)について紹介する。 我々の階層的アプローチは、古典的モデルと最近のトランスモデルの両方と比較して優れたパフォーマンスをもたらす。
• 参考スコア（独自算出の注目度）: 27.986011761759567
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Existing neural constructive solvers for routing problems have predominantly employed transformer architectures, conceptualizing the route construction as a set-to-sequence learning task. However, their efficacy has primarily been demonstrated on entirely random problem instances that inadequately capture real-world scenarios. In this paper, we introduce realistic Traveling Salesman Problem (TSP) scenarios relevant to industrial settings and derive the following insights: (1) The optimal next node (or city) to visit often lies within proximity to the current node, suggesting the potential benefits of biasing choices based on current locations. (2) Effectively solving the TSP requires robust tracking of unvisited nodes and warrants succinct grouping strategies. Building upon these insights, we propose integrating a learnable choice layer inspired by Hypernetworks to prioritize choices based on the current location, and a learnable approximate clustering algorithm inspired by the Expectation-Maximization algorithm to facilitate grouping the unvisited cities. Together, these two contributions form a hierarchical approach towards solving the realistic TSP by considering both immediate local neighbourhoods and learning an intermediate set of node representations. Our hierarchical approach yields superior performance compared to both classical and recent transformer models, showcasing the efficacy of the key designs.
• Abstract（参考訳）: ルーティング問題に対する既存のニューラルコンストラクティブソルバは、主にトランスフォーマーアーキテクチャを採用しており、経路構築をセット・ツー・シーケンス学習タスクとして概念化している。 しかし、それらの効果は、実世界のシナリオを不適切にキャプチャする全くランダムな問題インスタンスで主に実証されてきた。 本稿では,産業環境に関連する現実的なトラベリングセールスマン問題 (TSP) のシナリオを紹介し,(1) 最適な次のノード(または都市)は,現在位置に基づくバイアス選択の潜在的なメリットを示唆する。 2) TSP を効果的に解くには,未確認ノードのロバストな追跡と,グループ化戦略の簡潔化が必要である。 これらの知見に基づいて,Hypernetworksにインスパイアされた学習可能な選択層を統合して,現在位置に基づいて選択を優先順位付けする手法と,期待・最大化アルゴリズムにインスパイアされた学習可能な近似クラスタリングアルゴリズムを提案する。 これら2つのコントリビューションは、直近の局所近傍と中間ノード表現のセットの両方を学習することにより、現実的なTSPを解決するための階層的なアプローチを形成する。 我々の階層的アプローチは、古典的および最近のトランスモデルと比較して優れた性能を示し、鍵設計の有効性を示す。

関連論文リスト

• Towards Adaptive Neighborhood for Advancing Temporal Interaction Graph Modeling [19.831424038609462]
  テンポラルグラフネットワーク(TGN)は、テンポラル相互作用グラフのモデル化において、その顕著な性能を実証している。 本稿では,適応型近傍符号化機構を導入し,既存のTGNの強化を目指す。 既存のTGNとシームレスに統合可能な,フレキシブルなプラグアンドプレイモデルSEANを提案する。
  論文  参考訳（メタデータ） (2024-06-14T07:57:17Z)
• GASE: Graph Attention Sampling with Edges Fusion for Solving Vehicle Routing Problems [6.084414764415137]
  車両のルーティング問題を解決するためにEdges Fusionフレームワークを用いた適応型グラフ注意サンプリングを提案する。 提案手法は,既存の手法を2.08%-6.23%上回り,より強力な一般化能力を示す。
  論文  参考訳（メタデータ） (2024-05-21T03:33:07Z)
• An Efficient Learning-based Solver Comparable to Metaheuristics for the Capacitated Arc Routing Problem [67.92544792239086]
  我々は,高度メタヒューリスティックスとのギャップを著しく狭めるため,NNベースの解法を導入する。 まず,方向対応型注意モデル(DaAM)を提案する。 第2に、教師付き事前学習を伴い、堅牢な初期方針を確立するための教師付き強化学習スキームを設計する。
  論文  参考訳（メタデータ） (2024-03-11T02:17:42Z)
• Adaptive Hierarchical SpatioTemporal Network for Traffic Forecasting [70.66710698485745]
  本稿では,AHSTN(Adaptive Hierarchical SpatioTemporal Network)を提案する。 AHSTNは空間階層を利用し、マルチスケール空間相関をモデル化する。 2つの実世界のデータセットの実験により、AHSTNはいくつかの強いベースラインよりも優れたパフォーマンスを達成することが示された。
  論文  参考訳（メタデータ） (2023-06-15T14:50:27Z)
• On the Effective Usage of Priors in RSS-based Localization [56.68864078417909]
  本稿では、受信信号強度(RSS)指紋と畳み込みニューラルネットワークに基づくアルゴリズムLocUNetを提案する。 本稿では,密集市街地における局所化問題について検討する。 まず,LocUNetがRx位置やRxの事前分布を学習し,トレーニングデータから送信者(Tx)アソシエーションの好みを学習し,その性能を評価できることを示す。
  論文  参考訳（メタデータ） (2022-11-28T00:31:02Z)
• Continuous-Time and Multi-Level Graph Representation Learning for Origin-Destination Demand Prediction [52.0977259978343]
  本稿では,原位置需要予測(CMOD)のための連続時間および多段階動的グラフ表現学習法を提案する。 状態ベクトルは、過去のトランザクション情報を保持し、最近発生したトランザクションに従って継続的に更新される。 北京地下鉄とニューヨークタクシーの2つの実世界のデータセットを用いて実験を行い、そのモデルが最先端のアプローチに対して優れていることを実証した。
  論文  参考訳（メタデータ） (2022-06-30T03:37:50Z)
• Sign-Agnostic CONet: Learning Implicit Surface Reconstructions by Sign-Agnostic Optimization of Convolutional Occupancy Networks [39.65056638604885]
  畳み込み型ネットワークの符号非依存最適化により暗黙的表面再構成を学習する。 この目標をシンプルで効果的な設計で効果的に達成できることを示す。
  論文  参考訳（メタデータ） (2021-05-08T03:35:32Z)
• Dynamic Hierarchical Mimicking Towards Consistent Optimization Objectives [73.15276998621582]
  一般化能力を高めたCNN訓練を推進するための汎用的特徴学習機構を提案する。 DSNに部分的にインスパイアされた私たちは、ニューラルネットワークの中間層から微妙に設計されたサイドブランチをフォークしました。 カテゴリ認識タスクとインスタンス認識タスクの両方の実験により,提案手法の大幅な改善が示された。
  論文  参考訳（メタデータ） (2020-03-24T09:56:13Z)
• Decentralized MCTS via Learned Teammate Models [89.24858306636816]
  本稿では,モンテカルロ木探索に基づくトレーニング可能なオンライン分散計画アルゴリズムを提案する。 深層学習と畳み込みニューラルネットワークを用いて正確なポリシー近似を作成可能であることを示す。
  論文  参考訳（メタデータ） (2020-03-19T13:10:20Z)

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

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