論文の概要: Speeding up Local Optimization in Vehicle Routing with Tensor-based GPU Acceleration
- arxiv url: http://arxiv.org/abs/2506.17357v1
- Date: Fri, 20 Jun 2025 07:40:47 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-06-24 19:06:36.3788
- Title: Speeding up Local Optimization in Vehicle Routing with Tensor-based GPU Acceleration
- Title（参考訳）: テンソル型GPUアクセラレーションによる車両ルーティングにおける局所最適化の高速化
- Authors: Zhenyu Lei, Jin-Kao Hao, Qinghua Wu,
- Abstract要約: 本稿では,車両ルーティングにおいてよく使用される局所探索演算子を高速化する,テンソルベースのGPUアクセラレーション手法を提案する。
その低結合アーキテクチャは、GPUに完全にオフロードされた計算を伴うため、さまざまなローカル検索ベースのアルゴリズムとフレームワークにシームレスに統合される。
- 参考スコア（独自算出の注目度）: 23.87172157992149
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: Local search plays a central role in many effective heuristic algorithms for the vehicle routing problem (VRP) and its variants. However, neighborhood exploration is known to be computationally expensive and time consuming, especially for large instances or problems with complex constraints. In this study, we explore a promising direction to address this challenge by introducing an original tensor-based GPU acceleration method designed to speed up the commonly used local search operators in vehicle routing. By using an attribute-based representation, the method offers broad extensibility, making it applicable to different VRP variants. Its low-coupling architecture, with intensive computations completely offloaded to the GPU, ensures seamless integration in various local search-based algorithms and frameworks, leading to significant improvements in computational efficiency and potentially improved solution quality. Through comparative experiments on benchmark instances of three routing problems, we demonstrate the substantial computational advantages of the proposed approach over traditional CPU-based implementations. We also provide a detailed analysis of the strengths and limitations of the method, providing valuable insights into its performance characteristics and identifying potential bottlenecks in practical applications. These findings contribute to a better understanding and suggest directions for future improvements.
- Abstract（参考訳）: 局所探索は、車両ルーティング問題(VRP)とその変種に対する多くの効果的なヒューリスティックアルゴリズムにおいて中心的な役割を果たす。
しかし、特に大規模インスタンスや複雑な制約のある問題に対して、近隣探索は計算に高価で時間を要することが知られている。
本研究では,車両ルーティングにおいてよく使用される局所探索演算子の高速化を目的とした,テンソルベースのGPUアクセラレーション手法を導入することにより,この問題に対処するための有望な方向を探究する。
属性ベースの表現を使用することで、この手法は幅広い拡張性を提供し、異なるVRP変種に適用できる。
その低結合アーキテクチャは、GPUに完全にオフロードされた計算を伴うため、さまざまなローカル検索ベースのアルゴリズムとフレームワークのシームレスな統合が保証され、計算効率が大幅に向上し、ソリューションの品質が向上する可能性がある。
3つのルーティング問題に対するベンチマークインスタンスの比較実験を通じて、提案手法の従来のCPUベース実装に対する実質的な計算上の優位性を実証する。
また,本手法の強みと限界を詳細に分析し,その性能特性について貴重な知見を提供し,実用アプリケーションにおける潜在的なボトルネックを特定する。
これらの知見はさらなる理解と今後の改善の方向性に寄与する。
関連論文リスト
- Learning to Search for Vehicle Routing with Multiple Time Windows [13.91760960564074]
強化学習に基づく適応型可変近傍探索(RL-AVNS)を提案する。
提案手法は,実時間解状態と学習経験に基づいて局所演算子を動的に選択するための強化学習フレームワークを統合する。
論文 参考訳（メタデータ） (2025-05-29T05:03:28Z) - Learning with Local Search MCMC Layers [11.772298193297013]
不正確な解法による学習に理論的に根ざしたアプローチを導入する。
局所探索で使用される問題固有近傍系を提案分布に変換する。
時間窓を用いた大規模動的車両ルーティング問題に対する我々のアプローチを実証する。
論文 参考訳（メタデータ） (2025-05-20T11:47:42Z) - 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) - Ride-pool Assignment Algorithms: Modern Implementation and Swapping Heuristics [3.5112462023222504]
本稿では,車間ルーティングやリバランシングなどの関連コンポーネントとともに,いくつかの重要な配車プール割り当てアルゴリズムを含む配車プールシミュレータを提案する。
また,新しいアルゴリズムの拡張を容易にするために設計された,高度に最適化されたモジュール化されたC++もオープンソースとして公開しています。
マンハッタンの大規模な実世界のデータセットの実験では、選択された全てのアルゴリズムが互換性を持って実行されているが、新たに提案されたMulti-Round Linear Assignment with Cyclic Exchangeは、計算時間を大幅に短縮した最先端のサービスレートを達成する。
論文 参考訳（メタデータ） (2025-04-14T19:01:47Z) - Accelerating Vehicle Routing via AI-Initialized Genetic Algorithms [55.78505925402658]
車両ルーティング問題(VRP)は、トラベリングセールスパーソン問題の延長であり、進化的最適化における基本的なNPハードチャレンジである。
遺伝的アルゴリズムによってさらに最適化された初期解を迅速に生成するために、強化学習エージェント(事前インスタンスで訓練された)を使用した新しい最適化フレームワークを導入する。
例えば、EARLIは1秒以内に500カ所の車両ルーティングを処理し、同じソリューション品質の現在のソルバよりも10倍高速で、リアルタイムやインタラクティブなルーティングのようなアプリケーションを可能にする。
論文 参考訳（メタデータ） (2025-04-08T15:21:01Z) - Enhancing Dropout-based Bayesian Neural Networks with Multi-Exit on FPGA [20.629635991749808]
本稿では,フィールドプログラマブルゲートアレイ(FPGA)ベースのアクセラレータを効率よく生成するアルゴリズムとハードウェアの共同設計フレームワークを提案する。
アルゴリズムレベルでは、計算とメモリのオーバーヘッドを低減した、新しいマルチエグジット・ドロップアウトベースのベイズNNを提案する。
ハードウェアレベルでは,提案する効率的なベイズNNのためのFPGAベースのアクセラレータを生成するための変換フレームワークを提案する。
論文 参考訳（メタデータ） (2024-06-20T17:08:42Z) - 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) - Correlating sparse sensing for large-scale traffic speed estimation: A
Laplacian-enhanced low-rank tensor kriging approach [76.45949280328838]
本稿では,Laplacian enhanced Low-rank tensor (LETC) フレームワークを提案する。
次に,提案したモデルをネットワークワイド・クリグにスケールアップするために,複数の有効な数値手法を用いて効率的な解アルゴリズムを設計する。
論文 参考訳（メタデータ） (2022-10-21T07:25:57Z) - Scalable Vehicle Re-Identification via Self-Supervision [66.2562538902156]
自動車再同定は、都市規模の車両分析システムにおいて重要な要素の1つである。
車両再設計のための最先端のソリューションの多くは、既存のre-idベンチマークの精度向上に重点を置いており、計算の複雑さを無視することが多い。
推論時間に1つのネットワークのみを使用する自己教師型学習によって、シンプルで効果的なハイブリッドソリューションを提案する。
論文 参考訳（メタデータ） (2022-05-16T12:14:42Z) - Reinforcement Learning for Datacenter Congestion Control [50.225885814524304]
渋滞制御アルゴリズムの成功は、レイテンシとネットワーク全体のスループットを劇的に改善する。
今日まで、このような学習ベースのアルゴリズムはこの領域で実用的な可能性を示さなかった。
実世界のデータセンターネットワークの様々な構成に一般化することを目的としたRLに基づくアルゴリズムを考案する。
本稿では,この手法が他のRL手法よりも優れており,トレーニング中に見られなかったシナリオに一般化可能であることを示す。
論文 参考訳（メタデータ） (2021-02-18T13:49:28Z) - Reinforcement Learning Based Vehicle-cell Association Algorithm for
Highly Mobile Millimeter Wave Communication [53.47785498477648]
本稿では,ミリ波通信網における車とセルの関連性について検討する。
まず、ユーザ状態(VU)問題を離散的な非車両関連最適化問題として定式化する。
提案手法は,複数のベースライン設計と比較して,ユーザの複雑性とVUEの20%削減の合計で最大15%のゲインが得られる。
論文 参考訳（メタデータ） (2020-01-22T08:51:05Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。