ニューラル組合せ最適化（NCO）は、データからヒューリスティックを学習することで、複雑なグラフ最適化問題に対する従来のヒューリスティックベースの手法に代わる有望な選択肢を提供する。この種の問題は自動化の分野で頻繁に現れ、ロボットの経路計画、物流配送、捜索活動など様々なアプリケーションのモデル化に利用できる。NCOは決定論的な組合せ最適化問題に対して広く研究されてきたが、確率的な組合せ最適化問題を対象とした研究は限られている。不確実性（例えばランダムな移動時間）が存在する場合、問題はより複雑になり、正確な解法が難しくなる。
本研究では、確率的オリエンテーリング問題（Stochastic Orienteering Problem, SOP）を解くために、N(CO)$^2$：確率的制約付きニューラル組合せ最適化（Neural Combinatorial Optimization with Chance cOnstraints）を提案する。SOPでは、与えられた時間予算内でノードを訪問し報酬を最大化する経路を選択するが、ノード間の移動時間は不確実である。この不確実性に対処するため、N(CO)$^2$は確率的制約を導入し、経路の総時間が予算を超過する確率が事前設定された閾値以下であることを保証する。本フレームワークは手動で設計されたヒューリスティックを必要とせず、強化学習（RL）を統合することで経路選択方策を直接最適化する。具体的には、N(CO)$^2$はアテンションベースのニューラルネットワークを用いてグラフ構造をエンコードし、方策勾配法で訓練することで、探索と活用のバランスを取る。
実験では、著者らは様々なSOPインスタンス（ノード数、ランダム分布、確率的制約の閾値が異なる）でN(CO)$^2$を評価した。結果は、N(CO)$^2$が訓練データに現れない未知のインスタンスに対しても良好に汎化し、その求解品質は最先端の混合整数線形計画法（MILP）と同等かそれ以上であることを示した。さらに、N(CO)$^2$の求解速度はMILPを大幅に上回り、特に大規模問題で顕著なアドバンテージを示した。この成果により、ヒューリスティック設計における人間の労力が削減され、不確実な環境での適応的かつ効率的な意思決定が可能になる。
本論文は、IEEE自動化科学工学会議（CASE 2025）に掲載されている。著者らは研究の再現性を促進するため、コードとデータを公開している（論文リンク参照）。本研究は、ニューラル組合せ最適化を確率問題に拡張する重要な一歩であり、動的配送スケジューリングや緊急対応経路計画など、より現実的な応用への展開が期待される。