論文の概要: Multi-Task Learning for Routing Problem with Cross-Problem Zero-Shot
Generalization
- arxiv url: http://arxiv.org/abs/2402.16891v1
- Date: Fri, 23 Feb 2024 13:25:23 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-28 19:23:05.700827
- Title: Multi-Task Learning for Routing Problem with Cross-Problem Zero-Shot
Generalization
- Title(参考訳): クロスプロブレムゼロショット一般化によるルーティング問題に対するマルチタスク学習
- Authors: Fei Liu, Xi Lin, Qingfu Zhang, Xialiang Tong, Mingxuan Yuan
- Abstract要約: 車両ルーティング問題(VRP)は多くの現実世界のアプリケーションで見られる。
本研究では,クロスプロブレム一般化という重要な課題に取り組むための最初の試みを行う。
提案モデルでは、ゼロショットの一般化方式で、見当たらない属性の組み合わせでVRPを解くことができる。
- 参考スコア(独自算出の注目度): 17.73090399848471
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Vehicle routing problems (VRPs), which can be found in numerous real-world
applications, have been an important research topic for several decades.
Recently, the neural combinatorial optimization (NCO) approach that leverages a
learning-based model to solve VRPs without manual algorithm design has gained
substantial attention. However, current NCO methods typically require building
one model for each routing problem, which significantly hinders their practical
application for real-world industry problems with diverse attributes. In this
work, we make the first attempt to tackle the crucial challenge of
cross-problem generalization. In particular, we formulate VRPs as different
combinations of a set of shared underlying attributes and solve them
simultaneously via a single model through attribute composition. In this way,
our proposed model can successfully solve VRPs with unseen attribute
combinations in a zero-shot generalization manner. Extensive experiments are
conducted on eleven VRP variants, benchmark datasets, and industry logistic
scenarios. The results show that the unified model demonstrates superior
performance in the eleven VRPs, reducing the average gap to around 5% from over
20% in the existing approach and achieving a significant performance boost on
benchmark datasets as well as a real-world logistics application.
- Abstract(参考訳): 車両のルーティング問題(vrps)は、多くの現実世界のアプリケーションで見られるが、数十年間、重要な研究課題となっている。
近年,手動アルゴリズム設計なしでVRPを解く学習モデルを活用したニューラルネットワーク最適化(NCO)アプローチが注目されている。
しかし、現在のNCO手法では、ルーティング問題に対して1つのモデルを構築する必要があり、様々な特性を持つ現実の産業問題に対する実践的応用を著しく妨げている。
本研究では,クロスプロブレム一般化の重大な課題に取り組むための最初の試みを行う。
特に,共有属性の異なる組み合わせとしてVRPを定式化し,属性合成を通じて単一モデルを用いて同時に解決する。
このようにして、提案モデルは、ゼロショットの一般化方式で、見知らぬ属性の組み合わせでVRPを解くことができる。
11のvrp変種、ベンチマークデータセット、業界ロジスティックシナリオに関する広範な実験が行われている。
その結果,11個のVRPにおいて統合モデルは優れた性能を示し,既存のアプローチの20%以上から平均的なギャップを約5%削減し,ベンチマークデータセットや実世界のロジスティクスアプリケーション上での大幅なパフォーマンス向上を実現した。
関連論文リスト
- An Efficient Learning-based Solver Comparable to Metaheuristics for the
Capacitated Arc Routing Problem [67.92544792239086]
我々は,高度メタヒューリスティックスとのギャップを著しく狭めるため,NNベースの解法を導入する。
まず,方向対応型注意モデル(DaAM)を提案する。
第2に、教師付き事前学習を伴い、堅牢な初期方針を確立するための教師付き強化学習スキームを設計する。
論文 参考訳(メタデータ) (2024-03-11T02:17:42Z) - Combinatorial Optimization with Policy Adaptation using Latent Space
Search [46.02102888864839]
本稿では,複雑なNPハード問題を解くために,パフォーマンスアルゴリズムを設計するための新しいアプローチを提案する。
我々の検索戦略は11の標準ベンチマークタスクにおける最先端のアプローチよりも優れていることを示す。
論文 参考訳(メタデータ) (2023-11-13T12:24:54Z) - Towards Generalizable Neural Solvers for Vehicle Routing Problems via
Ensemble with Transferrable Local Policy [26.732971987678656]
我々は,局所移動可能な局所的特徴から学習する補助的政策を設計し,それを典型的な建設方針と統合し,アンサンブル政策を形成する。
共同トレーニングでは、集約されたポリシが協調的かつ補完的に実行され、一般化が促進される。
TSPLIBとCVRPLIBの2つのよく知られたベンチマークの結果、旅行セールスマン問題と静電容量化VRPは、アンサンブルポリシーがクロスディストリビューションとクロススケールの一般化性能の両方を著しく改善することを示した。
論文 参考訳(メタデータ) (2023-08-27T13:22:50Z) - Towards Omni-generalizable Neural Methods for Vehicle Routing Problems [14.210085924625705]
本稿では,VRPにおけるサイズと分布の両面での一般化を考慮した,挑戦的かつ現実的な設定について検討する。
提案するメタラーニングフレームワークは,推論中に新しいタスクに迅速に適応する能力を持つモデルを効果的に学習することを可能にする。
論文 参考訳(メタデータ) (2023-05-31T06:14:34Z) - Attention, Filling in The Gaps for Generalization in Routing Problems [5.210197476419621]
本稿では,既存のモデルの理解と改善を通じて,分野の統合を促進することを目的とする。
我々はまず,Sparse Dynamic Attention のための Kool et al. 法とその損失関数を適用することで,モデルの相違を第一に狙う。
次に、特定のシナリオにおける単一インスタンストレーニングよりも優れたパフォーマンスを示す混合インスタンストレーニングメソッドを使用することで、固有の違いをターゲットとします。
論文 参考訳(メタデータ) (2022-07-14T21:36:51Z) - Sample-Efficient, Exploration-Based Policy Optimisation for Routing
Problems [2.6782615615913348]
本稿では,エントロピーに基づく新しい強化学習手法を提案する。
さらに、我々は、期待したリターンを最大化する、政治以外の強化学習手法を設計する。
我々のモデルは様々な経路問題に一般化可能であることを示す。
論文 参考訳(メタデータ) (2022-05-31T09:51:48Z) - RoMA: Robust Model Adaptation for Offline Model-based Optimization [115.02677045518692]
入力出力クエリの静的データセットからブラックボックス目的関数を最大化する入力を探索する問題を考える。
この問題を解決するための一般的なアプローチは、真の客観的関数を近似するプロキシモデルを維持することである。
ここでの大きな課題は、検索中に逆最適化された入力を避ける方法である。
論文 参考訳(メタデータ) (2021-10-27T05:37:12Z) - An Overview and Experimental Study of Learning-based Optimization
Algorithms for Vehicle Routing Problem [49.04543375851723]
車両ルーティング問題(VRP)は典型的な離散最適化問題である。
多くの研究は、VRPを解決するための学習に基づく最適化アルゴリズムについて検討している。
本稿では、最近のこの分野の進歩を概観し、関連するアプローチをエンドツーエンドアプローチとステップバイステップアプローチに分割する。
論文 参考訳(メタデータ) (2021-07-15T02:13:03Z) - Efficient Model-Based Multi-Agent Mean-Field Reinforcement Learning [89.31889875864599]
マルチエージェントシステムにおける学習に有効なモデルベース強化学習アルゴリズムを提案する。
我々の理論的な貢献は、MFCのモデルベース強化学習における最初の一般的な後悔の限界である。
コア最適化問題の実用的なパラメトリゼーションを提供する。
論文 参考訳(メタデータ) (2021-07-08T18:01:02Z) - Quasi-Global Momentum: Accelerating Decentralized Deep Learning on
Heterogeneous Data [77.88594632644347]
ディープラーニングモデルの分散トレーニングは、ネットワーク上でデータプライバシとデバイス上での学習を可能にする重要な要素である。
現実的な学習シナリオでは、異なるクライアントのローカルデータセットに異質性が存在することが最適化の課題となる。
本稿では,この分散学習の難しさを軽減するために,運動量に基づく新しい手法を提案する。
論文 参考訳(メタデータ) (2021-02-09T11:27:14Z) - An Online Method for A Class of Distributionally Robust Optimization
with Non-Convex Objectives [54.29001037565384]
本稿では,オンライン分散ロバスト最適化(DRO)のクラスを解決するための実用的なオンライン手法を提案する。
本研究は,ネットワークの堅牢性向上のための機械学習における重要な応用を実証する。
論文 参考訳(メタデータ) (2020-06-17T20:19:25Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。