論文の概要: Learning to Delegate for Large-scale Vehicle Routing
- arxiv url: http://arxiv.org/abs/2107.04139v1
- Date: Thu, 8 Jul 2021 22:51:58 GMT
- ステータス: 処理完了
- システム内更新日: 2021-07-12 13:57:50.812055
- Title: Learning to Delegate for Large-scale Vehicle Routing
- Title（参考訳）: 大規模車両ルーティングのためのデリート学習
- Authors: Sirui Li, Zhongxia Yan, Cathy Wu
- Abstract要約: 車両ルーティング問題 (VRPs) は、幅広い実用化の課題である。
従来あるいは学習ベースの作業は、最大100人の顧客の小さな問題インスタンスに対して、適切なソリューションを実現します。
本稿では,大規模VRPを解くために,新たな局所探索アルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 4.425982186154401
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Vehicle routing problems (VRPs) are a class of combinatorial problems with
wide practical applications. While previous heuristic or learning-based works
achieve decent solutions on small problem instances of up to 100 customers,
their performance does not scale to large problems. This article presents a
novel learning-augmented local search algorithm to solve large-scale VRP. The
method iteratively improves the solution by identifying appropriate subproblems
and $\textit{delegating}$ their improvement to a black box subsolver. At each
step, we leverage spatial locality to consider only a linear number of
subproblems, rather than exponential. We frame subproblem selection as a
regression problem and train a Transformer on a generated training set of
problem instances. We show that our method achieves state-of-the-art
performance, with a speed-up of up to 15 times over strong baselines, on VRPs
with sizes ranging from 500 to 3000.
- Abstract（参考訳）: 車両経路問題(vrps)は、幅広い実用的応用を伴う組合せ問題の一種である。
これまでのヒューリスティックあるいはラーニングベースの作品は,100ユーザまでの小さな問題インスタンスで適切なソリューションを実現していますが,そのパフォーマンスは大きな問題にはスケールしません。
本稿では,大規模vrpを解決するための新しい学習型局所探索アルゴリズムを提案する。
このメソッドは、適切なサブプロブレムと$\textit{delegating}$をブラックボックスサブソルバに改良することで、ソリューションを反復的に改善する。
各ステップにおいて、空間的局所性を利用して指数関数ではなく、線形な部分問題のみを考える。
回帰問題としてサブプロブレム選択を行い、生成した問題インスタンスのトレーニングセット上でトランスフォーマーを訓練する。
提案手法は,500～3000のvrp上で,強力なベースラインよりも最大15倍のスピードアップで,最先端のパフォーマンスを実現する。
関連論文リスト
- Spatial-temporal-demand clustering for solving large-scale vehicle
routing problems with time windows [0.0]
本稿では,クラスタリングを用いて顧客をグループ化するDRI(Decompose-route-improve)フレームワークを提案する。
その類似度基準は、顧客の空間的、時間的、需要データを含む。
本研究では,解答サブプロブレム間でプルーンド局所探索(LS)を適用し,全体の解法を改善する。
論文 参考訳（メタデータ） (2024-01-20T06:06:01Z) - Genetic Algorithms with Neural Cost Predictor for Solving Hierarchical Vehicle Routing Problems [20.684353068460375]
車両の経路決定が高次決定と連動する場合、結果の最適化問題は計算に重大な課題をもたらす。
本稿では,ニューラルコスト予測器を用いた遺伝的アルゴリズム(GANCP)という,ディープラーニングに基づく新しいアプローチを提案する。
特に,提案するニューラルネットワークは,静電容量化車両ルーティング問題を解決するHGS-CVRPオープンソースパッケージの目的値について学習する。
論文 参考訳（メタデータ） (2023-10-22T02:46:37Z) - Optimizing Solution-Samplers for Combinatorial Problems: The Landscape
of Policy-Gradient Methods [52.0617030129699]
本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。
我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。
本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
論文 参考訳（メタデータ） (2023-10-08T23:39:38Z) - Too Big, so Fail? -- Enabling Neural Construction Methods to Solve
Large-Scale Routing Problems [10.832715681422842]
最先端のニューラルコンストラクション手法でさえ、単純なイテレーションによって性能が向上していることを示す。
本稿では, 解の局所的な部分を完全に破壊し, 改良された変種を再現する。
論文 参考訳（メタデータ） (2023-09-29T09:36:37Z) - A Neural Separation Algorithm for the Rounded Capacity Inequalities [19.31854552060491]
グラフニューラルネットワーク(GNN)による正確な問題の解を学習するグラフ粗化を用いた学習ベース分離アルゴリズムを設計する。
CVRPSEPは,VRPの解決に使用される様々なカットのための,一般的な分離ソフトウェアパッケージである。
論文 参考訳（メタデータ） (2023-06-29T20:03:44Z) - Towards Omni-generalizable Neural Methods for Vehicle Routing Problems [14.210085924625705]
本稿では,VRPにおけるサイズと分布の両面での一般化を考慮した,挑戦的かつ現実的な設定について検討する。
提案するメタラーニングフレームワークは,推論中に新しいタスクに迅速に適応する能力を持つモデルを効果的に学習することを可能にする。
論文 参考訳（メタデータ） (2023-05-31T06:14:34Z) - Learning to Optimize Permutation Flow Shop Scheduling via Graph-based
Imitation Learning [70.65666982566655]
置換フローショップスケジューリング(PFSS)は製造業で広く使われている。
我々は,より安定かつ正確に収束を加速する専門家主導の模倣学習を通じてモデルを訓練することを提案する。
我々のモデルのネットワークパラメータはわずか37%に減少し、エキスパートソリューションに対する我々のモデルの解のギャップは平均6.8%から1.3%に減少する。
論文 参考訳（メタデータ） (2022-10-31T09:46:26Z) - 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) - Accelerated Policy Learning with Parallel Differentiable Simulation [59.665651562534755]
微分可能シミュレータと新しいポリシー学習アルゴリズム(SHAC)を提案する。
本アルゴリズムは,スムーズな批判機能により局所最小化の問題を軽減する。
現状のRLと微分可能なシミュレーションベースアルゴリズムと比較して,サンプル効率と壁面時間を大幅に改善した。
論文 参考訳（メタデータ） (2022-04-14T17:46:26Z) - Deep Policy Dynamic Programming for Vehicle Routing Problems [89.96386273895985]
本稿では,学習ニューラルの強みと動的プログラミングアルゴリズムの強みを組み合わせた深層ポリシー動的プログラミング(d pdp)を提案する。
D PDPは、例の解からエッジを予測するために訓練されたディープニューラルネットワークから派生したポリシーを使用して、DP状態空間を優先し、制限する。
本研究では,旅行セールスマン問題 (TSP) と車両ルーティング問題 (VRP) の枠組みを評価し,ニューラルネットワークが(制限された)DPアルゴリズムの性能を向上させることを示す。
論文 参考訳（メタデータ） (2021-02-23T15:33:57Z) - Physarum Powered Differentiable Linear Programming Layers and
Applications [48.77235931652611]
一般線形プログラミング問題に対する効率的かつ微分可能な解法を提案する。
本稿では,ビデオセグメンテーションタスクとメタラーニングにおける問題解決手法について述べる。
論文 参考訳（メタデータ） (2020-04-30T01:50:37Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。