論文の概要: Learning to Handle Complex Constraints for Vehicle Routing Problems

• arxiv url: http://arxiv.org/abs/2410.21066v1
• Date: Mon, 28 Oct 2024 14:26:54 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-29 12:16:34.267894
• Title: Learning to Handle Complex Constraints for Vehicle Routing Problems
• Title（参考訳）: 自動車経路問題に対する複雑制約の扱いの学習
• Authors: Jieyi Bi, Yining Ma, Jianan Zhou, Wen Song, Zhiguang Cao, Yaoxin Wu, Jie Zhang,
• Abstract要約: 車両ルーティング問題(VRP)は多くの現実のシナリオをモデル化することができ、しばしば複雑な制約を伴います。 最近のニューラルメソッドは、実現可能性マスキングに基づくソリューションの構築において優れているが、複雑な制約を扱うのに苦労している。 本稿では,より複雑なVRPに向けたニューラルメソッドの能力を向上するための,新しい能動的機能改善フレームワークを提案する。
• 参考スコア（独自算出の注目度）: 26.354311541533754
• License:
• Abstract: Vehicle Routing Problems (VRPs) can model many real-world scenarios and often involve complex constraints. While recent neural methods excel in constructing solutions based on feasibility masking, they struggle with handling complex constraints, especially when obtaining the masking itself is NP-hard. In this paper, we propose a novel Proactive Infeasibility Prevention (PIP) framework to advance the capabilities of neural methods towards more complex VRPs. Our PIP integrates the Lagrangian multiplier as a basis to enhance constraint awareness and introduces preventative infeasibility masking to proactively steer the solution construction process. Moreover, we present PIP-D, which employs an auxiliary decoder and two adaptive strategies to learn and predict these tailored masks, potentially enhancing performance while significantly reducing computational costs during training. To verify our PIP designs, we conduct extensive experiments on the highly challenging Traveling Salesman Problem with Time Window (TSPTW), and TSP with Draft Limit (TSPDL) variants under different constraint hardness levels. Notably, our PIP is generic to boost many neural methods, and exhibits both a significant reduction in infeasible rate and a substantial improvement in solution quality.
• Abstract（参考訳）: 車両ルーティング問題(VRP)は多くの現実のシナリオをモデル化することができ、しばしば複雑な制約を伴います。 近年のニューラルメソッドは、実現可能性マスキングに基づくソリューションの構築に優れていますが、特にマスキング自体がNPハードである場合、複雑な制約を扱うのに苦労しています。 本稿では,より複雑なVRPに向けたニューラルメソッドの能力向上を目的とした,新しいPIPフレームワークを提案する。 当社のPIPは,制約意識を高める基盤としてラグランジアン乗算器を統合し,ソリューション構築過程を積極的に制御するために予防的不実現性マスキングを導入している。 さらに、補助デコーダと2つの適応戦略を用いて、これらの調整マスクを学習し、予測し、トレーニング中の計算コストを大幅に削減しながら性能を向上するPIP-Dを提案する。 PIP設計を検証するため,時間窓付きトラベリングセールスマン問題 (TSPTW) と,異なる制約硬度条件下でのドラフトリミット (TSPDL) 変種を用いたTSPについて広範な実験を行った。 特に、我々のPIPは、多くのニューラルメソッドを向上するために汎用的であり、実現不可能な速度の大幅な削減と、ソリューション品質の大幅な改善の両方を示します。

関連論文リスト

• Constrained Reinforcement Learning with Smoothed Log Barrier Function [27.216122901635018]
  CSAC-LB (Constrained Soft Actor-Critic with Log Barrier Function) と呼ばれる新しい制約付きRL法を提案する。 線形スムーズなログバリア関数を追加の安全評論家に適用することにより、事前トレーニングなしで競争性能を達成する。 CSAC-LBでは,様々な難易度を有する制約付き制御タスクにおいて,最先端の性能を実現する。
  論文  参考訳（メタデータ） (2024-03-21T16:02:52Z)
