論文の概要: A Hierarchical Destroy and Repair Approach for Solving Very Large-Scale Travelling Salesman Problem

• arxiv url: http://arxiv.org/abs/2308.04639v1
• Date: Wed, 9 Aug 2023 00:44:02 GMT
• ステータス: 処理完了
• システム内更新日: 2023-08-10 15:30:51.288234
• Title: A Hierarchical Destroy and Repair Approach for Solving Very Large-Scale Travelling Salesman Problem
• Title（参考訳）: 大規模トラベリングセールスマン問題の解決のための階層的破壊と修復手法
• Authors: Zhang-Hua Fu, Sipeng Sun, Jintong Ren, Tianshu Yu, Haoyu Zhang, Yuanyuan Liu, Lingxiao Huang, Xiang Yan, Pinyan Lu
• Abstract要約: 大規模トラベリングセールスマン問題(TSP)のための階層的破壊・修復フレームワークを提案する。 鍵となる革新的な概念は階層的な検索フレームワークであり、これは部分的なエッジを修正し、ある程度の等価性の保証の下で入力を小規模のTSPに圧縮するものである。 有名な大規模インスタンス(1万から1万の都市)に基づく公正な比較は、HDRが既存の最先端のアルゴリズムと非常に競合していることを示している。
• 参考スコア（独自算出の注目度）: 32.62389678555851
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: For prohibitively large-scale Travelling Salesman Problems (TSPs), existing algorithms face big challenges in terms of both computational efficiency and solution quality. To address this issue, we propose a hierarchical destroy-and-repair (HDR) approach, which attempts to improve an initial solution by applying a series of carefully designed destroy-and-repair operations. A key innovative concept is the hierarchical search framework, which recursively fixes partial edges and compresses the input instance into a small-scale TSP under some equivalence guarantee. This neat search framework is able to deliver highly competitive solutions within a reasonable time. Fair comparisons based on nineteen famous large-scale instances (with 10,000 to 10,000,000 cities) show that HDR is highly competitive against existing state-of-the-art TSP algorithms, in terms of both efficiency and solution quality. Notably, on two large instances with 3,162,278 and 10,000,000 cities, HDR breaks the world records (i.e., best-known results regardless of computation time), which were previously achieved by LKH and its variants, while HDR is completely independent of LKH. Finally, ablation studies are performed to certify the importance and validity of the hierarchical search framework.
• Abstract（参考訳）: 大規模トラベリングセールスマン問題(TSP)では、既存のアルゴリズムは計算効率と解品質の両方において大きな課題に直面している。 この問題に対処するため、我々は階層的破壊・修復(HDR)アプローチを提案し、慎重に設計された破壊・修復操作を適用して初期解を改善する。 重要なイノベーティブな概念は階層型検索フレームワークで、部分エッジを再帰的に修正し、入力インスタンスをある種の等価保証の下で小さなtspに圧縮する。 このきちんとした検索フレームワークは、適切な時間内に高い競争力のあるソリューションを提供できる。 19の有名な大規模インスタンス(1万から1万の都市)に基づく公正な比較は、HDRが既存の最先端のTSPアルゴリズムに対して、効率性とソリューションの品質の両方において高い競争力を持っていることを示している。 特に、3,162,278都市と10,000,000都市を持つ2つの大規模インスタンスにおいて、HDRは以前LKHとその変種によって達成された世界記録(計算時間に関係なく最もよく知られた結果)を破り、HDRはLKHから完全に独立している。 最後に,階層探索フレームワークの重要性と妥当性を検証するためのアブレーション研究を行った。

関連論文リスト

• Dancing to the State of the Art? How Candidate Lists Influence LKH for Solving the Traveling Salesperson Problem [1.6874375111244329]
  トラベリングセールスパーソン問題(TSP)の解決はいまだに永続的な課題である。 ヒューリスティックな解法は、高品質な解を見つけるための需要を効果的に解決する。 これらの解法の中で、Lin-Kernighan-Helsgaun(LKH)は遺伝的アルゴリズムの性能を補完するものとして際立っている。
  論文  参考訳（メタデータ） (2024-07-04T13:38:19Z)
• An algorithm for clustering with confidence-based must-link and cannot-link constraints [0.0]
  我々はPCCCアルゴリズム(Pairwise-Confidence-Constraints-Clustering)を導入する。 PCCCアルゴリズムは、オブジェクトのペアに提供された情報を考慮しながら、反復的にオブジェクトをクラスタに割り当てる。 既存のアルゴリズムとは異なり、我々のアルゴリズムは最大6万のオブジェクト、100のクラスタ、数百万のnot-link制約を持つ大規模インスタンスにスケールする。
  論文  参考訳（メタデータ） (2022-12-29T19:21:33Z)
• Efficient Joint-Dimensional Search with Solution Space Regularization for Real-Time Semantic Segmentation [27.94898516315886]
  この問題に対して,リアルタイムに実行可能な最適ネットワーク構造を探索する。 新たな解空間規則化(SSR)損失は、スーパーネットが離散的に収束することを効果的に促すために最初に提案される。 より高効率な探索を実現するために,新しい階層的・プログレッシブ・ソリューション・スペース・スライキング法を提案する。
  論文  参考訳（メタデータ） (2022-08-10T11:07:33Z)
• Hierarchical Similarity Learning for Aliasing Suppression Image Super-Resolution [64.15915577164894]
  エイリアスの影響を抑制するために階層画像超解像ネットワーク(HSRNet)を提案する。 HSRNetは、他の作品よりも定量的かつ視覚的なパフォーマンスを向上し、エイリアスをより効果的に再送信する。
  論文  参考訳（メタデータ） (2022-06-07T14:55:32Z)
• NTIRE 2022 Challenge on High Dynamic Range Imaging: Methods and Results [173.32437855731752]
  この課題はCVPR 2022と共同でNTIRE(New Trends in Image Restoration and Enhancement)ワークショップの一環として行われた。 この課題は、複数の低ダイナミックレンジ(LDR)観測からHDR画像を推定することを目的としている。
  論文  参考訳（メタデータ） (2022-05-25T10:20:06Z)
• Efficient Large Scale Inlier Voting for Geometric Vision Problems [3.1231364554255636]
  コンピュータビジョンにおける多くの応用において、アウター・リジェクション(英語版)と等価に不整集合最適化(英語版)が重要な要素である。 我々は、$Rd$の「交差」$k$次元曲面に基づいて、外周拒絶に対する効率的で一般的なアルゴリズムを提案する。 本手法は, 複数枚のカメラにおいて, 多数の一致が低い不整合比で発生する問題に対するアプローチの汎用性を示す。
  論文  参考訳（メタデータ） (2021-07-25T14:13:07Z)
• Combined Depth Space based Architecture Search For Person Re-identification [70.86236888223569]
  個人再識別(ReID)のための軽量で適切なネットワークの設計を目指しています。 本研究では,CDNetと呼ばれる効率的なネットワークアーキテクチャの探索に基づく,複合深さ空間(Componed Depth Space, CDS)と呼ばれる新しい検索空間を提案する。 そこで我々はTop-k Sample Search戦略という低コストの検索戦略を提案し、検索空間をフル活用し、局所的な最適結果のトラップを避ける。
  論文  参考訳（メタデータ） (2021-04-09T02:40:01Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。 SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。 本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-07-14T12:38:21Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。 既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。 我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
  論文  参考訳（メタデータ） (2020-05-09T02:48:23Z)

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

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