論文の概要: A Fast GRASP Metaheuristic for the Trigger Arc TSP with MIP-Based Construction and Multi-Neighborhood Local Search

• arxiv url: http://arxiv.org/abs/2508.08477v1
• Date: Mon, 11 Aug 2025 21:24:38 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-13 21:07:34.235483
• Title: A Fast GRASP Metaheuristic for the Trigger Arc TSP with MIP-Based Construction and Multi-Neighborhood Local Search
• Title（参考訳）: MIPを用いたTrigger Arc TSPのための高速GRASPメタヒューリスティック
• Authors: Joan Salvà Soler, Grégoire de Lambertye,
• Abstract要約: 本稿では,複数の構成と複数の近傍局所探索を組み合わせたGRASPに基づくメタヒューリスティックを提案する。 このアルゴリズムはMESS 2024のトップ3で完成し、状態依存の旅行コストを持つリアルタイムルーティングアプリケーションに適していることを示した。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: The Trigger Arc Traveling Salesman Problem (TA-TSP) extends the classical TSP by introducing dynamic arc costs that change when specific \textit{trigger} arcs are traversed, modeling scenarios such as warehouse operations with compactable storage systems. This paper introduces a GRASP-based metaheuristic that combines multiple construction heuristics with a multi-neighborhood local search. The construction phase uses mixed-integer programming (MIP) techniques to transform the TA-TSP into a sequence of tailored TSP instances, while the improvement phase applies 2-Opt, Swap, and Relocate operators. Computational experiments on MESS 2024 competition instances achieved average optimality gaps of 0.77\% and 0.40\% relative to the best-known solutions within a 60-second limit. On smaller, synthetically generated datasets, the method produced solutions 11.3\% better than the Gurobi solver under the same time constraints. The algorithm finished in the top three at MESS 2024, demonstrating its suitability for real-time routing applications with state-dependent travel costs.
• Abstract（参考訳）: Trigger Arc Traveling Salesman Problem (TA-TSP) は、特定の \textit{trigger} アークがトラバースされたときに変化する動的アークコストを導入することで、古典的な TSP を拡張している。 本稿では, GRASP に基づくメタヒューリスティックを導入し, 建設ヒューリスティックと周辺地域探索を組み合わせたメタヒューリスティックを提案する。 構築フェーズは、TA-TSPを2-Opt、Swap、Relocate演算子に変換する混合整数プログラミング(MIP)技術を使用する。 MESS 2024コンペティションインスタンスの計算実験では、60秒以内の最適解に対する平均最適解の差が 0.77\% と 0.40\% に達した。 より小さく合成的に生成されたデータセットでは、同じ時間制約下でグロビ解法よりも11.3\%良い解が生成される。 このアルゴリズムはMESS 2024のトップ3で完成し、状態依存の旅行コストを持つリアルタイムルーティングアプリケーションに適していることを示した。

関連論文リスト

• Fast T2T: Optimization Consistency Speeds Up Diffusion-Based Training-to-Testing Solving for Combinatorial Optimization [83.65278205301576]
  雑音レベルから与えられたインスタンスの最適解への直接写像を学習し、最小限のショットで高品質な生成を容易にすることを提案する。 これは、サンプル間の差を最小限に抑える最適化一貫性トレーニングプロトコルによって達成される。 The Traveling Salesman Problem (TSP) と Maximal Independent Set (MIS) は、ソリューションの品質と効率の両方に関して、Fast T2Tの優位性を実証している。
  論文  参考訳（メタデータ） (2025-02-05T07:13:43Z)
• DualOpt: A Dual Divide-and-Optimize Algorithm for the Large-scale Traveling Salesman Problem [16.841700899374654]
  大規模旅行セールスマン問題(T)を解決するための二分割最適化アルゴリズム(DualOpt)を提案する。 DualOptは、ソリューションの品質と計算効率の両方を改善するための2つの補完戦略を組み合わせる。 提案したDualOptは、文学における10の最先端アルゴリズムと比較して非常に競争力のある結果が得られる。
  論文  参考訳（メタデータ） (2025-01-15T04:16:28Z)
