論文の概要: Hybrid Node-Destroyer Model with Large Neighborhood Search for Solving the Capacitated Vehicle Routing Problem

• arxiv url: http://arxiv.org/abs/2508.08659v1
• Date: Tue, 12 Aug 2025 05:56:13 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-13 21:07:34.319026
• Title: Hybrid Node-Destroyer Model with Large Neighborhood Search for Solving the Capacitated Vehicle Routing Problem
• Title（参考訳）: 容量化車両経路問題の解法のための大規模近傍探索によるハイブリッドノードデストロイヤーモデル
• Authors: Bachtiar Herdianto, Romain Billot, Flavien Lucas, Marc Sevaux, Daniele Vigo,
• Abstract要約: 本稿ではメタヒューリスティックアルゴリズムの性能向上を目的とした反復学習ハイブリッド最適化手法を提案する。 提案手法は, 演算複雑性を低減し, 最適化プロセスに関わる探索空間を縮小する。
• 参考スコア（独自算出の注目度）: 1.9573380763700716
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: In this research, we propose an iterative learning hybrid optimization solver developed to strengthen the performance of metaheuristic algorithms in solving the Capacitated Vehicle Routing Problem (CVRP). The iterative hybrid mechanism integrates the proposed Node-Destroyer Model, a machine learning hybrid model that utilized Graph Neural Networks (GNNs) such identifies and selects customer nodes to guide the Large Neighborhood Search (LNS) operator within the metaheuristic optimization frameworks. This model leverages the structural properties of the problem and solution that can be represented as a graph, to guide strategic selections concerning node removal. The proposed approach reduces operational complexity and scales down the search space involved in the optimization process. The hybrid approach is applied specifically to the CVRP and does not require retraining across problem instances of different sizes. The proposed hybrid mechanism is able to improve the performance of baseline metaheuristic algorithms. Our approach not only enhances the solution quality for standard CVRP benchmarks but also proves scalability on very large-scale instances with up to 30,000 customer nodes. Experimental evaluations on benchmark datasets show that the proposed hybrid mechanism is capable of improving different baseline algorithms, achieving better quality of solutions under similar settings.
• Abstract（参考訳）: 本研究では,CVRP(Capacitated Vehicle Routing Problem)の解法におけるメタヒューリスティックアルゴリズムの性能を高めるために,反復学習ハイブリッド最適化法を提案する。 この反復的ハイブリッドメカニズムは、グラフニューラルネットワーク(GNN)を利用した機械学習ハイブリッドモデルであるNode-Destroyerモデルを統合し、メタヒューリスティック最適化フレームワーク内のLarge Neighborhood Search(LNS)オペレータをガイドする顧客ノードを特定し、選択する。 このモデルは、グラフとして表現できる問題と解の構造的特性を利用して、ノード除去に関する戦略的選択を導く。 提案手法は, 演算複雑性を低減し, 最適化プロセスに関わる探索空間を縮小する。 ハイブリッドアプローチは、特にCVRPに適用され、異なるサイズの問題インスタンスをまたいだ再トレーニングを必要としない。 提案したハイブリッド機構は,ベースラインメタヒューリスティックアルゴリズムの性能を向上させることができる。 我々のアプローチは、標準的なCVRPベンチマークのソリューション品質を向上させるだけでなく、最大30,000の顧客ノードを持つ非常に大規模なインスタンスのスケーラビリティも証明します。 ベンチマークデータセットの実験的評価から,提案したハイブリッド機構は,異なるベースラインアルゴリズムを改良し,類似した設定下でのソリューションの品質向上を実現することができることが示された。

関連論文リスト

• Preference Optimization for Combinatorial Optimization Problems [54.87466279363487]
  強化学習(Reinforcement Learning, RL)は、ニューラルネットワーク最適化のための強力なツールとして登場した。 大幅な進歩にもかかわらず、既存のRLアプローチは報酬信号の減少や大規模な行動空間における非効率な探索といった課題に直面している。 統計的比較モデルを用いて定量的報酬信号を定性的選好信号に変換する新しい手法であるPreference Optimizationを提案する。
  論文  参考訳（メタデータ） (2025-05-13T16:47:00Z)
