用神经网络解决随机路径规划问题，无需人工设计启发式方法。
N(CO)$^2$: Neural Combinatorial Optimization with Chance Constraints to Solve Stochastic Orienteering
- 基于强化学习框架，自动学习在不确定环境下的路径选择策略。
- 在多种随机路径规划任务中表现优异，媲美顶尖混合整数规划方法。
- 适合需要自适应决策的自动化系统，降低人工设计复杂度。
神经组合优化（NCO）通过数据驱动方式学习启发式策略，为复杂图优化问题提供替代传统启发式方法的前景。尽管已有大量研究聚焦于确定性组合优化，但针对随机组合优化的研究仍较少。本文提出 N(CO)²：一种结合机会约束的神经组合优化方法，用于求解随机定向路径问题（SOP），无需依赖手工设计的启发式规则。通过引入强化学习框架，模型在不确定性环境下优化路径选择，有效平衡探索与利用。实验表明，该方法在多样化的 SOP 实例上具有良好泛化能力，性能与当前最优的混合整数线性规划（MILP）方法相当。该方法显著减少人工设计启发式的投入，同时实现不确定环境中的自适应高效决策。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。