A comprehensive benchmark set and heuristics for the traveling thief problem

By Sergey Polyakovskiy, Mohammad Reza Bonyadi, Markus Wagner, Z. Michalewicz, F. Neumann. 2014

130 citations recorded by the source corpus.

Real-world optimization problems often consist of several NP-hard optimization problems that interact with each other. The goal of this paper is to provide a benchmark suite that promotes a research of the interaction between problems and their mutual influence. We establish a comprehensive benchmark suite for the traveling thief problem (TTP) which combines the traveling salesman problem and the knapsack problem. Our benchmark suite builds on common benchmarks for the two sub-problems which grant a basis to examine the potential hardness imposed by combining the two classical problems. Furthermore, we present some simple heuristics for TTP and their results on our benchmark suite.

Subfields: Artificial Intelligence, Industrial and Manufacturing Engineering

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Haroldo Gambini Santos
2. Greet Vanden Berghe
3. Matheus Guedes Vilas Boas
4. L. Merschmann

In Industrial and Manufacturing Engineering

1. Haroldo Gambini Santos
2. Greet Vanden Berghe
3. Matheus Guedes Vilas Boas
4. L. Merschmann

Citations in the corpus

• Optimal Decision Trees for the Algorithm Selection Problem: Integer Programming Based Approaches (2019, methodology): “ in the seminal paper of Rice (1976). To the best of our knowledge however, the use of decision trees for algorithm selection was mostly ignored in the literature. One recent exception is the work of Polyakovskiy et al. (2014) who evaluated many heuristics for the traveling thief problem and built a”