論文の概要: CaDA: Cross-Problem Routing Solver with Constraint-Aware Dual-Attention
- arxiv url: http://arxiv.org/abs/2412.00346v1
- Date: Sat, 30 Nov 2024 04:11:36 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-12-04 15:46:41.643661
- Title: CaDA: Cross-Problem Routing Solver with Constraint-Aware Dual-Attention
- Title（参考訳）: CaDA:制約付きデュアルアテンション付きクロスプロブレムルーティングソルバー
- Authors: Han Li, Fei Liu, Zhi Zheng, Yu Zhang, Zhenkun Wang,
- Abstract要約: 本稿では,車両経路問題に対する制約対応デュアルアテンションモデル(CaDA)を提案する。
CaDAは、異なる問題変種を効率的に表現する制約プロンプトを組み込んでいる。
より広範なグラフ情報を取得するためのグローバルブランチを備えたデュアルアテンション機構を備えている。
- 参考スコア（独自算出の注目度）: 21.554370739508528
- License:
- Abstract: Vehicle Routing Problems (VRPs) are significant Combinatorial Optimization (CO) problems holding substantial practical importance. Recently, Neural Combinatorial Optimization (NCO), which involves training deep learning models on extensive data to learn vehicle routing heuristics, has emerged as a promising approach due to its efficiency and the reduced need for manual algorithm design. However, applying NCO across diverse real-world scenarios with various constraints necessitates cross-problem capabilities. Current NCO methods typically employ a unified model lacking a constraint-specific structure, thereby restricting their cross-problem performance. Current multi-task methods for VRPs typically employ a constraint-unaware model, limiting their cross-problem performance. Furthermore, they rely solely on global connectivity, which fails to focus on key nodes and leads to inefficient representation learning. This paper introduces a Constraint-Aware Dual-Attention Model (CaDA), designed to address these limitations. CaDA incorporates a constraint prompt that efficiently represents different problem variants. Additionally, it features a dual-attention mechanism with a global branch for capturing broader graph-wide information and a sparse branch that selectively focuses on the most relevant nodes. We comprehensively evaluate our model on 16 different VRPs and compare its performance against existing cross-problem VRP solvers. CaDA achieves state-of-the-art results across all the VRPs. Our ablation study further confirms that each component of CaDA contributes positively to its cross-problem learning performance.
- Abstract（参考訳）: 車両ルーティング問題(英: Vehicle Routing Problems、VRP)は、実質的な重要性を持つ重要な組合せ最適化(CO)問題である。
最近、車両ルーティングヒューリスティックスを学ぶために、広範囲なデータに基づくディープラーニングモデルをトレーニングするNeural Combinatorial Optimization (NCO)が、その効率性と手動アルゴリズム設計の必要性の低減により、有望なアプローチとして登場した。
しかし、様々な制約で現実世界の様々なシナリオにNCOを適用するには、クロスプロブレム機能が必要である。
現在のNCO法は一般に制約固有の構造を持たない統一モデルを用いており、それによってクロスプロブレム性能が制限される。
現在のVRPのマルチタスク手法は、一般的に制約を意識しないモデルを用いており、そのクロスプロブレム性能を制限している。
さらに、それらはグローバル接続のみに依存しており、キーノードに集中できず、非効率な表現学習につながる。
本稿では,これらの制約に対処するために,CaDA(Constraint-Aware Dual-Attention Model)を提案する。
CaDAは、異なる問題変種を効率的に表現する制約プロンプトを組み込んでいる。
さらに、より広範なグラフ情報を取得するためのグローバルブランチと、最も関連するノードに選択的にフォーカスするスパースブランチを備えたデュアルアテンション機構を備えている。
我々は16種類のVRPのモデルを総合的に評価し、その性能を既存のクロスプロブレムVRPソルバと比較した。
CaDAはすべてのVRPで最先端の結果を達成する。
アブレーション研究により,CaDAの各コンポーネントが,そのクロスプロブレム学習性能に肯定的な寄与があることが確認された。
関連論文リスト
- IC/DC: Surpassing Heuristic Solvers in Combinatorial Optimization with Diffusion Models [6.260482448679642]
IC/DCは,教師なしの学習型最適化フレームワークである。
IC/DCは2つの異なる項目を含む問題の解決に特化しており、有効な解を生成するのに問題固有の探索プロセスは必要ない。
私たちは、問題固有の制約を順守しながら、ソリューションのコストを最小限に抑えるために、自己監督的な方法でモデルをトレーニングします。
論文 参考訳（メタデータ） (2024-10-15T06:53:30Z) - AUCSeg: AUC-oriented Pixel-level Long-tail Semantic Segmentation [88.50256898176269]
画素レベルのAUC損失関数を開発し,アルゴリズムの一般化能力に関する依存性グラフに基づく理論的解析を行う。
また、重要なメモリ需要を管理するために、Tail-Classes Memory Bankを設計する。
論文 参考訳（メタデータ） (2024-09-30T15:31:02Z) - Learning to Solve Combinatorial Optimization under Positive Linear Constraints via Non-Autoregressive Neural Networks [103.78912399195005]
組合せ最適化(英: Combinatorial Optimization、CO)は、計算機科学、応用数学などにおける基本的な問題である。
本稿では, 正線形制約下でのCO問題の解法として, 非自己回帰ニューラルネットワーク群を設計する。
本研究では,施設位置,最大被覆率,旅行セールスマン問題を含む代表的CO問題の解決において,この枠組みの有効性を検証する。
論文 参考訳（メタデータ） (2024-09-06T14:58:31Z) - UDC: A Unified Neural Divide-and-Conquer Framework for Large-Scale Combinatorial Optimization Problems [8.871356150316224]
2段階のニューラル手法は、大規模なCO問題に対処する際の効率性を示している。
本稿では,一般の大規模CO問題の解法として,統一型ニューラルディバイド・アンド・コンカー・フレームワーク(UDC)を開発する。
論文 参考訳（メタデータ） (2024-06-29T04:29:03Z) - Decision-focused Graph Neural Networks for Combinatorial Optimization [62.34623670845006]
最適化問題に取り組むための新たな戦略は、従来のアルゴリズムに代わるグラフニューラルネットワーク(GNN)の採用である。
GNNや従来のアルゴリズムソルバがCOの領域で人気が高まっているにもかかわらず、それらの統合利用とエンドツーエンドフレームワークにおけるそれらの相関について限定的な研究がなされている。
我々は、GNNを利用してCO問題に補助的なサポートで対処する決定に焦点を当てたフレームワークを導入する。
論文 参考訳（メタデータ） (2024-06-05T22:52:27Z) - GASE: Graph Attention Sampling with Edges Fusion for Solving Vehicle Routing Problems [6.084414764415137]
車両のルーティング問題を解決するためにEdges Fusionフレームワークを用いた適応型グラフ注意サンプリングを提案する。
提案手法は,既存の手法を2.08%-6.23%上回り,より強力な一般化能力を示す。
論文 参考訳（メタデータ） (2024-05-21T03:33:07Z) - An Efficient Learning-based Solver Comparable to Metaheuristics for the
Capacitated Arc Routing Problem [67.92544792239086]
我々は,高度メタヒューリスティックスとのギャップを著しく狭めるため,NNベースの解法を導入する。
まず,方向対応型注意モデル(DaAM)を提案する。
第2に、教師付き事前学習を伴い、堅牢な初期方針を確立するための教師付き強化学習スキームを設計する。
論文 参考訳（メタデータ） (2024-03-11T02:17:42Z) - Multi-Task Learning for Routing Problem with Cross-Problem Zero-Shot Generalization [18.298695520665348]
車両ルーティング問題(VRP)は多くの現実世界のアプリケーションで見られる。
本研究では,クロスプロブレム一般化という重要な課題に取り組むための最初の試みを行う。
提案モデルでは、ゼロショットの一般化方式で、見当たらない属性の組み合わせでVRPを解くことができる。
論文 参考訳（メタデータ） (2024-02-23T13:25:23Z) - A General Framework for Learning from Weak Supervision [93.89870459388185]
本稿では、新しいアルゴリズムを用いて、弱監督(GLWS)から学習するための一般的な枠組みを紹介する。
GLWSの中心は期待最大化(EM)の定式化であり、様々な弱い監督源を順応的に収容している。
また,EM計算要求を大幅に単純化する高度なアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-02-02T21:48:50Z) - Attention, Filling in The Gaps for Generalization in Routing Problems [5.210197476419621]
本稿では,既存のモデルの理解と改善を通じて,分野の統合を促進することを目的とする。
我々はまず,Sparse Dynamic Attention のための Kool et al. 法とその損失関数を適用することで,モデルの相違を第一に狙う。
次に、特定のシナリオにおける単一インスタンストレーニングよりも優れたパフォーマンスを示す混合インスタンストレーニングメソッドを使用することで、固有の違いをターゲットとします。
論文 参考訳（メタデータ） (2022-07-14T21:36:51Z) - Learning to Detect Critical Nodes in Sparse Graphs via Feature Importance Awareness [53.351863569314794]
クリティカルノード問題(CNP)は、削除が残余ネットワークのペア接続性を最大に低下させるネットワークから臨界ノードの集合を見つけることを目的としている。
本研究は,ノード表現のための特徴重要度対応グラフアテンションネットワークを提案する。
ダブルディープQネットワークと組み合わせて、初めてCNPを解くエンドツーエンドのアルゴリズムを作成する。
論文 参考訳（メタデータ） (2021-12-03T14:23:05Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。