論文の概要: An Efficient and Almost Optimal Solver for the Joint Routing-Assignment Problem via Partial JRA and Large-α Optimization

• arxiv url: http://arxiv.org/abs/2511.09563v1
• Date: Fri, 14 Nov 2025 01:00:10 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-14 22:53:22.319426
• Title: An Efficient and Almost Optimal Solver for the Joint Routing-Assignment Problem via Partial JRA and Large-α Optimization
• Title（参考訳）: JRA部分最適化と大域最適化による共同経路割り当て問題に対する効率的かつほぼ最適解法
• Authors: Qilong Yuan,
• Abstract要約: JRA(Joint Routing-Assignment)最適化問題は、プレースホルダーへのアイテムの割り当てと、各ノードペアを正確に1度訪問するハミルトンサイクルを決定する。 これまでの研究では、データセットとGurobi実装とともに、正確な混合整数プログラミング(MIP)ソルバが導入されていた。 本研究は, 大規模JRA問題に対する高精度, ほぼ最適解を実現する新しい, より効率的な手法を提案する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Joint Routing-Assignment (JRA) optimization problem simultaneously determines the assignment of items to placeholders and a Hamiltonian cycle that visits each node pair exactly once, with the objective of minimizing total travel cost. Previous studies introduced an exact mixed-integer programming (MIP) solver, along with datasets and a Gurobi implementation, showing that while the exact approach guarantees optimality, it becomes computationally inefficient for large-scale instances. To overcome this limitation, heuristic methods based on merging algorithms and shaking procedures were proposed, achieving solutions within approximately 1% deviation from the optimum. This work presents a novel and more efficient approach that attains high-accuracy, near-optimal solutions for large-scale JRA problems. The proposed method introduces a Partial Path Reconstructon (PPR) solver that first identifies key item-placeholder pairs to form a reduced subproblem, which is solved efficiently to refine the global solution. Using this PJAR framework, the initial heuristic merging solutions can be further improved, reducing the deviation by half. Moreover, the solution can be iteratively polished with PPR based solver along the optimization path to yield highly accurate tours. Additionally, a global Large-α constraint is incorporated into the JRA model to further enhance solution optimality. Experimental evaluations on benchmark datasets with n = 300, 500, and 1000 demonstrate that the proposed method consistently delivers almost optimal solutions, achieving an average deviation of 0.00% from the ground truth while maintaining high computational efficiency. Beyond the JRA problem, the proposed framework and methodologies exhibit strong potential for broader applications. The Framework can be applied to TSP and related optimization problems.
• Abstract（参考訳）: JRA (Joint Routing-Assignment) 最適化問題は、プレースホルダーへのアイテムの割り当てと、各ノードペアを正確に1度訪問するハミルトンサイクルを同時に決定する。 これまでの研究では、データセットとグロビの実装とともに、正確な混合整数プログラミング(MIP)の解法を導入し、正確なアプローチは最適性を保証するが、大規模インスタンスでは計算的に非効率になることを示した。 この制限を克服するため、最適化アルゴリズムと揺らぎ手順に基づくヒューリスティック手法が提案され、最適解から約1%の偏差で解が得られた。 本研究は, 大規模JRA問題に対する高精度, ほぼ最適解を実現する新しい, より効率的な手法を提案する。 提案手法では,まずキーアイテムとプレースホルダーのペアを同定して減算サブプロブレムを形成する部分パス再構成(PPR)解法を提案する。 このPJARフレームワークを使うことで、初期ヒューリスティックなマージソリューションをさらに改善し、偏差を半分に抑えることができる。 さらに、最適化経路に沿って、PPRベースのソルバを用いて繰り返し研磨することで、高精度なツアーを実現することができる。 さらに,JRAモデルにグローバルなLarge-α制約が組み込まれ,解の最適性をさらに向上する。 n = 300, 500, 1000 のベンチマークデータセットを用いた実験により,提案手法がほぼ最適な解を常に提供し,高い計算効率を維持しつつ,基礎的真理から平均 0.00% の偏差を達成できることを示した。 JRA問題以外にも,提案するフレームワークや方法論は幅広い応用の可能性を示している。 このフレームワークは、TSPと関連する最適化問題に適用できる。

