論文の概要: H-TSP: Hierarchically Solving the Large-Scale Travelling Salesman Problem

• arxiv url: http://arxiv.org/abs/2304.09395v1
• Date: Wed, 19 Apr 2023 03:10:30 GMT
• ステータス: 処理完了
• システム内更新日: 2023-04-20 15:38:34.117476
• Title: H-TSP: Hierarchically Solving the Large-Scale Travelling Salesman Problem
• Title（参考訳）: H-TSP: 大規模トラベルセールスマン問題の階層的解決
• Authors: Xuanhao Pan, Yan Jin, Yuandong Ding, Mingxiao Feng, Li Zhao, Lei Song, Jiang Bian
• Abstract要約: 本稿では,大規模トラベリングセールスマン問題(TSP)に対処する階層的強化学習(H-TSP)に基づくエンドツーエンド学習フレームワークを提案する。 我々は,H-TSPがSOTA検索に匹敵する結果が得られることを示し,時間消費を2桁まで削減する(3.32s vs. 395.85s)。 ソリューションの品質に関してはまだSOTAの結果にギャップがあるが、H-TSPは実用的なアプリケーション、特にオンコールルーティングや乗車などの時間に敏感なアプリケーションに有用であると考えている。
• 参考スコア（独自算出の注目度）: 11.310986634385742
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose an end-to-end learning framework based on hierarchical reinforcement learning, called H-TSP, for addressing the large-scale Travelling Salesman Problem (TSP). The proposed H-TSP constructs a solution of a TSP instance starting from the scratch relying on two components: the upper-level policy chooses a small subset of nodes (up to 200 in our experiment) from all nodes that are to be traversed, while the lower-level policy takes the chosen nodes as input and outputs a tour connecting them to the existing partial route (initially only containing the depot). After jointly training the upper-level and lower-level policies, our approach can directly generate solutions for the given TSP instances without relying on any time-consuming search procedures. To demonstrate effectiveness of the proposed approach, we have conducted extensive experiments on randomly generated TSP instances with different numbers of nodes. We show that H-TSP can achieve comparable results (gap 3.42% vs. 7.32%) as SOTA search-based approaches, and more importantly, we reduce the time consumption up to two orders of magnitude (3.32s vs. 395.85s). To the best of our knowledge, H-TSP is the first end-to-end deep reinforcement learning approach that can scale to TSP instances of up to 10000 nodes. Although there are still gaps to SOTA results with respect to solution quality, we believe that H-TSP will be useful for practical applications, particularly those that are time-sensitive e.g., on-call routing and ride hailing service.
• Abstract（参考訳）: 本稿では,大規模トラベリングセールスマン問題(TSP)に対する階層的強化学習(H-TSP)に基づくエンドツーエンド学習フレームワークを提案する。 提案したH-TSPは、2つのコンポーネントに依存するスクラッチから始まるTSPインスタンスのソリューションを構築する: 上位レベルポリシーは、トラバースされる全てのノードから、最小200個のノードの小さなサブセットを選択し、下位レベルポリシーは選択されたノードを入力として、それらを既存の部分ルート(当初はデポのみを含む)に接続するツアーを出力する。 提案手法は,上位と下位のポリシを共同でトレーニングすることで,時間を要する検索手順に頼ることなく,与えられたTSPインスタンスのソリューションを直接生成することができる。 提案手法の有効性を示すため,ノード数が異なるランダムに生成されたTSPインスタンスについて広範な実験を行った。 以上より,h-tsp は sota の検索方式と同等の結果 (gap 3.42% 対 7.32%) が得られ,さらに2桁のマグニチュード (3.32s 対 395.85s) を削減できることを示した。 私たちの知る限りでは、H-TSPは、最大10000ノードのTSPインスタンスにスケール可能な、最初のエンドツーエンドの深層強化学習アプローチです。 ソリューションの品質に関してはまだSOTAの結果にギャップがあるが、H-TSPは実用的なアプリケーション、特にオンコールルーティングや配車サービスなど、時間に敏感なアプリケーションに有用であると考えている。

関連論文リスト

• Start from Zero: Triple Set Prediction for Automatic Knowledge Graph Completion [49.19814695500355]
  トリプルセット予測(TSP)と呼ばれるグラフレベルの自動KG補完タスクを提案する。 TSPは、欠落した三重項の要素が与えられていないと仮定する。 予測のための巨大な候補三重項に対処するために,新しい,効率的なサブグラフベースGPHTを提案する。
  論文  参考訳（メタデータ） (2024-06-26T08:26:32Z)
• Learn to Tour: Operator Design For Solution Feasibility Mapping in Pickup-and-delivery Traveling Salesman Problem [12.34897099691387]
  本稿では,旅行セールスマン問題(TSP)の学習方法を提案する。 1対1のピックアップ・アンド・デリバリノードのシーケンスで一番短いツアーを見つける。 PDTSPでは、各ピックアップノードを対応する配信ノードの前に訪問しなければならないという優先的な制約を満たさなければならない。
  論文  参考訳（メタデータ） (2024-04-17T15:05:51Z)
