論文の概要: COMPASS: Ordered Clustered Routing at 100K Scale

• arxiv url: http://arxiv.org/abs/2609.20352v1
• Date: Thu, 17 Sep 2026 13:17:42 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-20 08:55:54.287453
• Title: COMPASS: Ordered Clustered Routing at 100K Scale
• Title（参考訳）: CompASS: 100Kスケールでのクラスタリングの順序付け
• Abstract要約: 大規模ルーティングは、しばしば所定の順序でノードのクラスタを訪問する必要があるため、順序付きクラスタ旅行セールスマン問題(OCTSP)が発生する。 我々は,並列サブソルバのオーケストレーションによる探索と学習促進ルーティングを組み合わせたOCTSPのCompassアルゴリズムを提案する。 100K合成ノードと28.5K実電子商取引ノードへのスケーリングを実演する。
• 参考スコア（独自算出の注目度）: 58.17379544011152
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Large-scale routing often requires visiting clusters of nodes in a prescribed order, giving rise to the Ordered Clustered Traveling Salesman Problem (OCTSP). Optimizing each cluster independently seems natural, but misses non-local dependencies. We introduce the COMPASS algorithm for OCTSP, which combines search with learning-accelerated routing by orchestrating parallel sub-solvers. COMPASS has no quality ceiling and its solutions keep improving with compute. It exploits the clustered structure, and can reach exact solutions in time exponential in cluster size rather than instance size. Empirically, COMPASS consistently outperforms alternative methods. Unlike common large-scale routing solvers, COMPASS consumes general distance matrices and is not limited to coordinate inputs. We demonstrate scaling to 100K synthetic nodes and to 28.5K real e-commerce nodes. To our knowledge, the latter is the largest reported routing solution over asymmetric distances, 9x beyond established ATSP benchmarks.
• Abstract（参考訳）: 大規模ルーティングでは、しばしばノードのクラスタを所定の順序で訪問する必要があるため、順序付きクラスタ旅行セールスマン問題(OCTSP)が発生する。 各クラスタを独立して最適化するのは自然に思えるが、非ローカルな依存関係を見逃す。 我々は,並列サブソルバのオーケストレーションによる探索と学習促進ルーティングを組み合わせたOCTSPのためのCompASSアルゴリズムを提案する。 comASSは品質の天井がなく、そのソリューションは計算によって改善され続けている。 クラスタ構造を利用しており、インスタンスサイズではなく、クラスタサイズで時間的に正確なソリューションに到達することができる。 経験的に、CompASSはオルタナティブメソッドよりも一貫して優れています。 一般的な大規模ルーティング解決器とは異なり、CompASSは一般的な距離行列を消費し、入力の座標に制限されない。 100K合成ノードと28.5K実電子商取引ノードへのスケーリングを実演する。 我々の知る限り、後者は、確立されたATSPベンチマークの9倍の非対称距離上のルーティングソリューションとして報告されている最大のものである。

関連論文リスト

• A Fast and Effective Method for Euclidean Anticlustering: The Assignment-Based-Anticlustering Algorithm [0.43748379918040853]
  代入ベースのアンチクラスタリングアルゴリズムは、非常に大きなインスタンスにスケールする。 ABAは、ソリューションの品質と実行時間の両方において、よく知られたMETIS法よりも優れている。 ABAアルゴリズムのコードはGitHubで公開されている。
  論文  参考訳（メタデータ） (2026-01-09T23:14:19Z)
• Towards a connection between the capacitated vehicle routing problem and the constrained centroid-based clustering [1.3927943269211591]
  実用的なランタイムにおける車両ルーティングの効率的な解決は、デリバリ管理企業にとって重要な課題である。 本稿では,CVRPとCCBC(Constrainedid-Based Clustering)の理論的および実験的関係について検討する。 提案するフレームワークは,3つの段階から構成される。第1段階では,制約付きセントロイドベースのクラスタリングアルゴリズムが,ユーザの実現可能なクラスタを生成する。
  論文  参考訳（メタデータ） (2024-03-20T22:24:36Z)
• Large Scale Constrained Clustering With Reinforcement Learning [1.3597551064547502]
  ネットワークが与えられた場合、各ノードではなく、クラスタレベルでリソースを割り当てることによって、リソースの割り当てと使用効率が向上する。 本稿では,この制約付きクラスタリング問題を強化学習を用いて解く手法を提案する。 結果の節では,大規模インスタンスにおいても,アルゴリズムが最適に近い解を見つけることを示す。
  論文  参考訳（メタデータ） (2024-02-15T18:27:18Z)
• Spatial-temporal-demand clustering for solving large-scale vehicle routing problems with time windows [0.0]
  本稿では,クラスタリングを用いて顧客をグループ化するDRI(Decompose-route-improve)フレームワークを提案する。 その類似度基準は、顧客の空間的、時間的、需要データを含む。 本研究では,解答サブプロブレム間でプルーンド局所探索(LS)を適用し,全体の解法を改善する。
  論文  参考訳（メタデータ） (2024-01-20T06:06:01Z)
• Hard Regularization to Prevent Deep Online Clustering Collapse without Data Augmentation [65.268245109828]
  オンラインディープクラスタリング(オンラインディープクラスタリング)とは、機能抽出ネットワークとクラスタリングモデルを組み合わせて、クラスタラベルを処理された各新しいデータポイントまたはバッチに割り当てることである。 オフラインメソッドよりも高速で汎用性が高いが、オンラインクラスタリングは、エンコーダがすべての入力を同じポイントにマッピングし、すべてを単一のクラスタに配置する、崩壊したソリューションに容易に到達することができる。 本稿では,データ拡張を必要としない手法を提案する。
  論文  参考訳（メタデータ） (2023-03-29T08:23:26Z)
• Implementing Reinforcement Learning Datacenter Congestion Control in NVIDIA NICs [64.26714148634228]
  渋滞制御 (CC) アルゴリズムの設計は非常に困難になる。 現在、計算能力に制限があるため、ネットワークデバイスにAIモデルをデプロイすることはできない。 我々は,近年の強化学習CCアルゴリズムに基づく計算軽度解を構築した。
  論文  参考訳（メタデータ） (2022-07-05T20:42:24Z)
• A Metaheuristic Algorithm for Large Maximum Weight Independent Set Problems [58.348679046591265]
  ノード重み付きグラフが与えられたとき、ノード重みが最大となる独立した(相互に非隣接な)ノードの集合を見つける。 このアプリケーションで放送されるグラフの中には、数十万のノードと数億のエッジを持つ大きなものもあります。 我々は,不規則なランダム化適応検索フレームワークにおいてメタヒューリスティックな新しい局所探索アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-03-28T21:34:16Z)
• ParChain: A Framework for Parallel Hierarchical Agglomerative Clustering using Nearest-Neighbor Chain [6.824747267214373]
  本稿では並列階層クラスタリング(HAC)アルゴリズムを設計するためのParChainフレームワークを提案する。 従来の並列HACアルゴリズムと比較して、我々の新しいアルゴリズムは線形メモリしか必要とせず、大規模データセットにスケーラブルである。 我々のアルゴリズムは、既存のアルゴリズムでは処理できない数千万のポイントでデータセットのサイズにスケールすることができる。
  論文  参考訳（メタデータ） (2021-06-08T23:13:27Z)

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

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