Traveling Thief Problem
People are facing real-world problems with dependencies and interwovenness every day. In order to provide studies on an interwoven problem to fill that gap between theory and practice, the Traveling Thief Problem, where the Traveling Salesman Problem and Knapsack Problem interact, was proposed. Research done on this problem will bring insights how to handle problems with interwovenness and therefore how to solve problems with real-world character.
The thief has to effects when these two problems are combined:
- When an item is picked the velocity decreases and the thief slows down.
- There is a depreciation which increases the value of items over time.
Both effects are affecting both components and therefore it is a complete interwoven system. There are different versions of the problem which were propsed. Single-objective by weights, multi-objective with depreciation and single-objective by a minimal profit contstraint.
We created a benchmark in order to investigate the Traveling Thief Problem systematically. Here