論文の概要: Learning to Deliver: a Foundation Model for the Montreal Capacitated Vehicle Routing Problem

• arxiv url: http://arxiv.org/abs/2403.00026v1
• Date: Wed, 28 Feb 2024 16:02:29 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-05 23:19:36.599634
• Title: Learning to Deliver: a Foundation Model for the Montreal Capacitated Vehicle Routing Problem
• Title（参考訳）: モントリオールのキャパシタン化車両ルーティング問題の基礎モデル
• Authors: Samuel J. K. Chin, Matthias Winkenbach, Akash Srivastava
• Abstract要約: モントリオール静電容量車両ルーティング問題(FM-MCVRP)の基礎モデルについて述べる。 FM-MCVRPは、キャパシタント車両ルーティング問題(CVRP)の変種に対する高品質な解を近似する新しいディープラーニング(DL)モデルである。 FM-MCVRP はトレーニングデータよりも優れた MCVRP ソリューションを生成し,トレーニング中に見られない大規模問題に一般化することを示した。
• 参考スコア（独自算出の注目度）: 5.295700401553376
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper, we present the Foundation Model for the Montreal Capacitated Vehicle Routing Problem (FM-MCVRP), a novel Deep Learning (DL) model that approximates high-quality solutions to a variant of the Capacitated Vehicle Routing Problem (CVRP) that characterizes many real-world applications. The so-called Montreal Capacitated Vehicle Routing Problem (MCVRP), first formally described by Bengio et al. (2021), is defined on a fixed and finite graph, which is analogous to a city. Each MCVRP instance is essentially the sub-graph connecting a randomly sampled subset of the nodes in the fixed graph, which represent a set of potential addresses in a real-world delivery problem on a given day. Our work exploits this problem structure to frame the MCVRP as an analogous Natural Language Processing (NLP) task. Specifically, we leverage a Transformer architecture embedded in a Large Language Model (LLM) framework to train our model in a supervised manner on computationally inexpensive, sub-optimal MCVRP solutions obtained algorithmically. Through comprehensive computational experiments, we show that FM-MCVRP produces better MCVRP solutions than the training data and generalizes to larger sized problem instances not seen during training. Even when compared to near-optimal solutions from state-of-the-art heuristics, FM-MCVRP yields competitive results despite being trained on inferior data. For instance, for 400-customer problems, FM-MCVRP solutions on average fall within 2% of the benchmark. Our results further demonstrate that unlike prior works in the literature, FM-MCVRP is a unified model, which performs consistently and reliably on a range of problem instance sizes and parameter values such as the vehicle capacity.
• Abstract（参考訳）: 本稿では,多くの実世界の応用を特徴付けるCVRP(Capacitated Vehicle Routing Problem)の変種に対して,高品質な解を近似する新しいDeep Learning (DL)モデルである,Montreal Capacitated Vehicle Routing Problem (FM-MCVRP)の基礎モデルを提案する。 モントリオール・キャパシタッド・ビークル・ルーティング問題(MCVRP、Montreal Capacitated Vehicle Routing Problem)は、Bengio et al. (2021)によって初めて公式に記述され、都市と類似した固定有限グラフ上で定義される。 それぞれのMCVRPインスタンスは、基本的には固定グラフ内のノードのランダムにサンプリングされたサブセットを接続するサブグラフであり、その日、現実世界の配送問題における潜在的なアドレスのセットを表す。 本研究は,MCVRPを自然言語処理(NLP)の類似タスクとするために,この問題構造を利用する。 具体的には,Large Language Model (LLM) フレームワークに組み込まれた Transformer アーキテクチャを利用して,アルゴリズムによって得られた計算コストの低い準最適 MCVRP ソリューションに基づいてモデルを教師付きでトレーニングする。 総合的な計算実験により,FM-MCVRP はトレーニングデータよりも優れた MCVRP ソリューションを生成し,トレーニング中に見られない大規模問題に一般化することを示した。 FM-MCVRPは、最先端のヒューリスティックによる最適に近い解と比較しても、劣ったデータで訓練されているにもかかわらず、競争結果が得られる。 例えば、400顧客問題の場合、fm-mcvrpソリューションは平均してベンチマークの2%以下である。 文献の先行研究と異なり,FM-MCVRPは一貫したモデルであり,問題インスタンスサイズや車両の容量などのパラメータ値の連続的かつ確実な性能を示す。

関連論文リスト

• MVMoE: Multi-Task Vehicle Routing Solver with Mixture-of-Experts [26.790392171537754]
  MRMoE(Mixed-of-experts)を用いたマルチタスク車両ルーティング解法を提案する。 我々はMVMoEの階層的ゲーティング機構を開発し、経験的性能と計算複雑性のトレードオフを良好に提供する。 実験により,本手法は10種類のVRPのゼロショット一般化性能を著しく向上させる。
  論文  参考訳（メタデータ） (2024-05-02T06:02:07Z)
