論文の概要: Graph Edit Distance Formulation for the Vehicle Routing Problem: Theory and Analysis

• arxiv url: http://arxiv.org/abs/2606.01987v1
• Date: Mon, 01 Jun 2026 09:46:45 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-02 21:34:31.703389
• Title: Graph Edit Distance Formulation for the Vehicle Routing Problem: Theory and Analysis
• Title（参考訳）: 車両走行問題に対するグラフ編集距離の定式化:理論と解析
• Authors: Adel Dabah,
• Abstract要約: 車両経路問題はグラフ編集距離(GED)問題として再構成可能であることを示す。 最適なルーティングは利用可能なエッジの5.5%しか使用せず、最適エッジの約3.0%はクラーク=ライトズによって一貫して見つからない。 エッジ付加目的は、エッジ予測に対する将来のグラフネットワークアプローチに対して、エッジごとの自然な監視信号を提供する。
• 参考スコア（独自算出の注目度）: 0.5956331701874674
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We show that the Vehicle Routing Problem (VRP) can be reformulated as a Graph Edit Distance (GED) maximization problem. Under a simple edge-deletion cost model, minimizing total route cost is equivalent to maximizing the total weight of edges deleted from the complete instance graph. This formulation models VRP at the edge level, where solutions are defined by selected edges rather than route sequences, enabling structural analyses that are difficult in classical formulations: per-edge attribution of solution quality, decomposition of the optimality gap, characterization of solution sparsity, and identification of edges that are hard to reach by greedy construction. Theoretically, we establish a merge-decomposition theorem showing that Clarke-Wright savings equal per-merge GED increments, and an approximation-transfer theorem that turns GED approximation ratios into VRP cost bounds. Using this reformulation, we analyze 90 CVRP benchmark instances with known optimal solutions. We find that optimal routing graphs use only 5.5% of available edges, that approximately 3.0% of optimal edges are consistently not found by Clarke-Wright heuristics under repeated restarts, and that the cost gap decomposes into missed optimal edges and substituted non-optimal edges of comparable total weight. The edge-additive objective provides a natural per-edge supervision signal for future graph neural network approaches to edge prediction, suggesting a potential connection to graph neural network approaches that we leave for follow-up work.
• Abstract（参考訳）: 車両ルーティング問題 (VRP) はグラフ編集距離 (GED) の最大化問題として再構成可能であることを示す。 単純なエッジ削除コストモデルでは、全ルートコストを最小化することは、完全なインスタンスグラフから削除されたエッジの総重量を最大化するのと等価である。 この定式化モデルは、エッジレベルでのVRPモデルであり、解はルートシーケンスではなく選択されたエッジによって定義され、古典的な定式化では難しい構造解析を可能にする。 理論的には、クラーク=ライトがマージ毎のGED増分を等しく節約することを示すマージ分解定理と、GED近似比をVRPコスト境界に変換する近似移動定理を確立する。 この再構成を用いて、90個のCVRPベンチマークインスタンスを、既知の最適解を用いて解析する。 最適ルーティンググラフは利用可能なエッジの5.5%しか使用せず、繰り返し再起動するクラーク=ライトヒューリスティックスでは、最適エッジの約3.0%は一貫して見つからず、コストギャップは、欠落した最適エッジと、同等の総重量の非最適エッジに分解される。 エッジ付加目的は、エッジ予測に対する将来のグラフニューラルネットワークアプローチのための、自然なエッジ毎の監視信号を提供する。

関連論文リスト

• Optimal Policy Learning under Budget and Coverage Constraints [0.0]
  予算と最小限の制約による最適政策学習について検討する。 この問題はクナプサック型構造を許容し,アフィンしきい値規則によって最適ポリシーを特徴付けることができることを示す。
  論文  参考訳（メタデータ） (2026-05-12T15:06:55Z)
• Model Compression with Exact Budget Constraints via Riemannian Manifolds [39.54576236079211]
  トータルコスト予算の下で各NグループにKオプションの1つを割り当てることは、効率的なAIにおいて繰り返し発生する問題である。 我々は、ソフトマックス緩和の下で、予算制約がロジット空間における滑らかなリーマン多様体を異常に単純な幾何学で定義することを示す新しいアプローチを示す。 これらの特性に基づいて、接射影、二分探索リトラクション、運動量輸送を標準とするリーマン制約最適化(RCO)を提案する。
  論文  参考訳（メタデータ） (2026-05-01T13:30:23Z)
• Enhancing Distributional Robustness in Principal Component Analysis by Wasserstein Distances [7.695578200868269]
  主成分分析(PCA)の分布ロバスト最適化(DRO)モデルについて,基礎となる確率分布の不確実性を考慮する。 結果の定式化は非滑らかな制約付き min-max 最適化問題につながり、曖昧性集合はタイプ2$ワッサーシュタイン距離で分布の不確かさを捉える。 この明示的な特徴付けは、元の DRO モデルを、複雑な非滑らかな項を持つスティーフェル多様体上の最小化問題に同値に再構成する。
  論文  参考訳（メタデータ） (2025-03-04T11:00:08Z)
• Autonomous Sparse Mean-CVaR Portfolio Optimization [6.358973724565783]
  本稿では,従来のモデルを任意の精度で近似できる,革新的な自律スパース平均CVaRポートフォリオモデルを提案する。 そこで我々は,近似交互線形化最小化アルゴリズムとネストした固定点近接アルゴリズム(どちらも収束)を併用してモデルを反復的に解く手法を提案する。
  論文  参考訳（メタデータ） (2024-05-13T15:16:22Z)
• ADEdgeDrop: Adversarial Edge Dropping for Robust Graph Neural Networks [53.41164429486268]
  グラフニューラルネットワーク(GNN)は、近隣ノードからグラフ構造化情報を収集する強力な能力を示した。 GNNの性能は、ノイズや冗長なグラフデータによって引き起こされる一般化の貧弱さと脆弱な堅牢性によって制限される。 本稿では,エッジの除去を誘導する対向エッジ予測器を利用する新しい対向エッジドロップ法 (ADEdgeDrop) を提案する。
  論文  参考訳（メタデータ） (2024-03-14T08:31:39Z)
• Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
  本稿では,ニューラルネットワークトレーニングを安定化(大規模)するための原理的手法として,線形アヘッドの理論解析を提案する。 最適化過程の不安定性は、しばしば損失ランドスケープの非単調性によって引き起こされるものであり、非拡張作用素の理論を活用することによって線型性がいかに役立つかを示す。
  論文  参考訳（メタデータ） (2023-10-20T12:45:12Z)
• Learning to solve Minimum Cost Multicuts efficiently using Edge-Weighted Graph Convolutional Neural Networks [13.985534521589257]
  グラフ畳み込みニューラルネットワーク(GNN)は、最適化の文脈で有望であることが証明されている。 我々は、グラフ畳み込みネットワーク、符号付きグラフ畳み込みネットワーク、グラフ等化ネットワークなど、さまざまなGNNに適応する。 エンドツーエンドのトレーニング可能なマルチカットへの最初のアプローチを提供する。
  論文  参考訳（メタデータ） (2022-04-04T10:21:02Z)
• Private Stochastic Non-Convex Optimization: Adaptive Algorithms and Tighter Generalization Bounds [72.63031036770425]
  有界非次元最適化のための差分プライベート(DP)アルゴリズムを提案する。 標準勾配法に対する経験的優位性について,2つの一般的なディープラーニング手法を実証する。
  論文  参考訳（メタデータ） (2020-06-24T06:01:24Z)

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

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