ReinforceNS: Reinforcement Learning-based Multi-start Neighborhood Search for Solving the Traveling Thief Problem

Tao Wu, Huachao Cui, Tao Guan, Yuesong Wang, Yan JinIJCAI 2024

Abstract

The Traveling Thief Problem (TTP) is a complex combinatorial optimization challenge that integrates the Traveling Salesman Problem (TSP) and the Knapsack Problem (KP) through interdependent constraints. This paper introduces ReinforceNS, a multi-start iterated neighborhood search algorithm that leverages reinforcement learning to optimize TTP solutions. By employing Q-learning to guide neighborhood selection and a specialized route-refining heuristic, ReinforceNS effectively addresses the non-linear coupling between travel speed and knapsack weight. Experimental results on 60 benchmark instances demonstrate that ReinforceNS outperforms existing state-of-the-art heuristics, achieving 12 new best results on competition benchmarks.

1. Introduction

The Traveling Thief Problem (TTP) is a "multi-component" optimization problem designed to reflect real-world interdependencies. It combines the routing requirements of the TSP with the packing decisions of the KP. The core difficulty lies in the coupling: as items are collected, the thief's speed decreases, increasing the time-dependent "rent" cost. Consequently, a route that is optimal for a light thief may be suboptimal as the knapsack fills. While machine learning has seen success in TSP and KP independently, its application to the coupled TTP remains a frontier in optimization research.

2. Methodology: ReinforceNS

The ReinforceNS algorithm follows a four-stage pipeline designed for efficiency and solution quality.

2.1 Pre-processing and Initialization

To manage computational complexity, the algorithm uses neighborhood reduction based on the LKH algorithm. Initialization involves solving the TSP component with CLKH and the KP component with a novel Iterated Greedy Packing (IGP) procedure. IGP uses a scoring function to balance item profit against weight and the distance from the depot.

2.2 RL-based Neighborhood Search (RLNS)

The central innovation is the use of Q-learning to guide "2-opt" edge exchanges. Rather than exhaustive or random searching, the RL agent learns which neighbor selections are most likely to yield objective improvements. The Q-table effectively acts as a memory of which moves have been successful in the past.

Illustration of a neighborhood search move (2-opt) within the routing component of the Traveling Thief Problem.

2.3 Post-Optimization

Following the search, the algorithm performs "item flipping" and a specialized "route refining" phase. This heuristic moves cities with heavy items toward the end of the tour, minimizing the duration of slow-speed travel.

3. Experimental Results

ReinforceNS was evaluated on 60 benchmark instances (categorized as CatA, CatB, and CatC) and compared against state-of-the-art (SOTA) algorithms: MATLS, S5, and CoCo.

Detailed performance comparison of ReinforceNS against SOTA algorithms across 60 benchmark instances, highlighting the 38 instances where ReinforceNS achieved superior results.

3.1 Performance Comparison

ReinforceNS outperformed SOTA competitors in 38 out of 60 instances. Statistical analysis shows that ReinforceNS achieves higher Relative Deviation Index (RDI) scores with significantly lower variance, indicating both superior performance and higher reliability within a fixed 600-second time limit.

3.2 Competition Benchmarks

On the 18 instances from the GECCO 2023 TTP Competition, ReinforceNS established 12 new best-known results, demonstrating its capability to push the boundaries of current optimization techniques.

4. Conclusion

ReinforceNS demonstrates the power of integrating reinforcement learning with traditional neighborhood search heuristics for complex, interdependent problems like TTP. By using RL to provide guidance to the search process and incorporating domain-specific route refining, the algorithm achieves state-of-the-art results. Future work will investigate deep reinforcement learning to further unify the routing and packing decision-making processes.

Summary updated

BibTeX
@inproceedings{wu2024reinforcens,
  author = {Tao Wu and Huachao Cui and Tao Guan and Yuesong Wang and Yan Jin},
  title = {{ReinforceNS: Reinforcement Learning-based Multi-start Neighborhood Search for Solving the Traveling Thief Problem}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
}
Figure