論文の概要: Learning to Solve Orienteering Problem with Time Windows and Variable Profits

• arxiv url: http://arxiv.org/abs/2603.06260v1
• Date: Fri, 06 Mar 2026 13:24:10 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-09 13:17:45.790543
• Title: Learning to Solve Orienteering Problem with Time Windows and Variable Profits
• Title（参考訳）: 時間的Windowsと可変利益でオリエンテーリング問題を解決するための学習
• Authors: Songqun Gao, Zanxi Ruan, Patrick Floor, Marco Roveri, Luigi Palopoli, Daniele Fontanelli,
• Abstract要約: 時間ウィンドウと可変利益(OPTWVP)によるオリエンテーリング問題は、多くの実世界のアプリケーションで一般的である。 サービス時間誘導軌道(DeCoST)を用いた学習型2段階Decoupled離散連続最適化を提案する。 OPTWVPインスタンスの実験では、DeCoSTは最先端のコンストラクティブソルバと最新のメタヒューリスティックアルゴリズムの両方より優れていることが示されている。
• 参考スコア（独自算出の注目度）: 5.973834170744548
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The orienteering problem with time windows and variable profits (OPTWVP) is common in many real-world applications and involves continuous time variables. Current approaches fail to develop an efficient solver for this orienteering problem variant with discrete and continuous variables. In this paper, we propose a learning-based two-stage DEcoupled discrete-Continuous optimization with Service-time-guided Trajectory (DeCoST), which aims to effectively decouple the discrete and continuous decision variables in the OPTWVP problem, while enabling efficient and learnable coordination between them. In the first stage, a parallel decoding structure is employed to predict the path and the initial service time allocation. The second stage optimizes the service times through a linear programming (LP) formulation and provides a long-horizon learning of structure estimation. We rigorously prove the global optimality of the second-stage solution. Experiments on OPTWVP instances demonstrate that DeCoST outperforms both state-of-the-art constructive solvers and the latest meta-heuristic algorithms in terms of solution quality and computational efficiency, achieving up to 6.6x inference speedup on instances with fewer than 500 nodes. Moreover, the proposed framework is compatible with various constructive solvers and consistently enhances the solution quality for OPTWVP.
• Abstract（参考訳）: 時間ウィンドウと可変利益(OPTWVP)によるオリエンテーリング問題は、多くの実世界のアプリケーションで一般的であり、連続時間変数を含む。 現在のアプローチでは、離散変数と連続変数を持つこのオリエンテーリング問題に対する効率的な解法の開発に失敗する。 本稿では,OPTWVP問題における離散的および連続的な決定変数を効果的に分離することを目的とした,サービス時誘導軌道(DeCoST)を用いた学習ベース2段階離散連続最適化を提案する。 第1段階では、経路と初期サービス時間割り当てを予測するために並列復号構造を用いる。 第2段階は、線形プログラミング(LP)の定式化を通じてサービス時間を最適化し、構造推定の長期学習を提供する。 我々は第2段階解の大域的最適性を厳格に証明する。 OPTWVPインスタンスの実験では、DeCoSTは、500ノード未満のインスタンスで最大6.6倍の推論スピードアップを達成し、最先端のコンストラクティブ・ソルバと最新のメタヒューリスティック・アルゴリズムの両方を、ソリューションの品質と計算効率で上回っている。 さらに,提案手法は様々な構成的解法と互換性があり,OPTWVPの解法品質を一貫して向上させる。

関連論文リスト

• Efficient End-to-End Learning for Decision-Making: A Meta-Optimization Approach [5.84228364962637]
  本稿では,最適化問題を近似する効率的なアルゴリズムを学習するメタ最適化手法を提案する。 我々は,学習方法の指数収束,近似保証,一般化境界を証明した。 この手法は計算効率に優れ、高品質な近似を高速に生成し、既存の手法と比較して問題の大きさでスケールする。
  論文  参考訳（メタデータ） (2025-05-16T15:27:50Z)
• A Problem-Oriented Perspective and Anchor Verification for Code Optimization [43.28045750932116]
  大規模言語モデル(LLM)は、様々なプログラミングタスクを解く際、顕著な能力を示している。 本稿では,LLMが最小実行時間に最適化する能力について検討する。
  論文  参考訳（メタデータ） (2024-06-17T16:10:10Z)
• Fast Two-Time-Scale Stochastic Gradient Method with Applications in Reinforcement Learning [5.325297567945828]
  本稿では,従来の手法よりもはるかに高速な収束を実現する2段階最適化手法を提案する。 提案手法は,既存の最先端技術に匹敵する,あるいは適合する新しいオンラインサンプルベース手法に特化していることを示す。
  論文  参考訳（メタデータ） (2024-05-15T19:03:08Z)
• Analyzing and Enhancing the Backward-Pass Convergence of Unrolled Optimization [50.38518771642365]
  ディープネットワークにおけるコンポーネントとしての制約付き最適化モデルの統合は、多くの専門的な学習タスクに有望な進歩をもたらした。 この設定における中心的な課題は最適化問題の解によるバックプロパゲーションであり、しばしば閉形式を欠いている。 本稿では, 非線形最適化の後方通過に関する理論的知見を提供し, 特定の反復法による線形システムの解と等価であることを示す。 Folded Optimizationと呼ばれるシステムが提案され、非ローリングなソルバ実装からより効率的なバックプロパゲーションルールを構築する。
  論文  参考訳（メタデータ） (2023-12-28T23:15:18Z)
• Accelerating Exact Combinatorial Optimization via RL-based Initialization -- A Case Study in Scheduling [1.3053649021965603]
  本研究の目的は、最適化問題に対処する機械学習(ML)を用いた革新的なアプローチを開発することである。 1) 粗粒スケジューラとしての解法, 2) 解緩和, 3) ILPによる正確な解法の3つのステップを含む新しい2段階のRL-to-ILPスケジューリングフレームワークを導入する。 提案フレームワークは, 正確なスケジューリング手法と比較して, 最大128ドルの高速化を実現しつつ, 同一のスケジューリング性能を示す。
  論文  参考訳（メタデータ） (2023-08-19T15:52:43Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。 我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。 我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
  論文  参考訳（メタデータ） (2021-06-08T15:54:44Z)
• Two-Stage Stochastic Optimization via Primal-Dual Decomposition and Deep Unrolling [86.85697555068168]
  2段階のアルゴリズム最適化は、様々な工学や科学的応用において重要な役割を果たす。 特に長期変数と短期変数が制約の中で結合されている場合、アルゴリズムは効率的ではない。 PDD-SSCAが既存のソリューションよりも優れたパフォーマンスを達成できることを示します。
  論文  参考訳（メタデータ） (2021-05-05T03:36:00Z)
• 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)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。 SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。 本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-07-14T12:38:21Z)

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

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