論文の概要: Neural Combinatorial Optimization Algorithms for Solving Vehicle Routing Problems: A Comprehensive Survey with Perspectives
- arxiv url: http://arxiv.org/abs/2406.00415v2
- Date: Tue, 15 Oct 2024 08:42:13 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-10-16 13:58:22.715085
- Title: Neural Combinatorial Optimization Algorithms for Solving Vehicle Routing Problems: A Comprehensive Survey with Perspectives
- Title（参考訳）: 車両経路問題の解法のためのニューラルコンビナート最適化アルゴリズム:視点を用いた総合的なサーベイ
- Authors: Xuan Wu, Di Wang, Lijie Wen, Yubin Xiao, Chunguo Wu, Yuesong Wu, Chaoyu Yu, Douglas L. Maskell, You Zhou,
- Abstract要約: この調査は、VRPのためのNCOソルバの包括的分類を提供することを目的としている。
我々は,すべてのNCOソルバを,構成の学習,改善の学習,予測の学習,予測の多元性解決の学習の4つのカテゴリに分けた。
我々は,SOTAソルバの欠点として,一般化の低さ,大規模VRPの解決能力の低下,NCOソルバと従来のOperations Researchアルゴリズムとの比較が困難である点を挙げる。
- 参考スコア（独自算出の注目度）: 14.47130974868925
- License:
- Abstract: Although several surveys on Neural Combinatorial Optimization (NCO) solvers specifically designed to solve Vehicle Routing Problems (VRPs) have been conducted. These existing surveys did not cover the state-of-the-art (SOTA) NCO solvers emerged recently. More importantly, to provide a comprehensive taxonomy of NCO solvers with up-to-date coverage, based on our thorough review of relevant publications and preprints, we divide all NCO solvers into four distinct categories, namely Learning to Construct, Learning to Improve, Learning to Predict-Once, and Learning to Predict-Multiplicity solvers. Subsequently, we present the inadequacies of the SOTA solvers, including poor generalization, incapability to solve large-scale VRPs, inability to address most types of VRP variants simultaneously, and difficulty in comparing these NCO solvers with the conventional Operations Research algorithms. Simultaneously, we propose promising and viable directions to overcome these inadequacies. In addition, we compare the performance of representative NCO solvers from the Reinforcement, Supervised, and Unsupervised Learning paradigms across both small- and large-scale VRPs. Finally, following the proposed taxonomy, we provide an accompanying web page as a live repository for NCO solvers. Through this survey and the live repository, we hope to make the research community of NCO solvers for VRPs more thriving.
- Abstract（参考訳）: 車両ルーティング問題(VRP)を解決するために特別に設計されたニューラルコンビネーション最適化(NCO)ソルバについて、いくつかの調査がなされている。
これらの既存の調査は、最近現れたSOTA(State-of-the-art) NCOソルバをカバーしていない。
より重要なことは、NCOソルバの包括的分類を最新の範囲で提供するために、関連する出版物やプレプリントの徹底的なレビューに基づいて、NCOソルバを4つの異なるカテゴリ、すなわち、学習から構築へ、学習から改善へ、学習から予測へ、学習から予測へ、そして予測から多元性へ、に分けたことである。
続いて、SOTAソルバの欠点として、一般化の不足、大規模VRPの解決能力の低下、ほとんどのVRP変種に同時に対処できないこと、NCOソルバを従来のオペレーツ・リサーチ・アルゴリズムと比較することの難しさを挙げる。
同時に、これらの不適切な状況を克服するための有望かつ実行可能な方向性を提案する。
さらに,小型VRPと大規模VRPの両分野において,強化,監視,教師なし学習の代表的なNCOソルバの性能を比較した。
最後に,提案した分類法に従って,NCOソルバのライブレポジトリとして付随するWebページを提供する。
この調査とライブレポジトリを通じて、VRPのためのNCOソルバの研究コミュニティをより繁栄させたいと思っています。
関連論文リスト
- Learning to Solve Combinatorial Optimization under Positive Linear Constraints via Non-Autoregressive Neural Networks [103.78912399195005]
組合せ最適化(英: Combinatorial Optimization、CO)は、計算機科学、応用数学などにおける基本的な問題である。
本稿では, 正線形制約下でのCO問題の解法として, 非自己回帰ニューラルネットワーク群を設計する。
本研究では,施設位置,最大被覆率,旅行セールスマン問題を含む代表的CO問題の解決において,この枠組みの有効性を検証する。
論文 参考訳（メタデータ） (2024-09-06T14:58:31Z) - UDC: A Unified Neural Divide-and-Conquer Framework for Large-Scale Combinatorial Optimization Problems [8.871356150316224]
2段階のニューラル手法は、大規模なCO問題に対処する際の効率性を示している。
本稿では,一般の大規模CO問題の解法として,統一型ニューラルディバイド・アンド・コンカー・フレームワーク(UDC)を開発する。
論文 参考訳（メタデータ） (2024-06-29T04:29:03Z) - Decision-focused Graph Neural Networks for Combinatorial Optimization [62.34623670845006]
最適化問題に取り組むための新たな戦略は、従来のアルゴリズムに代わるグラフニューラルネットワーク(GNN)の採用である。
GNNや従来のアルゴリズムソルバがCOの領域で人気が高まっているにもかかわらず、それらの統合利用とエンドツーエンドフレームワークにおけるそれらの相関について限定的な研究がなされている。
我々は、GNNを利用してCO問題に補助的なサポートで対処する決定に焦点を当てたフレームワークを導入する。
論文 参考訳（メタデータ） (2024-06-05T22:52:27Z) - Instance-Conditioned Adaptation for Large-scale Generalization of Neural Combinatorial Optimization [15.842155380912002]
本研究は,ニューラル最適化の大規模一般化のための新しいインスタンス・コンディション適応モデル(ICAM)を提案する。
特に,NCOモデルのための強力なインスタンス条件付きルーティング適応モジュールを設計する。
我々は,ラベル付き最適解を使わずに,モデルがクロススケールな特徴を学習することのできる,効率的な3段階強化学習ベーストレーニング手法を開発した。
論文 参考訳（メタデータ） (2024-05-03T08:00:19Z) - An Efficient Learning-based Solver Comparable to Metaheuristics for the
Capacitated Arc Routing Problem [67.92544792239086]
我々は,高度メタヒューリスティックスとのギャップを著しく狭めるため,NNベースの解法を導入する。
まず,方向対応型注意モデル(DaAM)を提案する。
第2に、教師付き事前学習を伴い、堅牢な初期方針を確立するための教師付き強化学習スキームを設計する。
論文 参考訳（メタデータ） (2024-03-11T02:17:42Z) - Improved Algorithms for Neural Active Learning [74.89097665112621]
非パラメトリックストリーミング設定のためのニューラルネットワーク(NN)ベースの能動学習アルゴリズムの理論的および経験的性能を改善する。
本研究では,SOTA(State-of-the-art (State-the-art)) 関連研究で使用されるものよりも,アクティブラーニングに適する人口減少を最小化することにより,2つの後悔の指標を導入する。
論文 参考訳（メタデータ） (2022-10-02T05:03:38Z) - How Good Is Neural Combinatorial Optimization? A Systematic Evaluation
on the Traveling Salesman Problem [31.451338706630583]
この研究は、ニューラル最適化ソルバと代替ソルバの総合的な比較研究を示す。
以上の結果から, NCO アプローチで学習した解法は, 従来の解法には及ばないことが明らかとなった。
論文 参考訳（メタデータ） (2022-09-22T10:50:36Z) - Solving the Traveling Salesperson Problem with Precedence Constraints by
Deep Reinforcement Learning [59.14935871979047]
本研究は, 深層強化学習(DRL)を用いた優先制約付きトラベリングセールスパーソン問題(TSPPC)の解を提案する。
これらのアプローチに共通しているのは、マルチヘッドアテンション層に基づくグラフモデルの利用である。
論文 参考訳（メタデータ） (2022-07-04T14:31:47Z) - Sym-NCO: Leveraging Symmetricity for Neural Combinatorial Optimization [16.127824824652077]
深部強化学習(DRL)に基づく最適化(CO)法は,従来のCO解法に比べて有意な効果を示した。
本稿では,既存のDRL-NCO法の性能向上を実現する新しいトレーニング手法であるSym-NCOを提案する。
論文 参考訳（メタデータ） (2022-05-26T07:55:43Z) - On the Difficulty of Generalizing Reinforcement Learning Framework for
Combinatorial Optimization [6.935838847004389]
現実の応用とグラフ上の組合せ最適化問題(COP)は、コンピュータサイエンスにおける標準的な課題である。
このアプローチの基本原理は、ノードのローカル情報とグラフ構造化データの両方を符号化するグラフニューラルネットワーク(GNN)をデプロイすることである。
我々は,クラウド上のセキュリティ対応電話機のクローン割り当てを古典的二次代入問題 (QAP) として,深層RLモデルが他の難題の解法に一般的に適用可能であるか否かを調査する。
論文 参考訳（メタデータ） (2021-08-08T19:12:04Z) - Combinatorial Pure Exploration with Full-bandit Feedback and Beyond:
Solving Combinatorial Optimization under Uncertainty with Limited Observation [70.41056265629815]
最適化アルゴリズムを開発する際、エッジウェイトなどのパラメータが入力として正確に知られていることが一般的である。
本稿では、最近、限られたフィードバックを伴う純粋探索問題に対する手法について概説する。
論文 参考訳（メタデータ） (2020-12-31T12:40:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。