• T-REX: Mixture-of-Rank-One-Experts with Semantic-aware Intuition for Multi-task Large Language Model Finetuning [31.276142111455847]
  大規模言語モデル(LLM)は多様なマルチタスクの微調整において重要な適応課題に直面している。 我々はmixunderlinetextbfTureunderlinetextbf-of-underlinetextbfRank-onunderlinetextbfE-eunderlinetextbfXper ts (textttT-REX) という新しいフレームワークを設計する。 Rank-1のエキスパートは、ミックス・アンド・マッチのメカニズムにより、線形パラメータのオーバーヘッドを持つエキスパートのベクトル部分空間を2次に拡張し、最適で近似誤差削減を達成することができる。
  論文  参考訳（メタデータ） (2024-04-13T12:14:58Z)
• Replicable Learning of Large-Margin Halfspaces [46.91303295440005]
  我々は,大マージンハーフスペースを学習する問題に対して,効率的なアルゴリズムを提供する。 Impagliazzo, Lei, Pitassi, Sorrellによるアルゴリズム [STOC 2022] の改良を行った。
  論文  参考訳（メタデータ） (2024-02-21T15:06:51Z)
• CARSS: Cooperative Attention-guided Reinforcement Subpath Synthesis for Solving Traveling Salesman Problem [4.190087134771218]
  本稿では,旅行セールスマン問題(TSP)に対処する新しいアプローチであるCARSSを紹介する。 CARSSはTSP解決プロセスを「サブパス生成」と「サブパス統合」の2つの異なる相乗的ステップに分解する 実証実験により、CARSSは単一エージェントの代替よりも優れていることが示された。
  論文  参考訳（メタデータ） (2023-12-24T05:25:43Z)
• ArchGym: An Open-Source Gymnasium for Machine Learning Assisted Architecture Design [52.57999109204569]
  ArchGymは、さまざまな検索アルゴリズムをアーキテクチャシミュレータに接続するオープンソースのフレームワークである。 我々は、カスタムメモリコントローラ、ディープニューラルネットワークアクセラレータ、AR/VRワークロード用のカスタムSOCを設計する際に、複数のバニラおよびドメイン固有の検索アルゴリズムにわたってArchGymを評価する。
  論文  参考訳（メタデータ） (2023-06-15T06:41:23Z)
• 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)
• FormerTime: Hierarchical Multi-Scale Representations for Multivariate Time Series Classification [53.55504611255664]
  formerTimeは、多変量時系列分類タスクの分類能力を改善する階層的表現モデルである。 1)時系列データから階層的なマルチスケール表現を学習し、(2)トランスフォーマーと畳み込みネットワークの強さを継承し、(3)自己維持メカニズムによって引き起こされる効率の課題に取り組む。
  論文  参考訳（メタデータ） (2023-02-20T07:46:14Z)
• Reinforcement Learning for Branch-and-Bound Optimisation using Retrospective Trajectories [72.15369769265398]
  機械学習は分岐のための有望なパラダイムとして登場した。 分岐のための単純かつ効果的なRLアプローチであるレトロ分岐を提案する。 我々は現在最先端のRL分岐アルゴリズムを3～5倍に上回り、500の制約と1000の変数を持つMILP上での最高のILメソッドの性能の20%以内である。
  論文  参考訳（メタデータ） (2022-05-28T06:08:07Z)
• Towards Feature-free TSP Solver Selection: A Deep Learning Approach [35.05032046810422]
  トラベリングセールスマン問題(TSP)は古典的なNPハード問題であり、多くの分野や産業で広く応用されている。 本稿では,TSPソルバ選択のためのディープラーニングフレームワークであるCTASを提案する。
  論文  参考訳（メタデータ） (2020-06-01T04:48:36Z)

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

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