# Solving Travelling Thief Problems using Coordination Based Methods

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 47 references that are in the map.
- First posted on arXiv 11 Oct 2023.

## Builds on (most cited first, 10 of 10)

- [A case study of algorithm selection for the traveling thief problem](https://mlsanity.com/paper/1609.00462/) (2016)
- [The ensmallen library for flexible numerical optimization](https://mlsanity.com/paper/2108.12981/) (2021)
- [Large neighborhoods with implicit customer selection for vehicle routing problems with profits](https://mlsanity.com/paper/1401.3794/) (2014)
- [Evolutionary computation for multicomponent problems: opportunities and future directions](https://mlsanity.com/paper/1606.06818/) (2016)
- [Exact Approaches for the Travelling Thief Problem](https://mlsanity.com/paper/1708.00331/) (2017)
- [Surrogate Assisted Optimisation for Travelling Thief Problems](https://mlsanity.com/paper/2005.06695/) (2020)
- [On the Use of Quality Diversity Algorithms for The Traveling Thief Problem](https://mlsanity.com/paper/2112.08627/) (2021)
- [The Packing While Traveling Problem](https://mlsanity.com/paper/1512.08831/) (2015)
- [Solving the Travelling Thief Problem based on Item Selection Weight and Reverse Order Allocation](https://mlsanity.com/paper/2012.08888/) (2020)
- [The Dynamic Travelling Thief Problem: Benchmarks and Performance of Evolutionary Algorithms](https://mlsanity.com/paper/2004.12045/) (2020)

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

- [LLM-Driven Co-Evolutionary Automated Heuristic Design for Bi-Component Coupled Combinatorial Optimization](https://mlsanity.com/paper/2606.00718/) (2026)

## Abstract (arXiv)

A travelling thief problem (TTP) is a proxy to real-life problems such as postal collection. TTP comprises an entanglement of a travelling salesman problem (TSP) and a knapsack problem (KP) since items of KP are scattered over cities of TSP, and a thief has to visit cities to collect items. In TTP, city selection and item selection decisions need close coordination since the thief's travelling speed depends on the knapsack's weight and the order of visiting cities affects the order of item collection. Existing TTP solvers deal with city selection and item selection separately, keeping decisions for one type unchanged while dealing with the other type. This separation essentially means very poor coordination between two types of decision. In this paper, we first show that a simple local search based coordination approach does not work in TTP. Then, to address the aforementioned problems, we propose a human designed coordination heuristic that makes changes to collection plans during exploration of cyclic tours. We further propose another human designed coordination heuristic that explicitly exploits the cyclic tours in item selections during collection plan exploration. Lastly, we propose a machine learning based coordination heuristic that captures characteristics of the two human designed coordination heuristics. Our proposed coordination based approaches help our TTP solver significantly outperform existing state-of-the-art TTP solvers on a set of benchmark problems. Our solver is named Cooperation Coordination (CoCo) and its source code is available from https://github.com/majid75/CoCo