論文の概要: Solving the Clustered Traveling Salesman Problem via TSP methods

• arxiv url: http://arxiv.org/abs/2007.05254v3
• Date: Thu, 14 Apr 2022 11:34:37 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-11 21:59:58.101381
• Title: Solving the Clustered Traveling Salesman Problem via TSP methods
• Title（参考訳）: TSP法によるクラスター旅行セールスマン問題の解法
• Authors: Yongliang Lu, Jin-Kao Hao, Qinghua Wu
• Abstract要約: クラスタ化トラベリングセールスマン問題(CTSP)は、一般的なトラベリングセールスマン問題(TSP)の変種である。 本研究ではCTSPをよく研究されたTSPに変換することでCTSPを解く変換手法について検討する。
• 参考スコア（独自算出の注目度）: 16.304413942851397
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Clustered Traveling Salesman Problem (CTSP) is a variant of the popular Traveling Salesman Problem (TSP) arising from a number of real-life applications. In this work, we explore a transformation approach that solves the CTSP by converting it to the well-studied TSP. For this purpose, we first investigate a technique to convert a CTSP instance to a TSP and then apply powerful TSP solvers (including exact and heuristic solvers) to solve the resulting TSP instance. We want to answer the following questions: How do state-of-the-art TSP solvers perform on clustered instances converted from the CTSP? Do state-of-the-art TSP solvers compete well with the best performing methods specifically designed for the CTSP? For this purpose, we present intensive computational experiments on various benchmark instances to draw conclusions.
• Abstract（参考訳）: クラスタ化トラベリングセールスマン問題(クラスタ化トラベリングセールスマン問題、CTSP)は、多くの実生活アプリケーションから生じる一般的なトラベリングセールスマン問題(TSP)の変種である。 本研究ではCTSPをよく研究されたTSPに変換することでCTSPを解く変換手法を検討する。 この目的のために,まずCTSPインスタンスをTSPに変換する手法について検討し,次に強力なTSPソルバ(正確かつヒューリスティックな解法を含む)を適用して結果のTSPインスタンスを解く。 最先端のTSPソルバは、CTSPから変換されたクラスタ化されたインスタンス上でどのように機能するのか? 最先端のTSPソルバはCTSP用に特別に設計された最高の動作方法とよく競合するのか? この目的のために,様々なベンチマークインスタンスにおける集中計算実験を行い,結論を導出する。

関連論文リスト

• Pointerformer: Deep Reinforced Multi-Pointer Transformer for the Traveling Salesman Problem [67.32731657297377]
  トラベリングセールスマン問題(TSP)は、もともと輸送と物流の領域で発生した古典的な経路最適化問題である。 近年, 深層強化学習は高い推論効率のため, TSP の解法として採用されている。 本稿では,多点変換器をベースとした新しいエンドツーエンドDRL手法であるPointerformerを提案する。
  論文  参考訳（メタデータ） (2023-04-19T03:48:32Z)
• H-TSP: Hierarchically Solving the Large-Scale Travelling Salesman Problem [11.310986634385742]
  本稿では,大規模トラベリングセールスマン問題(TSP)に対処する階層的強化学習(H-TSP)に基づくエンドツーエンド学習フレームワークを提案する。 我々は,H-TSPがSOTA検索に匹敵する結果が得られることを示し,時間消費を2桁まで削減する(3.32s vs. 395.85s)。 ソリューションの品質に関してはまだSOTAの結果にギャップがあるが、H-TSPは実用的なアプリケーション、特にオンコールルーティングや乗車などの時間に敏感なアプリケーションに有用であると考えている。
  論文  参考訳（メタデータ） (2023-04-19T03:10:30Z)
• 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)
• TCT: Convexifying Federated Learning using Bootstrapped Neural Tangent Kernels [141.29156234353133]
  最先端の凸学習手法は、クライアントが異なるデータ分布を持つ場合、集中型よりもはるかにパフォーマンスが劣る。 我々は、この格差は、非NISTityが提示した課題に大きく起因していることを示す。 本稿では,Train-Convexify Neural Network (TCT) 手法を提案する。
  論文  参考訳（メタデータ） (2022-07-13T16:58:22Z)
• Solving the Traveling Salesperson Problem with Precedence Constraints by Deep Reinforcement Learning [59.14935871979047]
  本研究は, 深層強化学習(DRL)を用いた優先制約付きトラベリングセールスパーソン問題(TSPPC)の解を提案する。 これらのアプローチに共通しているのは、マルチヘッドアテンション層に基づくグラフモデルの利用である。
  論文  参考訳（メタデータ） (2022-07-04T14:31:47Z)
• Learning to Solve Travelling Salesman Problem with Hardness-adaptive Curriculum [42.28343071442175]
  本稿では,既存手法の10倍の精度でインスタンスを生成するハードネス適応型ジェネレータを提案する。 提案手法は, 最適性ギャップの観点から, 最先端モデルに対する大幅な改善を実現する。
  論文  参考訳（メタデータ） (2022-04-07T05:59:05Z)
• On the Use of Quality Diversity Algorithms for The Traveling Thief Problem [11.590506672325668]
  現実世界の最適化では、いくつかのサブプロブレムが相互作用し、主要な問題を形成するのが一般的である。 本稿では,旅行セールスパーソン問題(TSP)とクナップサック問題(KP)の相互依存性を品質多様性(QD)アプローチを用いて検討する。
  論文  参考訳（メタデータ） (2021-12-16T05:08:39Z)
• Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instances [55.64521598173897]
  本稿では,旅行セールスマン問題(TSP)のヒートマップ構築に繰り返し使用可能な,小規模モデルのトレーニングを試みる。 ヒートマップは強化学習アプローチ(モンテカルロツリーサーチ)に供給され、高品質のソリューションの検索を案内します。 実験結果によると、この新しいアプローチは、既存の機械学習ベースのTSPアルゴリズムを明らかに上回る。
  論文  参考訳（メタデータ） (2020-12-19T11:06:30Z)
• Learning to Optimise General TSP Instances [2.6782615615913348]
  トラベリングセールスマン問題(TSP)は古典的な最適化問題である。 ディープラーニングはメタラーニングに成功し、過去の問題解決活動が将来のインスタンスを最適化する方法を学ぶのに役立つ。 本稿では,多種多様なTSP問題を解くための学習に基づく新しいアプローチを提案する。
  論文  参考訳（メタデータ） (2020-10-23T07:37:16Z)
• Towards Feature-free TSP Solver Selection: A Deep Learning Approach [35.05032046810422]
  トラベリングセールスマン問題(TSP)は古典的なNPハード問題であり、多くの分野や産業で広く応用されている。 本稿では,TSPソルバ選択のためのディープラーニングフレームワークであるCTASを提案する。
  論文  参考訳（メタデータ） (2020-06-01T04:48:36Z)

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

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