論文の概要: Graph-Coarsening Approach for the Capacitated Vehicle Routing Problem with Time Windows

• arxiv url: http://arxiv.org/abs/2510.22329v1
• Date: Sat, 25 Oct 2025 15:13:41 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-28 17:41:21.951332
• Title: Graph-Coarsening Approach for the Capacitated Vehicle Routing Problem with Time Windows
• Title（参考訳）: 時間窓付きキャパシタン化車両ルーティング問題に対するグラフ階層化手法
• Authors: Mustafa Mert Özyılmaz,
• Abstract要約: 本稿では,顧客をメタノードに集約するマルチレベルグラフ粗化・改善フレームワークを提案する。 提案手法は,特にキャパシティや時間窓の制約に関して,解の質を保ったり改善したりしながら,計算量を削減する。 また、量子インスパイアされた最適化手法の統合についても検討し、大規模な車両ルーティングタスクをさらに加速させる可能性を強調した。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) is a fundamental NP-hard optimization problem in logistics. Solving large-scale instances remains computationally challenging for exact solvers. This work introduces a multilevel graph coarsening and refinement framework that aggregates customers into meta-nodes using a spatio-temporal distance metric. The reduced problem is solved with classical heuristics and subsequently expanded back into the original space with feasibility corrections. Preliminary experiments on Solomon benchmark instances show that the proposed method reduces computation time while preserving or improving solution quality, particularly with respect to capacity and time window constraints. The paper also explores the integration of quantum-inspired optimization techniques, highlighting their potential to further accelerate large-scale vehicle routing tasks.
• Abstract（参考訳）: Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) は、ロジスティクスにおける基本的なNPハード最適化問題である。 大規模インスタンスの解法は、正確な解法において計算的に難しいままである。 この研究は、顧客を時空間距離メートル法を用いてメタノードに集約するマルチレベルグラフ粗大化および改善フレームワークを導入している。 還元された問題は古典的ヒューリスティックスによって解決され、その後、実現可能性補正によって元の空間に拡張される。 Solomonベンチマークインスタンスの予備実験により、提案手法は、特に容量や時間窓の制約に関して、ソリューションの品質を維持したり改善したりしながら、計算時間を短縮することを示した。 また、量子インスパイアされた最適化手法の統合についても検討し、大規模な車両ルーティングタスクをさらに加速させる可能性を強調した。

関連論文リスト

• Accelerating Vehicle Routing via AI-Initialized Genetic Algorithms [53.75036695728983]
  車両ルーティング問題 (VRP) は進化的最適化における基本的なNPハード問題である。 本稿では、強化学習エージェントを事前のインスタンスで訓練し、初期解を迅速に生成する最適化フレームワークを提案する。 このフレームワークは、様々な時間予算において、現在の最先端のソルバよりも一貫して優れています。
  論文  参考訳（メタデータ） (2025-04-08T15:21:01Z)
• A Greedy Quantum Route-Generation Algorithm [0.0]
  本稿では,量子コンピュータから得られた全てのサンプルからの情報を用いて,経路を生成するグリーディアルゴリズムを提案する。 有向非巡回グラフ (DAG) としての定式化における量子ビットの関係に気付き, 実現可能な解を適応的に構築するアルゴリズムを設計した。
  論文  参考訳（メタデータ） (2024-05-05T21:20:46Z)
• Roulette-Wheel Selection-Based PSO Algorithm for Solving the Vehicle Routing Problem with Time Windows [58.891409372784516]
  本稿では,Roulette Wheel Method (RWPSO) を用いた新しいPSO手法を提案する。 RWPSOのSolomon VRPTWベンチマークデータセットを用いた実験は、RWPSOが文学の他の最先端アルゴリズムと競合していることを示している。
  論文  参考訳（メタデータ） (2023-06-04T09:18:02Z)
• Rolling Horizon based Temporal Decomposition for the Offline Pickup and Delivery Problem with Time Windows [5.818566833386833]
  オフラインPDPTWのクラスを解くための新しい時間分解方式を提案する。 私たちのフレームワークはよりスケーラブルで、さまざまな難易度の問題インスタンスに対して優れたソリューションを提供することができます。
  論文  参考訳（メタデータ） (2023-03-06T20:07:05Z)
• Learning to Solve Combinatorial Graph Partitioning Problems via Efficient Exploration [72.15369769265398]
  実験により、ECORDは最大カット問題に対するRLアルゴリズムのための新しいSOTAを実現する。 最も近い競合と比較して、ECORDは最適性ギャップを最大73%削減する。
  論文  参考訳（メタデータ） (2022-05-27T17:13:10Z)
• Learning from Images: Proactive Caching with Parallel Convolutional Neural Networks [94.85780721466816]
  本稿では,プロアクティブキャッシングのための新しいフレームワークを提案する。 モデルベースの最適化とデータ駆動技術を組み合わせて、最適化問題をグレースケールのイメージに変換する。 数値計算の結果,提案手法は71.6%の計算時間を0.8%のコストで削減できることがわかった。
  論文  参考訳（メタデータ） (2021-08-15T21:32:47Z)
• Neural Fixed-Point Acceleration for Convex Optimization [10.06435200305151]
  本稿では,メタラーニング法と古典的加速度法を併用したニューラル固定点加速法を提案する。 コンベックスコーンプログラミングのための最先端の解法であるSCSに,我々のフレームワークを適用した。
  論文  参考訳（メタデータ） (2021-07-21T17:59:34Z)
• MineReduce: an approach based on data mining for problem size reduction [58.720142291102135]
  本稿では,マイニングパターンを用いて問題サイズの削減を行うMineReduceという手法を提案する。 異種車両ルーティング問題に対するMineReduceの適用について述べる。
  論文  参考訳（メタデータ） (2020-05-15T08:49:50Z)

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

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