論文の概要: Generating Diverse TSP Tours via a Combination of Graph Pointer Network and Dispersion

• arxiv url: http://arxiv.org/abs/2601.01132v2
• Date: Fri, 09 Jan 2026 07:40:19 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-12 13:49:32.184798
• Title: Generating Diverse TSP Tours via a Combination of Graph Pointer Network and Dispersion
• Title（参考訳）: グラフポインタネットワークと分散を組み合わせた逆TSPツアーの生成
• Authors: Hao-Tsung Yang, Ssu-Yuan Lo, Kuan-Lun Chen, Ching-Kai Wang,
• Abstract要約: ディバース・トラベリング・セールスマン問題(Diverse Traveling Salesman Problem, D-TSP)は、異なるツアーのセットを求める双基準最適化問題である。 D-TSPを2つの効率的なステップに分解する新しいハイブリッドフレームワークを提案する。 当社のアプローチは,大規模インスタンス(783都市)の360倍以上高速です。
• 参考スコア（独自算出の注目度）: 0.26999000177990923
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We address the Diverse Traveling Salesman Problem (D-TSP), a bi-criteria optimization challenge that seeks a set of $k$ distinct TSP tours. The objective requires every selected tour to have a length at most $c|T^*|$ (where $|T^*|$ is the optimal tour length) while minimizing the average Jaccard similarity across all tour pairs. This formulation is crucial for applications requiring both high solution quality and fault tolerance, such as logistics planning, robotics pathfinding or strategic patrolling. Current methods are limited: traditional heuristics, such as the Niching Memetic Algorithm (NMA) or bi-criteria optimization, incur high computational complexity $O(n^3)$, while modern neural approaches (e.g., RF-MA3S) achieve limited diversity quality and rely on complex, external mechanisms. To overcome these limitations, we propose a novel hybrid framework that decomposes D-TSP into two efficient steps. First, we utilize a simple Graph Pointer Network (GPN), augmented with an approximated sequence entropy loss, to efficiently sample a large, diverse pool of high-quality tours. This simple modification effectively controls the quality-diversity trade-off without complex external mechanisms. Second, we apply a greedy algorithm that yields a 2-approximation for the dispersion problem to select the final $k$ maximally diverse tours from the generated pool. Our results demonstrate state-of-the-art performance. On the Berlin instance, our model achieves an average Jaccard index of $0.015$, significantly outperforming NMA ($0.081$) and RF-MA3S. By leveraging GPU acceleration, our GPN structure achieves a near-linear empirical runtime growth of $O(n)$. While maintaining solution diversity comparable to complex bi-criteria algorithms, our approach is over 360 times faster on large-scale instances (783 cities), delivering high-quality TSP solutions with unprecedented efficiency and simplicity.
• Abstract（参考訳）: D-TSP(Diverse Traveling Salesman Problem, D-TSP)は、異なるTSPツアーを1セット1万ドルで提供する、双方向最適化の課題である。 目的は、選択されたすべてのツアーが、最大で$c|T^*|$(ここで$|T^*|$は最適なツアー長)でありながら、すべてのツアーペアの平均ジャカード類似性を最小化することである。 この定式化は、ロジスティクス計画、ロボティクスのパスフィニング、戦略的パトロールなど、高いソリューション品質と耐障害性の両方を必要とするアプリケーションにとって重要である。 Niching Memetic Algorithm (NMA)やbi-criteria Optimization(英語版)のような従来のヒューリスティックな手法は高い計算複雑性を生じさせる$O(n^3)$であるが、現代のニューラルアプローチ(例えばRF-MA3S)は限られた多様性の品質を達成し、複雑な外部メカニズムに依存している。 これらの制約を克服するため、D-TSPを2つの効率的なステップに分解する新しいハイブリッドフレームワークを提案する。 まず,シーケンスエントロピー損失を近似した単純なグラフポインタネットワーク(GPN)を用いて,多種多様なツアーのプールを効率的にサンプリングする。 この単純な修正は、複雑な外部メカニズムなしで、品質と多様性のトレードオフを効果的に制御する。 第2に、分散問題に対する2-近似を導出するグリーディアルゴリズムを適用し、生成されたプールから最終$k$の最大多様なツアーを選択する。 以上の結果から,最先端の性能が示された。 ベルリンの場合、平均ジャカード指数は0.015ドルであり、NMA(0.081ドル)とRF-MA3Sを大きく上回っている。 GPN構造はGPUアクセラレーションを活用することにより,ほぼ直線的なO(n)$のランタイム成長を実現する。 複雑な双基準アルゴリズムに匹敵するソリューションの多様性を維持しながら、我々のアプローチは大規模インスタンス(783都市)では360倍以上高速で、前例のない効率と単純さで高品質なTSPソリューションを提供する。