関連論文リスト

• Preference Optimization for Combinatorial Optimization Problems [54.87466279363487]
  強化学習(Reinforcement Learning, RL)は、ニューラルネットワーク最適化のための強力なツールとして登場した。 大幅な進歩にもかかわらず、既存のRLアプローチは報酬信号の減少や大規模な行動空間における非効率な探索といった課題に直面している。 統計的比較モデルを用いて定量的報酬信号を定性的選好信号に変換する新しい手法であるPreference Optimizationを提案する。
  論文  参考訳（メタデータ） (2025-05-13T16:47:00Z)
• DiffuSolve: Diffusion-based Solver for Non-convex Trajectory Optimization [9.28162057044835]
  最適軌道局所は非線形および高次元力学系において計算コストが高い。 本稿では,非次元オプティマ問題に対するDiffuに基づく一般モデルを提案する。 また,新たな制約付き拡散モデルであるDiff+を提案する。
  論文  参考訳（メタデータ） (2024-02-22T03:52:17Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• Learning Adaptive Evolutionary Computation for Solving Multi-Objective Optimization Problems [3.3266268089678257]
  本稿では, 深層強化学習(DRL)を用いた適応パラメータ制御とMOEAを統合したフレームワークを提案する。 DRLポリシは、最適化中のソリューションに対する突然変異の強度と確率を決定する値を適応的に設定するように訓練されている。 学習されたポリシーは転送可能であることを示す。つまり、単純なベンチマーク問題で訓練されたポリシーは、複雑な倉庫最適化問題を解決するために直接適用可能である。
  論文  参考訳（メタデータ） (2022-11-01T22:08:34Z)
• Mining Large Independent Sets on Massive Graphs [47.21699378695116]
  ARCISは、巨大なグラフ上の大きな独立した集合をマイニングするための効率的なアルゴリズムである。 ARCISは、ほとんどのインスタンスで最高の、または最も結びついたソリューション品質が得られることを示す。
  論文  参考訳（メタデータ） (2022-08-16T14:39:38Z)
• Outlier-Robust Sparse Estimation via Non-Convex Optimization [73.18654719887205]
  空間的制約が存在する場合の高次元統計量と非破壊的最適化の関連について検討する。 これらの問題に対する新規で簡単な最適化法を開発した。 結論として、効率よくステーションに収束する一階法は、これらのタスクに対して効率的なアルゴリズムを導出する。
  論文  参考訳（メタデータ） (2021-09-23T17:38:24Z)
• A Two-stage Framework and Reinforcement Learning-based Optimization Algorithms for Complex Scheduling Problems [54.61091936472494]
  本稿では、強化学習(RL)と従来の運用研究(OR)アルゴリズムを組み合わせた2段階のフレームワークを開発する。 スケジューリング問題は,有限マルコフ決定過程 (MDP) と混合整数計画過程 (mixed-integer programming process) の2段階で解決される。 その結果,本アルゴリズムは,アジャイルな地球観測衛星スケジューリング問題に対して,安定かつ効率的に十分なスケジューリング計画を得ることができた。
  論文  参考訳（メタデータ） (2021-03-10T03:16:12Z)
• Meta-learning based Alternating Minimization Algorithm for Non-convex Optimization [9.774392581946108]
  複数変数の非プロブレムに挑戦する新しい解を提案する。 提案手法では,他の手法が一般的に失敗するケースに対して,効果的なイテレーションを実現することができる。
  論文  参考訳（メタデータ） (2020-09-09T10:45:00Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。 SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。 本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-07-14T12:38:21Z)

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

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