論文の概要: Accelerating Vehicle Routing via AI-Initialized Genetic Algorithms
- arxiv url: http://arxiv.org/abs/2504.06126v2
- Date: Sat, 20 Sep 2025 17:28:21 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-09-23 14:36:44.965191
- Title: Accelerating Vehicle Routing via AI-Initialized Genetic Algorithms
- Title（参考訳）: AI初期化遺伝的アルゴリズムによる車両ルーティングの高速化
- Authors: Ido Greenberg, Piotr Sielski, Hugo Linsenmaier, Rajesh Gandham, Shie Mannor, Alex Fender, Gal Chechik, Eli Meirom,
- Abstract要約: 車両ルーティング問題 (VRP) は進化的最適化における基本的なNPハード問題である。
本稿では、強化学習エージェントを事前のインスタンスで訓練し、初期解を迅速に生成する最適化フレームワークを提案する。
このフレームワークは、様々な時間予算において、現在の最先端のソルバよりも一貫して優れています。
- 参考スコア（独自算出の注目度）: 53.75036695728983
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Vehicle Routing Problems (VRP) are an extension of the Traveling Salesperson Problem and are a fundamental NP-hard challenge in combinatorial optimization. Solving VRP in real-time at large scale has become critical in numerous applications, from growing markets like last-mile delivery to emerging use-cases like interactive logistics planning. In many applications, one has to repeatedly solve VRP instances drawn from the same distribution, yet current state-of-the-art solvers treat each instance on its own without leveraging previous examples. We introduce an optimization framework where a reinforcement learning agent is trained on prior instances and quickly generates initial solutions, which are then further optimized by a genetic algorithm. This framework, Evolutionary Algorithm with Reinforcement Learning Initialization (EARLI), consistently outperforms current state-of-the-art solvers across various time budgets. For example, EARLI handles vehicle routing with 500 locations within one second, 10x faster than current solvers for the same solution quality, enabling real-time and interactive routing at scale. EARLI can generalize to new data, as we demonstrate on real e-commerce delivery data of a previously unseen city. By combining reinforcement learning and genetic algorithms, our hybrid framework takes a step forward to closer interdisciplinary collaboration between AI and optimization communities towards real-time optimization in diverse domains.
- Abstract（参考訳）: 車両ルーティング問題(VRP)は、トラベリングセールスパーソン問題の延長であり、組合せ最適化における基本的なNPハードチャレンジである。
VRPを大規模にリアルタイムに解決することは、ラストマイル配送のような成長市場から、インタラクティブなロジスティクス計画のような新たなユースケースに至るまで、多くのアプリケーションで重要になっている。
多くのアプリケーションでは、同じディストリビューションから引き出されたVRPインスタンスを何度も解決しなければならないが、現在の最先端の解決者は、以前の例を活用せずに、それぞれのインスタンスを単独で扱う必要がある。
本稿では、強化学習エージェントを事前のインスタンスで訓練し、初期解を迅速に生成し、遺伝的アルゴリズムによりさらに最適化する最適化フレームワークを提案する。
このフレームワークであるEvolutionary Algorithm with Reinforcement Learning Initialization (EARLI)は、様々な時間予算で現在の最先端の解法よりも一貫して優れています。
例えば、EARLIは1秒以内に500カ所の車両ルーティングを処理し、同じソリューション品質の現在の解決器よりも10倍高速で、大規模にリアルタイムかつインタラクティブなルーティングを可能にする。
EARLIは、これまで目に見えなかった都市の実際のEコマース配信データで示すように、新しいデータに一般化することができる。
強化学習と遺伝的アルゴリズムを組み合わせることで、私たちのハイブリッドフレームワークは、AIと最適化コミュニティ間の学際的なコラボレーションを、さまざまな領域でリアルタイムに最適化するための一歩前進します。
関連論文リスト
- Learning for routing: A guided review of recent developments and future directions [3.3629991374416477]
旅行セールスマン問題(TSP)や車両ルーティング問題(VRP)などのルーティング問題に焦点をあてる。
これらの問題の本質的な複雑さのため、正確なアルゴリズムは最適解を見つけるのに過剰な計算時間を必要とすることが多い。
本稿では,MLに基づく分類体系を構築ベースおよび改良ベースアプローチに適用し,様々な問題特性に適用可能であることを明らかにする。
論文 参考訳（メタデータ） (2025-06-30T19:39:11Z) - Dynamic Location Search for Identifying Maximum Weighted Independent Sets in Complex Networks [0.47248250311484113]
本稿では,最大重み付き独立集合(MWIS)問題を解くための,新しい,効率的なアルゴリズムを提案する。
MWIS問題のNPハード性を考えると,提案アルゴリズムであるDynLSには3つの重要なイノベーションが組み込まれている。
我々の実験結果はDynLSの優れた性能を示し、1000秒以内の高品質なソリューションを一貫して提供した。
論文 参考訳（メタデータ） (2025-05-07T10:35:53Z) - Multi-Agent Environments for Vehicle Routing Problems [1.0179489519625304]
本稿では,従来の車両ルーティング問題をシミュレートするマルチエージェント環境からなるライブラリを提案する。
PyTorch上に構築されたこのライブラリは、新しいルーティング問題のカスタマイズと導入を容易にする、柔軟なモジュラーアーキテクチャ設計を提供する。
論文 参考訳（メタデータ） (2024-11-21T18:46:23Z) - Learn to Solve Vehicle Routing Problems ASAP: A Neural Optimization Approach for Time-Constrained Vehicle Routing Problems with Finite Vehicle Fleet [0.0]
車両の車両サイズが有限である時間制約付静電容量VRPを解くためのNCO手法を提案する。
この手法は、柔軟性と堅牢な一般化の両方を示す、適切で費用効率のよい解を見つけることができる。
論文 参考訳（メタデータ） (2024-11-07T15:16:36Z) - 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) - Machine Learning Insides OptVerse AI Solver: Design Principles and
Applications [74.67495900436728]
本稿では,Huawei CloudのOpsVerse AIソルバに機械学習(ML)技術を統合するための総合的研究について述べる。
本稿では,実世界の多面構造を反映した生成モデルを用いて,複雑なSATインスタンスとMILPインスタンスを生成する手法を紹介する。
本稿では,解解器性能を著しく向上させる,最先端パラメータチューニングアルゴリズムの導入について詳述する。
論文 参考訳（メタデータ） (2024-01-11T15:02:15Z) - TOP-Former: A Multi-Agent Transformer Approach for the Team Orienteering Problem [47.40841984849682]
車両群のためのルートプランニングは、荷物の配送、監視、輸送といった応用において重要な課題である。
ToP-Formerは、チームのオリエンテーリング問題を効率的に正確に解くために設計されたマルチエージェント経路計画ニューラルネットワークである。
論文 参考訳（メタデータ） (2023-11-30T16:10:35Z) - Combinatorial Optimization enriched Machine Learning to solve the
Dynamic Vehicle Routing Problem with Time Windows [5.4807970361321585]
最適化層を組み込んだ新しい機械学習パイプラインを提案する。
最近,EURO Meets NeurIPS Competition at NeurIPS 2022において,このパイプラインを波による動的車両ルーティング問題に適用した。
提案手法は,提案した動的車両経路問題の解法において,他の全ての手法よりも優れていた。
論文 参考訳（メタデータ） (2023-04-03T08:23:09Z) - Ranking Cost: Building An Efficient and Scalable Circuit Routing Planner
with Evolution-Based Optimization [49.207538634692916]
そこで我々は、効率よくトレーニング可能なルータを形成するための新しい回路ルーティングアルゴリズム、Randing Costを提案する。
提案手法では,A*ルータが適切な経路を見つけるのに役立つコストマップと呼ばれる新しい変数群を導入する。
我々のアルゴリズムはエンドツーエンドで訓練されており、人工データや人間の実演は一切使用しない。
論文 参考訳（メタデータ） (2021-10-08T07:22:45Z) - Boosted Genetic Algorithm using Machine Learning for traffic control
optimization [4.642759477873937]
本稿では,信号化都市交差点における交通信号タイミングの最適化手法を提案する。
高速かつ信頼性の高い決定を生成することを目的として、高速実行機械学習(ML)アルゴリズムと信頼できる遺伝的アルゴリズム(GA)を組み合わせる。
新たなBGA-MLは,元のGAアルゴリズムよりもはるかに高速であり,非リカレントインシデント条件下でうまく適用可能であることを示す。
論文 参考訳（メタデータ） (2021-03-11T00:39:18Z) - Deep Policy Dynamic Programming for Vehicle Routing Problems [89.96386273895985]
本稿では,学習ニューラルの強みと動的プログラミングアルゴリズムの強みを組み合わせた深層ポリシー動的プログラミング(d pdp)を提案する。
D PDPは、例の解からエッジを予測するために訓練されたディープニューラルネットワークから派生したポリシーを使用して、DP状態空間を優先し、制限する。
本研究では,旅行セールスマン問題 (TSP) と車両ルーティング問題 (VRP) の枠組みを評価し,ニューラルネットワークが(制限された)DPアルゴリズムの性能を向上させることを示す。
論文 参考訳（メタデータ） (2021-02-23T15:33:57Z) - Reinforcement Learning Based Vehicle-cell Association Algorithm for
Highly Mobile Millimeter Wave Communication [53.47785498477648]
本稿では,ミリ波通信網における車とセルの関連性について検討する。
まず、ユーザ状態(VU)問題を離散的な非車両関連最適化問題として定式化する。
提案手法は,複数のベースライン設計と比較して,ユーザの複雑性とVUEの20%削減の合計で最大15%のゲインが得られる。
論文 参考訳（メタデータ） (2020-01-22T08:51:05Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。