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


The travelling thief problem (TTP) is a combination of the traditional traveling salesman problem(TSP) and the knapsack problem(KP), which is an NP-hard problem. Compared with the independent TSP and KP, the TTP is more realistic and has higher research value. Previous TTP solving algorithms are mainly heuristic algorithms with limited performance, and other types of algorithms are less studied. To acquire better solution for TTP, a staged strategy of incorporating reinforcement learning is proposed. The first stage generates an item selection plan based on the properties of items. The second stage uses a reinforcement learning algorithm (Actor-Critic algorithm) to solve the travel path. The third stage introduces neighborhood search strategy to optimize the obtained solution. Experiments show that the proposed algorithm achieves good results on most test cases and, in some cases, outperforms the compared algorithms in terms of solution quality, demonstrating the superior performance of the proposed algorithm. 


相关文章