• Multi-Task Learning for Routing Problem with Cross-Problem Zero-Shot Generalization [18.298695520665348]
  車両ルーティング問題(VRP)は多くの現実世界のアプリケーションで見られる。 本研究では,クロスプロブレム一般化という重要な課題に取り組むための最初の試みを行う。 提案モデルでは、ゼロショットの一般化方式で、見当たらない属性の組み合わせでVRPを解くことができる。
  論文  参考訳（メタデータ） (2024-02-23T13:25:23Z)
• Transforming Image Super-Resolution: A ConvFormer-based Efficient Approach [58.57026686186709]
  本稿では, Convolutional Transformer Layer (ConvFormer) を導入し, ConvFormer-based Super-Resolution Network (CFSR) を提案する。 CFSRは畳み込みベースのアプローチとトランスフォーマーベースのアプローチの両方の利点を継承する。 CFSRは計算コストと性能のバランスが最適であることを示す実験である。
  論文  参考訳（メタデータ） (2024-01-11T03:08:00Z)
• MOTO: Offline Pre-training to Online Fine-tuning for Model-based Robot Learning [52.101643259906915]
  本研究では,高次元観測による強化学習におけるオフライン事前学習とオンラインファインチューニングの問題について検討する。 既存のモデルベースオフラインRL法は高次元領域におけるオフラインからオンラインへの微調整には適していない。 本稿では,事前データをモデルベース値拡張とポリシー正則化によって効率的に再利用できるオンラインモデルベース手法を提案する。
  論文  参考訳（メタデータ） (2024-01-06T21:04:31Z)
• A Multi-Head Ensemble Multi-Task Learning Approach for Dynamical Computation Offloading [62.34538208323411]
  共有バックボーンと複数の予測ヘッド(PH)を組み合わせたマルチヘッドマルチタスク学習(MEMTL)手法を提案する。 MEMTLは、追加のトレーニングデータを必要とせず、推測精度と平均平方誤差の両方でベンチマーク手法より優れている。
  論文  参考訳（メタデータ） (2023-09-02T11:01:16Z)
• Towards Omni-generalizable Neural Methods for Vehicle Routing Problems [14.210085924625705]
  本稿では,VRPにおけるサイズと分布の両面での一般化を考慮した,挑戦的かつ現実的な設定について検討する。 提案するメタラーニングフレームワークは,推論中に新しいタスクに迅速に適応する能力を持つモデルを効果的に学習することを可能にする。
  論文  参考訳（メタデータ） (2023-05-31T06:14:34Z)
• On Continual Model Refinement in Out-of-Distribution Data Streams [64.62569873799096]
  現実世界の自然言語処理(NLP)モデルは、アウト・オブ・ディストリビューション(OOD)データストリームの予測エラーを修正するために、継続的に更新する必要がある。 既存の継続学習(CL)問題設定は、そのような現実的で複雑なシナリオをカバーできない。 連続モデル改良(CMR)と呼ばれる新しいCL問題定式化を提案する。
  論文  参考訳（メタデータ） (2022-05-04T11:54:44Z)
• An SMT Based Compositional Model to Solve a Conflict-Free Electric Vehicle Routing Problem [2.64699517152535]
  CF-EVRP(Electric Conflict-Free Vehicle Routing Problem)は、車両の運転範囲の制限、顧客への配送時間帯の制限、道路セグメントが許容できる車両数に対する制限といった制約を含む。 我々は、問題をより小さく、より単純なサブプロブレムに分解し、準最適で実現可能なソリューションを提供する構成モデルを開発する。
  論文  参考訳（メタデータ） (2021-06-10T20:37:46Z)
• MMCGAN: Generative Adversarial Network with Explicit Manifold Prior [78.58159882218378]
  本稿では,モード崩壊を緩和し,GANのトレーニングを安定させるために,明示的な多様体学習を採用することを提案する。 玩具データと実データの両方を用いた実験により,MMCGANのモード崩壊緩和効果,トレーニングの安定化,生成サンプルの品質向上効果が示された。
  論文  参考訳（メタデータ） (2020-06-18T07:38:54Z)
• An Online Method for A Class of Distributionally Robust Optimization with Non-Convex Objectives [54.29001037565384]
  本稿では,オンライン分散ロバスト最適化(DRO)のクラスを解決するための実用的なオンライン手法を提案する。 本研究は,ネットワークの堅牢性向上のための機械学習における重要な応用を実証する。
  論文  参考訳（メタデータ） (2020-06-17T20:19:25Z)
• A Quantum Annealing Approach for Dynamic Multi-Depot Capacitated Vehicle Routing Problem [5.057312718525522]
  本稿では,AQC(Adiabatic Quantum Computation)の原理に基づく量子コンピューティングアルゴリズムを提案する。 従来のアルゴリズムと比較して、車両ルーティング問題(VRP)のような最適化問題の解法において、計算上の利点が顕著に示された。 これは、輸送、物流、サプライチェーン管理の分野における実世界の応用におけるNPハード最適化問題である。
  論文  参考訳（メタデータ） (2020-05-26T01:47:39Z)

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

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