確率制約付きニューラル組合せ最適化による確率的オリエンテーリング問題の解法
N(CO)$^2$: Neural Combinatorial Optimization with Chance Constraints to Solve Stochastic Orienteering
手動ヒューリスティックを使わず、強化学習を用いて確率的オリエンテーリング問題を解くニューラル組合せ最適化手法を提案し、多様なインスタンスで汎化性能を実証した。
詳しい要約
1. どんなもの?
2. 先行研究と比べてどこがすごい?
3. 技術・手法の肝は?
4. どうやって有効だと検証した?
5. 議論はある?
6. 次に読むべき論文は?
※ AIが要旨から生成した要約です。正確性は原文をご確認ください。
著者: Anas Saeed, Marcos Abel Zuzuárregui, Stefano Carpin
分類: cs.RO, cs.LG
原文アブストラクト
Neural combinatorial optimization (NCO) offers a promising alternative to traditional heuristic-based methods for solving complex graph optimization problems by proposing to learn heuristics through data. This class of problems frequently arises in automation, as it can be used to model a variety of applications. While NCO has been extensively studied for deterministic combinatorial optimization problems, there are only a few works that aim to solve stochastic combinatorial optimization problems. In this work, we present N(CO)$^2$: Neural Combinatorial Optimization with Chance cOnstraints to solve the Stochastic Orienteering Problem (SOP) without the use of hand-crafted heuristics. By integrating a reinforcement learning (RL) framework, the model optimizes path selection under uncertainty, effectively balancing exploration and exploitation. Empirical results demonstrate that our method generalizes well across diverse SOP instances, achieving competitive performance compared to the state-of-the-art mixed-integer linear program (MILP) for the task. The proposed approach reduces human effort in heuristic design while enabling adaptive and efficient decision-making in uncertain environments.
関連論文
- ベースライン不要のニューラル組合せ最適化のための方策最適化組合せ最適化
- 車両経路問題のためのセグメンテーション学習組合せ最適化
- 厳密な組合せ最適化のための深層強化学習:分枝変数選択の学習組合せ最適化
- 組合せ最適化問題の構造化近似の学習組合せ最適化
- カッティングプレーン法によるチームオリエンテーリング問題の解法組合せ最適化
- 多重スタックTSPの近似可能性組合せ最適化
