A Genetic Algorithm for the Thief Orienteering Problem

This paper approaches the Thief orienteering Problem, a multi-component problem that combines two combinatorial problems: orienteering Problem (OP) and Knapsack Problem (KP). In this problem, a person (called thief) has a capacitated knapsack and has a time limit to collect objects distributed in a set of points. The departure and arrival points are fixed. The thief begins his journey with an empty knapsack and travels with speed inversely proportional to the weight of the knapsack. As long as he has time, the thief can go through the points collecting the objects. The objective of the problem is to define which route and which objects the thief must collect to maximize the profit of the knapsack. We developed a heuristic algorithm based on the genetic algorithm (GA) metaheuristic and computational experiments were carried out in order to compare the performance of the developed algorithm with the existing algorithms in the literature. Our results showed that our GA was superior in the majority of the cases.