論文の概要: An Efficient Learning-based Solver Comparable to Metaheuristics for the
Capacitated Arc Routing Problem
- arxiv url: http://arxiv.org/abs/2403.07028v1
- Date: Mon, 11 Mar 2024 02:17:42 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-14 00:14:11.618621
- Title: An Efficient Learning-based Solver Comparable to Metaheuristics for the
Capacitated Arc Routing Problem
- Title（参考訳）: 容量アークルーティング問題に対するメタヒューリスティックスに匹敵する効率的な学習型解法
- Authors: Runze Guo, Feng Xue, Anlong Ming, Nicu Sebe
- Abstract要約: 我々は,高度メタヒューリスティックスとのギャップを著しく狭めるため,NNベースの解法を導入する。
まず,方向対応型注意モデル(DaAM)を提案する。
第2に、教師付き事前学習を伴い、堅牢な初期方針を確立するための教師付き強化学習スキームを設計する。
- 参考スコア（独自算出の注目度）: 67.92544792239086
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Recently, neural networks (NN) have made great strides in combinatorial
optimization. However, they face challenges when solving the capacitated arc
routing problem (CARP) which is to find the minimum-cost tour covering all
required edges on a graph, while within capacity constraints. In tackling CARP,
NN-based approaches tend to lag behind advanced metaheuristics, since they lack
directed arc modeling and efficient learning methods tailored for complex CARP.
In this paper, we introduce an NN-based solver to significantly narrow the gap
with advanced metaheuristics while exhibiting superior efficiency. First, we
propose the direction-aware attention model (DaAM) to incorporate
directionality into the embedding process, facilitating more effective
one-stage decision-making. Second, we design a supervised reinforcement
learning scheme that involves supervised pre-training to establish a robust
initial policy for subsequent reinforcement fine-tuning. It proves particularly
valuable for solving CARP that has a higher complexity than the node routing
problems (NRPs). Finally, a path optimization method is proposed to adjust the
depot return positions within the path generated by DaAM. Experiments
illustrate that our approach surpasses heuristics and achieves decision quality
comparable to state-of-the-art metaheuristics for the first time while
maintaining superior efficiency.
- Abstract（参考訳）: 近年、ニューラルネットワーク(NN)は組合せ最適化において大きな進歩を遂げている。
しかし、キャパシティ制約内にあるグラフ上のすべてのエッジをカバーする最小コストのツアーを見つけるために、キャパシタ付きアークルーティング問題(CARP)を解く際の課題に直面している。
CARPに取り組む場合、NNベースのアプローチは、複雑なCARPに適した直接アークモデリングと効率的な学習方法が欠如しているため、高度なメタヒューリスティックスよりも遅れやすい。
本稿では,高度メタヒューリスティックスとのギャップを大幅に狭めるとともに,優れた効率性を示すNNベースの解法を提案する。
まず,方向認識型注意モデル(DaAM)を提案する。
第2に,教師付きプレトレーニングを含む教師付き強化学習方式を設計し,その後の強化微調整のための堅牢な初期方針を確立する。
ノードルーティング問題(NRP)よりも複雑であるCARPの解決には特に有用である。
最後に,DAAM が生成した経路内のデポ位置を調整する経路最適化手法を提案する。
実験により、我々のアプローチはヒューリスティックスを超え、優れた効率を維持しながら、最先端のメタヒューリスティックスに匹敵する意思決定品質を初めて達成したことを示す。
関連論文リスト
- CHARME: A chain-based reinforcement learning approach for the minor embedding problem [16.24890195949869]
本稿では,CHARME という名前の小さな埋め込み問題に対処するために,強化学習(RL)技術を利用した新しい手法を提案する。
CHARMEには、ポリシーモデリングのためのグラフニューラルネットワーク(GNN)アーキテクチャ、ソリューションの有効性を保証する状態遷移アルゴリズム、効果的なトレーニングのための順序探索戦略の3つの重要なコンポーネントが含まれている。
詳細では、CHARME は Minorminer や ATOM のような高速な埋め込み法に比べて優れた解が得られる。
論文 参考訳（メタデータ） (2024-06-11T10:12:10Z) - Decision-focused Graph Neural Networks for Combinatorial Optimization [62.34623670845006]
最適化問題に取り組むための新たな戦略は、従来のアルゴリズムに代わるグラフニューラルネットワーク(GNN)の採用である。
GNNや従来のアルゴリズムソルバがCOの領域で人気が高まっているにもかかわらず、それらの統合利用とエンドツーエンドフレームワークにおけるそれらの相関について限定的な研究がなされている。
我々は、GNNを利用してCO問題に補助的なサポートで対処する決定に焦点を当てたフレームワークを導入する。
論文 参考訳（メタデータ） (2024-06-05T22:52:27Z) - Instance-Conditioned Adaptation for Large-scale Generalization of Neural Combinatorial Optimization [15.842155380912002]
本研究は,ニューラル最適化の大規模一般化のための新しいインスタンス・コンディション適応モデル(ICAM)を提案する。
特に,NCOモデルのための強力なインスタンス条件付きルーティング適応モジュールを設計する。
我々は,ラベル付き最適解を使わずに,モデルがクロススケールな特徴を学習することのできる,効率的な3段階強化学習ベーストレーニング手法を開発した。
論文 参考訳（メタデータ） (2024-05-03T08:00:19Z) - CGD: Constraint-Guided Diffusion Policies for UAV Trajectory Planning [26.10588918124538]
計算時間を短縮するために成功した戦略は、Imitation Learning (IL)を使用して専門家から高速ニューラルネットワーク(NN)ポリシーを開発することである。
結果のNNポリシは,専門家と同様のトラジェクトリを高速に生成する上で有効だが,その出力は動的実現可能性を明確に考慮していない。
本稿では,トラジェクトリ計画のための新しいILベースのアプローチであるConstraint-Guided Diffusion (CGD)を提案する。
論文 参考訳（メタデータ） (2024-05-02T21:50:26Z) - Optimizing Inventory Routing: A Decision-Focused Learning Approach using
Neural Networks [0.0]
我々は、現実世界のIRPを解決するための意思決定に基づくアプローチを定式化し、提案する。
このアプローチは、在庫予測とルーティング最適化を直接エンドツーエンドシステムに統合することで、堅牢なサプライチェーン戦略を保証する可能性がある。
論文 参考訳（メタデータ） (2023-11-02T04:05:28Z) - Stochastic Unrolled Federated Learning [85.6993263983062]
本稿では,UnRolled Federated Learning (SURF)を導入する。
提案手法は,この拡張における2つの課題,すなわち,非学習者へのデータセット全体の供給の必要性と,フェデレート学習の分散的性質に対処する。
論文 参考訳（メタデータ） (2023-05-24T17:26:22Z) - Improved Algorithms for Neural Active Learning [74.89097665112621]
非パラメトリックストリーミング設定のためのニューラルネットワーク(NN)ベースの能動学習アルゴリズムの理論的および経験的性能を改善する。
本研究では,SOTA(State-of-the-art (State-the-art)) 関連研究で使用されるものよりも,アクティブラーニングに適する人口減少を最小化することにより,2つの後悔の指標を導入する。
論文 参考訳（メタデータ） (2022-10-02T05:03:38Z) - Solving the vehicle routing problem with deep reinforcement learning [0.0]
本稿では,NP-Hard 問題のクラスに属する有名な問題である Vehicle Routing Problem (VRP) に対する RL の適用について述べる。
第2フェーズでは、アクターと批評家の背後にあるニューラルアーキテクチャが確立され、畳み込みニューラルネットワークに基づいたニューラルアーキテクチャを採用することが選択された。
広範囲なインスタンスで行った実験では、アルゴリズムが優れた一般化能力を持ち、短時間で良い解に達することが示されている。
論文 参考訳（メタデータ） (2022-07-30T12:34:26Z) - Fidelity-Guarantee Entanglement Routing in Quantum Networks [64.49733801962198]
絡み合いルーティングは、2つの任意のノード間のリモート絡み合い接続を確立する。
量子ネットワークにおける複数のソース・デスティネーション(SD)ペアの忠実性を保証するために、精製可能な絡み合わせルーティング設計を提案する。
論文 参考訳（メタデータ） (2021-11-15T14:07:22Z) - Ranking Cost: Building An Efficient and Scalable Circuit Routing Planner
with Evolution-Based Optimization [49.207538634692916]
そこで我々は、効率よくトレーニング可能なルータを形成するための新しい回路ルーティングアルゴリズム、Randing Costを提案する。
提案手法では,A*ルータが適切な経路を見つけるのに役立つコストマップと呼ばれる新しい変数群を導入する。
我々のアルゴリズムはエンドツーエンドで訓練されており、人工データや人間の実演は一切使用しない。
論文 参考訳（メタデータ） (2021-10-08T07:22:45Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。