融合强化学习的分阶段策略求解旅行背包问题

来源：计算机工程与科学杂志2025年第1期北京时间：

作者：章政, 夏小云, 陈泽丰, 向毅

单位：1.浙江理工大学计算机科学与技术学院,浙江 杭州 310018；2.嘉兴大学人工智能学院,浙江 嘉兴 314001；3.中山大学人工智能学院,广东 珠海 519082；4.华南理工大学软件学院，广东 广州 510006

摘要：旅行背包问题TTP是传统的旅行商问题和背包问题的结合，属于NP难问题。相较于独立的旅行商问题和背包问题，旅行背包问题更加符合现实情况，具有更高的研究价值。先前的TTP求解算法主要为启发式算法，性能有限，其他类型的算法则研究较少。为了提高TTP的求解性能，提出了融合强化学习的算法，采用分阶段策略。第1阶段根据物品的属性生成物品选择计划，第2阶段利用强化学习演员-评论家（Actor-Critic）算法求解旅行路径，第3阶段引入邻域搜索策略优化所得解。实验结果表明，所提算法在大部分算例上都取得了较好的结果，并且在部分算例上，解的质量超越了其他对比算法，表明了所提算法具有较优的性能。

关键词：强化学习,旅行背包问题,演员-评论家算法,组合优化,

基金资助：国家重点研发计划(2023YFC3305900,2023YFC3305903)；国家自然科学基金（62206313,61703183）;中央高校基本科研业务费专项资金（2024ZYGXZR097）；广东省基础与应用基础研究基金(2024A1515030022)；浙江省自然科学基金（LGG19F030010）；嘉兴大学“勤慎”青年学者培养计划（嘉院人字〔2023〕12号）