論文の概要: Multi-Task Learning for Routing Problem with Cross-Problem Zero-Shot Generalization
- arxiv url: http://arxiv.org/abs/2402.16891v2
- Date: Fri, 12 Apr 2024 15:34:18 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-15 17:23:29.235623
- Title: Multi-Task Learning for Routing Problem with Cross-Problem Zero-Shot Generalization
- Title(参考訳): クロスプロブレムゼロショット一般化を用いたルーティング問題に対するマルチタスク学習
- Authors: Fei Liu, Xi Lin, Zhenkun Wang, Qingfu Zhang, Xialiang Tong, Mingxuan Yuan,
- Abstract要約: 車両ルーティング問題(VRP)は多くの現実世界のアプリケーションで見られる。
本研究では,クロスプロブレム一般化という重要な課題に取り組むための最初の試みを行う。
提案モデルでは、ゼロショットの一般化方式で、見当たらない属性の組み合わせでVRPを解くことができる。
- 参考スコア(独自算出の注目度): 18.298695520665348
- 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. The source code is included in https://github.com/FeiLiu36/MTNCO.
- Abstract(参考訳): 車両ルーティング問題(VRPs)は、何十年もの間、重要な研究課題であった。
近年,手動アルゴリズム設計なしでVRPを解く学習モデルを活用したニューラル組合せ最適化(NCO)アプローチが注目されている。
しかし、現在のNCO手法では、ルーティング問題に対して1つのモデルを構築する必要があり、様々な特性を持つ現実の産業問題に対する実践的応用を著しく妨げている。
本研究では,クロスプロブレム一般化という重要な課題に取り組むための最初の試みを行う。
特に,共有属性の異なる組み合わせとしてVRPを定式化し,属性合成を通じて単一モデルを用いて同時に解決する。
このようにして、提案モデルは、ゼロショットの一般化方式で、見当たらない属性の組み合わせで、VRPをうまく解くことができる。
大規模な実験は、11のVRP変種、ベンチマークデータセット、業界ロジスティックシナリオで実施されている。
その結果,11個のVRPにおいて統合モデルは優れた性能を示し,既存のアプローチの20%以上から平均的なギャップを約5%削減し,ベンチマークデータセットや実世界のロジスティクスアプリケーション上での大幅なパフォーマンス向上を実現した。
ソースコードはhttps://github.com/FeiLiu36/MTNCOに含まれる。
関連論文リスト
- Joint Demonstration and Preference Learning Improves Policy Alignment with Human Feedback [58.049113055986375]
我々は、報酬モデルとポリシーをトレーニングするために、AIHF(Alignment with Integrated Human Feedback)と呼ばれる単一ステージアプローチを開発する。
提案した手法は、一般的なアライメントアルゴリズムに容易に還元し、活用できる、効率的なアルゴリズムの集合を認めている。
本研究では,LLMにおけるアライメント問題と,MuJoCoにおけるロボット制御問題を含む広範な実験により,提案手法の有効性を実証する。
論文 参考訳(メタデータ) (2024-06-11T01:20:53Z) - Improving Generalization of Neural Vehicle Routing Problem Solvers Through the Lens of Model Architecture [9.244633039170186]
本稿では,ESF(Scaling Factor)とDS(Distributed-Specific)デコーダを提案する。
ESFは、様々な大きさのVRPを解く際に、トレーニング中に発見された慣れ親しんだものに対して、モデルの注意重みパターンを調整する。
DSデコーダは、複数の補助光デコーダを通して複数のトレーニング分布パターンのVRPを明示的にモデル化し、モデル表現空間を拡大する。
論文 参考訳(メタデータ) (2024-06-10T09:03:17Z) - Prompt Learning for Generalized Vehicle Routing [17.424910810870273]
本研究は, クロスディストリビューション適応のためのニューラル最適化において, 効率的なプロンプト学習手法について検討する。
提案モデルでは, 各種分布の一連のプロンプトを学習し, 最良適合のプロンプトを選択し, 各問題インスタンスに対して事前学習したアテンションモデルを提案する。
また、分散予測とゼロショット一般化の両方において、既存の一般化されたモデルよりも、多様な新しいタスクセットに優れる。
論文 参考訳(メタデータ) (2024-05-20T15:42:23Z) - MVMoE: Multi-Task Vehicle Routing Solver with Mixture-of-Experts [26.790392171537754]
MRMoE(Mixed-of-experts)を用いたマルチタスク車両ルーティング解法を提案する。
我々はMVMoEの階層的ゲーティング機構を開発し、経験的性能と計算複雑性のトレードオフを良好に提供する。
実験により,本手法は10種類のVRPのゼロショット一般化性能を著しく向上させる。
論文 参考訳(メタデータ) (2024-05-02T06:02:07Z) - An Efficient Learning-based Solver Comparable to Metaheuristics for the
Capacitated Arc Routing Problem [67.92544792239086]
我々は,高度メタヒューリスティックスとのギャップを著しく狭めるため,NNベースの解法を導入する。
まず,方向対応型注意モデル(DaAM)を提案する。
第2に、教師付き事前学習を伴い、堅牢な初期方針を確立するための教師付き強化学習スキームを設計する。
論文 参考訳(メタデータ) (2024-03-11T02:17:42Z) - Towards Generalizable Neural Solvers for Vehicle Routing Problems via Ensemble with Transferrable Local Policy [24.91781032046481]
車両ルーティング問題(VRP)のための多くのニューラルネットワーク構築手法は、特定のノード分布と限られたスケールを持つ合成問題インスタンスに焦点を当てている。
我々は,局所移動可能な局所的特徴から学習する補助的政策を設計し,それを典型的な建設方針と統合し,アンサンブル政策を形成する。
共同トレーニングでは、集約されたポリシが協調的かつ補完的に実行され、一般化が促進される。
論文 参考訳(メタデータ) (2023-08-27T13:22:50Z) - Towards Omni-generalizable Neural Methods for Vehicle Routing Problems [14.210085924625705]
本稿では,VRPにおけるサイズと分布の両面での一般化を考慮した,挑戦的かつ現実的な設定について検討する。
提案するメタラーニングフレームワークは,推論中に新しいタスクに迅速に適応する能力を持つモデルを効果的に学習することを可能にする。
論文 参考訳(メタデータ) (2023-05-31T06:14:34Z) - Reinforcement Learning for Branch-and-Bound Optimisation using
Retrospective Trajectories [72.15369769265398]
機械学習は分岐のための有望なパラダイムとして登場した。
分岐のための単純かつ効果的なRLアプローチであるレトロ分岐を提案する。
我々は現在最先端のRL分岐アルゴリズムを3~5倍に上回り、500の制約と1000の変数を持つMILP上での最高のILメソッドの性能の20%以内である。
論文 参考訳(メタデータ) (2022-05-28T06:08:07Z) - RoMA: Robust Model Adaptation for Offline Model-based Optimization [115.02677045518692]
入力出力クエリの静的データセットからブラックボックス目的関数を最大化する入力を探索する問題を考える。
この問題を解決するための一般的なアプローチは、真の客観的関数を近似するプロキシモデルを維持することである。
ここでの大きな課題は、検索中に逆最適化された入力を避ける方法である。
論文 参考訳(メタデータ) (2021-10-27T05:37:12Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。