Abstract: 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. 

Key words: reinforcement learning, travelling thief problem (TTP), Actor-Critic algorithm, combinatorial optimizatio