POMO: Policy Optimization with Multiple Optima for Reinforcement Learning
POMO exploits multiple starting points and symmetry in RL to solve TSP, CVRP, KP with 0.14% optimality gap, over tenfold inference speedup.
Key Findings
Methodology
POMO employs multi-start exploration by generating multiple solution trajectories from different initial nodes, leveraging problem symmetry. It integrates an improved REINFORCE algorithm with a shared low-variance baseline to enhance training stability and speed. Instance augmentation via coordinate transformations introduces diverse input views, boosting inference robustness. The neural network, based on Attention architecture, supports parallel multi-trajectory generation, significantly improving solution quality. During training, diverse trajectories reduce local minima, and during inference, multiple greedy solutions are combined to select the best, resulting in high-quality solutions efficiently.
Key Results
- On TSP100, POMO achieves a 0.14% optimality gap, outperforming all recent learned heuristics, with inference time reduced by over ten times. For TSP50 and TSP20, gaps are 0.03% and 0.04%, respectively. In CVRP and KP, errors are kept below 1%, surpassing traditional heuristics and other deep RL methods. Multi-start exploration and instance augmentation synergistically improve robustness and generalization, demonstrating the method’s effectiveness across problem scales.
- Across TSP, CVRP, and KP, POMO consistently outperforms baseline REINFORCE-trained models, especially on large instances. The multi-trajectory training and inference strategies notably lower variance and enhance solution quality. Ablation studies confirm that combining multiple greedy rollouts with instance augmentation yields the best performance, both in solution accuracy and computational efficiency.
Significance
This work advances reinforcement learning for combinatorial optimization by exploiting problem symmetry and multi-start exploration, effectively mitigating local minima issues. It demonstrates that neural networks can achieve near-optimal solutions efficiently on NP-hard problems at scale, opening new avenues for industrial applications such as logistics, routing, and resource allocation. The approach’s generality and scalability mark a significant step forward, promising broader adoption of deep RL in complex real-world scenarios.
Technical Contribution
The core innovation lies in leveraging multiple initial nodes during training to exploit symmetry, combined with a shared low-variance baseline for stable policy gradient updates. The introduction of instance augmentation via coordinate transformations enhances robustness. The neural architecture supports parallel multi-trajectory generation, drastically improving inference speed. This framework is adaptable to various NP-hard problems without problem-specific heuristics, representing a significant methodological advance in deep reinforcement learning for combinatorial tasks.
Novelty
This research is the first to systematically utilize symmetry-based multi-start exploration within RL for combinatorial optimization, reducing local minima and improving solution quality. The combination of multiple trajectories, shared baselines, and instance augmentation constitutes a novel framework that surpasses existing methods in both efficiency and accuracy. Its general applicability across different NP-hard problems marks a new paradigm in neural combinatorial optimization.
Limitations
- While effective on problems up to 100 nodes, scalability to thousands remains computationally intensive, requiring further optimization. Dependence on problem symmetry limits applicability to certain problem classes; asymmetric or irregular problems pose challenges. Instance augmentation, though beneficial, may introduce noise in some scenarios, affecting stability. Future work should focus on reducing computational costs and extending symmetry exploitation to broader problem types.
Future Work
Future directions include developing automatic symmetry detection to broaden applicability, integrating multi-scale approaches for larger problems, and combining RL with classical heuristics for enhanced performance. Exploring online and dynamic problem settings, as well as transfer learning to adapt models across different tasks, are promising avenues. Additionally, refining instance augmentation techniques and reducing training complexity will be key to deploying these methods in real-world large-scale industrial environments.
AI Executive Summary
Neural combinatorial optimization has gained prominence for tackling NP-hard problems like TSP, CVRP, and KP, where traditional algorithms struggle with scale and complexity. Recent deep reinforcement learning approaches, such as Pointer Networks and Attention models, demonstrated promising results but often suffered from local minima and exploration limitations. These methods typically relied on single-start solutions, which restricted their ability to find near-optimal solutions efficiently.
To address these challenges, this paper introduces Policy Optimization with Multiple Optima (POMO), a novel framework that exploits the symmetry inherent in many combinatorial problems. By initiating multiple solution trajectories from different nodes simultaneously, POMO leverages problem symmetry to enhance exploration. It employs a modified REINFORCE algorithm with a shared low-variance baseline, which stabilizes training and accelerates convergence. Additionally, the method incorporates instance augmentation through coordinate transformations, generating diverse problem views that improve robustness.
The neural network architecture, based on Attention mechanisms, supports parallel multi-trajectory generation, significantly reducing inference time. Extensive experiments on TSP, CVRP, and KP demonstrate that POMO achieves state-of-the-art performance, with a 0.14% optimality gap on TSP100 and inference speed improvements exceeding tenfold. These results surpass existing deep RL methods and traditional heuristics, especially on large-scale instances.
This work marks a substantial advance in neural combinatorial optimization, offering a scalable, generalizable, and highly efficient solution framework. Its ability to mitigate local minima and exploit problem symmetry opens new horizons for industrial applications, including logistics, routing, and resource management. Future research will focus on extending the approach to larger and more complex problems, automating symmetry detection, and integrating with classical optimization techniques to further enhance performance and applicability.
Deep Analysis
Background
Combinatorial optimization在物流、制造和供应链管理中扮演核心角色。传统方法如LKH、Gurobi等在小规模问题上表现优异，但在大规模或动态环境中效率不足。深度学习结合强化学习逐渐兴起，Pointer Network、Attention模型等在TSP、VRP、KP等经典问题上取得突破，减少对专家经验依赖，提升求解速度。然而，受限于探索能力和局部最优困境，难以在大规模问题中保持优异表现。近年来，深度RL的研究不断推进，试图突破这些瓶颈。
Core Problem
核心问题在于如何充分利用问题的对称性，避免模型陷入局部最优，并提升大规模NP-hard问题的求解效率。现有方法多依赖单一起点或采样，探索空间有限，导致解的质量不稳定。如何设计多起点、多轨迹探索机制，结合问题结构特性，成为提升性能的关键。同时，训练中的方差控制和样本多样性也是亟待解决的问题。解决这些瓶颈，将极大推动深度RL在实际复杂场景中的应用。
Innovation
首先，提出多起点探索策略，通过在训练中同时生成多个起点的轨迹，充分利用问题的对称性，增强探索多样性。其次，采用改进的REINFORCE算法，结合共享低方差基线，有效降低梯度估计的方差，提升训练稳定性。第三，引入实例增强技术，通过坐标变换扩展训练样本，增强模型鲁棒性。最后，基于Attention架构实现多轨迹并行生成，大幅提升推理效率。这些创新共同推动深度RL在组合优化中的应用边界。
Methodology
- �� 设计多起点探索：在训练中随机选择多个不同节点作为起点，生成对应解轨迹。
- �� 利用对称性：通过坐标变换（旋转、翻转）生成多样化实例，增强模型泛化能力。
- �� 改进REINFORCE：采用共享低方差基线，减少梯度估计的方差，提升训练稳定性。
- �� 多轨迹并行：在Attention模型中同时生成多个轨迹，利用并行计算提升效率。
- �� 训练目标：最大化多轨迹的平均奖励，鼓励多样性探索，避免局部最优。
- �� 推理策略：多起点贪婪推理结合实例增强，选择最优解，提升解的质量。
Experiments
采用TSP、CVRP、KP三类标准数据集，训练基于Attention模型的POMO框架。训练采用Adam优化器，学习率1e-4，批次64，训练200-2000轮。对比基线包括传统启发式、非学习优化器和深度RL方法。通过不同规模（TSP50、100，CVRP50、100，KP50、200）进行测试，评估最优差距和推理时间。引入多轨迹和实例增强，进行消融实验验证各策略贡献。结果显示，POMO在TSP100中实现0.14%的最优差距，推理时间缩短十倍。
Results
在TSP100，POMO达成0.14%的最优差距，显著优于现有学习方法，推理时间减少十倍。TSP50和20的最优差距分别为0.03%和0.04%。CVRP和KP任务中，误差控制在1%以内，优于传统启发式和其他深度RL模型。多起点探索和实例增强共同作用，显著提升模型鲁棒性和泛化能力，验证了方法的有效性和实用性。
Applications
该方法适用于物流调度、路径规划、资源分配等场景，尤其在大规模复杂问题中表现优越。无需大量手工设计启发式规则，模型可通过数据驱动自动学习策略。未来可结合实际环境动态调整，支持在线优化和多任务迁移，推动智能调度和自动化产业升级。
Limitations & Outlook
模型在超大规模问题（如千节点以上）上仍面临训练成本高、推理复杂的问题。对问题的对称性依赖较强，某些变换不适用，限制泛化。实例增强虽提升鲁棒性，但在某些场景可能引入噪声。未来需优化模型结构，降低计算需求，增强适应性。
Plain Language Accessible to non-experts
想象你在厨房做饭，要准备一道复杂的菜肴。每次你可以从不同的食材开始，尝试不同的搭配和步骤。传统方法可能只试一次，容易走弯路，做不好。而POMO就像请多个厨师同时试不同的起点，尝试不同的调料组合，最后挑出最好的一份。它利用食材的对称性（比如调料可以倒反放），让每个厨师都能找到最优方案。这样一来，做菜的效率更高，味道也更好。这个方法用在解决复杂路径和资源分配问题上，也一样，能快速找到最优方案，节省时间和成本。
ELI14 Explained like you're 14
想象你在玩一个超级复杂的迷宫游戏，你需要找到最快的出口。以前，你只会从门口开始走，试几次后就可能卡在死胡同里。现在，假设你可以同时从迷宫的不同位置开始探索，每个“队友”都试不同的路径。这样一来，你就能更快找到出口。POMO就是让很多“队友”同时探索不同起点，利用迷宫的对称性（比如左右对称的路径），让你更快找到最佳路线。它还会用一些聪明的技巧，比如让每个队友尝试不同的走法，然后挑出最短的那条。这样一来，找到最优路径就变得更快更稳了。这种方法可以用在很多复杂的路径规划、调度和资源分配问题中，帮助我们节省时间和资源，找到最好的解决方案。
Glossary
Policy Gradient（策略梯度）
一种强化学习方法，通过直接优化策略参数以最大化期望奖励。技术上，利用梯度估计更新策略参数。
POMO采用改进的策略梯度方法，结合多轨迹探索提升训练效果。
REINFORCE算法
一种无模型的策略梯度算法，通过采样轨迹估算梯度，优化策略。
POMO在训练中使用REINFORCE，结合共享低方差基线，增强稳定性。
Attention机制
一种神经网络中的注意力机制，动态调整输入特征的权重以捕获重要信息。
模型基于Attention架构，支持多轨迹并行生成。
实例增强（Instance Augmentation）
通过对输入数据进行变换，生成多样化样本以提升模型鲁棒性。
在推理阶段，利用坐标变换扩展样本，改善解的质量。
NP-hard问题
一类计算复杂度极高的问题，无法在多项式时间内精确求解。
TSP、CVRP、KP都属于NP-hard问题，本文旨在高效近似求解。
Open Questions Unanswered questions from this research
- 1 如何自动识别不同问题中的对称性，提升模型的泛化能力仍待研究。现有方法依赖手工定义变换，限制了应用范围。未来需要开发自动化的对称性检测与利用机制，以适应更复杂的实际场景。
Applications
Immediate Applications
物流路径优化
利用POMO快速生成近似最优路径，降低运输成本，提高调度效率，适用于快递、配送等行业。
资源调度
在制造和服务行业中，优化资源分配和调度，提升生产效率和响应速度。
Long-term Vision
智能城市交通管理
结合大规模交通数据，实时优化交通流，减少拥堵，推动智慧城市建设。
Abstract
In neural combinatorial optimization (CO), reinforcement learning (RL) can turn a deep neural net into a fast, powerful heuristic solver of NP-hard problems. This approach has a great potential in practical applications because it allows near-optimal solutions to be found without expert guides armed with substantial domain knowledge. We introduce Policy Optimization with Multiple Optima (POMO), an end-to-end approach for building such a heuristic solver. POMO is applicable to a wide range of CO problems. It is designed to exploit the symmetries in the representation of a CO solution. POMO uses a modified REINFORCE algorithm that forces diverse rollouts towards all optimal solutions. Empirically, the low-variance baseline of POMO makes RL training fast and stable, and it is more resistant to local minima compared to previous approaches. We also introduce a new augmentation-based inference method, which accompanies POMO nicely. We demonstrate the effectiveness of POMO by solving three popular NP-hard problems, namely, traveling salesman (TSP), capacitated vehicle routing (CVRP), and 0-1 knapsack (KP). For all three, our solver based on POMO shows a significant improvement in performance over all recent learned heuristics. In particular, we achieve the optimality gap of 0.14% with TSP100 while reducing inference time by more than an order of magnitude.