A comprehensive benchmark set and heuristics for the traveling thief problem

Sergey Polyakovskiy, Mohammad Reza Bonyadi, Markus Wagner, Zbigniew Michalewicz, Frank Neumann

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

92 Citations (Scopus)

Abstract

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 bench-mark 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.

Original languageEnglish
Title of host publicationGECCO 2014 - Proceedings of the 2014 Genetic and Evolutionary Computation Conference
PublisherAssociation for Computing Machinery (ACM)
Pages477-484
Number of pages8
ISBN (Print)9781450326629
DOIs
Publication statusPublished - 2014
Externally publishedYes
EventThe Genetic and Evolutionary Computation Conference 2014 - Vancouver, Canada
Duration: 12 Jul 201416 Jul 2014
Conference number: 16th
https://dl.acm.org/doi/proceedings/10.1145/2576768 (Proceedings)

Conference

ConferenceThe Genetic and Evolutionary Computation Conference 2014
Abbreviated titleGECCO 2014
Country/TerritoryCanada
CityVancouver
Period12/07/1416/07/14
Internet address

Keywords

  • Benchmarks
  • Interdependence
  • Knapsack problem
  • Traveling thief problem

Cite this