論文の概要: Graph Attention-based Deep Reinforcement Learning for solving the Chinese Postman Problem with Load-dependent costs

• arxiv url: http://arxiv.org/abs/2310.15516v3
• Date: Tue, 19 Dec 2023 06:39:27 GMT
• ステータス: 処理完了
• システム内更新日: 2023-12-20 22:40:15.712980
• Title: Graph Attention-based Deep Reinforcement Learning for solving the Chinese Postman Problem with Load-dependent costs
• Title（参考訳）: 負荷依存コストによる中国のポストマン問題を解決するためのグラフ注意に基づく深層強化学習
• Authors: Cong Dao Tran, Truong Son Hy
• Abstract要約: 本稿では、負荷依存コストで中国ポストマン問題(CPP-LC)に対処する新しいDRLフレームワークを提案する。 本稿では,CPP-LC問題に効果的に対応するためのエンコーダとデコーダからなるDRL,すなわちArcDRLに基づく自己回帰モデルを提案する。 また,CPP-LCのためのアルゴリズム(EA)に基づくバイオインスパイアされた新しいメタヒューリスティックソリューションを提案する。
• 参考スコア（独自算出の注目度）: 2.1212179660694104
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Recently, Deep reinforcement learning (DRL) models have shown promising results in solving routing problems. However, most DRL solvers are commonly proposed to solve node routing problems, such as the Traveling Salesman Problem (TSP). Meanwhile, there has been limited research on applying neural methods to arc routing problems, such as the Chinese Postman Problem (CPP), since they often feature irregular and complex solution spaces compared to TSP. To fill these gaps, this paper proposes a novel DRL framework to address the CPP with load-dependent costs (CPP-LC) (Corberan et al., 2018), which is a complex arc routing problem with load constraints. The novelty of our method is two-fold. First, we formulate the CPP-LC as a Markov Decision Process (MDP) sequential model. Subsequently, we introduce an autoregressive model based on DRL, namely Arc-DRL, consisting of an encoder and decoder to address the CPP-LC challenge effectively. Such a framework allows the DRL model to work efficiently and scalably to arc routing problems. Furthermore, we propose a new bio-inspired meta-heuristic solution based on Evolutionary Algorithm (EA) for CPP-LC. Extensive experiments show that Arc-DRL outperforms existing meta-heuristic methods such as Iterative Local Search (ILS) and Variable Neighborhood Search (VNS) proposed by (Corberan et al., 2018) on large benchmark datasets for CPP-LC regarding both solution quality and running time; while the EA gives the best solution quality with much more running time. We release our C++ implementations for metaheuristics such as EA, ILS and VNS along with the code for data generation and our generated data at https://github.com/HySonLab/Chinese_Postman_Problem
• Abstract（参考訳）: 近年,深い強化学習(DRL)モデルがルーティング問題を解く上で有望な結果を示している。 しかしながら、ほとんどのDRLソルバは、トラベリングセールスマン問題(TSP)のようなノードルーティング問題を解決するために一般的に提案されている。 一方、中国ポストマン問題(CPP)のようなアークルーティング問題に対するニューラルネットワークの適用については、TSPと比較して不規則で複雑な解空間がしばしばあるため、限定的な研究がなされている。 これらのギャップを埋めるために,負荷制約を伴う複雑なアークルーティング問題であるCPP-LC(Corberan et al., 2018)に対処する新しいDRLフレームワークを提案する。 この手法の目新しさは2つある。 まず、CPP-LCをマルコフ決定過程(MDP)シーケンシャルモデルとして定式化する。 次に、CPP-LC課題に効果的に対応するために、エンコーダとデコーダからなるDRL、すなわちArc-DRLに基づく自己回帰モデルを導入する。 このようなフレームワークにより、DRLモデルはルーティング問題に対して効率よく、かつ、辛抱強く動作する。 さらに,CPP-LCのための進化的アルゴリズム(EA)に基づくバイオインスパイアされた新しいメタヒューリスティックソリューションを提案する。 大規模な実験により、Arc-DRLは、(Corberanらによって提案された)CPP-LCの大規模なベンチマークデータセットにおいて、反復局所探索(ILS)や可変近傍探索(VNS)のような既存のメタヒューリスティックな手法よりも、ソリューションの品質と実行時間の両方に関して優れていることが示された。 EA、ILS、VNSといったメタヒューリスティクスのためのC++実装と、データ生成のためのコード、生成されたデータはhttps://github.com/HySonLab/ Chinese_Postman_Problemでリリースしています。

関連論文リスト

• Offline Reinforcement Learning for Learning to Dispatch for Job Shop Scheduling [0.9831489366502301]
  ジョブショップスケジューリング問題(JSSP)の新しいアプローチであるオフライン強化学習(Offline-LD)について紹介する。 Offline-LDは2つのCQLベースのQ-ラーニング手法をマスク可能なアクション空間に適用し、離散SACのための新しいエントロピーボーナス修正を導入し、前処理による報酬正規化を活用する。 実験の結果,Offline-LDは生成されたインスタンスとベンチマークインスタンスの両方でオンラインRLを上回っていることがわかった。
  論文  参考訳（メタデータ） (2024-09-16T15:18:10Z)
