# Surrogate Assisted Optimisation for Travelling Thief Problems

arXiv: https://arxiv.org/abs/2005.06695 · HTML: https://mlsanity.com/paper/2005.06695/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 May 2020.

## Built on by (most cited first, 3 of 3)

- [The First AI4TSP Competition: Learning to Solve Stochastic Routing Problems](https://mlsanity.com/paper/2201.10453/) (2022)
- [Solving Travelling Thief Problems using Coordination Based Methods](https://mlsanity.com/paper/2310.07156/) (2023)
- [Surrogate Assisted Monte Carlo Tree Search in Combinatorial Optimization](https://mlsanity.com/paper/2403.09925/) (2024)

## Abstract (arXiv)

The travelling thief problem (TTP) is a multi-component optimisation problem involving two interdependent NP-hard components: the travelling salesman problem (TSP) and the knapsack problem (KP). Recent state-of-the-art TTP solvers modify the underlying TSP and KP solutions in an iterative and interleaved fashion. The TSP solution (cyclic tour) is typically changed in a deterministic way, while changes to the KP solution typically involve a random search, effectively resulting in a quasi-meandering exploration of the TTP solution space. Once a plateau is reached, the iterative search of the TTP solution space is restarted by using a new initial TSP tour. We propose to make the search more efficient through an adaptive surrogate model (based on a customised form of Support Vector Regression) that learns the characteristics of initial TSP tours that lead to good TTP solutions. The model is used to filter out non-promising initial TSP tours, in effect reducing the amount of time spent to find a good TTP solution. Experiments on a broad range of benchmark TTP instances indicate that the proposed approach filters out a considerable number of non-promising initial tours, at the cost of omitting only a small number of the best TTP solutions.