論文の概要: Accelerating Vehicle Routing via AI-Initialized Genetic Algorithms

• arxiv url: http://arxiv.org/abs/2504.06126v1
• Date: Tue, 08 Apr 2025 15:21:01 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-09 13:31:48.493761
• 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ハードチャレンジである。 遺伝的アルゴリズムによってさらに最適化された初期解を迅速に生成するために、強化学習エージェント(事前インスタンスで訓練された)を使用した新しい最適化フレームワークを導入する。 例えば、EARLIは1秒以内に500カ所の車両ルーティングを処理し、同じソリューション品質の現在のソルバよりも10倍高速で、リアルタイムやインタラクティブなルーティングのようなアプリケーションを可能にする。
• 参考スコア（独自算出の注目度）: 55.78505925402658
• License:
• 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. Such applications involve solving similar problem instances repeatedly, yet current state-of-the-art solvers treat each instance on its own without leveraging previous examples. We introduce a novel optimization framework that uses a reinforcement learning agent - trained on prior instances - to quickly generate initial solutions, which are then further optimized by genetic algorithms. Our framework, Evolutionary Algorithm with Reinforcement Learning Initialization (EARLI), consistently outperforms current state-of-the-art solvers across various time scales. For example, EARLI handles vehicle routing with 500 locations within 1s, 10x faster than current solvers for the same solution quality, enabling applications like real-time and interactive routing. EARLI can generalize to new data, as demonstrated on real e-commerce delivery data of a previously unseen city. Our hybrid framework presents a new way to combine reinforcement learning and genetic algorithms, paving the road for closer interdisciplinary collaboration between AI and optimization communities towards real-time optimization in diverse domains.
• Abstract（参考訳）: 車両ルーティング問題(VRP)は、トラベリングセールスパーソン問題の延長であり、組合せ最適化における基本的なNPハードチャレンジである。 VRPを大規模にリアルタイムに解決することは、ラストマイル配送のような成長市場から、インタラクティブなロジスティクス計画のような新たなユースケースに至るまで、多くのアプリケーションで重要になっている。 このようなアプリケーションは、同様の問題を何度も解決するが、現在の最先端の解決者は、以前の例を活用せずに、それぞれのインスタンスを単独で扱う。 遺伝的アルゴリズムによってさらに最適化された初期解を迅速に生成するために、強化学習エージェント(事前インスタンスで訓練された)を使用した新しい最適化フレームワークを導入する。 我々のフレームワークであるEvolutionary Algorithm with Reinforcement Learning Initialization (EARLI) は、様々な時間スケールにおける現在の最先端の解法よりも一貫して優れています。 例えば、EARLIは1秒以内に500カ所の車両ルーティングを処理し、同じソリューション品質の現在のソルバよりも10倍高速で、リアルタイムやインタラクティブなルーティングのようなアプリケーションを可能にする。 EARLIは、これまで見えなかった都市の実際のEコマース配信データに示されているように、新しいデータに一般化することができる。 我々のハイブリッドフレームワークは、強化学習と遺伝的アルゴリズムを組み合わせる新しい方法を提供する。

関連論文リスト

• 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)
• 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)
• Reconfigurable Intelligent Surface Assisted Mobile Edge Computing with Heterogeneous Learning Tasks [53.1636151439562]
  モバイルエッジコンピューティング(MEC)は、AIアプリケーションに自然なプラットフォームを提供します。 再構成可能なインテリジェントサーフェス(RIS)の助けを借りて、MECで機械学習タスクを実行するインフラストラクチャを提示します。 具体的には,モバイルユーザの送信パワー,基地局のビームフォーミングベクトル,risの位相シフト行列を共同で最適化することにより,参加ユーザの学習誤差を最小化する。
  論文  参考訳（メタデータ） (2020-12-25T07:08:50Z)
• Reinforcement Learning Based Vehicle-cell Association Algorithm for Highly Mobile Millimeter Wave Communication [53.47785498477648]
  本稿では,ミリ波通信網における車とセルの関連性について検討する。 まず、ユーザ状態(VU)問題を離散的な非車両関連最適化問題として定式化する。 提案手法は,複数のベースライン設計と比較して,ユーザの複雑性とVUEの20%削減の合計で最大15%のゲインが得られる。
  論文  参考訳（メタデータ） (2020-01-22T08:51:05Z)

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

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