A comprehensive benchmark set and heuristics for the traveling thief problem

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

doi:10.1145/2576768.2598249

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 proceeding › Conference Paper › Research › peer-review

83 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 language	English
Title of host publication	GECCO 2014 - Proceedings of the 2014 Genetic and Evolutionary Computation Conference
Publisher	Association for Computing Machinery (ACM)
Pages	477-484
Number of pages	8
ISBN (Print)	9781450326629
DOIs	https://doi.org/10.1145/2576768.2598249
Publication status	Published - 2014
Externally published	Yes
Event	The Genetic and Evolutionary Computation Conference 2014 - Vancouver, Canada Duration: 12 Jul 2014 → 16 Jul 2014 Conference number: 16th https://dl.acm.org/doi/proceedings/10.1145/2576768 (Proceedings)

Conference

Conference	The Genetic and Evolutionary Computation Conference 2014
Abbreviated title	GECCO 2014
Country/Territory	Canada
City	Vancouver
Period	12/07/14 → 16/07/14
Internet address	https://dl.acm.org/doi/proceedings/10.1145/2576768 (Proceedings)

Keywords

Benchmarks
Interdependence
Knapsack problem
Traveling thief problem

Access to Document

10.1145/2576768.2598249

Cite this

@inproceedings{1edb7517744f4f2a9bea36e7c9576342,

title = "A comprehensive benchmark set and heuristics for the traveling thief problem",

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.",

keywords = "Benchmarks, Interdependence, Knapsack problem, Traveling thief problem",

author = "Sergey Polyakovskiy and Bonyadi, {Mohammad Reza} and Markus Wagner and Zbigniew Michalewicz and Frank Neumann",

year = "2014",

doi = "10.1145/2576768.2598249",

language = "English",

isbn = "9781450326629",

pages = "477--484",

booktitle = "GECCO 2014 - Proceedings of the 2014 Genetic and Evolutionary Computation Conference",

publisher = "Association for Computing Machinery (ACM)",

address = "United States of America",

note = "The Genetic and Evolutionary Computation Conference 2014, GECCO 2014 ; Conference date: 12-07-2014 Through 16-07-2014",

url = "https://dl.acm.org/doi/proceedings/10.1145/2576768",

}

Polyakovskiy, S, Bonyadi, MR, Wagner, M, Michalewicz, Z & Neumann, F 2014, A comprehensive benchmark set and heuristics for the traveling thief problem. in GECCO 2014 - Proceedings of the 2014 Genetic and Evolutionary Computation Conference. Association for Computing Machinery (ACM), pp. 477-484, The Genetic and Evolutionary Computation Conference 2014, Vancouver, British Columbia, Canada, 12/07/14. https://doi.org/10.1145/2576768.2598249

A comprehensive benchmark set and heuristics for the traveling thief problem. / Polyakovskiy, Sergey; Bonyadi, Mohammad Reza; Wagner, Markus et al.

GECCO 2014 - Proceedings of the 2014 Genetic and Evolutionary Computation Conference. Association for Computing Machinery (ACM), 2014. p. 477-484.

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

TY - GEN

T1 - A comprehensive benchmark set and heuristics for the traveling thief problem

AU - Polyakovskiy, Sergey

AU - Bonyadi, Mohammad Reza

AU - Wagner, Markus

AU - Michalewicz, Zbigniew

AU - Neumann, Frank

N1 - Conference code: 16th

PY - 2014

Y1 - 2014

N2 - 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.

AB - 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.

KW - Benchmarks

KW - Interdependence

KW - Knapsack problem

KW - Traveling thief problem

UR - http://www.scopus.com/inward/record.url?scp=84905686852&partnerID=8YFLogxK

U2 - 10.1145/2576768.2598249

DO - 10.1145/2576768.2598249

M3 - Conference Paper

AN - SCOPUS:84905686852

SN - 9781450326629

SP - 477

EP - 484

BT - GECCO 2014 - Proceedings of the 2014 Genetic and Evolutionary Computation Conference

PB - Association for Computing Machinery (ACM)

T2 - The Genetic and Evolutionary Computation Conference 2014

Y2 - 12 July 2014 through 16 July 2014

ER -

A comprehensive benchmark set and heuristics for the traveling thief problem

Abstract

Conference

Keywords

Access to Document

Other files and links

Cite this