論文の概要: Learning to Solve Soft-Constrained Vehicle Routing Problems with Lagrangian Relaxation

• arxiv url: http://arxiv.org/abs/2207.09860v2
• Date: Thu, 21 Jul 2022 13:11:05 GMT
• ステータス: 処理完了
• システム内更新日: 2022-07-22 10:30:18.754085
• Title: Learning to Solve Soft-Constrained Vehicle Routing Problems with Lagrangian Relaxation
• Title（参考訳）: ラグランジアン緩和によるソフト制約車両経路問題の解法
• Authors: Qiaoyue Tang, Yangzhe Kong, Lemeng Pan, Choonmeng Lee
• Abstract要約: 現実世界のアプリケーションにおける車両ルーティング問題(VRP)には、様々な制約が伴うことが多い。 ソフト制約付きVRPを解くために,強化学習に基づく手法を提案する。 本稿では,3種類のVRP,TSPTW(Travelling Salesman Problem with Time Windows),CVRP(Capacitated VRP),CVRPTW(Capacitated VRP with Time Windows)に適用する。
• 参考スコア（独自算出の注目度）: 0.4014524824655105
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Vehicle Routing Problems (VRPs) in real-world applications often come with various constraints, therefore bring additional computational challenges to exact solution methods or heuristic search approaches. The recent idea to learn heuristic move patterns from sample data has become increasingly promising to reduce solution developing costs. However, using learning-based approaches to address more types of constrained VRP remains a challenge. The difficulty lies in controlling for constraint violations while searching for optimal solutions. To overcome this challenge, we propose a Reinforcement Learning based method to solve soft-constrained VRPs by incorporating the Lagrangian relaxation technique and using constrained policy optimization. We apply the method on three common types of VRPs, the Travelling Salesman Problem with Time Windows (TSPTW), the Capacitated VRP (CVRP) and the Capacitated VRP with Time Windows (CVRPTW), to show the generalizability of the proposed method. After comparing to existing RL-based methods and open-source heuristic solvers, we demonstrate its competitive performance in finding solutions with a good balance in travel distance, constraint violations and inference speed.
• Abstract（参考訳）: 現実世界のアプリケーションにおける車両ルーティング問題(VRP)は、しばしば様々な制約が伴うため、正確な解法やヒューリスティックな探索手法にさらなる計算課題をもたらす。 近年,サンプルデータからヒューリスティックな動きパターンを学習するアイデアは,ソリューション開発コストの削減にますます期待されている。 しかし、より多くのタイプの制約付きvrpに対処するための学習ベースのアプローチを使うことは依然として課題である。 この難しさは最適解を探しながら制約違反を制御することである。 この課題を解決するために,ラグランジアン緩和手法を導入し,制約付きポリシー最適化を用いてソフト制約付きVRPを解くための強化学習手法を提案する。 本手法は,3種類のVRP,TSPTW(Travelling Salesman Problem with Time Windows),CVRP(Capacitated VRP with Time Windows),CVRPTW(Capacitated VRP with Time Windows)に適用し,提案手法の一般化可能性を示す。 既存のrlベースの手法とオープンソースのヒューリスティックソルバとの比較を行った結果,旅行距離,制約違反,推論速度のバランスが良好であるソリューションを見つけることで,その競合性を示す。

関連論文リスト

• Looking Ahead to Avoid Being Late: Solving Hard-Constrained Traveling Salesman Problem [36.88003015541172]
  そこで本稿では,TSP と Time Windows (TSPTW) の正当性を改善するために,ルックアヘッド情報を用いた新しい学習手法を提案する。 多様なデータセットに関する包括的な実験により、MUSLAは既存のベースラインを上回り、一般化可能性を示す。
  論文  参考訳（メタデータ） (2024-03-08T13:49:21Z)
• Reinforcement Learning for Solving Stochastic Vehicle Routing Problem with Time Windows [0.09831489366502298]
  本稿では,時空間における車両ルーティング問題 (SVRP) の最適化のための強化学習手法を提案する。 我々は、特定の顧客時間窓とともに、不確実な旅行コストと需要を考慮に入れた新しいSVRPの定式化を開発する。 ルーティングコストを最小限に抑えるために、強化学習を通じてトレーニングされた注意ベースのニューラルネットワークが使用される。
  論文  参考訳（メタデータ） (2024-02-15T07:35:29Z)
