# Efficiently solving the thief orienteering problem with a max-min ant colony optimization approach

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 32 references that are in the map.
- First posted on arXiv 21 Sep 2021.

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

- [A case study of algorithm selection for the traveling thief problem](https://mlsanity.com/paper/1609.00462/) (2016)
- [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)
- [Packing While Traveling: Mixed Integer Programming for a Class of Nonlinear Knapsack Problems](https://mlsanity.com/paper/1411.5768/) (2014)
- [A Fully Polynomial Time Approximation Scheme for Packing While Traveling](https://mlsanity.com/paper/1702.05217/) (2017)
- [Ants can orienteer a thief in their robbery](https://mlsanity.com/paper/2004.07017/) (2020)

## Abstract (arXiv)

We tackle the Thief Orienteering Problem (ThOP), an academic multi-component problem that combines two classical combinatorial problems, namely the Knapsack Problem and the Orienteering Problem. In the ThOP, a thief has a time limit to steal items that distributed in a given set of cities. While traveling, the thief collects items by storing them in their knapsack, which in turn reduces the travel speed. The thief has as the objective to maximize the total profit of the stolen items. In this article, we present an approach that combines swarm-intelligence with a randomized packing heuristic. Our solution approach outperforms existing works on almost all the 432 benchmarking instances, with significant improvements.