• An Efficient Learning-based Solver Comparable to Metaheuristics for the Capacitated Arc Routing Problem [67.92544792239086]
  我々は,高度メタヒューリスティックスとのギャップを著しく狭めるため,NNベースの解法を導入する。 まず,方向対応型注意モデル(DaAM)を提案する。 第2に、教師付き事前学習を伴い、堅牢な初期方針を確立するための教師付き強化学習スキームを設計する。
  論文  参考訳（メタデータ） (2024-03-11T02:17:42Z)
• Capsa: A Unified Framework for Quantifying Risk in Deep Neural Networks [142.67349734180445]
  ディープニューラルネットワークにリスク認識を提供する既存のアルゴリズムは複雑でアドホックである。 ここでは、リスク認識でモデルを拡張するためのフレームワークであるcapsaを紹介します。
  論文  参考訳（メタデータ） (2023-08-01T02:07:47Z)
• Neural Fields with Hard Constraints of Arbitrary Differential Order [61.49418682745144]
  我々は、ニューラルネットワークに厳しい制約を課すための一連のアプローチを開発する。 制約は、ニューラルネットワークとそのデリバティブに適用される線形作用素として指定することができる。 私たちのアプローチは、広範囲の現実世界のアプリケーションで実証されています。
  論文  参考訳（メタデータ） (2023-06-15T08:33:52Z)
• Travel the Same Path: A Novel TSP Solving Strategy [0.0]
  我々は、必要に応じて適切な選択を行う決定論的アルゴリズムを支援する模倣学習フレームワークについて検討する。 我々は、模倣学習フレームワークの下で訓練されたグラフニューラルネットワークの強力な一般化能力を示す。
  論文  参考訳（メタデータ） (2022-10-12T03:56:37Z)
• Learning to Solve Soft-Constrained Vehicle Routing Problems with Lagrangian Relaxation [0.4014524824655105]
  現実世界のアプリケーションにおける車両ルーティング問題(VRP)には、様々な制約が伴うことが多い。 ソフト制約付きVRPを解くために,強化学習に基づく手法を提案する。 本稿では,3種類のVRP,TSPTW(Travelling Salesman Problem with Time Windows),CVRP(Capacitated VRP),CVRPTW(Capacitated VRP with Time Windows)に適用する。
  論文  参考訳（メタデータ） (2022-07-20T12:51:06Z)
• Penalized Proximal Policy Optimization for Safe Reinforcement Learning [68.86485583981866]
  本稿では、等価な制約のない問題の単一最小化により、煩雑な制約付きポリシー反復を解決するP3Oを提案する。 P3Oは、コスト制約を排除し、クリップされたサロゲート目的による信頼領域制約を除去するために、単純なyet効果のペナルティ関数を利用する。 P3Oは,一連の制約された機関車作業において,報酬改善と制約満足度の両方に関して,最先端のアルゴリズムより優れていることを示す。
  論文  参考訳（メタデータ） (2022-05-24T06:15:51Z)
• Deep Policy Dynamic Programming for Vehicle Routing Problems [89.96386273895985]
  本稿では,学習ニューラルの強みと動的プログラミングアルゴリズムの強みを組み合わせた深層ポリシー動的プログラミング(d pdp)を提案する。 D PDPは、例の解からエッジを予測するために訓練されたディープニューラルネットワークから派生したポリシーを使用して、DP状態空間を優先し、制限する。 本研究では,旅行セールスマン問題 (TSP) と車両ルーティング問題 (VRP) の枠組みを評価し,ニューラルネットワークが(制限された)DPアルゴリズムの性能を向上させることを示す。
  論文  参考訳（メタデータ） (2021-02-23T15:33:57Z)
• Local Propagation in Constraint-based Neural Network [77.37829055999238]
  ニューラルネットワークアーキテクチャの制約に基づく表現について検討する。 本稿では,いわゆるアーキテクチャ制約を満たすのに適した簡単な最適化手法について検討する。
  論文  参考訳（メタデータ） (2020-02-18T16:47:38Z)

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

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