論文の概要: Towards Generalizable Neural Solvers for Vehicle Routing Problems via Ensemble with Transferrable Local Policy
- arxiv url: http://arxiv.org/abs/2308.14104v3
- Date: Sun, 5 May 2024 13:55:07 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-08 00:55:03.398220
- Title: Towards Generalizable Neural Solvers for Vehicle Routing Problems via Ensemble with Transferrable Local Policy
- Title（参考訳）: トランスファーブルローカルポリシを用いた車両ルーティング問題に対する一般化可能なニューラルソルバーの実現に向けて
- Authors: Chengrui Gao, Haopu Shang, Ke Xue, Dong Li, Chao Qian,
- Abstract要約: 車両ルーティング問題(VRP)のための多くのニューラルネットワーク構築手法は、特定のノード分布と限られたスケールを持つ合成問題インスタンスに焦点を当てている。
我々は,局所移動可能な局所的特徴から学習する補助的政策を設計し,それを典型的な建設方針と統合し,アンサンブル政策を形成する。
共同トレーニングでは、集約されたポリシが協調的かつ補完的に実行され、一般化が促進される。
- 参考スコア（独自算出の注目度）: 24.91781032046481
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Machine learning has been adapted to help solve NP-hard combinatorial optimization problems. One prevalent way is learning to construct solutions by deep neural networks, which has been receiving more and more attention due to the high efficiency and less requirement for expert knowledge. However, many neural construction methods for Vehicle Routing Problems~(VRPs) focus on synthetic problem instances with specified node distributions and limited scales, leading to poor performance on real-world problems which usually involve complex and unknown node distributions together with large scales. To make neural VRP solvers more practical, we design an auxiliary policy that learns from the local transferable topological features, named local policy, and integrate it with a typical construction policy (which learns from the global information of VRP instances) to form an ensemble policy. With joint training, the aggregated policies perform cooperatively and complementarily to boost generalization. The experimental results on two well-known benchmarks, TSPLIB and CVRPLIB, of travelling salesman problem and capacitated VRP show that the ensemble policy significantly improves both cross-distribution and cross-scale generalization performance, and even performs well on real-world problems with several thousand nodes.
- Abstract（参考訳）: 機械学習はNPハードな組合せ最適化問題を解決するのに役立っている。
一般的な方法の1つはディープニューラルネットワークによるソリューション構築の学習である。
しかし、車両ルーティング問題(VRP)のための多くのニューラルネットワーク構築手法は、特定のノード分布と限られたスケールを持つ合成問題インスタンスに焦点を合わせており、通常は複雑で未知のノード分布と大規模なノード分布を含む実世界の問題では性能が劣る。
ニューラルVRPソルバをより実用的なものにするために,局所移動可能なトポロジカルな特徴から学習する補助ポリシーを設計し,それを典型的な建設方針(VRPインスタンスのグローバルな情報から学習する)と統合し,アンサンブルポリシーを形成する。
共同トレーニングでは、集約されたポリシが協調的かつ補完的に実行され、一般化が促進される。
TSPLIBとCVRPLIBの2つのよく知られたベンチマークの結果、旅行セールスマン問題と静電容量化VRPは、アンサンブルポリシーがクロスディストリビューションとクロススケールの一般化性能の両方を著しく改善し、数千ノードの現実世界問題でもうまく機能することを示した。
関連論文リスト
- Joint Admission Control and Resource Allocation of Virtual Network Embedding via Hierarchical Deep Reinforcement Learning [69.00997996453842]
本稿では,仮想ネットワークの埋め込みにおいて,入出力制御と資源配分を併用して学習する深層強化学習手法を提案する。
HRL-ACRAは,受入率と長期平均収益の両面で,最先端のベースラインを上回っていることを示す。
論文 参考訳（メタデータ） (2024-06-25T07:42:30Z) - An Efficient Learning-based Solver Comparable to Metaheuristics for the
Capacitated Arc Routing Problem [67.92544792239086]
我々は,高度メタヒューリスティックスとのギャップを著しく狭めるため,NNベースの解法を導入する。
まず,方向対応型注意モデル(DaAM)を提案する。
第2に、教師付き事前学習を伴い、堅牢な初期方針を確立するための教師付き強化学習スキームを設計する。
論文 参考訳（メタデータ） (2024-03-11T02:17:42Z) - Multi-Task Learning for Routing Problem with Cross-Problem Zero-Shot Generalization [18.298695520665348]
車両ルーティング問題(VRP)は多くの現実世界のアプリケーションで見られる。
本研究では,クロスプロブレム一般化という重要な課題に取り組むための最初の試みを行う。
提案モデルでは、ゼロショットの一般化方式で、見当たらない属性の組み合わせでVRPを解くことができる。
論文 参考訳（メタデータ） (2024-02-23T13:25:23Z) - Genetic Algorithms with Neural Cost Predictor for Solving Hierarchical Vehicle Routing Problems [20.684353068460375]
車両の経路決定が高次決定と連動する場合、結果の最適化問題は計算に重大な課題をもたらす。
本稿では,ニューラルコスト予測器を用いた遺伝的アルゴリズム(GANCP)という,ディープラーニングに基づく新しいアプローチを提案する。
特に,提案するニューラルネットワークは,静電容量化車両ルーティング問題を解決するHGS-CVRPオープンソースパッケージの目的値について学習する。
論文 参考訳（メタデータ） (2023-10-22T02:46:37Z) - Learning Collaborative Policies to Solve NP-hard Routing Problems [13.13675711285772]
本稿では,学習協調政策(LCP)と呼ばれる新しい階層的問題解決戦略を提案する。
2つの反復DRLポリシー(シードとリバイザ)を使って、ほぼ最適解を効果的に見つけることができる。
広汎な実験により,提案した2都市連携方式は,NP-ハードルーティング問題に対する単都市DRLフレームワークよりも改善されることが示された。
論文 参考訳（メタデータ） (2021-10-26T19:46:21Z) - Path Regularization: A Convexity and Sparsity Inducing Regularization
for Parallel ReLU Networks [75.33431791218302]
本稿では,ディープニューラルネットワークのトレーニング問題について検討し,最適化環境に隠された凸性を明らかにするための解析的アプローチを提案する。
我々は、標準のディープ・ネットワークとResNetを特別なケースとして含む、ディープ・パラレルなReLUネットワークアーキテクチャについて検討する。
論文 参考訳（メタデータ） (2021-10-18T18:00:36Z) - Dimension-Free Rates for Natural Policy Gradient in Multi-Agent
Reinforcement Learning [22.310861786709538]
協調型マルチエージェント強化学習のためのスケーラブルなアルゴリズムを提案する。
このアルゴリズムは,次元自由な統計量と計算量とで,グローバルな最適ポリシーに収束することを示す。
論文 参考訳（メタデータ） (2021-09-23T23:38:15Z) - Deep Policy Dynamic Programming for Vehicle Routing Problems [89.96386273895985]
本稿では,学習ニューラルの強みと動的プログラミングアルゴリズムの強みを組み合わせた深層ポリシー動的プログラミング(d pdp)を提案する。
D PDPは、例の解からエッジを予測するために訓練されたディープニューラルネットワークから派生したポリシーを使用して、DP状態空間を優先し、制限する。
本研究では,旅行セールスマン問題 (TSP) と車両ルーティング問題 (VRP) の枠組みを評価し,ニューラルネットワークが(制限された)DPアルゴリズムの性能を向上させることを示す。
論文 参考訳（メタデータ） (2021-02-23T15:33:57Z) - Local Propagation in Constraint-based Neural Network [77.37829055999238]
ニューラルネットワークアーキテクチャの制約に基づく表現について検討する。
本稿では,いわゆるアーキテクチャ制約を満たすのに適した簡単な最適化手法について検討する。
論文 参考訳（メタデータ） (2020-02-18T16:47:38Z) - Reinforcement Learning Based Vehicle-cell Association Algorithm for
Highly Mobile Millimeter Wave Communication [53.47785498477648]
本稿では,ミリ波通信網における車とセルの関連性について検討する。
まず、ユーザ状態(VU)問題を離散的な非車両関連最適化問題として定式化する。
提案手法は,複数のベースライン設計と比較して,ユーザの複雑性とVUEの20%削減の合計で最大15%のゲインが得られる。
論文 参考訳（メタデータ） (2020-01-22T08:51:05Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。