# The Traveling Thief Problem with Time Windows: Benchmarks and Heuristics

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 37 references that are in the map.
- First posted on arXiv 8 Apr 2026.

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

- [Combining Reinforcement Learning with Lin-Kernighan-Helsgaun Algorithm for the Traveling Salesman Problem](https://mlsanity.com/paper/2012.04461/) (2020)
- [Learning to Handle Complex Constraints for Vehicle Routing Problems](https://mlsanity.com/paper/2410.21066/) (2024)
- [Reinforced Lin-Kernighan-Helsgaun Algorithms for the Traveling Salesman Problems](https://mlsanity.com/paper/2207.03876/) (2022)
- [A case study of algorithm selection for the traveling thief problem](https://mlsanity.com/paper/1609.00462/) (2016)
- [Evolutionary Diversity Optimisation for The Traveling Thief Problem](https://mlsanity.com/paper/2204.02709/) (2022)
- [On the Use of Quality Diversity Algorithms for The Traveling Thief Problem](https://mlsanity.com/paper/2112.08627/) (2021)
- [Solving the Travelling Thief Problem based on Item Selection Weight and Reverse Order Allocation](https://mlsanity.com/paper/2012.08888/) (2020)
- [A weighted-sum method for solving the bi-objective traveling thief problem](https://mlsanity.com/paper/2011.05081/) (2020)
- [Weighted-Scenario Optimisation for the Chance Constrained Travelling Thief Problem](https://mlsanity.com/paper/2505.00269/) (2025)
- [Recent Advances in Disaster Emergency Response Planning: Integrating Optimization, Machine Learning, and Simulation](https://mlsanity.com/paper/2505.03979/) (2025)

## Abstract (arXiv)

While traditional optimization problems were often studied in isolation, many real-world problems today require interdependence among multiple optimization components. The traveling thief problem (TTP) is a multi-component problem that has been widely studied in the literature. In this paper, we introduce and investigate the TTP with time window constraints which provides a TTP variant highly relevant to real-world situations where good can only be collected at given time intervals. We examine adaptions of existing approaches for TTP and the Traveling Salesperson Problem (TSP) with time windows to this new problem and evaluate their performance. Furthermore, we provide a new heuristic approach for the TTP with time windows. To evaluate algorithms for TTP with time windows, we introduce new TTP benchmark instances with time windows based on TTP instances existing in the literature. Our experimental investigations evaluate the different approaches and show that the newly designed algorithm outperforms the other approaches on a wide range of benchmark instances.