【标题】Reinforcement Learning to Solve NP-hard Problems: an Application to the CVRP（强化学习在解决NP难问题中的应用）

【作者团队】Leo Ardon

【发表日期】14 January, 2022

【论文链接】https://arxiv.org/pdf/2201.05393.pdf

【推荐理由】本文评估了强化学习（RL）在解决一个经典的组合优化问题中的应用：容量约束车辆路径问题（CVRP）。文章在RL框架中形式化了这个问题，并在一组基准实例上比较了两种最有前途的RL方法与传统的求解技术。通过返回的解决方案的质量和返回所需的时间来衡量不同的方法。尽管没有返回最佳解，但与传统解算器相比，RL方法具有许多优势。首先，该框架的多功能性允许解决更复杂的组合问题。此外，RL算法学习解决问题所需的技能，而不是试图解决问题的特定实例。然后，经过培训的策略可以准即时地为一个看不见的问题提供解决方案，而不必从头开始解决它。最后，使用经过训练的模型使RL解算器成为迄今为止最快的解算器，因此使该方法更适合用户体验最重要的商业用途。知识转移等技术也可以用来提高算法的训练效率，帮助解决更大更复杂的问题