関連論文リスト

• Scalable 3D Registration via Truncated Entry-wise Absolute Residuals [65.04922801371363]
  3ドルの登録アプローチでは、1000万ドル(107ドル)以上のポイントペアを、99%以上のランダムなアウトレイアで処理することができる。 我々はこの手法をTEARと呼び、Trncated Entry-wise Absolute Residualsを演算するoutlier-robust損失を最小限にする。
  論文  参考訳（メタデータ） (2024-04-01T04:43:39Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• Distributed Extra-gradient with Optimal Complexity and Communication Guarantees [60.571030754252824]
  複数のプロセッサ/ワーカー/クライアントがローカルなデュアルベクトルにアクセス可能なマルチGPU設定において、モノトン変分不等式(VI)問題を考察する。 モノトーンVI問題に対するデファクトアルゴリズムであるExtra-gradientは、通信効率が良くないように設計されている。 そこで本稿では,VI の解法に適した非バイアスで適応的な圧縮手法である量子化一般化外部勾配 (Q-GenX) を提案する。
  論文  参考訳（メタデータ） (2023-08-17T21:15:04Z)
• A Hybrid Genetic Algorithm for the min-max Multiple Traveling Salesman Problem [0.9790236766474201]
  本稿では,Multiple Traveling Salesman Problem (mTSP) を解くためのハイブリッド遺伝的アルゴリズムを提案する。 新たなクロスオーバーオペレーターは、2人の親からの同様のツアーを組み合わせるように設計されており、人口に対して大きな多様性を提供する。 我々のアルゴリズムは、ベンチマークセットに対してテストした場合に、同様のカットオフ時間しきい値で、すべての既存のアルゴリズムを平均で上回ります。
  論文  参考訳（メタデータ） (2023-07-14T01:57:10Z)
• Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
  本稿では,スムーズさを生かし,問題依存量による動的後悔のT$への依存を補う新しいオンラインアルゴリズムを提案する。 この結果が本質的な難易度に適応しているのは, 既往の結果よりも厳密であり, 最悪の場合, 同一レートの保護が可能であるからである。
  論文  参考訳（メタデータ） (2021-12-29T02:42:59Z)
• Optimal and Efficient Dynamic Regret Algorithms for Non-Stationary Dueling Bandits [27.279654173896372]
  我々は,非定常的あるいは時間的に異なる選好の下で,$K$のDueling Banditsにおける空力的後悔の最小化問題について検討した。 これは、エージェントが各ラウンドで一対のアイテムを選択し、このペアに対する相対的な二項のウィンロスフィードバックのみを観察するオンライン学習設定である。
  論文  参考訳（メタデータ） (2021-11-06T16:46:55Z)
• Genetic column generation: Fast computation of high-dimensional multi-marginal optimal transport problems [0.0]
  CG内の二重状態が「逆」の役割を果たすMMOT用に作られた遺伝的学習法を使用します。 最大120のグリッドポイントと最大30のマージンを持つベンチマーク問題に対して,本手法は常に精度を見出した。
  論文  参考訳（メタデータ） (2021-03-23T15:24:50Z)
• Online Model Selection for Reinforcement Learning with Function Approximation [50.008542459050155]
  我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。 また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
  論文  参考訳（メタデータ） (2020-11-19T10:00:54Z)

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

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