• Tractable Offline Learning of Regular Decision Processes [50.11277112628193]
  この研究は、正則決定過程(RDP)と呼ばれる非マルコフ環境のクラスにおけるオフライン強化学習(RL)を研究する。 インスは、未来の観測と過去の相互作用からの報酬の未知の依存を実験的に捉えることができる。 多くのアルゴリズムは、まずこの未知の依存関係を自動学習技術を用いて再構築する。
  論文  参考訳（メタデータ） (2024-09-04T14:26:58Z)
• Multiobjective Vehicle Routing Optimization with Time Windows: A Hybrid Approach Using Deep Reinforcement Learning and NSGA-II [52.083337333478674]
  本稿では、時間窓を用いた多目的車両ルーティング問題(MOVRPTW)に対処するために、ウェイト・アウェア・ディープ・強化学習(WADRL)手法を提案する。 WADRLの結果を最適化するために非支配的ソート遺伝的アルゴリズム-II (NSGA-II) 法を用いる。
  論文  参考訳（メタデータ） (2024-07-18T02:46:06Z)
• Leveraging Constraint Programming in a Deep Learning Approach for Dynamically Solving the Flexible Job-Shop Scheduling Problem [1.3927943269211593]
  本稿では,制約プログラミング(CP)をディープラーニング(DL)ベースの方法論に統合し,両者の利点を活用することを目的とする。 本稿では,CP が生成する最適解を用いて DL モデルを訓練し,高品質なデータからモデルを学習する手法を提案する。 我々のハイブリッドアプローチは3つの公開FJSSPベンチマークで広範囲にテストされ、5つの最先端DRLアプローチよりも優れた性能を示している。
  論文  参考訳（メタデータ） (2024-03-14T10:16:57Z)
• Enhancing Column Generation by Reinforcement Learning-Based Hyper-Heuristic for Vehicle Routing and Scheduling Problems [9.203492057735074]
  カラム生成(CG)は変数を動的に生成することで大規模問題を解決する重要な手法である。 CGの性能を高めるために,RLHHと呼ばれる強化学習に基づく超ヒューリスティックフレームワークを提案する。
  論文  参考訳（メタデータ） (2023-10-15T00:05:50Z)
• Learning RL-Policies for Joint Beamforming Without Exploration: A Batch Constrained Off-Policy Approach [1.0080317855851213]
  本稿では,ネットワークにおけるパラメータキャンセル最適化の問題点について考察する。 探索と学習のために実世界でアルゴリズムをデプロイすることは、探索せずにデータによって達成できることを示す。
  論文  参考訳（メタデータ） (2023-10-12T18:36:36Z)
• Efficient Diffusion Policies for Offline Reinforcement Learning [85.73757789282212]
  Diffsuion-QLは、拡散モデルでポリシーを表現することによってオフラインRLの性能を大幅に向上させる。 これら2つの課題を克服するために,効率的な拡散政策(EDP)を提案する。 EDPは、サンプリングチェーンの実行を避けるために、トレーニング中の腐敗したアクションからアクションを構築する。
  論文  参考訳（メタデータ） (2023-05-31T17:55:21Z)
• Pointerformer: Deep Reinforced Multi-Pointer Transformer for the Traveling Salesman Problem [67.32731657297377]
  トラベリングセールスマン問題(TSP)は、もともと輸送と物流の領域で発生した古典的な経路最適化問題である。 近年, 深層強化学習は高い推論効率のため, TSP の解法として採用されている。 本稿では,多点変換器をベースとした新しいエンドツーエンドDRL手法であるPointerformerを提案する。
  論文  参考訳（メタデータ） (2023-04-19T03:48:32Z)
• MARLIN: Soft Actor-Critic based Reinforcement Learning for Congestion Control in Real Networks [63.24965775030673]
  そこで本研究では,汎用的な渋滞制御(CC)アルゴリズムを設計するための新しい強化学習(RL)手法を提案する。 我々の解であるMARLINは、Soft Actor-Criticアルゴリズムを用いてエントロピーとリターンの両方を最大化する。 我々は,MARLINを実ネットワーク上で訓練し,実ミスマッチを克服した。
  論文  参考訳（メタデータ） (2023-02-02T18:27:20Z)
• Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processes [61.11090361892306]
  Reward-free reinforcement learning (RL) は、エージェントが探索中に報酬関数にアクセスできないような環境を考える。 この分離は線形MDPの設定には存在しないことを示す。 我々は$d$次元線形 MDP における報酬のない RL に対する計算効率の良いアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-01-26T22:09:59Z)
• Learning Collaborative Policies to Solve NP-hard Routing Problems [13.13675711285772]
  本稿では,学習協調政策(LCP)と呼ばれる新しい階層的問題解決戦略を提案する。 2つの反復DRLポリシー(シードとリバイザ)を使って、ほぼ最適解を効果的に見つけることができる。 広汎な実験により,提案した2都市連携方式は,NP-ハードルーティング問題に対する単都市DRLフレームワークよりも改善されることが示された。
  論文  参考訳（メタデータ） (2021-10-26T19:46:21Z)

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

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