• Reinforcement Learning for Solving Stochastic Vehicle Routing Problem [0.09831489366502298]
  本研究では、車両ルーティング問題(SVRP)解決における強化学習(RL)と機械学習(ML)技術の利用のギャップを解消する。 本稿では,SVRPのキーソースを包括的に扱う新しいエンドツーエンドフレームワークを提案する。 提案モデルでは,広く採用されている最先端のメユーリスティックよりも優れた性能を示し,旅行コストの3.43%削減を実現している。
  論文  参考訳（メタデータ） (2023-11-13T19:46:22Z)
• Roulette-Wheel Selection-Based PSO Algorithm for Solving the Vehicle Routing Problem with Time Windows [58.891409372784516]
  本稿では,Roulette Wheel Method (RWPSO) を用いた新しいPSO手法を提案する。 RWPSOのSolomon VRPTWベンチマークデータセットを用いた実験は、RWPSOが文学の他の最先端アルゴリズムと競合していることを示している。
  論文  参考訳（メタデータ） (2023-06-04T09:18:02Z)
• 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)
• Sample-Efficient, Exploration-Based Policy Optimisation for Routing Problems [2.6782615615913348]
  本稿では,エントロピーに基づく新しい強化学習手法を提案する。 さらに、我々は、期待したリターンを最大化する、政治以外の強化学習手法を設計する。 我々のモデルは様々な経路問題に一般化可能であることを示す。
  論文  参考訳（メタデータ） (2022-05-31T09:51:48Z)
• An Overview and Experimental Study of Learning-based Optimization Algorithms for Vehicle Routing Problem [49.04543375851723]
  車両ルーティング問題(VRP)は典型的な離散最適化問題である。 多くの研究は、VRPを解決するための学習に基づく最適化アルゴリズムについて検討している。 本稿では、最近のこの分野の進歩を概観し、関連するアプローチをエンドツーエンドアプローチとステップバイステップアプローチに分割する。
  論文  参考訳（メタデータ） (2021-07-15T02:13:03Z)
• Deep Policy Dynamic Programming for Vehicle Routing Problems [89.96386273895985]
  本稿では,学習ニューラルの強みと動的プログラミングアルゴリズムの強みを組み合わせた深層ポリシー動的プログラミング(d pdp)を提案する。 D PDPは、例の解からエッジを予測するために訓練されたディープニューラルネットワークから派生したポリシーを使用して、DP状態空間を優先し、制限する。 本研究では,旅行セールスマン問題 (TSP) と車両ルーティング問題 (VRP) の枠組みを評価し,ニューラルネットワークが(制限された)DPアルゴリズムの性能を向上させることを示す。
  論文  参考訳（メタデータ） (2021-02-23T15:33:57Z)
• Learning Vehicle Routing Problems using Policy Optimisation [4.093722933440819]
  最先端のアプローチは強化学習を使ってポリシーを学習し、学習ポリシーは擬似解法として機能する。 これらのアプローチは、あるケースでは優れた性能を示しているが、ルーティング問題に典型的な大きな検索空間を考えると、ポリシーの貧弱さに早すぎる可能性がある。 より多くのポリシーを提供することで探索を支援するエントロピー正規化強化学習(ERRL)を提案する。
  論文  参考訳（メタデータ） (2020-12-24T14:18:56Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。 SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。 本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-07-14T12:38:21Z)
• Guided Constrained Policy Optimization for Dynamic Quadrupedal Robot Locomotion [78.46388769788405]
  我々は,制約付きポリシー最適化(CPPO)の実装に基づくRLフレームワークであるGCPOを紹介する。 誘導制約付きRLは所望の最適値に近い高速収束を実現し,正確な報酬関数チューニングを必要とせず,最適かつ物理的に実現可能なロボット制御動作を実現することを示す。
  論文  参考訳（メタデータ） (2020-02-22T10:15:53Z)

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

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