論文の概要: Combining Constructive and Perturbative Deep Learning Algorithms for the Capacitated Vehicle Routing Problem

• arxiv url: http://arxiv.org/abs/2211.13922v1
• Date: Fri, 25 Nov 2022 06:20:11 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-28 19:00:05.842308
• Title: Combining Constructive and Perturbative Deep Learning Algorithms for the Capacitated Vehicle Routing Problem
• Title（参考訳）: キャパシタ付き車両経路問題に対する構成的・摂動的深層学習アルゴリズムの併用
• Authors: Roberto Garc\'ia-Torres, Alitzel Adriana Macias-Infante, Santiago Enrique Conant-Pablos, Jos\'e Carlos Ortiz-Bayliss and Hugo Terashima-Mar\'in
• Abstract要約: 容量化車両ルーティング問題(Capacitated Vehicle Routing Problem)は、複数の場所に製品を届ける車両の最適経路を見つけることの難題となるNPハード問題である。 近年,この問題に対処する構築的で摂動的なディープラーニングベースのアルゴリズムの開発が試みられている。 本稿では,2つの強力な構築型および摂動型ディープラーニングに基づくアルゴリズムを組み合わせた,複合型Deep ConstructorとPerturbatorを提案する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Capacitated Vehicle Routing Problem is a well-known NP-hard problem that poses the challenge of finding the optimal route of a vehicle delivering products to multiple locations. Recently, new efforts have emerged to create constructive and perturbative heuristics to tackle this problem using Deep Learning. In this paper, we join these efforts to develop the Combined Deep Constructor and Perturbator, which combines two powerful constructive and perturbative Deep Learning-based heuristics, using attention mechanisms at their core. Furthermore, we improve the Attention Model-Dynamic for the Capacitated Vehicle Routing Problem by proposing a memory-efficient algorithm that reduces its memory complexity by a factor of the number of nodes. Our method shows promising results. It demonstrates a cost improvement in common datasets when compared against other multiple Deep Learning methods. It also obtains close results to the state-of-the art heuristics from the Operations Research field. Additionally, the proposed memory efficient algorithm for the Attention Model-Dynamic model enables its use in problem instances with more than 100 nodes.
• Abstract（参考訳）: 容量化車両ルーティング問題(Capacitated Vehicle Routing Problem)は、複数の場所に製品を届ける車両の最適経路を見つけることの難題となるNPハード問題である。 近年,Deep Learning を用いてこの問題に対処するための建設的・摂動的ヒューリスティックの構築が試みられている。 本稿では,2つの強力な構成的・摂動的深層学習に基づくヒューリスティックを組み合わせ,その中核に注意機構を用いた複合型深層構築と摂動器の開発に参画する。 さらに,ノード数によるメモリ複雑性を低減させるメモリ効率のアルゴリズムを提案することにより,容量化車両ルーティング問題に対する注意モデル動的性を改善する。 我々の方法は有望な結果を示す。 他の複数のディープラーニング手法と比較して、一般的なデータセットのコスト改善を示す。 また、オペレーティング・リサーチ・フィールドから最先端のアート・ヒューリスティックスに密接な結果を得られる。 さらに、注意モデル・動的モデルのためのメモリ効率のよいアルゴリズムにより、100ノード以上の問題インスタンスで使用できる。

関連論文リスト

• A Neural Column Generation Approach to the Vehicle Routing Problem with Two-Dimensional Loading and Last-In-First-Out Constraints [3.9594431485015096]
  2次元負荷制約 (2L-CVRP) を持つ車両ルーティング問題は, 実用的, アルゴリズム的に重要な課題である。 本稿では,高度な機械学習技術,特に注意と再発機構の新たな組み合わせを統合した,正確なアルゴリズムを提案する。 提案アルゴリズムは、標準テストベッドにおけるオープンインスタンスの解決に成功し、機械学習モデルの導入による大幅な改善を実証する。
  論文  参考訳（メタデータ） (2024-06-18T09:58:29Z)
• 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)
• 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)
• Combining Reinforcement Learning and Optimal Transport for the Traveling Salesman Problem [18.735056206844202]
  我々は,従来の自己回帰的アプローチよりもはるかに高速に,監督や推論なしに学習できるモデルを構築することができることを示す。 また、ディープラーニングモデルに最適なトランスポートアルゴリズムを組み込むことで、エンドツーエンドのトレーニング中に割り当て制約を強制する利点を実証的に評価する。
  論文  参考訳（メタデータ） (2022-03-02T07:21:56Z)
• 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)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Strong Generalization and Efficiency in Neural Programs [69.18742158883869]
  本稿では,ニューラルプログラム誘導の枠組みを強く一般化する効率的なアルゴリズムを学習する問題について検討する。 ニューラルネットワークの入力/出力インターフェースを慎重に設計し、模倣することで、任意の入力サイズに対して正しい結果を生成するモデルを学ぶことができる。
  論文  参考訳（メタデータ） (2020-07-07T17:03:02Z)
• Learning to Stop While Learning to Predict [85.7136203122784]
  多くのアルゴリズムにインスパイアされたディープモデルは全ての入力に対して固定深度に制限される。 アルゴリズムと同様に、深いアーキテクチャの最適深さは、異なる入力インスタンスに対して異なるかもしれない。 本稿では, ステアブルアーキテクチャを用いて, この様々な深さ問題に対処する。 学習した深層モデルと停止ポリシーにより,多様なタスクセットのパフォーマンスが向上することを示す。
  論文  参考訳（メタデータ） (2020-06-09T07:22:01Z)
• A Deep Reinforcement Learning Algorithm Using Dynamic Attention Model for Vehicle Routing Problems [20.52666896700441]
  本稿では,NPハード問題,車両ルーティング問題に焦点をあてる。 本モデルは,従来の手法よりも優れ,また,優れた一般化性能を示す。
  論文  参考訳（メタデータ） (2020-02-09T04:51:53Z)

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

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