• A RankNet-Inspired Surrogate-Assisted Hybrid Metaheuristic for Expensive Coverage Optimization [5.757318591302855]
  大規模カバレッジ最適化タスクを処理するために,RangeNetによるSurrogate支援ハイブリッドメタヒューリスティックを提案する。 我々のアルゴリズムは、EMVOPの最先端アルゴリズムを一貫して上回っている。
  論文  参考訳（メタデータ） (2025-01-13T14:49:05Z)
• DiffSG: A Generative Solver for Network Optimization with Diffusion Model [75.27274046562806]
  生成拡散モデルは、様々なクロスドメインアプリケーションで人気がある。 これらのモデルは複雑なネットワーク最適化問題に対処する上で有望である。 本稿では拡散モデルに基づく解生成という,拡散モデル生成のための新しいフレームワークを提案する。
  論文  参考訳（メタデータ） (2024-08-13T07:56:21Z)
• Self-Improved Learning for Scalable Neural Combinatorial Optimization [15.842155380912002]
  本研究は、ニューラルネットワーク最適化のスケーラビリティを向上させるための新しい自己改善学習(SIL)手法を提案する。 我々は,ラベル付きデータを使わずに大規模問題インスタンス上での直接モデルトレーニングを可能にする,効率的な自己改善機構を開発した。 さらに,計算モデルに対する線形注意複雑化機構を設計し,オーバヘッドの少ない大規模問題インスタンスを効率的に処理する。
  論文  参考訳（メタデータ） (2024-03-28T16:46:53Z)
• A Deep Unrolling Model with Hybrid Optimization Structure for Hyperspectral Image Deconvolution [50.13564338607482]
  本稿では,DeepMixと呼ばれるハイパースペクトルデコンボリューション問題に対する新しい最適化フレームワークを提案する。 これは3つの異なるモジュール、すなわちデータ一貫性モジュール、手作りの正規化器の効果を強制するモジュール、および装飾モジュールで構成されている。 本研究は,他のモジュールの協調作業によって達成される進歩を維持するために設計された,文脈を考慮した認知型モジュールを提案する。
  論文  参考訳（メタデータ） (2023-06-10T08:25:16Z)
• Backpropagation of Unrolled Solvers with Folded Optimization [55.04219793298687]
  ディープネットワークにおけるコンポーネントとしての制約付き最適化モデルの統合は、多くの専門的な学習タスクに有望な進歩をもたらした。 1つの典型的な戦略はアルゴリズムのアンローリングであり、これは反復解法の操作による自動微分に依存している。 本稿では,非ロール最適化の後方通過に関する理論的知見を提供し,効率よく解けるバックプロパゲーション解析モデルを生成するシステムに繋がる。
  論文  参考訳（メタデータ） (2023-01-28T01:50:42Z)
• Neural Improvement Heuristics for Graph Combinatorial Optimization Problems [49.85111302670361]
  本稿では,ノード,エッジ,あるいはその両方に情報をエンコードするグラフベースの問題を扱う新しいニューラル改善(NI)モデルを提案する。 提案モデルは,各地区の操作の選択を誘導する丘登頂に基づくアルゴリズムの基本的な構成要素として機能する。
  論文  参考訳（メタデータ） (2022-06-01T10:35:29Z)
• Hybrid Henry Gas Solubility Optimization Algorithm with Dynamic Cluster-to-Algorithm Mapping for Search-based Software Engineering Problems [1.0323063834827413]
  本稿ではHenry Gas Solubility Optimization(HGSO)アルゴリズムの新しい変種であるHGSO(Hybrid HGSO)について述べる。 前者とは異なり、HHGSOは異なるメタヒューリスティックアルゴリズムを提供する複数のクラスタを同じ集団内で共存させることができる。 HHGSOは、適応的な切替係数を持つペナル化および報酬モデルによる動的クラスタ-アルゴリズムマッピングを発明し、メタヒューリスティックなハイブリダイゼーションのための新しいアプローチを提供する。
  論文  参考訳（メタデータ） (2021-05-31T12:42:15Z)
• MineReduce: an approach based on data mining for problem size reduction [58.720142291102135]
  本稿では,マイニングパターンを用いて問題サイズの削減を行うMineReduceという手法を提案する。 異種車両ルーティング問題に対するMineReduceの適用について述べる。
  論文  参考訳（メタデータ） (2020-05-15T08:49:50Z)

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

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