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

We tackle the Thief Orienteering Problem (ThOP), which is academic multi-component problem: it combines two classical combinatorial problems, namely the Knapsack Problem (KP) and the Orienteering Problem (OP). In this problem, 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 while also paying for the rented knapsack. 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 of the 432 benchmarking instances, with significant improvements.