• Hint-before-Solving Prompting: Guiding LLMs to Effectively Utilize Encoded Knowledge [85.17343729885003]
  我々は,Hint-before-Solving Prompting (HSP)を導入し,その問題を解くためのヒントを生成する。 HSPは推論タスクの精度を効果的に向上させることができる。 我々はHSPと細調整されたLlemma-7Bに基づいてHSPMATHデータセットを構築し、64.3精度を達成した。
  論文  参考訳（メタデータ） (2024-02-22T05:58:03Z)
• Pointerformer: Deep Reinforced Multi-Pointer Transformer for the Traveling Salesman Problem [67.32731657297377]
  トラベリングセールスマン問題(TSP)は、もともと輸送と物流の領域で発生した古典的な経路最適化問題である。 近年, 深層強化学習は高い推論効率のため, TSP の解法として採用されている。 本稿では,多点変換器をベースとした新しいエンドツーエンドDRL手法であるPointerformerを提案する。
  論文  参考訳（メタデータ） (2023-04-19T03:48:32Z)
• DPTDR: Deep Prompt Tuning for Dense Passage Retrieval [53.217524851268216]
  ディーププロンプトチューニング(DPT)は多くの自然言語処理(NLP)タスクで大きな成功を収めている。 しかし、微細チューニング(FT)が依然として支配的な高密度検索においては、十分に解明されていない。 本稿では,DPTに基づく検索手法,すなわち検索指向の中間事前学習と統合負のマイニングの2つのモデル非依存型およびタスク非依存型戦略を提案する。
  論文  参考訳（メタデータ） (2022-08-24T12:55:00Z)
• Improving Generalization of Deep Reinforcement Learning-based TSP Solvers [19.29028564568974]
  本稿では,ディープラーニングアーキテクチャとDRL学習方法を含むMAGICという新しいアプローチを提案する。 マルチレイヤパーセプトロン,グラフニューラルネットワーク,アテンションモデルを統合したアーキテクチャでは,旅行セールスマンソリューションを逐次生成するポリシを定義している。 1) DRLポリシー更新をローカル検索とインターリーブし(新しいローカル検索技術を用いて)、(2) 新たなシンプルなベースラインを使用し、(3) 勾配学習を適用した。
  論文  参考訳（メタデータ） (2021-10-06T15:16:19Z)
• Learning Semantic Segmentation of Large-Scale Point Clouds with Random Sampling [52.464516118826765]
  我々はRandLA-Netを紹介した。RandLA-Netは、大規模ポイントクラウドのポイントごとの意味を推論する、効率的で軽量なニューラルネットワークアーキテクチャである。 我々のアプローチの鍵は、より複雑な点選択アプローチではなく、ランダムな点サンプリングを使用することである。 我々のRandLA-Netは、既存のアプローチよりも最大200倍高速な1回のパスで100万ポイントを処理できます。
  論文  参考訳（メタデータ） (2021-07-06T05:08:34Z)
• Learning to Optimise General TSP Instances [2.6782615615913348]
  トラベリングセールスマン問題(TSP)は古典的な最適化問題である。 ディープラーニングはメタラーニングに成功し、過去の問題解決活動が将来のインスタンスを最適化する方法を学ぶのに役立つ。 本稿では,多種多様なTSP問題を解くための学習に基づく新しいアプローチを提案する。
  論文  参考訳（メタデータ） (2020-10-23T07:37:16Z)
• Solving the Clustered Traveling Salesman Problem via TSP methods [16.304413942851397]
  クラスタ化トラベリングセールスマン問題(CTSP)は、一般的なトラベリングセールスマン問題(TSP)の変種である。 本研究ではCTSPをよく研究されたTSPに変換することでCTSPを解く変換手法について検討する。
  論文  参考訳（メタデータ） (2020-07-10T08:56:06Z)
• Towards Feature-free TSP Solver Selection: A Deep Learning Approach [35.05032046810422]
  トラベリングセールスマン問題(TSP)は古典的なNPハード問題であり、多くの分野や産業で広く応用されている。 本稿では,TSPソルバ選択のためのディープラーニングフレームワークであるCTASを提案する。
  論文  参考訳（メタデータ） (2020-06-01T04:48:36Z)
• MetricUNet: Synergistic Image- and Voxel-Level Learning for Precise CT Prostate Segmentation via Online Sampling [66.01558025094333]
  本稿では,前立腺領域を高速に局在させる第1段階と,前立腺領域を正確に区分する第2段階の2段階のフレームワークを提案する。 マルチタスクネットワークにおけるボクセルワイドサンプリングによる新しいオンラインメトリック学習モジュールを提案する。 本手法は,従来のクロスエントロピー学習法やDice損失学習法と比較して,より代表的なボクセルレベルの特徴を効果的に学習することができる。
  論文  参考訳（メタデータ） (2020-05-15T10:37:02Z)

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

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